Space-efficient closure representations

Zhong Shao, Andrew W. Appel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

54 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM Conference on LISP and Functional Programming
PublisherPubl by ACM
Pages150-161
Number of pages12
Edition3
ISBN (Print)0897916433, 9780897916431
DOIs
StatePublished - 1994
EventProceedings of the 1994 ACM Conference on LISP and Functional Programming - Orlando, FL, USA
Duration: Jun 27 1994Jun 29 1994

Publication series

NameProceedings of the ACM Conference on LISP and Functional Programming
Number3
Volume7

Other

OtherProceedings of the 1994 ACM Conference on LISP and Functional Programming
CityOrlando, FL, USA
Period6/27/946/29/94

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Space-efficient closure representations'. Together they form a unique fingerprint.

Cite this