Scheme as IL (Charles Farnum)
Fri, 31 Jul 1992 13:52:26 GMT

          From comp.compilers

Related articles
Re: Pros and cons of high-level intermediate languages (1992-07-23)
Re: Pros and cons of high-level intermediate languages (1992-07-29)
Scheme as IL (1992-07-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Charles Farnum)
Organization: Compilers Central
Date: Fri, 31 Jul 1992 13:52:26 GMT
References: 92-07-107 92-07-082
Keywords: translator, design, bibliography, Scheme
Posted-Date: Fri, 31 Jul 92 09:52:26 -0400 (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.



%A Richard Andrews Kelsey
%T Compilation by Program Transformation
%I Yale University
%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
%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


Post a followup to this message

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