William D. Clinger
Abstract
Optimizing compilers for higher-order languages need not be terribly complex. The problems created by non-local, non-global variables can be eliminated by allocating all such variables in the heap. Lambda lifting makes this practical by eliminating all non-local variables except for those that would have to be allocated in the heap anyway. The eliminated non-local variables become local variables that can be allocated in registers. Since calls to known procedures are just gotos that pass arguments, lifted lambda expressions are just assembly language labels that have been augmented by a list of symbolic names for the registers that are live at that label.
- 1 Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992. Google Scholar
Digital Library
- 2 AT&T Bell Laboratories. Standard ML of New Jersey system modules (version 0.93). February 15, 1993.Google Scholar
- 3 Lennart Augustsson. A compiler for Lazy ML. Uonference Record of the 198~1 A CM Symposium on Lisp and Functional Programming, pages 218-227, August 1984. Google ScholarDigital Library
- 4 Clinger, W.D. The Scheme 311 compiler: an exercise in denotational semantics. Conference Record of the 198d A CM Symposium on Lisp and Functional Programming, August 1984, pages 356-364. Google ScholarDigital Library
- 5 Clinger, W.D., Hartheimer, A.H., and Ost, E.M. Implementation strategies for continuations. Proceedings of the 1988 A CM Conference on Lisp and Functional Programming, pages 124-131, July 1988. Google ScholarDigital Library
- 6 Clinger, W., and Rees, J. Macros that work. Proceedings of the 1991 ACM Conference on Principles of Programm~ng Languages, pages 155-162, January 1991. Google ScholarDigital Library
- 7 Clinger, W., and Rees, J. {editors}. Revised4 report on the algorithmic language Scheme. Lisp Pointers 4(3), July-September 1991, pages 1-55. Google ScholarDigital Library
- 8 R. Kent Dybvig. The Scheme Programming Language. Prentice-Hall, 1987. Google ScholarDigital Library
- 9 M~rc Feeley and James Miller. A parallel virtual machine for efficient Scheme compilation. Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, June 1990. Google ScholarDigital Library
- 10 Richard P. Gabriel. Performance and Evaluation of Lisp Systems. MIT Press, 1985. Google ScholarDigital Library
- 11 Lars Thomas Hansen. The Impact of Programming Style on the Performance of Scheme Programs. M.S. thesis, University of Oregon, 1992.Google Scholar
- 12 Chris Hanson. Efficient stack allocation for tailrecursive languages. Proceedings of the 1990 A CM Conference on Lisp and Functional Programming, June 1990. Google ScholarDigital Library
- 13 Robert Hieb, R. Kent Dybvig, and Carl Bruggeman. Representing control in the presence of first-class continuations. PLDI '90, SIGPLAN Notices, 25(6), pages 66-77, June 1990. Google ScholarDigital Library
- 14 John Hughes. Super combinators: a new implementation method for applicative languages. Proceedings of the 1992 Symposium on Lisp and Functional Programming, pages 122-132.Google Scholar
- 15 IEEE Standard 1178-1990. IEEE Standard for the Scheme Programming Language. IEEE, New York, 1991. Google ScholarDigital Library
- 16 David Kranz, Richard Kelsey, Jonathan Rees, Paul Hudak, James Philbin, and Norman Adams. Orbit: an optimizing compiler for Scheme. Proceedings of the SiG- PLAN '86 Symposium on Compiler Construction, SIG- PLAN Notices, 21(7), pages 219-233, July 1986. Google ScholarDigital Library
- 17 Lightship Software, Inc. MacScheme Version 4 software and manual. Lightship Software, 1992.Google Scholar
- 18 Robert A MacLachlan. The Python compiler for CMU Common Lisp. Proceedings of the 1992 A CM Conference on Lisp and Functional Programming, LISP Pointers, 5(1), pages 235-246, June 1992. Google ScholarDigital Library
- 19 Guillermo Juan Rozas. Taming the Y operator. Proceedings of the 1992 A CM Conference on Lisp and Functional Programming, LISP Pointers, 5(1), pages 226- 234, June 1992. Google ScholarDigital Library
- 20 Guy Lewis Steele Jr. and Gerald Jay Sussman. Lambda, the ultimate imperative. MIT Artificial Intelligence Memo 353, March 1976.Google Scholar
- 21 Guy Lewis Steele Jr. Lambda, the ultimate declarative. MiT Artificial Intelligence Memo 379, November 1976.Google Scholar
- 22 Guy Lewis Steele Jr. Debunking the "expensive procedure call" myth, or procedure call implementations considered harmful, or lambda, the ultimate GOTO. ACM Conference Proceedings, pages 153-162. ACM, 1977. Google ScholarDigital Library
- 23 Guy Lewis Steele Jr. Rabbit: a compiler for Scheme. MIT Artificial Intelligence Laboratory Technical Report 474, May 1978. Google ScholarDigital Library
- 24 Guy Lewis Steele Jr. Compiler optimization based on viewing LAMBDA as RENAME + GOTO. In AI: An MIT Perspective. Patrick Henry Winston and Richard Henry Brown, editors. MIT Press, 1980.Google Scholar
- 25 D.A. Turner. New implementation techniques for applicative languages. Software--Practice and Experience, 9, pages 31-49, 1979.Google Scholar
- 26 Mitchell Wand and Paul Steckler. Selective and lightweight closure conversion. Proceedings of the 1995 A CM Symposium on Principles of Programming Languages, pages 435-445, January 1994. Google ScholarDigital Library
Index Terms
- Lambda, the ultimate label or a simple optimizing compiler for Scheme
Recommendations
Lambda, the ultimate label or a simple optimizing compiler for Scheme
LFP '94: Proceedings of the 1994 ACM conference on LISP and functional programmingOptimizing compilers for higher-order languages need not be terribly complex. The problems created by non-local, non-global variables can be eliminated by allocating all such variables in the heap. Lambda lifting makes this practical by eliminating all ...
A Surprisingly Simple Lua Compiler
SBLP '21: Proceedings of the 25th Brazilian Symposium on Programming LanguagesDynamically-typed programming languages are often implemented using interpreters, which offer several advantages in terms of portability and flexibility of the implementation. However, as a language matures and its programs get bigger, programmers may ...
An optimizing compiler for lexically scoped LISP
SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler constructionWe are developing an optimizing compiler for a dialect of the LISP language. The current target architecture is the S-I, a multiprocessing supercomputer designed at Lawrence Livermore National Laboratory. While LISP is usually thought of as a language ...
Comments