Article

Free access

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

Author:

Luc MarangetAuthors Info & Claims

POPL '91: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 255 - 269

https://doi.org/10.1145/99583.99618

Published: 03 January 1991 Publication History

PDF eReader

References

[1]

M. Abadi, L. Cardelli, P.-L. Curien, J.-J. L~vy, "Explicit substitutions". POPL'90.

Digital Library

Google Scholar

[2]

L. Augustsson, "Compiling Lazy Functional Languages Part II". PhD thesis, Chalmers University of Technology, Sweden, 1987.

Google Scholar

[3]

G. Berry, J.-J. L~vy, "Minimal and Optimal Computations of Recursive Programs". JACM Vol. 26, No 1, 1979.

Digital Library

Google Scholar

[4]

G. Cousineau, P.-L. Curien, M. Mauny, "The Categorical Abstract Machine". Functional Programming Languages an Computer Architecture, 1985, LCNS.

Digital Library

Google Scholar

[5]

J. Field, "On Laziness and Optimality in Lambda Interpreters : Tools for Specification and Analysis". POPL'90.

Digital Library

Google Scholar

[6]

T. Hardin, J.-J. L@vy, "A confluent Calculus of Substitution". France-Japan Artificial Inteligence and Computer Science Symposium, Izu, 1989.

Google Scholar

[7]

J.R. Hindley, J.P. Seldin, "Introduction to Combinators and A-calculus". London Mathematical Society, Students Texts 1~ Cambridge University Press, 1986.

Digital Library

Google Scholar

[8]

B.T. Howard, J.C. Mitchell, "Operational and Axiomatic Semantics of PCF". L&FP'90.

Digital Library

Google Scholar

[9]

G. Huet, J.-J. L~vy, "Call by Need Computations in Non-Ambiguous Linear Term Rewriting Systems". INRIA, technical report 359, 1979.

Google Scholar

[10]

T. Johnsson, "Compiling Lazy Functional Languages". P hD thesis, Chalmers University of Technology, Sweden, 1987.

Google Scholar

[11]

V. K. Kathail, "Optimal Interpreters for Lambdacalculus Based Functional Languages". Communication at the SEMAGRAPH workshop, Paris, April 1990.

Google Scholar

[12]

J.t~. Kennaway, "An Outline of Some Results of Staples on Optimal Reduction Orders in Replacements Systems". Internal Report CSA/19/1984.

Google Scholar

[13]

J. Lamping, "An Algorithm for Optimal Lambda Calculus Reduction". POPL'90.

Digital Library

Google Scholar

[14]

X. Leroy, "The Zinc experiment" an economical implementation of the ML Language". INP~IA, technical report 117, 1989.

Google Scholar

[15]

J.-J. L~vy, "R@ductions correctes et optimales dans le ~-calcul". Th~se de Doctorat d'Etat, Universit~ Paris VII, 1978.

Google Scholar

[16]

M. O'Donnell, "Computing in Systems Described by Equations". LNCS No 58, Eds G. Goos and J. Hartmanis, Springer, 1977.

Digital Library

Google Scholar

[17]

S. L. Peyton Jones, "The Implementation of Functional Programming Languages". Prentice-Hall, 1987.

Digital Library

Google Scholar

[18]

G.D. Plotkin, "LCF Considered as a Programming Language". Theoretical Computer Science, 5:225- 255, 1977.

Crossref

Google Scholar

[19]

J. Vuillemin, "Syntaxe, S~mantique et axiomatique d'un language de programmation simple". Th~se de doctorat d'~tat, Universit~ Paris VI, 1974.

Google Scholar

Cited By

View all

