From: erich
Subject: Lisp implementation question about iteration and symboltable lookup
Date:
Message-ID: <8vo71o$qdk$1@nnrp1.deja.com>
Hi!
I'm new to this newsgroup and didn't find an FAQ for it (there must be
some...but where?), so I'd like to apologize in advance if this question
is not appropriate here. Now to the question:
I'm about to implement a simple, dynamically-scoped lisp dialect that
will probably will be the slowest implementation ever because it's
written in BASIC (yes, you've heard right...). Anyway, it's a fun
project. But I've got a problem with implementing DO and iteration in
general.
Right now, there's one large symboltable that hashes the symbols to
underlying representations of lisp objects like strings, integer, atoms,
lists. When a procedure call is being evaluated, it's arguments are
bound to the formal parameters of the corresponding lambda construct,
then the body is evaluated, and then the formal parameters are unbound
again. In this process, the symboltable acts like a simple parameter
stack. Okay, works fine so far, and although nobody likes dynamic scope,
it's so easy to implement :) But how can I handle iteration? When a
return in the DO body is evaluated, it must exit the loop immediately
and return the argument of the return.
But the problem is, that evaluation in my implementation is recursive,
and the return has no idea where it should return to. Also, can't a
return occur at any nesting level in the DO body? For example, if it
would occur inside a LET, the bindings of LET would have to be unbound
again, or a big mess will be the result.
The only solution I can imagine is to put the formal parameters of a
procedure and all other local bindings like that of LET on an additional
stack upon binding them, such that when the evaluator exits out of a
nested evaluation process, it knows the local variables to unbind. This
seems extremely ineffective to me (pushing additional symbols on an
additional stack each time a procedure is called), and I still have no
clue how I could make a return return, when the body of a DO is
evaluated recursively..?
Any hints are welcome :)
Regards,
Erich
Sent via Deja.com http://www.deja.com/
Before you buy.