From: Ray S. Dillinger
Subject: Implementing Scheme in Scheme
Date:
Message-ID: <32E120CA.644A@sonic.net>
It seems that every textbook on Scheme, or CL for that matter,
indulges in the narcissistic pleasure of describing the semantics
of LISP in LISP (whichever value of LISP you happen to be using).
While that's neat for monkeying up variations on the language
or being able to experiment with alternate semantics, it's not
exactly the same as writing a compiler for a C in C. Ultimately
that C compiler emits raw machine code, which may use
fundamentally different data structures and optimization
strategies than it does itself.
There are a lot of things that LISP's hide from their users,
that the compiler absolutely has to deal with -- things like
memory management and garbage collection, for starters.
Has anyone done a *complete* compiler for LISP in LISP? A
compiler where you could, for example, have a different
garbage collection strategy, different structure for cons
cells, different strategy for type tracking, etc, from the
source language, etc, by changing the code of the compiler?
Lets say I have LISP "A" -- which uses stop-and-copy GC and
doesn't support static records. (Static records, BTW, are
pretty much needed if you want to be able to call routines
written in other languages on your data, or vice versa).
Can I implement in LISP "A" a compiler for LISP "B", which
uses generational GC and supports static records? Let's say
yes.
Now that I have the implementation of LISP "B", I should be
able to recompile it on itself, so the compiler itself, as
well as applications developed with it, will be able to use
generational GC. And if I come up with another good machine-
code optimization, I should be able to change the code,
recompile. and get the benefit of it.
Right now, this sort of compilation is something that LISP
systems do not do, as far as I know.
Bear
"Ray S. Dillinger" <····@sonic.net> writes:
> It seems that every textbook on Scheme, or CL for that matter,
> indulges in the narcissistic pleasure of describing the semantics
> of LISP in LISP (whichever value of LISP you happen to be using).
Keep in mind that these examples deal with interpretation, not
compiling. A compiler produces code in a different language, an
interpreter produces the result of running the program. Writing an
interpreter is sufficient to cover how the language works. Specifying
how to write a compiler is a task that requires more knowledge and
covers more material than a Scheme/CL textbook needs to.
--
.. Kjetil Valstadsve <·····@pvv.org>
.. http://www.pvv.org/~eddie/
Kjetil Valstadsve <·····@ra.pvv.ntnu.no> writes:
> "Ray S. Dillinger" <····@sonic.net> writes:
> > It seems that every textbook on Scheme, or CL for that matter,
> > indulges in the narcissistic pleasure of describing the semantics
> > of LISP in LISP (whichever value of LISP you happen to be using).
>
[...]
> Writing an interpreter is sufficient to cover how the language
> works. Specifying how to write a compiler is a task that requires
> more knowledge and covers more material than a Scheme/CL textbook
> needs to.
Curious. Then why does _Structure and Interpretation of Computer
Programs_ (the canonical textbook using Scheme) cover compiling
Scheme?
--
T. Kurt Bond, ···@wvlink.mpl.com
In article <···············@ra.pvv.ntnu.no>
·····@ra.pvv.ntnu.no "Kjetil Valstadsve" writes:
> Keep in mind that these examples deal with interpretation, not
> compiling. A compiler produces code in a different language, an
> interpreter produces the result of running the program. Writing an
> interpreter is sufficient to cover how the language works. Specifying
> how to write a compiler is a task that requires more knowledge and
> covers more material than a Scheme/CL textbook needs to.
A compiler needn't produce source code. Many of the compilers
I've written produced binary code (threaded, s-exprs, etc),
and this isn't at all unusual for Lisp. A number of Lisp
tutorials include compilers that don't produce source code,
nor is this unique to Lisp. The code doesn't need to be saved
to a file, either.
Examples of compilers written in Lisp include Yale Haskell,
OPS5, and Screamer. There are many others, but I won't bother
listing them all. You can get many of them via the Internet.
--
<URL:http://www.enrapture.com/cybes/> You can never browse enough
Martin Rodgers � Developer and Information Broker � London, UK
Please remove the "nospam" if you want to email me.
"Blow out the candles, HAL."
···@wvlink.mpl.com (T. Kurt Bond) writes:
> Kjetil Valstadsve <·····@ra.pvv.ntnu.no> writes:
> > Writing an interpreter is sufficient to cover how the language
> > works. Specifying how to write a compiler is a task that requires
> > more knowledge and covers more material than a Scheme/CL textbook
> > needs to.
>
> Curious. Then why does _Structure and Interpretation of Computer
> Programs_ (the canonical textbook using Scheme) cover compiling
> Scheme?
The register machine was introduced to cover the typical control
mechanics of a Scheme evaluator, not the semantics of Scheme
itself. The compilation section is a natural step even further. SICP
is not a Scheme textbook, it is, as you say, a textbook using Scheme,
and one that certainly covers more material than a Scheme textbook
needs to.
The depth of the knowledge required to understand a language seems to
me as a question of abstraction. If you can find no arguments against
the idea that understanding requires writing a compiler to
register-machine code, what's to stop you from requring knowledge of
the processes at transistor-level as well?
--
.. Kjetil Valstadsve <·····@pvv.org>
.. http://www.pvv.org/~eddie/
············@nospam.wildcard.demon.co.uk (Cyber Surfer) writes:
> A compiler needn't produce source code.
Without intending to be rhetorical, what is your definition of a
compiler?
--
.. Kjetil Valstadsve <·····@pvv.org>
.. http://www.pvv.org/~eddie/
In article <···············@iq.pvv.ntnu.no>
·····@iq.pvv.ntnu.no "Kjetil Valstadsve" writes:
> ············@nospam.wildcard.demon.co.uk (Cyber Surfer) writes:
>
> > A compiler needn't produce source code.
>
> Without intending to be rhetorical, what is your definition of a
> compiler?
Ok, but please keep in mind that the following is very general,
and deliberately vague. Books like SICP can give you some details.
PJ Brown's Writing Interactive Compilers and Interpreters explains
it all in some simpler terms, using Basic instead of Scheme.
Compiling (most languages) is a specialised area of string
processing. The input string is parsed into an internal form,
perhaps a tree, which is then "crunched", finally producing
anothe string. A series of internal forms may be used. The
output string may be object code, or source in another language.
Lisp code can begin life as a tree, and be compiled into a
string or another tree. The tree<->string transformation can
go in either direction, any number of times, using as many
different forms of representation as necessary.
E.g. Quick Basic, which I'm told transformed the source code
into threaded code to run, and then back into source code to
edit, going thru an intermediate form on the way.
Imagine a program that "decompiles" object code for one CPU
into an intermediate form, and the compile it into object code
for another CPU. The intermediate form might well use a series
of dataflow graphs (directed acyclic graphs).
Of course, this general definition could also include SGML tools,
and I see nothing wrong with that. The strings might not be
programs or object code, but the principles are the same.
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
Martin Rodgers � Developer and Information Broker � London, UK
Please remove the "nospam" if you want to email me.
"Blow out the candles, HAL."
In article <·············@sonic.net>
"Ray S. Dillinger" <····@sonic.net> writes:
...
Can I implement in LISP "A" a compiler for LISP "B", which
uses generational GC and supports static records? Let's say
yes.
Now that I have the implementation of LISP "B", I should be
able to recompile it on itself, so the compiler itself, as
well as applications developed with it, will be able to use
generational GC. And if I come up with another good machine-
code optimization, I should be able to change the code,
recompile. and get the benefit of it.
Right now, this sort of compilation is something that LISP
systems do not do, as far as I know.
People have been doing things like this in Lisp and Scheme since the
1960's.
--
Alan Bawden ····@LCS.MIT.EDU
617/492-7274 06BF9EB8FC4CFC24DC75BDAE3BB25C4B
Some examples of metacircular implementations may be found in:
Kiczales, Gregor, Jim des Rivieres, and Daniel G. Bobrow.
The Art of the Metaobject Protocol.
MIT Press 1991. 335 pages. ISBN 0-262-61074-4. $34.95
Paepcke, Andreas, Editor
Object-Oriented Programming: the CLOS Perspective.
MIT Press, 1993, ISBN 0-262-16136-2.
See:
http://www.parc.xerox.com/spl/projects/oi/
(Including a list of available papers.)
http://www-mitpress.mit.edu
(For information on these texts.)
Ray S. Dillinger wrote:
>
> It seems that every textbook on Scheme, or CL for that matter,
> indulges in the narcissistic pleasure of describing the semantics
> of LISP in LISP (whichever value of LISP you happen to be using).
>
> While that's neat for monkeying up variations on the language
> or being able to experiment with alternate semantics, it's not
> exactly the same as writing a compiler for a C in C. Ultimately
> that C compiler emits raw machine code, which may use
> fundamentally different data structures and optimization
> strategies than it does itself.
>
> There are a lot of things that LISP's hide from their users,
> that the compiler absolutely has to deal with -- things like
> memory management and garbage collection, for starters.
>
> Has anyone done a *complete* compiler for LISP in LISP? A
> compiler where you could, for example, have a different
> garbage collection strategy, different structure for cons
> cells, different strategy for type tracking, etc, from the
> source language, etc, by changing the code of the compiler?
>
> Lets say I have LISP "A" -- which uses stop-and-copy GC and
> doesn't support static records. (Static records, BTW, are
> pretty much needed if you want to be able to call routines
> written in other languages on your data, or vice versa).
>
> Can I implement in LISP "A" a compiler for LISP "B", which
> uses generational GC and supports static records? Let's say
> yes.
>
> Now that I have the implementation of LISP "B", I should be
> able to recompile it on itself, so the compiler itself, as
> well as applications developed with it, will be able to use
> generational GC. And if I come up with another good machine-
> code optimization, I should be able to change the code,
> recompile. and get the benefit of it.
>
> Right now, this sort of compilation is something that LISP
> systems do not do, as far as I know.
>
> Bear
Ray S. Dillinger (····@sonic.net) wrote:
> Can I implement in LISP "A" a compiler for LISP "B", which
> uses generational GC and supports static records? Let's say
> yes.
Have a look at Scheme48. It doesn't have a full compiler, but it's written
in Scheme *entirely*, including the virtual machine and garbage collector.
Scheme48 has a compiler (for a subset of Scheme) which generates efficient
C code; this is used to bring up the virtual machine.
Greetings,
Jens.
--
Internet: ···········@bbn.hp.com Phone: +49-7031-14-7698 (TELNET 778-7698)
MausNet: [currently offline] Fax: +49-7031-14-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]