article

Free access

Efficient compilation of lazy evaluation

Author:

Thomas JohnssonAuthors Info & Claims

ACM SIGPLAN Notices, Volume 19, Issue 6

Pages 58 - 69

https://doi.org/10.1145/502949.502880

Published: 01 June 1984 Publication History

Abstract

This paper describes the principles underlying an efficient implementation of a lazy functional language, compiling to code for ordinary computers. It is based on combinator-like graph reduction: the user defined functions are used as rewrite rules in the graph. Each function is compiled into an instruction sequence for an abstract graph reduction machine, called the G-machine, the code reduces a function application graph to its value. The G-machine instructions are then translated into target code. Speed improvements by almost two orders of magnitude over previous lazy evaluators have been measured; we provide some performance figures.

References

[1]

L. Augustsson, "FC manual", Memo 13, Programming Methodology Group, Chalmers University of Technology, Goteborg (1982).

[2]

J. Backus, "Can Programming be Liberated from the yon Neumann Style? A funtional style and its algebra of programs", Comm. ACM, Vol. 21 no. 8 pp. 613-641 (August 1978).

Digital Library

[3]

L. Cardelli, "ML under UNIX", Polymorphism: The NL/LCF/Hope Newsletter, Vol. I no. 3 (January 1984).

[4]

R. Fenichel and J. Yochelson, "A LISP garbage-collector for virtual memory computer systems", Comm. of the ACM, Vol. 12 no. 11 pp. 611-612 (November 1969).

Digital Library

[5]

D. P. Friedman and D. S. Wise, "Cons should not evaluate its arguments", pp. 257-284 in Automata, la---ages a, Programming, Edinburgh Univ. Press

[6]

M. Gordon, R. Milner, and C. Wadsworth, "Edinburgh LCF", Lecture Notes in Computer Science, Vol. 78, Springer Verlag (1979).

[7]

P. Hudak and D. Kranz, "A Combinatorbased Compiler for a Functional Language", pp. 122-132 in Prec. 11th ACM Syrup. on Principles of Programming languages (1984).

Digital Library

[8]

J. Hughes, "Super Combinators: A New Implementation Method for Applicative Languages", pp. I-I0 in Proceedings of the 1982 ACIq Symposium on Lisp and Functional Programming, Pittsburgh (1982).

Digital Library

[9]

T. Johnsson, "Code Generation for Lazy Evaluation", Memo 22, Programming Methodology Group, Chalmers University of Technology, Goteborg (1981).

[10]

N.D. Jones and S.S. Muchnick, "A Fixed-Program Machine for Combinator Expression Evaluation", pp. 11-20 in Proceedings o f the 1982 ACMSymposium on Lisp and Functional Programming, Pittsburgh (1982).

Digital Library

[11]

P. J. Landin, "The Mechanical Evaluation of Expressions", Computer Journal, No. 6 pp. 308-320 (January 1964).

[12]

P. J. Landin, "The Next 700 Programming Languages", Comm. of the ACM, Vol. 9 no. 3 pp. 157-164 (March 1966).

Digital Library

[13]

R. Milner, "A Theory of Type Polymorphism in Programming", Journal of Computer and System Sciences, Vol. 17 no. 3 pp. 348-375 (1978).

[14]

R. Milner, "Standard ML Proposal", Polymorphism: The /LCF/Hope Newsletter, Vol. I no. 3 (January 1984).

[15]

A. Mycroft, "The Theory and Practice of Transforming Call-by-Need into Callby-Value", pp. 269-281 in Proc. 4th Int. Symp. on Programming, Lecture Notes i n Computer Science, Vol. 83, Springer Verlag, Paris (April 1980).

Digital Library

[16]

D.A. Turner, "An implementation of SASL", TR/75/4, St. Andrews (1975).

[17]

D. A. Turner, "New Implementation Techniques for Applicative Languages", Software Practice and Experience, Vol. 9 PP. 31-49 (1979).

Cited By

Mizuno MSumii E(2019)Formal Verifications of Call-by-Need and Call-by-Name Evaluations with Mutual RecursionProgramming Languages and Systems10.1007/978-3-030-34175-6_10(181-201)Online publication date: 18-Nov-2019
https://doi.org/10.1007/978-3-030-34175-6_10
Stelle GStefanovic DOlivier SForrest S(2019)Cactus Environment MachineMicrobial Metabolic Engineering10.1007/978-3-030-14805-8_2(24-43)Online publication date: 21-Feb-2019
https://doi.org/10.1007/978-3-030-14805-8_2
Stelle GStefanovic D(2018)Verifiably LazyProceedings of the 30th Symposium on Implementation and Application of Functional Languages10.1145/3310232.3310236(49-58)Online publication date: 5-Sep-2018
https://dl.acm.org/doi/10.1145/3310232.3310236
Show More Cited By

