How can I write the Eval function?
(eval '(+ 2 3))
5
The eval global button is just the LispMe way
of implementing the read-eval-print loop.
Lisp in the palm of your hand,
what will they think of next?
> Lisp in the palm of your hand,
> what will they think of next?
APL on a laptop? Oh, wait a minute... they already did that
(in 1983, I think).
--
Raymond Wiker, Orion Systems AS
+47 370 61150
As an academic matter, though - it is possible to write eval in terms of
other primitive functions?
why, yes, that's a regular exercise in Scheme courses.
#:Erik
--
Y2K conversion simplified: Januark, Februark, March, April, Mak, June,
Julk, August, September, October, November, December.
My memory is a little hazy and I only played with one of these
for a few hours, so I don't know if I got all the details exactly right.
I would love to spend all day puzzling it out, but I have already given up
to to lack of time and unfamiliarity with the language. Would anyone mind
posting the solution (to the problem of writing Eval in terms of the other
basic Scheme functions)?
> Eric:
Ok, here we go. Greetings, Wolfgang.
---
(de Eval (x env)
(cond ((symbol? x) (Symbol-lookup x env))
((atom? x) x)
((equal? 'quote (car x)) (cadr x))
((equal? 'lambda (car x)) (Build-closure x env))
((equal? 'if (car x))
(if (Eval (cadr x) env)
(Eval (caddr x) env)
(Eval (cadddr x) env)))
(else (Apply (Eval (car x) env)
(map (lambda (i) (Eval i env)) (cdr x))))))
(de Apply (f args)
(cond ((Primitive? f) (apply (eval f) args))
((Closure? f) (Apply-Closure f args))
(else (error 'Apply
"expects type <procedure> as 1st argument"))))
(de Primitive? (x) (and (symbol? x) (primitive? (eval x))))
(de Apply-Closure (f args)
(de bind (varis args)
(unless (= (length varis) (length args))
(error 'Apply-Closure
"wrong number of arguments, expected ~a, given ~a"
(length varis)
(length args)))
(pairlis varis args))
(de evlis (exprs env)
(if (pair? (cdr exprs))
(begin (Eval (car exprs) env) (evlis (cdr exprs env)))
(Eval (car exprs) env)))
(evlis (Closure-exprs f)
(cons (bind (Closure-varis f) args) (Closure-env f))))
(de Symbol-lookup (x env)
(cond ((null? env)
(if (primitive? (eval x))
x
(error 'Symbol-lookup "~ unbound." x)))
((let ((s (assoc x (car env)))) (and s (cadr s))))
(else (Symbol-lookup x (cdr env)))))
(de New-closure (varis env exprs)
(list '*closure* varis env exprs))
(de Closure? (x) (and (pair? x) (equal? '*closure* (car x))))
(de Closure-varis (x) (cadr x))
(de Closure-env (x) (caddr x))
(de Closure-exprs (x) (cadddr x))
(de Build-closure (x env)
(assert (equal? 'lambda (car x)))
(unless (pair? (cddr x))
(error 'closure "expression list must not be empty."))
(New-closure (cadr x) env (cddr x)))
(de test-with-y-combinator ()
;;; eval is the ordinary built-in eval,
;;; Eval is what we defined above.
;;; this should return (720 720)
(let ((x '(((lambda (le)
((lambda (f) (lambda (x) ((f f) x)))
(lambda (f) (le (lambda (x) ((f f) x))))))
(lambda (phi)
(lambda (n) (if (<= n 1) 1 (* n (phi (1- n)))))))
6)))
(list (eval x) (Eval x '()))))
(test-with-y-combinator)
This is a nice Scheme *interpreter*, but it is not the equivalent of
eval. To appreciate why, consider how variable lookup is done. If I
load the definitions of Eval etc. into a Scheme session, and type
(define x 1)
(Eval '(+ x 1) '()) ; eval x in a null environment
I will get an error complaining about unbound symbols x and +. This
can be remedied by providing an environment where they are bound:
(Eval '(+ x 1) (list (list 'x x) (list '+ +)))
which will evaluate to 2 (I hope, I could not actually run the example
because of the nonstandard syntax). Even this does not get us all the
way, however, since changes to the bindings in Eval's environment do
not propagate back to the underlying implementation's
environment. It would be easy enough to augment the interpreter with
set!, but this would work as follows. First we build an environment
where x and + are bound to their current values:
(define env (list (list 'x x) (list '+ +)))
after which the values of env and x are:
env ==> ((x 1) (+ <procedure>))
x ==> 1
After evaluating
(Eval '(set! x (+ x 1)) env)
the values of env and x are:
env ==> ((x 2) (+ <procedure>))
x ==> 1
which is clearly not what one would expect from eval. The Revised^5
Report on Scheme allows for some restricted access to the underlying
environment, but even there it is not possible to portably access and
mutate bindings created by the user.
In Common Lisp (Allegro in particular):
user(1): (setq x 1)
1
user(2): (eval '(+ x 1))
2
user(3): (eval '(setq x (+ x 1)))
2
user(4): x
2
If this is a regular exercise, Erik must be attending some tough
Scheme courses ;-)
--
Pertti Kellom\"aki, Tampere Univ. of Technology, Software Systems Lab
And doubles the max number of nodes to 16K !
>
> As an academic matter, though - it is possible to write eval in terms of
> other primitive functions?
In Structure and Interpretation of Computer Programs in chapter 4 titled
Metelinguistic Abstraction is a definition for eval and apply, but it
assumes some procedures that are not available in LispMe.
SICP is a great academic text for Scheme.
You should check out comp.lang.scheme
Thanks,
Jeff Sandys
Wolfgang Hukriede <whuk...@ifm.uni-kiel.de> writes:
> (de Eval (x env)
> (cond ((symbol? x) (Symbol-lookup x env))
> ((atom? x) x)
> ((equal? 'quote (car x)) (cadr x))
> ((equal? 'lambda (car x)) (Build-closure x env))
> ((equal? 'if (car x))
[...]
For fun, I tried implementing a Scheme interpreter in Emacs Lisp.
It works rather well, apart from tail recursion, continuations and
macros. I guess tail recursion would be the easiest of these.
I chose to represent Scheme-specific types (such as booleans and
procedures) as vectors whose first element is eq to a magic cons
cell. This way, the Scheme code can't fake them.
One thing in my interpreter works differently from yours.
Namely, my eval does not compare the car of the form to 'quote
and such; rather, it just looks it up in the current environment
like any other symbol. This lookup normally returns a
magic-tagged vector which represents a builtin macro. The
evaluator notices this and passes the unevaluated argument list
to the Emacs Lisp function referred to by the vector. Thus one
can bind quote as a variable or bind another symbol to the value
of quote.
Is this correct behavior?
That's how many real interpreters actually work. The hard-coded
comparisons are generally only found in pedagogical interpreters, to
emphasize that these symbols really are part of the language's syntax, not
something that users should expect to be able to extend or redefine, just
like keywords in conventional languages.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.