Efficient compilation of lazy evaluation

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

• Augu82: L. Augustsson, "FC manual", Memo 13, Programming Methodology Group, Chalmers University of Technology, Goteborg (1982).
• Back78: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• Card84: L. Cardelli, "ML under UNIX", Polymorphism: The NL/LCF/Hope Newsletter, Vol. I no. 3 (January 1984).
• Feni69: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• Frie76: 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
• Gord79: M. Gordon, R. Milner, and C. Wadsworth, "Edinburgh LCF", Lecture Notes in Computer Science, Vol. 78, Springer Verlag (1979).
• Huda84: Paul Hudak , David Kranz, A combinator-based compiler for a functional language, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.122-132, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800523]
• Hugh82: R. J. M. Hughes, Super-combinators a new implementation method for applicative languages, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.1-10, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802129]
• John81: T. Johnsson, "Code Generation for Lazy Evaluation", Memo 22, Programming Methodology Group, Chalmers University of Technology, Goteborg (1981).
• Jone82: Neil D. Jones , Steven S. Muchnick, A fixed-program machine for combinator expression evaluation, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.11-20, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802130]
• Land64: P. J. Landin, "The Mechanical Evaluation of Expressions", Computer Journal, No. 6 pp. 308-320 (January 1964).
• Land66: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• Miln78: R. Milner, "A Theory of Type Polymorphism in Programming", Journal of Computer and System Sciences, Vol. 17 no. 3 pp. 348-375 (1978).
• Miln84: R. Milner, "Standard ML Proposal", Polymorphism: The /LCF/Hope Newsletter, Vol. I no. 3 (January 1984).
• Mycr8o: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• Turn75: D.A. Turner, "An implementation of SASL", TR/75/4, St. Andrews (1975).
• Turn79: D. A. Turner, "New Implementation Techniques for Applicative Languages", Software Practice and Experience, Vol. 9 PP. 31-49 (1979).