Rabbit: A Compiler for Scheme/Front Matter
Technical Report 474
MIT Artificial Intelligence Laboratory
|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.|
|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
|11.||CONTROLLING OFFICE NAME AND ADDRESS||12.||REPORT DATE|
|Advanced Research Projects Agency
1400 Wilson Blvd
|13.||NUMBER OF PAGES|
|14.||MONITORING AGENCY NAME & ADDRESS(if different from Controlling Office)||15.||SECURITY CLASS (of this report)|
|Office of Naval Research
|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.)|
|19.||KEY WORDS (Continue on reverse side if necessary and identify by block number)|
|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.
|1473||EDITION OF 1 NOV 63 IS OBSOLETE
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.