Scheme as IL

gat@forsight.jpl.nasa.gov (Erann Gat) writes:
|>Richard Kelsey wrote a dissertation about using a subset of Scheme as an
|>intermediate language for compilation. It seems like an elegant approach
|>to me (though to be perfectly honest I don't really have the background to
|>evaluate it properly). Is anyone familar enough with this work to offer a
|>more educated opinion on it?


I came to more or less the same conclusion: studied traditional tuple-ish
ILs for a year, came up with a list of desireables, discovered this was a
subset of Scheme, and then discovered Steele's proposal for Scheme as the
universal Intermediate Language. Kelsey's dissertation is a nice
verification that a Scheme-like IL can be used for a standard imperative
language without efficiency loss.


I strongly believe that a ``scheme-like'' IL (the key features from Scheme
are the lambda-calculus plus imperative features --- see Matthias
Felleisen's dissertation for a serious study) is ideal for any situation
where one is compiling widely-different languages; it meshes well both
with standard hardware and with imperative/functional/OO languages and I
think, with logical languages as well (did a brief study on this but
didn't push it very hard). My dissertation has more information on using
a Scheme-like IL in a system for quickly generating prototype compiler
optimizers, although the stuff therein on ILs is more of the ``here's what
I did'' variety than a defense of it.


The thread from which this sprang was on C as an IL; note that
`Scheme-like' ILs are not simply subsets of scheme, and you don't use them
as one would C. In a Kelsey-style compiler, the generated IL is
transformed into code that is equivalent to the original and still legal
under the scheme-like semantics, but that is also trivially transformable
into efficient machine code. There is no stage where you could stop the
process, feed the code to a standard Scheme compiler, and hope to get
reasonable machine-code as a result.


    /charlie


References:


%A Richard Andrews Kelsey
%T Compilation by Program Transformation
%I Yale University
%R PhD |DISS|
%D |MAY| 1989


%A Charles Farnum
%T Pattern-based Languages for Prototyping of Compiler Optimizers
%I |UCB|
%R |TR| UCB/CSD 90/608
%D |DEC| 1990


%A Matthias Felleisen
%T The Calculi of Lambda-v-CS Conversion: A Syntactic Theory of Control
      and State in Imperative Higher-order Programming Languages
%I Indiana University
%R PhD |DISS|
%D |AUG| 1987


%A Guy Lewis Steele~Jr.
%A Gerald Jay Sussman
%T LAMBDA: The Ultimate Imperative
%R AI Memo No. 353
%I |MIT| Artificial Intelligence Laboratories
%D March 1976


%A Guy Lewis Steele~Jr.
%T LAMBDA: The Ultimate Declarative
%R AI Memo No. 379
%I |MIT| Artificial Intelligence Laboratories
%D November 1976


--

Return to the comp.compilers page.
Search the comp.compilers archives again.