Rabbit: A Compiler for Scheme/Front Matter

by Guy L. Steele, Jr.

Technical Report 474

RABBIT:
A Compiler
for SCHEME

Guy Lewis Steele

MIT Artificial Intelligence Laboratory

UNCLASSIFIED SECURITY CLASSIFICATION OF THIS (When Data Entered)

Sent 12/7/78

ADA 061996

REPORT DOCUMENTATION PAGE

READ INSTRUCTIONS
BEFORE COMPLETING FORM

1.

REPORT NUMBER

2.

GOVT ACCESSION NO.

2.

RECIPIENT'S CATALOG NO.

TR474

4.

TITLE (and Subtitles)

5.

TYPE OF REPORT & PERIOD COVERED

RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization)

Technical Report

6.

PERFORMING ORG. REPORT NUMBER

7.

AUTHORS(s)

8.

CONTRACT OR GRANT NUMBERS

Guy Lewis Steele

N00014-75-C-0643

9.

PERFORMING ORGANIZATION NAME AND ADDRESS

10.

PROGRAM ELEMENT, PROJECT, TASK AREA & WORK UNIT NUMBERS

Artificial Intelligence Laboratory

545 Technology Square
Cambridge, Massachusetts 02139

11.

CONTROLLING OFFICE NAME AND ADDRESS

12.

REPORT DATE

Advanced Research Projects Agency

1400 Wilson Blvd
Arlington, Virginia 22209

May 1978

13.

NUMBER OF PAGES

272

14.

MONITORING AGENCY NAME & ADDRESS(if different from Controlling Office)

15.

SECURITY CLASS (of this report)

Office of Naval Research

Information Systems
Arlington, Virginia 22217

UNCLASSIFIED

15a.

DECLASSIFICATION/DOWNGRADE SCHEDULE

16.

DISTRIBUTION STATEMENT (of this Report)

Distribution of this document is unlimited.

17.

DISTRIBUTION STATEMENT (of the abstract entered in Block 20, if different from Report.)

18.

SUPPLEMENTARY NOTES

None

19.

KEY WORDS (Continue on reverse side if necessary and identify by block number)

compiler optimization	tail-recursion
code generation	lambda calculus
LISP	lexical scoping
macros	continuations

18.

ABSTRACT (Continue on reverse side if necessary and identify by block number)

We have developed a compiler for the lexically-scoped dialect of LISP known as SCHEME. The compiler knows relatively little about specific data manipulation primitives such as arithmetic operators, but concentrates on general issues of environment and contral. Rather than having specialized knowledge about a large variety of control and environment constructs, the compiler handles only a small basis set which reflects the semantics of lambda-calculus. All of the traditional imperative constructs, such as sequencing, assignment, looping, GOTO, as well as many standard (cont'd) LISP constructs such as AND, OR, and COND, are expressed as macros in terms of the applicative basis set. A small number of optimization techniques, coupled with the treatment of function calls as GOTO statements, serve to produce code as good as that produced by more traditional compilers. The macro approach enables speedy implementation of new constructs as desired without sacrificing efficiency in the generated code.

A fair amount of analysis is devoted to determining whether environments may be stack-allocated or must be heap-allocated. Heap-allocated environments are necessary in general because SCHEME (unlike Algol 60 and Algol 68, for example) allows procedures with free lexically scoped variable to be returned as the values of other procedures: the Algol stack-allocation environment strategy does not suffice. The methods used here indicate heap-allocating generalizaiton of the "display" technique leads to an efficient implementation of such "upward funargs". Moreover, compile-time optimization and analysis can eliminate many "funargs" entirely, and so far fewer environment structures need be allocated at run time than might expected.

A subset of SCHEME (rather than triples, for example) serves as the representation intermedieate between the optimized SCHEME code and the final output code; code is expressed in this subset in the so'called constinuation-passing style. As a subset of SCHEME, it enjoys the same theoretical properties; one could even apply the same optimizer used on the input code to the intermediate code. However, the subset is so chosen that all temporary quantities are made manifest as variables, and no control stack is needed to evaluate it. As a result, this apparently applicative representation admits an imperative interpretation which permits easy transcription to fianl imperative machine code. These qualities suggest that an applicative language like SCHEME is a better candidate for an UNCOL than the more imperative candidates proposed to date.

DD

FORM 1 JAN 73

1473

EDITION OF 1 NOV 63 IS OBSOLETE S/N 0:02-014-6601

UNCLASSIFIED SECURITY CLASSIFICATION OF THIS (When Data Entered)

This research was conducted at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract number N00014-75-C-0643.