Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!usc!snorkelwacker.mit.edu!apple!bbn.com!nic!news.cs.brandeis.edu!news!feeley
From: feeley@chaos.cs.brandeis.edu (Marc Feeley)
Newsgroups: comp.lang.scheme
Subject: Re: Maclisp vs. CL & Scheme (r^4).
Message-ID: <FEELEY.91Mar3111439@chaos.cs.brandeis.edu>
Date: 3 Mar 91 16:14:39 GMT
References: <9103011804.AA29248@schizo>
Sender: usenet@news.cs.brandeis.edu
Organization: Computer Science, Brandeis University, Waltham, MA, USA
Lines: 65
In-Reply-To: gjc@mitech.COM's message of 1 Mar 91 13:21:27 GMT

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