Efficient compilation of lazy evaluation
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

Efficient compilation of lazy evaluation
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

This paper describes the principles underlying an efficient implementation of a lazy functional language, compiling to code for ordinary computers. It is based on combinator-like graph reduction: the user defined functions are used as rewrite rules in ...
Efficient compilation of lazy evaluation
SIGPLAN '84: Proceedings of the 1984 SIGPLAN symposium on Compiler construction

This paper describes the principles underlying an efficient implementation of a lazy functional language, compiling to code for ordinary computers. It is based on combinator-like graph reduction: the user defined functions are used as rewrite rules in ...
Hybrid eager and lazy evaluation for efficient compilation of haskell

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 19, Issue 6

Proceedings of the SIGPLAN '84 symposium on compiler construction

June 1984

318 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/502949

Issue’s Table of Contents

SIGPLAN '84: Proceedings of the 1984 SIGPLAN symposium on Compiler construction
June 1984
328 pages
ISBN:0897911393
DOI:10.1145/502874
General Chair:
Mary Van Deusen
IBM
,
Program Chair:
Susan L. Graham
University of California, Berkeley

Copyright © 1984 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1984

Published in SIGPLAN Volume 19, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

141
Total Citations
View Citations
1,013
Total Downloads

Downloads (Last 12 months)212
Downloads (Last 6 weeks)31

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mizuno MSumii E(2019)Formal Verifications of Call-by-Need and Call-by-Name Evaluations with Mutual RecursionProgramming Languages and Systems10.1007/978-3-030-34175-6_10(181-201)Online publication date: 18-Nov-2019
https://doi.org/10.1007/978-3-030-34175-6_10
Stelle GStefanovic DOlivier SForrest S(2019)Cactus Environment MachineMicrobial Metabolic Engineering10.1007/978-3-030-14805-8_2(24-43)Online publication date: 21-Feb-2019
https://doi.org/10.1007/978-3-030-14805-8_2
Stelle GStefanovic D(2018)Verifiably LazyProceedings of the 30th Symposium on Implementation and Application of Functional Languages10.1145/3310232.3310236(49-58)Online publication date: 5-Sep-2018
https://dl.acm.org/doi/10.1145/3310232.3310236
Joudrier HThiard F(2017)A greedy approach for a rolling stock management problem using multi-interval constraint propagationAnnals of Operations Research10.1007/s10479-017-2543-y271:2(1165-1183)Online publication date: 7-Jun-2017
https://doi.org/10.1007/s10479-017-2543-y
Barendregt H(2014)The Impact of the Lambda Calculus in Logic and Computer ScienceBulletin of Symbolic Logic10.2307/4210133:02(181-215)Online publication date: 15-Jan-2014
https://doi.org/10.2307/421013
Zerny I(2013)On graph rewriting, reduction, and evaluation in the presence of cyclesHigher-Order and Symbolic Computation10.1007/s10990-014-9103-926:1-4(63-84)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1007/s10990-014-9103-9
Sestoft PSestoft P(2012)A First-Order Functional LanguageProgramming Language Concepts10.1007/978-1-4471-4156-3_4(57-76)Online publication date: 2012
https://doi.org/10.1007/978-1-4471-4156-3_4
Wilhelm RSeidl HWilhelm RSeidl H(2010)Functional Programming LanguagesCompiler Design10.1007/978-3-642-14909-2_3(57-104)Online publication date: 2-Nov-2010
https://doi.org/10.1007/978-3-642-14909-2_3
Nilsson HFritzson P(2008)Algorithmic debugging for lazy functional languagesJournal of Functional Programming10.1017/S095679680000109X4:03(337-369)Online publication date: 7-Nov-2008
https://doi.org/10.1017/S095679680000109X
Runciman CToyn IFirth M(2008)An incremental, exploratory and transformational environment for lazy functional programmingJournal of Functional Programming10.1017/S09567968000006293:01(93-115)Online publication date: 7-Nov-2008
https://doi.org/10.1017/S0956796800000629
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents