article

Free access

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

Author:

Henry G. BakerAuthors Info & Claims

ACM SIGPLAN Notices, Volume 30, Issue 9

Pages 17 - 20

https://doi.org/10.1145/214448.214454

Published: 01 September 1995 Publication History

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]

Appel, A.W. "Garbage collection can be faster than stack allocation". Info. Proc. Letts. 25, 4 (1987), 275-279.

Digital Library

[2]

Appel, A.W. "Simple Generational Garbage Collection and Fast Allocation". SW Prac. & Exper. 19, 2 (1989), 171+.

Digital Library

[3]

Appel, A.W. "A Runtime System". Lisp & Symbolic Comput. 3, 4 (Nov. 1990), 343-380.

Digital Library

[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]

Baker, H.G. "List Processing in Real Time on a Serial Computer". CACM 21, 4 (April 1978), 280-294.

Digital Library

[6]

Baker, H.G. "CONS Should Not CONS Its Arguments, or, a Lazy alloc is a Smart alloc". Sigplan Not. 27, 3 (Mar. 1992), 24-34.

Digital Library

[7]

Bartlett, J. "Scheme¿C: A portable Scheme-to-C compiler". Tech. Rept., DEC West. Res. Lab., 1989.

[8]

Berry, D.M. "Block Structure: Retention vs. Deletion". Proc. 3rd Sigact Symp. Th. of Comp. Shaker Hgts., 1971.

Digital Library

[9]

Cheney, C.J. "A nonrecursive list compacting algorithm". CACM 13, 11 (Nov. 1970), 677-678.

Digital Library

[10]

Clinger, W., Hartheimer, A., and Ost, E. "Implementation strategies for continuations". Proc. LFP, 1988, 124-131.

Digital Library

[11]

Danvy, O. "Memory Allocation and Higher-Order Functions". Proc. Sigplan '87 Symp. on Interp & Interp. Techs., ACM Sigplan Not. 22, 7 (July 1987), 241-252.

Digital Library

[12]

Fairbairn, J., and Wray, S.C. "TIM: a simple abstract machine to execute supercombinators". Proc. 1987 FPCA.

Digital Library

[13]

Fischer, M.J. "Lambda Calculus Schemata". ACM Conf. Proving Asserts. re Progs., Sigplan Not. 7, 1 (Jan. 1972).

Digital Library

[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]

Hanson, C. "Efficient stack allocation for tail-recursive languages". Proc. LFP, June 1990.

Digital Library

[16]

IEEE. IEEE Standard for the Scheme Programming Language. IEEE-1178-1990, IEEE, NY, Dec. 1990.

Digital Library

[17]

Peyton Jones, S.L. The Implementation of Functional Programming Languages. Prentice-Hall, New York, 1987.

Digital Library

[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]

Tarditi, D., & Lee, P. "No assembly required: Compiling standard ML to C". ACM LOPLAS 1, 2 (1992), 161-177.

Digital Library

Cited By

Yasugi MIkeuchi RHiraishi TKomiya T(2019)Evaluating Portable Mechanisms for Legitimate Execution Stack Access with a Scheme Interpreter in an Extended SC LanguageJournal of Information Processing10.2197/ipsjjip.27.17727(177-189)Online publication date: 2019
https://doi.org/10.2197/ipsjjip.27.177
Baxter SNigam RPolitz JKrishnamurthi SGuha A(2018)Putting in all the stops: execution control for JavaScriptACM SIGPLAN Notices10.1145/3296979.319237053:4(30-45)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192370
Willis JWu NErdweg SOliveira B(2018)Garnishing parsec with parsleyProceedings of the 9th ACM SIGPLAN International Symposium on Scala10.1145/3241653.3241656(24-34)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241653.3241656
Show More Cited By

Index Terms

CONS should not CONS its arguments, part II: Cheney on the M.T.A.
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types

Recommendations

CONS should not CONS its arguments, or, a lazy alloc is a smart alloc

Lazy allocation is a model for allocating objects on the execution stack of a high-level language which does not create dangling references. Our model provides safe transportation into the heap for objects that may survive the deallocation of the ...
MediaBench II video: Expediting the next generation of video systems research

The first step towards the design of video processors and systems is to achieve an understanding of the major applications, including not only the theory, but also the workload characteristics of the many image and video compression standards. ...
Multics Emacs (Prose and Cons): A commercial text-processing system in Lisp
LFP '80: Proceedings of the 1980 ACM conference on LISP and functional programming

This paper addresses the choice of Lisp as the implementation language, and its consequences, including some of the implementation issues. The detailed history of Multics Emacs, its system-level design considerations, and its impact on Multics and its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © 1995 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1995

Published in SIGPLAN Volume 30, Issue 9

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
1,020
Total Downloads

Downloads (Last 12 months)303
Downloads (Last 6 weeks)47

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yasugi MIkeuchi RHiraishi TKomiya T(2019)Evaluating Portable Mechanisms for Legitimate Execution Stack Access with a Scheme Interpreter in an Extended SC LanguageJournal of Information Processing10.2197/ipsjjip.27.17727(177-189)Online publication date: 2019
https://doi.org/10.2197/ipsjjip.27.177
Baxter SNigam RPolitz JKrishnamurthi SGuha A(2018)Putting in all the stops: execution control for JavaScriptACM SIGPLAN Notices10.1145/3296979.319237053:4(30-45)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192370
Willis JWu NErdweg SOliveira B(2018)Garnishing parsec with parsleyProceedings of the 9th ACM SIGPLAN International Symposium on Scala10.1145/3241653.3241656(24-34)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241653.3241656
Baxter SNigam RPolitz JKrishnamurthi SGuha AFoster JGrossman D(2018)Putting in all the stops: execution control for JavaScriptProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192370(30-45)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192370
Tolpin Dvan de Meent JYang HWood FSchrijvers T(2016)Design and Implementation of Probabilistic Programming Language AnglicanProceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages10.1145/3064899.3064910(1-12)Online publication date: 31-Aug-2016
https://dl.acm.org/doi/10.1145/3064899.3064910
Feeley M(2015)Compiling for multi-language task migrationACM SIGPLAN Notices10.1145/2936313.281671351:2(63-77)Online publication date: 21-Oct-2015
https://dl.acm.org/doi/10.1145/2936313.2816713
Feeley MSerrano M(2015)Compiling for multi-language task migrationProceedings of the 11th Symposium on Dynamic Languages10.1145/2816707.2816713(63-77)Online publication date: 21-Oct-2015
https://dl.acm.org/doi/10.1145/2816707.2816713
Tauber TBi XShi ZZhang WLi HZhang ZOliveira B(2015)Memory-Efficient Tail Calls in the JVM with Imperative Functional ObjectsProgramming Languages and Systems10.1007/978-3-319-26529-2_2(11-28)Online publication date: 9-Dec-2015
https://doi.org/10.1007/978-3-319-26529-2_2
Thivierge EFeeley MDanvy O(2012)Efficient compilation of tail calls and continuations to JavaScriptProceedings of the 2012 Annual Workshop on Scheme and Functional Programming10.1145/2661103.2661108(47-57)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1145/2661103.2661108
Willcock JNewton RLumsdaine AFilinski AGrelck C(2012)AvalancheProceedings of the 1st ACM SIGPLAN workshop on Functional high-performance computing10.1145/2364474.2364479(15-26)Online publication date: 15-Sep-2012
https://dl.acm.org/doi/10.1145/2364474.2364479
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents