Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

How to implement a lisp interpreter?

87 views
Skip to first unread message

Abdullah Abdul Khadir

unread,
Sep 6, 2009, 3:14:31 AM9/6/09
to
Hi,

I was reading Paul Graham's article on "The roots of lisp" and I
came across the code given below,

(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) 'quote) (cadr e))
((eq (car e) 'atom) (atom (eval. (cadr e) a)))
((eq (car e) 'eq) (eq (eval. (cadr e) a) (eval.
(caddr e) a)))
((eq (car e) 'car) (car (eval. (cadr e) a)))
((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))
((eq (car e) 'cons) (cons (eval. (cadr e) a) (eval.
(caddr e) a)))
((eq (car e) 'cond) (evcon. (cdr e) a))
('t (eval. (cons (assoc. (car e) a) (cdr e)) a))))
((eq (caar e) 'label)
(eval. (cons (caddar e) (cdr e)) (cons (list (cadar e)
(car e)) a)))
((eq (caar e) 'lambda)
(eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr
e) a)) a)))))

The idea is very good, however, we have a catch 22 problem or a
problem of "the chicken or the egg" which kind of hampers the
enjoyment. I am assuming that all the functions used in the function
eval. given above have been implemented. Now, we have the following
problem(s),

1) In order to create the interpreter we need to be able to define
functions and interpret or compile them into executables. In
particular we need to be able to interpret/compile the eval. function
given above.
2) However, in order to interpret eval. we need an interpreter.
3) If we already had an interpreter that could interpret eval. then
what is the need for eval. we may as well use the interpreter that was
able to interpret eval.

My guess is that all lisp compilers have the same problem. Any ideas
as to how the interpreters such as sbcl or cmucl or clisp overcome the
above scenario. I need the solution pertaining to this particular
problem.

Thanks in advance,

Abdullah Abdul Khadir
------------------------------------------------------------------
Home page : www.cmi.ac.in/~abdullah
My blog : www.linuxandlisp.blogspot.com

Thomas Munro

unread,
Sep 6, 2009, 4:30:31 AM9/6/09
to
On Sep 6, 8:14 am, Abdullah Abdul Khadir <abdullah....@gmail.com>
wrote:

> 1) In order to create the interpreter we need to be able to define
> functions and interpret or compile them into executables. In
> particular we need to be able to interpret/compile the eval. function
> given above.

If you have nothing, only a computer and some way to type in machine
code instructions and run them, then you need to implement EVAL in
machine code, as the original Lisp guys did:

http://www-formal.stanford.edu/jmc/history/lisp/node3.html

> 2) However, in order to interpret eval. we need an interpreter.
> 3) If we already had an interpreter that could interpret eval. then
> what is the need for eval. we may as well use the interpreter that was
> able to interpret eval.

Once you have an interpreter (using hand written machine code), you
can use it to run your compiler which is written in Lisp. Then you can
compile EVAL to machine code, and you don't need your hand written
machine code anymore.

> My guess is that all lisp compilers have the same problem. Any ideas
> as to how the interpreters such as sbcl or cmucl or clisp overcome the
> above scenario. I need the solution pertaining to this particular
> problem.

SBCL is written in Common Lisp, so you need an existing Common Lisp
implementation such as CLISP or (more commonly) an earlier version of
SBCL to build it. Every new language has the same bootstrap problem
to kick this cycle off, if the interpreter and/or compiler is written
in the language itself. Temporary scaffolding and intermediate
languages (which in some cases may be defunct) have been used to get
started at some point in history. The first C compilers were probably
written in assembler and/or maybe some B or BCPL, from what I can see
on the Wikipedia page. Arc, a new Lisp dialect, was implemented in
Scheme. At some point they will presumably want to implement Arc in
pure Arc, and drop the training wheels, if they haven't already.

Slobodan Blazeski

