Rabbit: A Compiler for Scheme/Front Matter

From Wikisource
Jump to: navigation, search
Rabbit: A Compiler for Scheme by Guy L. Steele, Jr.
Front Matter

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

SMS 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
macro 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 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, 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 Alqol 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 generalization of the "display" technique leads to an efficient implementation of such "upward funarqs". 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 that 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 final 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.