Rabbit: A Compiler for Scheme

by Guy L. Steele, Jr.

RABBIT:

A Compiler for SCHEME

(A Dialect of LISP)

A Study in

Compiler Optimization

Based on Viewing
LAMBDA as RENAME
and
PROCEDURE CALL as GOTO

using the techniques of

Macro Definition of Control and Environment Structures
Source-to-Source Transformation
Procedure Integration
and
Tail-Recursion

Guy Lewis Steele Jr.

Massachusetts Institute of Technology

May 1978

Revised version of a dissertation submitted (under the title "Compiler Optimization Based on Viewing LAMBDA as RENAME plus GOTO") to the Department of Electrical Engineering and Computer Science on May 12, 1977, in partial fulfillment of the requirements for the degree of Master of Science.

Chapters (not listed in original)

• Front matter
• Abstract
• Author's Note
• Acknowledgements

Contents
1.Introduction	7
A.Background	7
B.The Thesis	10
2.The Source Language - SCHEME	15
3.The Target Language	18
4.The Target Machine	22
5.Language Design Considerations	25
6.The Use of Macros	28
7.The Imperative Treatment of Applicative Constructs	37
8.Compilation Strategy	44
A.Alpha-conversion and macro-expansion	45
B.Preliminary analysis	46
C.Optimization	49
D.Conversion to Continuation-Passing Style	56
E.Environment and closure analysis	60
F.Code generation	64
9.Example: Compilation of Iterative Factorial	69
10.Performance Measurements	86
11.Comparison with Other Work	88
12.Conclusions and Future Work	90
Notes	93
References	113
Appendix	117

---