CONS should not CONS its arguments, part II
- 1 September 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 30 (9) , 17-20
- https://doi.org/10.1145/214448.214454
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.Keywords
This publication has 13 references indexed in Scilit:
- CONS should not CONS its arguments, or, a lazy alloc is a smart allocACM SIGPLAN Notices, 1992
- Standard ML of New JerseyPublished by Springer Nature ,1991
- A runtime systemHigher-Order and Symbolic Computation, 1990
- Simple generational garbage collection and fast allocationSoftware: Practice and Experience, 1989
- Implementation strategies for continuationsPublished by Association for Computing Machinery (ACM) ,1988
- Memory allocation and higher-order functionsACM SIGPLAN Notices, 1987
- Garbage collection can be faster than stack allocationInformation Processing Letters, 1987
- List processing in real time on a serial computerCommunications of the ACM, 1978
- Block structure (Extended Abstract): Retention or deletion?Published by Association for Computing Machinery (ACM) ,1971
- A nonrecursive list compacting algorithmCommunications of the ACM, 1970