Proper tail recursion and space efficiency

ABSTRACT

The IEEE/ANSI standard for Scheme requires implementations to be properly tail recursive. This ensures that portable code can rely upon the space efficiency of continuation-passing style and other idioms. On its face, proper tail recursion concerns the efficiency of procedure calls that occur within a tail context. When examined closely, proper tail recursion also depends upon the fact that garbage collection can be asymptotically more space-efficient than Algol-like stack allocation.Proper tail recursion is not the same as ad hoc tail call optimization in stack-based languages. Proper tail recursion often precludes stack allocation of variables, but yields a well-defined asymptotic space complexity that can be relied upon by portable programs.This paper offers a formal and implementation-independent definition of proper tail recursion for Scheme. It also shows how an entire family of reference implementations can be used to characterize related safe-for-space properties, and proves the asymptotic inequalities that hold between them.

REFERENCES

• AFL95: Alexander Aiken , Manuel Fähndrich , Raph Levien, Better static memory management: improving region-based analysis of higher-order languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.174-185, June 18-21, 1995, La Jolla, California, United States
• App92: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• AS96: Andrew W. Appel and Zhong Sham. An empirical and analytic study of stack vs. heap cost for languages with closures. Journal of Functional Programming, 6(1):47-74, 1996.
• Bak95: Henry G. Baker, CONS should not CONS its arguments, part II: Cheney on the M.T.A., ACM SIGPLAN Notices, v.30 n.9, p.17-20, Sept. 1995 [doi>10.1145/214448.214454]
• Boe93: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• CH94: William D. Clinger , Lars Thomas Hansen, Lambda, the ultimate label or a simple optimizing compiler for Scheme, Proceedings of the 1994 ACM conference on LISP and functional programming, p.128-139, June 27-29, 1994, Orlando, Florida, United States
• Cha88: D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States
• Cli84: 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]
• CLR90: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• FH95: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• Fis72: Michael J. Fischer, Lambda calculus schemata, Proceedings of ACM conference on Proving assertions about programs, p.104-109, January 06-07, 1972, Las Cruces, New Mexico, United States
• FSDF93: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States
• GW95: Joshua D. Guttman , John D. Ramsdell , Mitchell Wand, VLISP: a verified implementation of Scheme, Lisp and Symbolic Computation, v.8 n.1-2, p.5-32, March 1995 [doi>10.1007/BF01128406]
• Han90: 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]
• Hew77: Carl Hewitt. Viewing control structures as patterns of passing messages. Artificial Intelligence, 8:323-364, 1977.
• IEE91: CORPORATE IEEE, Inc. Staff, IEEE Std 1178-1990, IEEE Standard for the Scheme Programming Language, IEEE Standards Office, New York, NY, 1991
• KCR98: Richard Kelsey, William Clinger, and Jonathan Rees (eds.). Revised5 report on the algorithmic language Scheme. ftr://ftr. nj. nee. com/pub/kel sey/rSrs, ps, February 1998.
• KKsR+86: 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
• Knu73: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• Lig90: CORPORATE Lightship Software, MacScheme: manual and software, MIT Press, Cambridge, MA, 1990
• MFH95: Greg Morrisett , Matthias Felleisen , Robert Harper, Abstract models of memory management, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.66-77, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224182]
• MH97: G. Morrisett , R. Harper, Semantics of memory management for polymorphic languages, Higher order operational techniques in semantics, Cambridge University Press, New York, NY, 1999
• NN92: Hanne Riis Nielson , Flemming Nielson, Semantics with applications: a formal introduction, John Wiley & Sons, Inc., New York, NY, 1992
• Que96: Christian Queinnec , Kathleen Callaway, Lisp in small pieces, Cambridge University Press, New York, NY, 1996
• Ram94: John D. Ramsdell, Scheme: the new generation, ACM SIGPLAN Lisp Pointers, v.VII n.4, p.13-14, Oct. 1994 [doi>10.1145/382109.382668]
• Ram97: John D. RamsdeIl. The tail recursive SECD machine. To appear, 1998.
• Ser97: Manuel Serrano. Bigloo user's manual. Part of the Bigloo 1.9 distribution available via httr: / / cuiww~, uni ge. ch/~e rrano/b igloo, html, 1997.
• SF96: Manuel Serrano , Marc Feeley, Storage use analysis and its applications, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.50-61, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• Sis97: Jeffrey Mark Siskind. Stalin - a STAtic Language ImplementatioN. Software available via http://w~, neci .nj .nec. com/homepages/qobi/, 1997.
• SS75: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• SS76: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• SS78a: Guy L Steele , Gerald J Sussman, The Art of the Interpreter or, The Modularity Complex (Parts Zero, One, and Two), Massachusetts Institute of Technology, Cambridge, MA, 1978
• SS78b: Guy L. Steele, Jr. and Gerald Jay Sussman. The revised report on SCHEME. Artificial Intelligence Memo 452, Massachusetts Institute of Technology, Cambridge~ MA, January 1978.
• Ste76: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• Ste77: 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]
• Ste78: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• TT94: Mads Tofte , Jean-Pierre Talpin, Implementation of the typed call-by-value λ-calculus using a stack of regions, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.188-201, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177855]
• Wan80: Mitchell Wand, Continuation-Based Program Transformation Strategies, Journal of the ACM (JACM), v.27 n.1, p.164-180, Jan. 1980 [doi>10.1145/322169.322183]
• WF78: Mitchell Wand and Daniel P. Friedman. Compiling larnbda expressions using continuations and factorizations. Journal of Computer Languages, 3:241-263, 1978.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: SCHEME

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Algorithms, Languages, Standardization