article

Free access

Space-efficient closure representations

Authors:

Andrew W. AppelAuthors Info & Claims

ACM SIGPLAN Lisp Pointers, Volume VII, Issue 3

Pages 150 - 161

https://doi.org/10.1145/182590.156783

Published: 01 July 1994 Publication History

Abstract

Many modern compilers implement function calls (or returns) in two steps: first, a closure environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a “jump with arguments (or results)”. Closure conversion, which decides where and how to represent closures at runtime, is a crucial step in compilation of functional languages. We have a new algorithm that exploits the use of compile-time control and data flow information to optimize closure representations. By extensive closure sharing and allocating as many closures in registers as possible, our new closure conversion algorithm reduces heap allocation by 36% and memory fetches for local/global variables by 43%; and improves the already-efficient code generated by the Standard ML of New Jersey compiler by about 17% on a DECstation 5000. Moreover, unlike most other approaches, our new closure allocation scheme satisfies the strong “safe for space complexity” rule, thus achieving good asymptotic space usage.

References

[1]

Andrew W. A ppel. Garbage collection can be faster than stack allocation. In}ormation Processing Letter, 25(4):275- 79, 1987.

Digital Library

[2]

Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992.

Digital Library

[3]

Andrew W. Appel and Trevor Jim. Optimizing closure environment representations. Technical Report 168, Dept. of Computer Science, Princeton University, Princeton, N J, 1988.

[4]

Andrew W. Appel and Trevor Jim. Continuation-passing, closure-passing style. In Sixteenth A CM Syrup. on Principles of Programming Languages, pages 293-302, New York, 1989. ACM Press.

[5]

Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In Martin Wirsing, editor, Third Int'I Syrup. on Prog. Lang. Implementation and Logic Programming, pages 1-13, New York, August 1991. Springer-Verlag.

[6]

Andrew W. Appel and Zhong Shao. Callee-save registers in continuation-passing style. Lisp and Symbolic Computation, 5(3):191-221, 19~2.

Digital Library

[7]

Andrew W. Appel and Zhong Shao. An empirical and analytic study of stack vs. heap cost for languages with closures. Technical Report CS-TR-450-94, Princeton University, Department of Computer Science, Princeton, N J, March 1994.

[8]

Lennart Augustsson. Garbage collection in the < v,g >- machine. Technical Report PMG memo 73, Dept. of Computer Sciences, Chalmers University of Technology, Goteborg, Sweden, December 1989.

[9]

Henry G. Baker. The buried binding and stale binding problems of LISP 1.5. unpublished, undistributed paper, June 1976.

[10]

Luca Cardelli. Compiling a functional language. In Proc. of the 198~ ACM Conference on Lisp and Functional Programming, pages 208-217, August 1984.

Digital Library

[11]

David R. Chase. Safety considerations for storage allocation optimizations. In Proc. A CM SIGPLAN '88 Con}. on Prog. Lang. Design and Implementation, pages 1-9, New York, June 1988. ACM Press.

Digital Library

[12]

Fred C. Chow. Minimizing register usage penalty at procedure calls. In Proc. A CM SIGPLAN '88 Conf. on Prog. Lang. Design and Implementation, pages 85-94, New York, June 1988. ACM Press.

Digital Library

[13]

William D Clinger, Anne H Hartheimer, and Eric MOst. Implementation strategies for continuations. In 1988 A CM Conference on Lisp and Fucntional Programming, pages 124-131, New York, June 1988. ACM Press.

Digital Library

[14]

G. Cousineau, P. L. Curien, and M. Mauny. The categorical abstract macl~ne. In J. P. Jouannaud, editor, Functional Programming Languages and Computer Architecture, LNCS Vol 201, pages 50-64, New York, 1985. Springer-Verlag.

Digital Library

[15]

Olivier Danvy. Memory allocation and higher-order functions. In Proceedings of the SIGPLAN'87 Symposium on Interpreters and Interpretive Techniques, pages 241-252. ACM Press, June 1987.

