Optimal derivations in weak lambda-calculi and in orthogonal term rewriting systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal derivations in weak lambda-calculi and in orthogonal term rewriting systems

Full text

Pdf (1.40 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Orlando, Florida, United States

Pages: 255 - 269

Year of Publication: 1991

ISBN:0-89791-419-8

Author

Luc Maranget

INRIA Rocquencourt

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 13, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/99583.99618 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Abadi, L. Cardelli, P.-L. Curien, J.-J. L~vy, "Explicit substitutions". POPL'90.
	2	L. Augustsson, "Compiling Lazy Functional Languages Part II". PhD thesis, Chalmers University of Technology, Sweden, 1987.
	3	Gérard Berry , Jean-Jacques Lévy, Minimal and Optimal Computations of Recursive Programs, Journal of the ACM (JACM), v.26 n.1, p.148-175, Jan. 1979 [doi>10.1145/322108.322122]
	4	G. Cousineau , P. L. Curien , M. Mauny, The categorical abstract machine, Proc. of a conference on Functional programming languages and computer architecture, p.50-64, January 1985, Nancy, France
	5	John Field, On laziness and optimality in lambda interpreters: tools for specification and analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, December 1989, San Francisco, California, United States [doi>10.1145/96709.96710]
	6	T. Hardin, J.-J. L@vy, "A confluent Calculus of Substitution". France-Japan Artificial Inteligence and Computer Science Symposium, Izu, 1989.
	7	J. Roger Hindley , Jonathan P. Seldin, Introduction to combinators and &lgr;-calculus, Cambridge University Press, New York, NY, 1986
	8	Brian T. Howard , John C. Mitchell, Operational and axiomatic semantics of PCF, Proceedings of the 1990 ACM conference on LISP and functional programming, p.298-306, June 27-29, 1990, Nice, France [doi>10.1145/91556.91677]
	9	G. Huet, J.-J. L~vy, "Call by Need Computations in Non-Ambiguous Linear Term Rewriting Systems". INRIA, technical report 359, 1979.
	10	T. Johnsson, "Compiling Lazy Functional Languages". P hD thesis, Chalmers University of Technology, Sweden, 1987.
	11	V. K. Kathail, "Optimal Interpreters for Lambdacalculus Based Functional Languages". Communication at the SEMAGRAPH workshop, Paris, April 1990.
	12	J.t~. Kennaway, "An Outline of Some Results of Staples on Optimal Reduction Orders in Replacements Systems". Internal Report CSA/19/1984.
	13	John Lamping, An algorithm for optimal lambda calculus reduction, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-30, December 1989, San Francisco, California, United States [doi>10.1145/96709.96711]
	14	X. Leroy, "The Zinc experiment" an economical implementation of the ML Language". INP~IA, technical report 117, 1989.
	15	J.-J. L~vy, "R@ductions correctes et optimales dans le ~-calcul". Th~se de Doctorat d'Etat, Universit~ Paris VII, 1978.
	16	Michael J. O'Donnell, Computing in Systems Described by Equations, Springer-Verlag New York, Inc., Secaucus, NJ, 1977
	17	Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
	18	G.D. Plotkin, "LCF Considered as a Programming Language". Theoretical Computer Science, 5:225- 255, 1977.
	19	J. Vuillemin, "Syntaxe, S~mantique et axiomatique d'un language de programmation simple". Th~se de doctorat d'~tat, Universit~ Paris VI, 1974.

CITED BY 17

	Martín Abadi , Butler Lampson , Jean-Jacques Lévy, Analysis and caching of dependencies, ACM SIGPLAN Notices, v.31 n.6, p.83-91, June 15, 1996
	Pierre-Louis Curien , Thérèse Hardin , Jean-Jacques Lévy, Confluence properties of weak and strong calculi of explicit substitutions, Journal of the ACM (JACM), v.43 n.2, p.362-397, March 1996
	Yves Bertot, Occurrences in debugger specifications, ACM SIGPLAN Notices, v.26 n.6, p.327-337, June 1991
	Nobuko Yoshida, Optimal reduction in weak-&lgr;-calculus with shared environments, Proceedings of the conference on Functional programming languages and computer architecture, p.243-252, June 09-11, 1993, Copenhagen, Denmark
	John Launchbury, A natural semantics for lazy evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.144-154, March 1993, Charleston, South Carolina, United States
	Sergio Antoy , Rachid Echahed , Michael Hanus, A needed narrowing strategy, Journal of the ACM (JACM), v.47 n.4, p.776-822, July 2000
	Zena M. Ariola , John Maraist , Martin Odersky , Matthias Felleisen , Philip Wadler, A call-by-need lambda calculus, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.233-246, January 23-25, 1995, San Francisco, California, United States
	Andrew Moran , David Sands, Improvement in a lazy context: an operational theory for call-by-need, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.43-56, January 20-22, 1999, San Antonio, Texas, United States
	Salvador Lucas, Context-sensitive rewriting strategies, Information and Computation, v.178 n.1, p.294-343, October 10, 2002
	Sergio Antoy , Rachid Echahed , Michael Hanus, A needed narrowing strategy, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.268-279, January 16-19, 1994, Portland, Oregon, United States
	Zurab Khasidashvili , John Glauert, Relating conflict-free stable transition and event models via redex families, Theoretical Computer Science, v.286 n.1, p.65-95, 6 September 2002
	Daniel J. Dougherty , Pierre Lescanne , Luigi Liquori, Addressed term rewriting systems: application to a typed object calculus, Mathematical Structures in Computer Science, v.16 n.4, p.667-709, August 2006
	Sandra Alves , Mário Florido , Ian Mackie , François-Régis Sinot, Minimality in a Linear Calculus with Iteration, Electronic Notes in Theoretical Computer Science (ENTCS), 204, p.163-179, April, 2008
	Zena M. Ariola , Matthias Felleisen, The call-by-need lambda calculus, Journal of Functional Programming, v.7 n.3, p.265-301, May 1997
	Thérèse Hardin , Luc Maranget , Bruno Pagano, Functional runtime systems within the lambda-sigma calculus, Journal of Functional Programming, v.8 n.2, p.131-176, March 1998
	John Maraist , Martin Odersky , Philip Wadler, The call-by-need lambda calculus, Journal of Functional Programming, v.8 n.3, p.275-317, May 1998
	Joachim Niehren, Uniform confluence in concurrent computation, Journal of Functional Programming, v.10 n.5, p.453-499, September 2000