Browse Prior Art Database

ORBIT: An Optimizing Compiler for Scheme

IP.com Disclosure Number: IPCOM000128722D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 16 page(s) / 53K

Publishing Venue

Software Patent Institute

Related People

David Kranz: AUTHOR [+7]

Abstract

In this paper we describe an optimizing compiler for Scheme [3, 13] called Orbit that incorporates our experience with an earlier Scheme compiler called TC [10, 111, together with some ideas from Steele's Rabbit compiler (14]. The three main design goals have been correctness, generating very efficient compiled code, and portability.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ORBIT: An Optimizing Compiler for Scheme

David Kranz*, Richard Kelsey*, Jonathan Rees* Paul Hudak*, James Phllbin*, and Norman Adams+

1. Introduction

In this paper we describe an optimizing compiler for Scheme [3, 13] called Orbit that incorporates our experience with an earlier Scheme compiler called TC [10, 111, together with some ideas from Steele's Rabbit compiler (14]. The three main design goals have been correctness, generating very efficient compiled code, and portability.

In spirit, Orbit is similar to the Rabbit compiler in that it depends on a translation of source code into mcontinuation-passing style" (CPS), a convenient intermediate form that makes control-now explicit. After CPS conversion. procedures take an extra argument called a continuation (another procedure) that represents the next logical execution point after execution of the procedure body. Thus procedures do not "return," but rather ucontinue intou the code represented by the continuation. This permits. for example, a general but simple way to optimize tail-recursions into loops.

Steele's seminal work on Rabbit demonstrated the general benefits of this approach to compiler design. However, his work was primarily research oriented, and Rabbit was essentially a prototype compiler (consider, for example, that it generated `.%4ACLISP code). TC, on the other hand. was one of the first practical compilers for a Scheme dialect. and much was learned through its design and construction.2 Orbit now represents a culmination of that learning process, in which CPS conversion has been implemented thoroughly, extended in critical ways, and set in a framework of other important compiler innovations to yield a practical compiler that generates production-quality code competitive with the best compilers for Lisp as well as non- Lisp languages.3 The new ideas in Orbit include:

1. An extension to CPS conversion called assignment conversion that facilitates treatment of assiVied variables. . (See section 3.)

2. Compact and efficient runtime data representations, the most important being those for lexical closures, which are represented in different ways depending on information gleaned from a static analysis of their use. (See sections 4 and 5.)

3. A register allocation strategy based on trace scheduling that optimizes register usage across forks and joiris (and which, because of CPS conversion, includes procedure calls). (See section
6.)

4. An integral table-driven assembler that uses hints from the code generator to order blocks so as to min-imize the number and size of jumps. (See section 7.)

5. A technique for defining the behavior of primitive operations in Scheme source modules rather than in the internal logic of the compiler. (See section 9.1.)

Yale University Page 1 Dec 31, 1986

Page 2 of 16

ORBIT: An Optimizing Compiler for Scheme

6. Flexibility in configuring the runtime support system for user progr...