From: Pablo de Heras Ciechomski
Subject: Interpreter writing references?
Date: 
Message-ID: <E7Yj5.2611$7g1.41108@nntpserver.swip.net>
Are there any good references for how to write a small LISP subset compiler?
Books or links are very appreciated. I have only come across one book called
"Interpreting LISP" by Gary D Knoll. The sad thing is I don't know
functional programming so lambda doesn't ring any bells :)

Thank you in advance
/Pablo

From: Kent M Pitman
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <sfwg0ofjxaa.fsf@world.std.com>
"Pablo de Heras Ciechomski" <·····@efd.lth.se> writes:

> Are there any good references for how to write a small LISP subset compiler?

You'll have to say whether you want to write a small "LISP subset compiler"
or a "small Lisp subset" compiler.  How small? How chosen?  Some subsets don't
really simplify the task at all.  Others do.  You might check the web and 
perhaps an index of published papers on a thing called CLICC done in Europe,
which I think had a goal similar to that you might be describing--to do
simple, efficient compilation of a particular CL subset (which might or might
not be the one you contemplate).  They might have summarized how they picked
their subset or what their techniques are...

> Books or links are very appreciated. I have only come across one book called
> "Interpreting LISP" by Gary D Knoll. The sad thing is I don't know
> functional programming so lambda doesn't ring any bells :)

(I remember the year before I first took Analysis in high school thumbing 
through a calculus text and saying to a friend "this looks all very 
straightforward, except what's this squiggly thing [integral sign]?" I'd
just assumed it was another pure functional simple operator like + or * that
had no special syntactic impact on the text around it...)

Fortunately, lambda is just a notation for anonymous functions and isn't 
going to be your chief enemy in this regard.  But it's still wise for you
to invest in some book on Lisp or Scheme to learn how Lambda is used or
all Lisp is going to look opaque to you.
 
The book of choice when I was in college was called The Anatomy of Lisp
or some such, by Jon Allen (spelling?), I think.  The book is extremely dated
now and doesn't really address modern Lisp implementation issues.  I'm not
sure there is a logical successor, which if it's true is something of a pity.
Or maybe I just haven't had the recent need to go seek one out and someone
who has will suggest a modern equivalent...

> Thank you in advance

Not sure how much help this has been, but alwyas happy to try.  As are most
of the people on this group.  Doubtless others will chime in, especially if
you can be more specific about your needs, since the topic in the vague form
you've specified it is really quite open-ended.
From: Pablo de Heras Ciechomski
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <vk0k5.2783$7g1.43188@nntpserver.swip.net>
A small subset would be the most accurate. I don't need all the bells and
whistles of LISP. Just a form of script language that is easy to parse.
Maybe the book I have isn't that bad.

I'll check CLICC out :)

/Pablo
From: Martin Cracauer
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <8mtncr$m0d$1@counter.bik-gmbh.de>
"Pablo de Heras Ciechomski" <·····@efd.lth.se> writes:

>A small subset would be the most accurate. I don't need all the bells and
>whistles of LISP. Just a form of script language that is easy to parse.

I find static scoping just as important in script languages as
elsewhere.  And without exceptions, you will quickly run into serious
problems for non-trivial scripts with more than one ("library") layer.
Once you bother to implement both, you will quickly find yourself
having too much to do.

Is there any reason you can't use an existing embeddable Scheme
interpreter?  That way, your users may build their own libraries and
reuse then anywhere when Scheme extension is supported.  Not to speak
of reusing SLIB, having (format ...) (or whatever it is called in
slib) is often the most practical thing to debug script extensions for
the users.

Martin
-- 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Martin Cracauer <········@bik-gmbh.de> http://www.bik-gmbh.de/~cracauer/
FreeBSD - where you want to go. Today. http://www.freebsd.org/
From: Pablo de Heras Ciechomski
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <A9yk5.51$mW5.40@nntpserver.swip.net>
>Is there any reason you can't use an existing embeddable Scheme
>interpreter?  That way, your users may build their own libraries and
>reuse then anywhere when Scheme extension is supported.  Not to speak
>of reusing SLIB, having (format ...) (or whatever it is called in
>slib) is often the most practical thing to debug script extensions for
>the users.


I want to do the interpreter myself. That's why :)

/Pablo
From: Martin Cracauer
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <8muevl$1r59$1@counter.bik-gmbh.de>
"Pablo de Heras Ciechomski" <·····@efd.lth.se> writes:

