Implementing Closures using Run-time Code Generation

Information

Martin Grabmüller: Implementing Closures using Run-time Code Generation, in Forschungsberichte Fakultät IV - Elektrotechnik und Informatik, number 2006-02, Technische Universität Berlin, February 2006.

Part of the work in this report was presented in a talk.

52+iv pages, format DIN A4, English.

Abstract

This report describes an implementation of a purely functional strict programming language which relies heavily on run-time code generation. Closures are not implemented as data structures containing code pointers and bindings for free variables, but instead by generating the machine code for a closure each time it is constructed. The actual values of free variables are embedded into the machine code instead of using references to a closure record. The goal of this experimental implementation is to examine the possibilities of run-time code generation - and just-in-time compilation in general - in the context of purely functional languages. The implementation details are described and the performance of several example programs is measured and compared to other functional language implementations.

Table of Contents

• Abstract
• 1 Introduction
• 1.1 The Problem
• 1.2 Run-time Code Generation
• 1.3 Structure of this Report
• 1.4 Acknowledgements
• 2 Closure Implementation Techniques
• 2.1 Example
• 2.2 Flat Closures
• 2.3 Nested Closures
• 2.4 Run-time Code Generation of Wrapper Functions
• 2.5 Lambda Lifting
• 3 Implementing Closures with Run-time Code Generation
• 3.1 Target Machine
• 3.2 Architecture
• 3.3 Design Decisions
• 3.4 Source Language
• 3.5 Code Generation Outline
• 3.6 Compilation Scheme
• 3.7 Code Generation for Source Expressions
• 3.8 Optimizing Tail Calls
• 3.9 Compilation of Mutually Recursive Functions
• 3.10 Optimizations
• 3.11 Limitations
• 4 Evaluation
• 4.1 Benchmark Programs
• 4.2 Platform
• 4.3 Performance Results
• 4.4 Comparison with other Implementations
• 4.4.1 Results
• 4.4.2 Language and Implementations Differences
• 4.4.3 Comment
• 4.5 Evaluation Conclusion
• 4.6 Compilation Scheme
• 4.7 Code Generation for Source Expressions
• 4.8 Optimizing Tail Calls
• 4.9 Compilation of Mutually Recursive Functions
• 4.10 Optimizations
• 4.11 Limitations
• 5 Conclusion and Future Work
• 5.1 Related Work
• 5.2 Future Work
• 5.3 Conclusion
• A Example Program Source Code
• A.1 Benchmark Programs
• A.2 Opal Programs
• A.3 Standard ML Programs
• A.4 Haskell Programs
• A.5 Scheme Programs
• A.6 C Programs

Download

This report is available electronically: [ PDF ]

BibTeX Entry

@TechReport{Grabmueller2006ImplementingClosures,
  author =	 {Martin Grabm{\"u}ller},
  title =	 {{Implementing Closures using Run-time Code
                  Generation}},
  institution =	 {Technische Universit{\"a}t Berlin},
  year =	 2006,
  type =	 {Research report},
  number =	 {\mbox{2006-02} in {\em Forschungsberichte Fakult{\"a}t IV
                  -- Elektrotechnik und Informatik}},
  month =	 {February},
  abstract =	 {This report describes an implementation of a purely
                  functional strict programming language which relies
                  heavily on run-time code generation. Closures are
                  not implemented as data structures containing code
                  pointers and bindings for free variables, but
                  instead by generating the machine code for a closure
                  each time it is constructed. The actual values of
                  free variables are embedded into the machine code
                  instead of using references to a closure record. The
                  goal of this experimental implementation is to
                  examine the possibilities of run-time code
                  generation -- and just-in-time compilation in
                  general -- in the context of purely functional
                  languages. The implementation details are described
                  and the performance of several example programs is
                  measured and compared to other functional language
                  implementations. }
}