CONS should not CONS its arguments, part II: Cheney on the M.T.A.

ABSTRACT

Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Our C version of the "Boyer" benchmark is available at ftp://ftp.netcom.com/pub/hb/hbaker/cboyer13.c.

REFERENCES

• 1: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• 2: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 3: Andrew W. Appel, A runtime system, Lisp and Symbolic Computation, v.3 n.4, p.343-380, Nov. 1990 [doi>10.1007/BF01807697]
• 4: Appel, A.W., and MacQueen, D.B. "Standard ML of New Jersey". In Wirsing, M., ed. Third Int'l Symp on Progr Lang Implementation and Logic Progr., Springer, August 1991.
• 5: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 6: Henry G. Baker, CONS should not CONS its arguments, or, a lazy alloc is a smart alloc, ACM SIGPLAN Notices, v.27 n.3, p.24-34, March 1992 [doi>10.1145/130854.130858]
• 7: Bartlett, J. "Scheme¿C: A portable Scheme-to-C compiler". Tech. Rept., DEC West. Res. Lab., 1989.
• 8: Daniel M. Berry, Block structure (Extended Abstract): Retention or deletion?, Proceedings of the third annual ACM symposium on Theory of computing, p.86-100, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805041]
• 9: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 10: 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]
• 11: O. Danvy, Memory allocation and higher-order functions, ACM SIGPLAN Notices, v.22 n.7, p.241-252, July 1987
• 12: John Fairbairn , Stuart Wray, TIM: A simple, lazy abstract machine to execute supercombinators, Proc. of a conference on Functional programming languages and computer architecture, p.34-45, October 1987, Portland, Oregon, United States
• 13: Michael J. Fischer, Lambda calculus schemata, ACM SIGPLAN Notices, v.7 n.1, p.104-109, January 1972
• 14: Friedman, D.P., and Wise, D.S. "CONS Should Not Evaluate Its Arguments". In Michaelson, S., and Milner, R., eds. Automata, Languages and Programming, Edinburgh U. Press, 1976, 257-284.
• 15: 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]
• 16: CORPORATE IEEE, Inc. Staff, IEEE Std 1178-1990, IEEE Standard for the Scheme Programming Language, IEEE Standards Office, New York, NY, 1991
• 17: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 18: Stallman, R.M. "Phantom Stacks: If you look too hard, they aren't there". AI Memo 556, MIT AI Lab., July 1980.
• 19: Stallman, R.M. Using and Porting GNU CC. Free Software Foundation, Inc. February, 1990.
• 20: Steiner, J., and Hawkes, B. "The M.T.A." On the album The Kingston Trio At Large, released June 8, 1959, reached number 15 on June 15, 1959. Copyright Atlantic Music 1956-57.
• 21: David Tarditi , Peter Lee , Anurag Acharya, No assembly required: compiling standard ML to C, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.161-177, June 1992 [doi>10.1145/151333.151343]

INDEX TERMS

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

          Nouns: C

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

General Terms:
Design, Languages