>>Is there any reason you can't use an existing embeddable Scheme
>>interpreter?  That way, your users may build their own libraries and
>>reuse then anywhere when Scheme extension is supported.  Not to speak
>>of reusing SLIB, having (format ...) (or whatever it is called in
>>slib) is often the most practical thing to debug script extensions for
>>the users.

>I want to do the interpreter myself. That's why :)

I guessed that :-), but don't you think the energy is better spent
contributing to an existing project?

Martin
-- 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Martin Cracauer <········@bik-gmbh.de> http://www.bik-gmbh.de/~cracauer/
FreeBSD - where you want to go. Today. http://www.freebsd.org/
From: Neel Krishnaswami
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <slrn8p19hm.9fa.neelk@brick.cswv.com>
Kent M Pitman <······@world.std.com> wrote:
>  
> The book of choice when I was in college was called The Anatomy of
> Lisp or some such, by Jon Allen (spelling?), I think.  The book is
> extremely dated now and doesn't really address modern Lisp
> implementation issues.  I'm not sure there is a logical successor,
> which if it's true is something of a pity.  Or maybe I just haven't
> had the recent need to go seek one out and someone who has will
> suggest a modern equivalent...
 
Christian Queinnec's _Lisp in Small Pieces_ is IMO wonderful. 

It's very comprehensive, covering everything from namespace issues
(Lisp-1 or Lisp-N?  How should the global environment be scroped?) to
exceptions, continuations, and call/cc, as well as implementations of
macros and eval. He works through pure interpreters, bytecode
compilers and compilation to C.

The only big lacunae are garbage collection and object representation
issues. (He suggests using a third-party GC like the Boehm collector,
and he does show how to implement tagged integers, but beyond that
there's very little.) Also missing are the really fancy-pants
optimizations like CMUCL or Stalin do.

Also, he doesn't skimp on the source code; everything he talks about
he actually implements. This means that what he does is very well-
documented, but between all the code and all the different designs
there isn't room for a lot of different implementations of each design
choice. This is okay, I think, since reading _LiSP_ is good background
for reading all the different papers available on the Web.


Neel
From: Pablo de Heras Ciechomski
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <bB6k5.3008$7g1.43427@nntpserver.swip.net>
I checked out "L.I.S.P." on Amazon. This book really is really what I was
looking for. It isn't cheap but I think it's worth it.

/Pablo
From: Martin Cracauer
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <8mtmmb$la5$1@counter.bik-gmbh.de>
"Pablo de Heras Ciechomski" <·····@efd.lth.se> writes:

>I checked out "L.I.S.P." on Amazon. This book really is really what I was
>looking for. It isn't cheap but I think it's worth it.

Uh?  Never heard of that one and my amazon search returns 34 items,
all non-programming.

Could you please post more details?

Martin
-- 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Martin Cracauer <········@bik-gmbh.de> http://www.bik-gmbh.de/~cracauer/
FreeBSD - where you want to go. Today. http://www.freebsd.org/
From: Kent M Pitman
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <sfwog31pfyw.fsf@world.std.com>
········@counter.bik-gmbh.de (Martin Cracauer) writes:

> "Pablo de Heras Ciechomski" <·····@efd.lth.se> writes:
> 
> >I checked out "L.I.S.P." on Amazon. This book really is really what I was
> >looking for. It isn't cheap but I think it's worth it.
> 
> Uh?  Never heard of that one and my amazon search returns 34 items,
> all non-programming.

I think he meant "Lisp In Small Pieces" by Christian Queinnec, which had
been alluded to earlier in the discussion.  L.I.S.P. is (surely not
accidentally) the acronym for the title.
From: Martin Cracauer
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <8mu4jj$1fh9$1@counter.bik-gmbh.de>
Kent M Pitman <······@world.std.com> writes:

>········@counter.bik-gmbh.de (Martin Cracauer) writes:

>> "Pablo de Heras Ciechomski" <·····@efd.lth.se> writes:
>> 
>> >I checked out "L.I.S.P." on Amazon. This book really is really what I was
>> >looking for. It isn't cheap but I think it's worth it.
>> 
>> Uh?  Never heard of that one and my amazon search returns 34 items,
>> all non-programming.

>I think he meant "Lisp In Small Pieces" by Christian Queinnec, which had
>been alluded to earlier in the discussion.  L.I.S.P. is (surely not
>accidentally) the acronym for the title.

Ah, thanks.  I actually bought it quite cheap here in Germany, maybe
we are lucky just one time ;-)