Accattoli BBarenbaum P(2023)A Diamond Machine for Strong EvaluationProgramming Languages and Systems10.1007/978-981-99-8311-7_4(69-90)Online publication date: 26-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-8311-7_4
Lucas S(2020)Context-sensitive RewritingACM Computing Surveys10.1145/339767753:4(1-36)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3397677
Accattoli BBonelli EKesner DLombardi C(2014)A nonstandard standardization theoremACM SIGPLAN Notices10.1145/2578855.253588649:1(659-670)Online publication date: 8-Jan-2014
https://dl.acm.org/doi/10.1145/2578855.2535886
Show More Cited By

Index Terms

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

Recommendations

Sequentiality in orthogonal term rewriting systems

For orthogonal term rewriting systems Q. Huet and J.-J. Levy have introduced the property of 'strong sequentiality'. A strongly sequential orthogonal term rewriting system admits an efficiently computable normalizing one-step reduction strategy. As ...
Confluent term rewriting systems
RTA'05: Proceedings of the 16th international conference on Term Rewriting and Applications

The confluence property is one of the most important properties of term rewriting systems, and various sufficient criteria for proving this property have been widely investigated. A necessary and sufficient criterion for confluence of terminating term ...
Term Collections in λ and ρ-calculi

The @r-calculus generalises term rewriting and the @l-calculus by defining abstractions on arbitrary patterns and by using a pattern-matching algorithm which is a parameter of the calculus. In particular, equational theories that do not have unique ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '91: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1991

366 pages

ISBN:0897914198

DOI:10.1145/99583

Chairman:
David Wise
Indiana Univ., Bloomington

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL91

Sponsor:

POPL91: 18th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages

January 21 - 23, 1991

Florida, Orlando, USA

Acceptance Rates

POPL '91 Paper Acceptance Rate 31 of 152 submissions, 20%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
333
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)13

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Accattoli BBarenbaum P(2023)A Diamond Machine for Strong EvaluationProgramming Languages and Systems10.1007/978-981-99-8311-7_4(69-90)Online publication date: 26-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-8311-7_4
Lucas S(2020)Context-sensitive RewritingACM Computing Surveys10.1145/339767753:4(1-36)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3397677
Accattoli BBonelli EKesner DLombardi C(2014)A nonstandard standardization theoremACM SIGPLAN Notices10.1145/2578855.253588649:1(659-670)Online publication date: 8-Jan-2014
https://dl.acm.org/doi/10.1145/2578855.2535886
Accattoli BBonelli EKesner DLombardi CJagannathan SSewell P(2014)A nonstandard standardization theoremProceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2535838.2535886(659-670)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2535838.2535886
Balabonski T(2013)Weak optimality, and the meaning of sharingACM SIGPLAN Notices10.1145/2544174.250060648:9(263-274)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2544174.2500606
Balabonski TMorrisett GUustalu T(2013)Weak optimality, and the meaning of sharingProceedings of the 18th ACM SIGPLAN international conference on Functional programming10.1145/2500365.2500606(263-274)Online publication date: 25-Sep-2013
https://dl.acm.org/doi/10.1145/2500365.2500606
Balabonski TField JHicks M(2012)A unified approach to fully lazy sharingProceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2103656.2103713(469-480)Online publication date: 25-Jan-2012
https://dl.acm.org/doi/10.1145/2103656.2103713
Balabonski T(2012)A unified approach to fully lazy sharingACM SIGPLAN Notices10.1145/2103621.210371347:1(469-480)Online publication date: 25-Jan-2012
https://dl.acm.org/doi/10.1145/2103621.2103713
Balabonski TKutsia TSchreiner WFernández M(2010)Optimality for dynamic patternsProceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming10.1145/1836089.1836119(231-242)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1836089.1836119
Asperti ALaneve C(2009)Interaction Systems I: The theory of optimal reductionsMathematical Structures in Computer Science10.1017/S09601295000005664:4(457-504)Online publication date: 4-Mar-2009
https://doi.org/10.1017/S0960129500000566
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Sequentiality in orthogonal term rewriting systems

Confluent term rewriting systems

Term Collections in λ and ρ-calculi