Rabbit: A Compiler for Scheme

AI Technical Report 474, the sixth of the Lambda Papers.

554923Rabbit: A Compiler for Scheme1978Guy 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)

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



This work is licensed under the Creative Commons Attribution 3.0 Unported License. This page must provide all available authorship information.

Public domainPublic domainfalsefalse

This work is free and may be used by anyone for any purpose. If you wish to use this content, you do not need to request permission as long as you follow any licensing requirements mentioned on this page.

Wikimedia has received an e-mail confirming that the copyright holder has approved publication under the terms mentioned on this page. This correspondence has been reviewed by an OTRS member and stored in our permission archive. The correspondence is available to trusted volunteers.

Public domainPublic domainfalsefalse