Digital Library

[16]

Amer Diwan, David Tarditi, and Eliot Moss. Memory subsystem performance of programs using copying garbage collection. In Proc. ~1st Annual A CM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, pages 1- 14. ACM Press, 1994.

Digital Library

[17]

Lal George, Florent Guillaume, and John Reppy. A portable and optimizing backend for the SML/NJ compiler. In Proceedings of the 199~ International Conference on Compiler Construction, page (to appear), April 1994.

Digital Library

[18]

Carsten K. Gomard and Peter Sestoft. Globalization and live variables. In Proceedings of the 1991 Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 166-177. ACM Press, June 1991.

Digital Library

[19]

Jr. Guy L. Steele and Gerald Jay Sussman. The dream of a lifetime: A lazy variable extent mechanism. In Proceeding s of the i980 LISP Conference, pages 163-172, Stanford, 1980.

Digital Library

[20]

Chris Hanson. Efficient stack allocation for taJl-recursive languages. In 1990 A CM Conference on Lisp and Fucntional Programming, pages 106-118, New York, June 1990. ACM Press.

Digital Library

[21]

Robert Hieb, R. Kent Dybvig, and Carl Bruggeman. Representing control in the presence of first-class continuations. In Proc. A CM SIGPLAN '90 Con}. on Prog. Lang. Design and Implementation, pages 66-77, New York, 1990. ACM Press.

Digital Library

[22]

Thomas Johnsson. Lambda Lifting: Transforming Programs to Recursive Equations. In The Second International Conference on Functional Programming Languages and Computer Architecture, pages 190-203, New York, September 1985. Springcr-Verlag.

Digital Library

[23]

Norman P. Jouppi. Cache write policies and performance. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 191-201. ACM Press, May 1993.

Digital Library

[24]

Richard Kelsey and Paul Hudak. Realistic compilation by program transformation. In Sixteenth A CM Syrup. on Principles of Programming Languages, pages 281-92, New York, 1989. ACM Press.

[25]