unread,
Sep 6, 2009, 4:36:28 AM9/6/09
to
On Sep 6, 9:14 am, Abdullah Abdul Khadir <abdullah....@gmail.com>
wrote:
One day a group of eminent scientists got together and decided that
Man had come a
long way and no longer needed God. So they picked one scientist to go
and tell Him that
they were done with Him.
The scientist walked up to God and said, “God, we’ve decided that we
no longer need
You. We’re to the point that we can clone people and do many
miraculous things, so why
don’t You just retire?”
God listened very patiently to the man and then said, “Very well, but
first, how about
this, let’s have a Man-making contest.”
To which the scientist replied, “Okay, great!”
But God added, “Now, we’re going to do this just like I did back in
the old days with Adam.”
The scientist said, “Sure, no problem” and bent down and grabbed
himself a handful of dirt.
God just looked at him and said, “No, no, no—You go get your own
dirt!”

>
> My guess is that all lisp compilers have the same problem. Any ideas
> as to how the interpreters such as sbcl or cmucl
sbcl and cmucl are compilers.

> or clisp overcome the
> above scenario. I need the solution pertaining to this particular
> problem.

Assuming that no lisp compiler exists for some platform they could
overcome this problem by building on top of preexisting core made in
lower language for which compiler already exists (usually c/c++ which
are pretty much everywhere), then add lisp functionality to that
core. Another option is to COMPILE to target language like c,
assembly or machine instructions for the desired platform from some
other platform that already has an lisp implementation.


Bobi
http://www.linkedin.com/in/slobodanblazeski

Pascal Costanza

unread,
Sep 6, 2009, 5:00:28 AM9/6/09
to

Notice what Paul Graham did in the article: He explained all the
operators necessary for implementing eval. in terms of plain English. If
he hadn't done that, you wouldn't be able to understand eval.

The same has to be done in an implementation: You have to 'explain' (aka
implement) all the operators necessary for implementing eval. in terms
of plain machine language (or some other intermediate language that
already runs on the machine) before you can implement eval. like that.

The metacircular version of eval. gives you a model of the language that
is easier to understand than the 'real' implementation, and also allows
you to do some forms of metaprogramming that wouldn't be possible without.

Take a look at "The Art of the Interpreter" by Sussman and Steele as an
example to see how they use metacircular interpreters to explain
different variations of Lisp in a way that is much more succinct than if
they would explain it with other means.


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/

Rainer Joswig

unread,
Sep 6, 2009, 6:26:48 AM9/6/09
to
On 6 Sep., 09:14, Abdullah Abdul Khadir <abdullah....@gmail.com>
wrote:

> My guess is that all lisp compilers have the same problem. Any ideas


> as to how the interpreters such as sbcl or cmucl or clisp overcome the
> above scenario. I need the solution pertaining to this particular
> problem.

If you want to know more about how to implement Lisp-like languages
(interpreters and compilers), then I recommend reading 'Lisp in small
pieces'.

http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiSP.html

It really is an outstanding book.

Rob Warnock

unread,
Sep 6, 2009, 8:25:16 AM9/6/09
to
Rainer Joswig <jos...@lisp.de> wrote:
+---------------

| If you want to know more about how to implement Lisp-like languages
| (interpreters and compilers), then I recommend reading 'Lisp in small
| pieces'.
|
| http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiSP.html
|
| It really is an outstanding book.
+---------------

I strongly second this recommendation.


-Rob

-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

Vinay

unread,
Sep 7, 2009, 3:48:50 AM9/7/09
to
On Sep 6, 5:25 am, r...@rpw3.org (Rob Warnock) wrote:
> Rainer Joswig  <jos...@lisp.de> wrote:
> +---------------
> | If you want to know more about how to implement Lisp-like languages
> | (interpreters and compilers), then I recommend reading 'Lisp in small
> | pieces'.
> |
> |http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiSP.html
> |
> | It really is an outstanding book.
> +---------------
>
> I strongly second this recommendation.
>
> -Rob
>
> -----
> Rob Warnock                     <r...@rpw3.org>

> 627 26th Avenue                 <URL:http://rpw3.org/>
> San Mateo, CA 94403             (650)572-2607

I think "Anatomy of Lisp" is better as a first book on implementing
lisp. Its a bit dated, and hard to get. You'd have to buy it used ...

http://www.amazon.com/Anatomy-Lisp-McGraw-Hill-computer-science/dp/007001115X

0 new messages