Lambda, the ultimate label or a simple optimizing compiler for Scheme

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.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: AT&T Bell Laboratories. Standard ML of New Jersey system modules (version 0.93). February 15, 1993.
• 3: Lennart Augustsson, A compiler for lazy ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.218-227, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802038]
• 4: William Clinger, The scheme 311 compiler an exercise in denotational semantics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.356-364, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802052]
• 5: Will Clinger , Anne Hartheimer , Eric Ost, Implementation strategies for continuations, Proceedings of the 1988 ACM conference on LISP and functional programming, p.124-131, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62692]
• 6: William Clinger , Jonathan Rees, Macros that work, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.155-162, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99607]
• 7: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 8: R. Kent Dybvig, The SCHEME programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 9: Marc Feeley , James S. Miller, A parallel virtual machine for efficient scheme compilation, Proceedings of the 1990 ACM conference on LISP and functional programming, p.119-130, June 27-29, 1990, Nice, France [doi>10.1145/91556.91606]
• 10: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 11: Lars Thomas Hansen. The Impact of Programming Style on the Performance of Scheme Programs. M.S. thesis, University of Oregon, 1992.
• 12: Chris Hanson, Efficient stack allocation for tail-recursive languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.106-118, June 27-29, 1990, Nice, France [doi>10.1145/91556.91603]
• 13: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, ACM SIGPLAN Notices, v.25 n.6, p.66-77, Jun. 1990
• 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.
• 15: CORPORATE IEEE, Inc. Staff, IEEE Std 1178-1990, IEEE Standard for the Scheme Programming Language, IEEE Standards Office, New York, NY, 1991
• 16: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• 17: Lightship Software, Inc. MacScheme Version 4 software and manual. Lightship Software, 1992.
• 18: Robert A. MacLachlan, The Python compiler for CMU Common Lisp, Proceedings of the 1992 ACM conference on LISP and functional programming, p.235-246, June 22-24, 1992, San Francisco, California, United States
• 19: Guillermo Juan Rozas, Taming the Y operator, ACM SIGPLAN Lisp Pointers, v.V n.1, p.226-234, Jan. 1992
• 20: Guy Lewis Steele Jr. and Gerald Jay Sussman. Lambda, the ultimate imperative. MIT Artificial Intelligence Memo 353, March 1976.
• 21: Guy Lewis Steele Jr. Lambda, the ultimate declarative. MiT Artificial Intelligence Memo 379, November 1976.
• 22: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 23: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 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.
• 25: D.A. Turner. New implementation techniques for applicative languages. Software--Practice and Experience, 9, pages 31-49, 1979.
• 26: Mitchell Wand , Paul Steckler, Selective and lightweight closure conversion, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.435-445, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178044]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: SCHEME
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Languages, Measurement, Performance