D. Kranz, R. Kelsey, J. Rees, P. Hudak, J. Philbin, and N. Adams. ORBIT: An optimizing compiler for Scheme. SIGPLAN Notices (Proc. Sigplan '86 Syrup. on Compiler Construction), 21(7):219-33, July 1986.

Digital Library

[26]

David Kranz. ORBIT: An optimizing compiler for Scheme. PhD thesis, Yale University, New Haven, CT, 1987.

Digital Library

[27]

P. J. Landin. The mechanical evaluation of expressions. Computer Journal, 6(4):308-20, 1964.

[28]

Xavier Leroy. Unboxed objects and polymorphic typing. In Nineteenth Annual A CM Syrup. on Principles of Prog. Languages, New York, Jan 1992. ACM Press.

Digital Library

[29]

Robin Milner, Mads Tofte, and Robert Harper. The Definition of Standard ML. MIT Press, Cambridge, Massachusetts, 1990.

Digital Library

[30]

Guillermo Juan Rozas. Liar, an algoblike compiler for scheme. S.B. thesis, MIT Dept. of Computer Science and Electrical Engineering, June 1984.

[31]

Barbara G. Ryder and Marvin C. Paull. Elimination algorithms for data flow analysis. A CM Computing Surveys, 18(3):277-316, September 1986.

Digital Library

[32]

Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie-Mellon University, Pittsburgh, PA, May 1991. CMU-CS-91-145.

Digital Library

[33]

Guy L. Steele. Rabbit: a compiler for Scheme. Technical Report Ai-TR-474, MIT, Cambridge, MA, 1978.

Digital Library

[34]

Robert E. Tarjan. Testing flow graph reducibility. Journal of Compuier and System Science, 9(3):355-365, December 1974.

Digital Library

[35]

Mads Torte and Jean-Pierre Talpin. Implementation of the typed call-by-value A-calculus using a stack of regions. In Proc. 21st Annual ACM SIGPLAN-SIGACT Syrup. on Principles of Programming Languages, pages 188-201. ACM Press, 1994.

Digital Library

[36]

David M. Ungar. The Design and Evaluation of a High Performance Smalltalk System. MIT Press, Cambridge, MA, 1986.

Digital Library

Cited By

Farvardin KReppy J(2020)A New Backend for Standard ML of New JerseyProceedings of the 32nd Symposium on Implementation and Application of Functional Languages10.1145/3462172.3462191(55-66)Online publication date: 2-Sep-2020
https://dl.acm.org/doi/10.1145/3462172.3462191
Farvardin KReppy JDonaldson ATorlak E(2020)From folklore to fact: comparing implementations of stacks and continuationsProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385994(75-90)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385994
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
Show More Cited By

Index Terms

Space-efficient closure representations
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Procedures, functions and subroutines
      2. Language types

Recommendations

Efficient and safe-for-space closure conversion

Modern compilers often implement function calls (or returns) in two steps: first, a “closure” environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a “...
Space-efficient closure representations
LFP '94: Proceedings of the 1994 ACM conference on LISP and functional programming

Many modern compilers implement function calls (or returns) in two steps: first, a closure environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a “jump ...
Closure

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Lisp Pointers

ACM SIGPLAN Lisp Pointers Volume VII, Issue 3

July-Sept. 1994

327 pages

ISSN:1045-3563

DOI:10.1145/182590

Editor:
Robert R. Kessler
Univ. of Utah, Salt Lake City

Issue’s Table of Contents

LFP '94: Proceedings of the 1994 ACM conference on LISP and functional programming
July 1994
327 pages
ISBN:0897916433
DOI:10.1145/182409
Chairman:
Robert R. Kessler
Univ. of Utah, Salt Lake City

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1994

Published in SIGPLAN-LISPPOINTERS Volume VII, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
792
Total Downloads

Downloads (Last 12 months)108
Downloads (Last 6 weeks)21

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Farvardin KReppy J(2020)A New Backend for Standard ML of New JerseyProceedings of the 32nd Symposium on Implementation and Application of Functional Languages10.1145/3462172.3462191(55-66)Online publication date: 2-Sep-2020
https://dl.acm.org/doi/10.1145/3462172.3462191
Farvardin KReppy JDonaldson ATorlak E(2020)From folklore to fact: comparing implementations of stacks and continuationsProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3385994(75-90)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3385994
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
Danvy OSchultz U(1997)Lambda-droppingACM SIGPLAN Notices10.1145/258994.25900732:12(90-106)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1145/258994.259007
Danvy OSchultz UGallagher JConsel C(1997)Lambda-droppingProceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation10.1145/258993.259007(90-106)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1145/258993.259007
Bowman W(2024)A Low-Level Look at A-Normal FormProceedings of the ACM on Programming Languages10.1145/36897178:OOPSLA2(165-191)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689717
Yu XTang WXiong TChen WHe JYang BQi Z(2023)Enhancing embedded systems development with TSAutomated Software Engineering10.1007/s10515-023-00404-x31:1Online publication date: 6-Dec-2023
https://dl.acm.org/doi/10.1007/s10515-023-00404-x
Paraskevopoulou ZLi JAppel A(2021)Compositional optimizations for CertiCoqProceedings of the ACM on Programming Languages10.1145/34735915:ICFP(1-30)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473591
Sullivan ZDownen PAriola ZLindley SMogensen T(2021)Strictly capturing non-strict closuresProceedings of the 2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation10.1145/3441296.3441398(74-89)Online publication date: 18-Jan-2021
https://dl.acm.org/doi/10.1145/3441296.3441398
Sanchez-Rola IBalzarotti DSantos I(2020)Cookies from the PastDigital Threats: Research and Practice10.1145/34194731:4(1-24)Online publication date: 22-Dec-2020
https://dl.acm.org/doi/10.1145/3419473
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