# Rabbit: A Compiler for Scheme/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 | REPORT DOCUMENTATION PAGE | REPORT DOCUMENTATION PAGE | REPORT DOCUMENTATION PAGE | READ INSTRUCTIONS BEFORE COMPLETING FORM | READ INSTRUCTIONS BEFORE COMPLETING FORM |
| 1. | REPORT NUMBER | 2. | GOVT ACCESSION NO. | 2. | RECIPIENT'S CATALOG NO. |
| | TR474 | | |
| 4. | TITLE (and Subtitles) | TITLE (and Subtitles) | TITLE (and Subtitles) | 5. | TYPE OF REPORT & PERIOD COVERED |
| | RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization) | RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization) | RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization) | | Technical Report |
| | RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization) | RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization) | RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization) | 6. | PERFORMING ORG. REPORT NUMBER |
| 7. | AUTHORS(s) | AUTHORS(s) | AUTHORS(s) | 8. | CONTRACT OR GRANT NUMBERS |
| | Guy Lewis Steele | Guy Lewis Steele | Guy Lewis Steele | | N00014-75-C-0643 |
| 9. | PERFORMING ORGANIZATION NAME AND ADDRESS | PERFORMING ORGANIZATION NAME AND ADDRESS | PERFORMING ORGANIZATION NAME AND ADDRESS | 10. | PROGRAM ELEMENT, PROJECT, TASK AREA & WORK UNIT NUMBERS |
| | Artificial Intelligence Laboratory 545 Technology Square Cambridge, Massachusetts 02139 | Artificial Intelligence Laboratory 545 Technology Square Cambridge, Massachusetts 02139 | Artificial Intelligence Laboratory 545 Technology Square Cambridge, Massachusetts 02139 |
| 11. | CONTROLLING OFFICE NAME AND ADDRESS | CONTROLLING OFFICE NAME AND ADDRESS | CONTROLLING OFFICE NAME AND ADDRESS | 12. | REPORT DATE |
| | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | | May 1978 |
| | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | 13. | NUMBER OF PAGES |
| | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | Advanced Research Projects Agency 1400 Wilson Blvd Arlington, Virginia 22209 | | 272 |
| 14. | MONITORING AGENCY NAME & ADDRESS(if different from Controlling Office) | MONITORING AGENCY NAME & ADDRESS(if different from Controlling Office) | MONITORING AGENCY NAME & ADDRESS(if different from Controlling Office) | 15. | SECURITY CLASS (of this report) |
| | Office of Naval Research Information Systems Arlington, Virginia 22217 | Office of Naval Research Information Systems Arlington, Virginia 22217 | Office of Naval Research Information Systems Arlington, Virginia 22217 | | UNCLASSIFIED |
| | Office of Naval Research Information Systems Arlington, Virginia 22217 | Office of Naval Research Information Systems Arlington, Virginia 22217 | Office of Naval Research Information Systems Arlington, Virginia 22217 | 15a. | DECLASSIFICATION/DOWNGRADE SCHEDULE |
| 16. | DISTRIBUTION STATEMENT (of this Report) | DISTRIBUTION STATEMENT (of this Report) | DISTRIBUTION STATEMENT (of this Report) | DISTRIBUTION STATEMENT (of this Report) | DISTRIBUTION STATEMENT (of this Report) |
| | Distribution of this document is unlimited. | Distribution of this document is unlimited. | Distribution of this document is unlimited. | Distribution of this document is unlimited. | Distribution of this document is unlimited. |
| 17. | DISTRIBUTION STATEMENT (of the abstract entered in Block 20, if different from Report.) | DISTRIBUTION STATEMENT (of the abstract entered in Block 20, if different from Report.) | DISTRIBUTION STATEMENT (of the abstract entered in Block 20, if different from Report.) | DISTRIBUTION STATEMENT (of the abstract entered in Block 20, if different from Report.) | DISTRIBUTION STATEMENT (of the abstract entered in Block 20, if different from Report.) |
| 18. | SUPPLEMENTARY NOTES | SUPPLEMENTARY NOTES | SUPPLEMENTARY NOTES | SUPPLEMENTARY NOTES | SUPPLEMENTARY NOTES |
| | None | None | None | None | None |
| 19. | KEY WORDS (Continue on reverse side if necessary and identify by block number) | KEY WORDS (Continue on reverse side if necessary and identify by block number) | KEY WORDS (Continue on reverse side if necessary and identify by block number) | KEY WORDS (Continue on reverse side if necessary and identify by block number) | 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 | compiler optimization tail-recursion code generation lambda calculus LISP lexical scoping macros continuations | compiler optimization tail-recursion code generation lambda calculus LISP lexical scoping macros continuations | compiler optimization tail-recursion code generation lambda calculus LISP lexical scoping macros continuations | 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) | ABSTRACT (Continue on reverse side if necessary and identify by block number) | ABSTRACT (Continue on reverse side if necessary and identify by block number) | ABSTRACT (Continue on reverse side if necessary and identify by block number) | 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. | 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. | 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. | 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. | 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.