[comp.lang.scheme] Maclisp vs. CL & Scheme

gjc@mitech.COM (03/01/91)

Funny thing about EVAL in Maclisp:

Even if Maclisp did not have EVAL, it would be possible, nay, I know
from experience that it *was* possible, to write an EVAL in Maclisp.
With the proper calls from DDT you could even patch your running
copy of "TS LISP" so that your new eval took the place of the EVAL
built-in written in PDP-10 assembler.

You could write MACLISP EVAL in MACLISP using only documented primitives.
You could write MACLIPS READ in MACLISP using only documented primitives.
You could write MACLISP PRINT in MACLISP using only documented primitives.

In COMMON-LISP it is *NOT* *POSSIBLE* to write PRINT using only
functions provided in COMMON-LISP. It may be possible to write READ and EVAL.
(Any comments?)

What about the new Scheme standard. Even if it does not have EVAL,
is it possible to write EVAL? Is it possible to write READ and PRINT?

-gjc

p.s. It is not possible to write COMMON-LISP READ in COMMON-LISP,
because of some poor definition of the behavior of "#," at least.
And that is also something that gives trouble to attempts at EVAL.

feeley@chaos.cs.brandeis.edu (Marc Feeley) (03/04/91)

In gjc@mitech.COM's message of 1 Mar 91 13:21:27 GMT:

> What about the new Scheme standard. Even if it does not have EVAL,
> is it possible to write EVAL? Is it possible to write READ and PRINT?

It all depends how much functionality you want...  If these procedures do not
have to tie in to the underlying Scheme then it is of course possible
(because Scheme is Turing equivalent).

However, it is not possible to write a portable EVAL procedure because there
is no way in standard Scheme (R4RS or IEEE) to access global variables
through their names.  We would like the following code to print 100:

(define x 50)
(EVAL '(set! x (+ x x)))
(write x)

EVAL would be possible given procedures to reference and set global variables
(and perhaps define them), for example (global-var-ref name) and
(global-var-set! name val).  Think of global-var-ref as:

(define (global-var-ref name)
  (case name
    ((a) a)
    ((b) b)
    ... etc for all possible variable names!

and similarly for global-var-set!.  Here is a simple EVAL (which does not
handle the derived forms) that uses these procedures:

(define (EVAL expr)
  (define (eval-in-env expr env)
    (define (e x)
      (define (build-env vars vals env)
        (cond ((null? vars) env)
              ((pair? vars) (cons (cons (car vars) (car vals))
                                  (build-env (cdr vars) (cdr vals) env)))
              (else         (cons (cons vars vals) env))))
      (cond ((symbol? x) ; variable reference
             (let ((y (assq x env))) (if y (cdr y) (global-var-ref x))))
            ((not (pair? x)) ; constant
             x)
            ((eq? (car x) 'QUOTE) ; quoted constant
             (cadr x))
            ((eq? (car x) 'SET!) ; assignment
             (let ((y (assq (cadr x) env)) (val (e (caddr x))))
               (if y (set-cdr! y val) (global-var-set! (cadr x) val))))
            ((eq? (car x) 'IF) ; conditional
             (if (e (cadr x))
               (e (caddr x))
               (if (pair? (cdddr x)) (e (cadddr x)))))
            ((eq? (car x) 'LAMBDA) ; lambda expr
             (lambda l (eval-in-env (caddr x) (build-env (cadr x) l env))))
            (else ; we could check for derived special forms before this
             (apply (e (car x)) (map e (cdr x))))))
    (e expr))
  (eval-in-env expr '()))

It isn't clear that procedures like this should be in the standard
because there are many implementation dependent alternatives.  For
example, should there be multiple global environments?  Should environments
be first class environments?  I guess the standard(s) reflect that there
is no aggreement (yet) on this issue...

Marc -- feeley@cs.brandeis.edu