Martin
-- 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Martin Cracauer <········@bik-gmbh.de> http://www.bik-gmbh.de/~cracauer/
FreeBSD - where you want to go. Today. http://www.freebsd.org/
From: Peter Norvig
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <3991A0C6.21A6AB25@norvig.com>
Neel Krishnaswami wrote:

> Christian Queinnec's _Lisp in Small Pieces_ is IMO wonderful.
> 

In my opinion too.  As I wrote at
http://www.amazon.com/exec/obidos/ASIN/0521562473/

This is an excellent book on Lisp implementation. You'll get a lot out
of it, whether you are interested in writing compilers and interpreters
(for Lisp or any language) or whether you just want to see how Lisp
works. It is the modern day successor to Allen's "Anatomy of Lisp".

-Peter Norvig
From: Donald Fisk
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <3995ED93.336A875E@enterprise.net.nospam>
Neel Krishnaswami wrote:
> 
> Kent M Pitman <······@world.std.com> wrote:
> >
> > The book of choice when I was in college was called The Anatomy of
> > Lisp or some such, by Jon Allen (spelling?), I think.  The book is
> > extremely dated now and doesn't really address modern Lisp
> > implementation issues.  I'm not sure there is a logical successor,
> > which if it's true is something of a pity.  Or maybe I just haven't
> > had the recent need to go seek one out and someone who has will
> > suggest a modern equivalent...
> 
> Christian Queinnec's _Lisp in Small Pieces_ is IMO wonderful.
> 
> It's very comprehensive, covering everything from namespace issues
> (Lisp-1 or Lisp-N?  How should the global environment be scroped?) to
> exceptions, continuations, and call/cc, as well as implementations of
> macros and eval. He works through pure interpreters, bytecode
> compilers and compilation to C.
> 
> The only big lacunae are garbage collection and object representation
> issues. (He suggests using a third-party GC like the Boehm collector,
> and he does show how to implement tagged integers, but beyond that
> there's very little.) Also missing are the really fancy-pants
> optimizations like CMUCL or Stalin do.
> 
> Also, he doesn't skimp on the source code; everything he talks about
> he actually implements. This means that what he does is very well-
> documented, but between all the code and all the different designs
> there isn't room for a lot of different implementations of each design
> choice. This is okay, I think, since reading _LiSP_ is good background
> for reading all the different papers available on the Web.

I now own a copy of this book.   One of the lacunae (object
representation)
is covered well in The Art of the MetaObject Protocol, which takes you
through the implementation of CLOSette.   There's still a need for
decent coverage of garbage collection, though of course one way to
get around it is to implement in Java.   Garbage collectors are a pig
to debug; the only way I know of is careful inspection of gc()'s
code.

> Neel

-- 
Le Hibou
With regard to Mr Blair's "gut British instinct" --
would that be the same British gut, with "pussy-
hunter" tattooed on it, we saw being repatriated
from Charleroi recently? -- Peter Kenvyn Jones
From: Edward Jason Riedy
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <8n53si$2ld$1@agate.berkeley.edu>
And Donald Fisk writes:
 - 
 - There's still a need for decent coverage of garbage collection, 
 - though of course one way to get around it is to implement in Java.

I don't know of any Java implementations with advanced gc 
implementations.  I do know of quite a few performance oddities
due to Sun's stop-all-threads-and-copy collector...

But if you want more on garbage collection, the current book to buy
is Richard Jones's Garbage Collection:
  http://www.cs.ukc.ac.uk/people/staff/rej/gcbook/gcbook.html
He also has a sizable bibliography available on-line for finding
more references.  (Look for Paul Wilson for some good, on-line ones.)

Jason
From: Pekka P. Pirinen
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <ixk8dibejt.fsf@harlequin.co.uk>
Donald Fisk <··········@enterprise.net.nospam> writes:
> There's still a need for decent coverage of garbage collection,
> though of course one way to get around it is to implement in Java.
> Garbage collectors are a pig to debug; the only way I know of is
> careful inspection of gc()'s code.

There's a good deal of material available on GC techniques (start with
Jones' book, as recommended), but nothing on implementation and
debugging that I know of.  Although, it occurs to me that several good
GCs are available in source form -- it might be possible to learn
something from them.

In my experience, the secret is just applying the usual high-quality
programming techniques in spades: Lots of run-time consistency
checking.  Be paranoid; a broken GC will sneak up and corrupt your
data where you least expect it.  Document every assumption and
restriction, and check them at run-time if at all possible.  Produce
logs about everything.  Count everything you can; it helps with
debugging and tuning.  Of course you only want checks, logging and
statistics in the debug build; make sure this is the _only_ way in
which the debug build is different.  Even so, learn to use your
debugger at machine level.  And yes, writing clear and simple code so
that you _can_ inspect it is perhaps the most important contribution
to quality, because nothing makes as much difference as code approvals
and inspections.
-- 
Pekka P. Pirinen
 The Memory Management Reference: articles, bibliography, glossary, news
 <URL:http://www.harlequin.com/mm/reference/>
From: Christopher Browne
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <G3Ho5.4242$g53.95184@news5.giganews.com>
Centuries ago, Nostradamus foresaw a time when Pekka P. Pirinen would say:
> The Memory Management Reference: articles, bibliography, glossary, news
> <URL:http://www.harlequin.com/mm/reference/>

Note that has moved to
   <http://www.xanalys.com/software_tools/mm/>
-- 
(concatenate 'string "cbbrowne" ·@" "hex.net")
<http://www.ntlug.org/~cbbrowne/>
"Tooltips are the proof that icons don't work."
-- Stefaan A. Eeckels
From: Pekka P. Pirinen
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <ix66o64qzz.fsf@harlequin.co.uk>
········@news.hex.net (Christopher Browne) writes:
> Centuries ago, Nostradamus foresaw a time when Pekka P. Pirinen would say:
> > The Memory Management Reference: articles, bibliography, glossary, news
> > <URL:http://www.harlequin.com/mm/reference/>
> 
> Note that has moved to
>    <http://www.xanalys.com/software_tools/mm/>

Yes, I moved it there.  However, the old URLs work, and will continue
to do so for the forseeable future, since both companies contribute to
the effort.  I put in the harlequin.com URL, since I'm employed by
Harlequin myself, but outside users should probably take Christopher
Browne's advice and use the new URL to spare the overhead of
redirection.
-- 
Pekka P. Pirinen, editor, The Memory Management Reference
The triumph of cloning tech: A sheep that looks just like another sheep.
From: David Combs
Subject: Re: Interpreter writing references?
Date: 
Message-ID: <8ofqm2$3io$1@slb0.atl.mindspring.net>
In article <··············@harlequin.co.uk>,
Pekka P. Pirinen <·····@harlequin.co.uk> wrote:
>
>In my experience, the secret is just applying the usual high-quality
>programming techniques in spades: Lots of run-time consistency
>checking.  Be paranoid; a broken GC will sneak up and corrupt your
>data where you least expect it.  Document every assumption and
>restriction, and check them at run-time if at all possible.  Produce
>logs about everything.  Count everything you can; it helps with
>debugging and tuning.  Of course you only want checks, logging and
>statistics in the debug build; make sure this is the _only_ way in
>which the debug build is different.  Even so, learn to use your
>debugger at machine level.  And yes, writing clear and simple code so
>that you _can_ inspect it is perhaps the most important contribution
>to quality, because nothing makes as much difference as code approvals
>and inspections.

The language I use, mainsail (MAchine INdependent SAIL),
has gc, and with that a debugger command to check
memory consistency; that is, that pointers are all
pointing to something legal, etc.

So, you can run that from time to time to see
when you have screwed up some pointer operation (in
a regular program).  (I used this way back in early
80's when just starting with the language; haven't
had to in a long time).

Anyway, another feature is that it counts instructions
executed when a program is compiled debuggable.

And, the debugger has a "stop at instr count reaching
  <some number you enter>".

So, trick is to set that stop-count, run the program,
it stops at that point (and puts you into the debugger),
you run the consistency checker, to see if you have
screwed up yet (this is where you have screwed something,
but don't get the fatal effect until much later).

So, what you do is use bisection; you can really home
in quick to the exact instruction (in the debugger,
the statement) where you screw up.

VERY, VERY NICE.

(Do lisps have such a feature, eg for people who
boldly poke pointers?)

David