Recitation 16


Today's Ideas:
-- implementing the environment model


Part 1: Recitation Problems

Tuesday's problem:

Scheme's if and Scheme*'s if* behave differently.
-- What's the difference?
-- write a new version of eval-if that makes if* behave like if

(define (eval-if exp)
  (let ((predicate   (cadr exp))
        (consequent  (caddr exp))
        (alternative (cadddr exp)))
    (let ((test (eval predicate)))
      (cond
       ((eq? test #t)  (eval consequent))
       ((eq? test #f)  (eval alternative))
       (else           (error "predicate not a conditional: "
                              predicate))))))

Answer: in Scheme*, the then-branch is evaluated only if the test evaluates to the boolean value #t, whereas in MIT Scheme, the then-branch is evaluated so long as the test does not evaluate to #f (which happens also to be the empty list :-( ). So, for example, (if 1 2 3) evaluates to 2 in MIT Scheme but (if* 1 2 3) throws an error in Scheme*.

Thursday's problem:

What is the result of this sequence of evaluations? Write a substitution model trace omitting uninteresting steps.

(define (extend-env-with-new-frame names values env) env)
(eval '(define* x* 10) GE)
(eval '(define* twice* (lambda* (x*) (plus* x* x*))) GE)
(eval '(twice* 4) GE)
Answer: Redefining extend-env-with-new-frame causes this procedure to do nothing: it returns the same environment it was given! So during execution no frames will be hung, and every expression will be evaluated in the GE. The result of the last eval is therefore 20. This redefinition has essentially made our interpreter like the primitive version we saw earlier with only one global environment.


Part 2: Playing with the interpreter

Our entire interpreter is collected together below. This corresponds to the final verson of the interpreter from Thursday's lecture.

Challenge problems:

-- Find the code that makes this interpreter "applicative order" -- that is, arguments get evaluated before an operator is applied.

It's the application? branch of the eval procedure. Since the underlying Scheme implementation is known to be applicative order, the argument expressions to appl must be evaluated before appl is applied.

-- Can you figure out what order arguments are evaluated in? How would you change the interpreter to ensure that arguments are evaluated from left to right? Hint: this can be done simply by redefining one built-in procedure.

This is trickier. Again, we need to look at the application? branch of the eval procedure. The map expression will determine what order arguments are evaluated in. It boils down to how map is implemented.  In fact, with the usual implementation of map, it can't be determined, since we'd need to know what order the arguments to the cons call were evaluated in. To fix the order to be left to right, we could redefine map as follows:

(define (map f p)
  (if (null? p) '()
      (let ((result (f (car p))))
           (cons result (map f (cdr p))))))

Now all that determines the order of evaluation is that the interpreter is applicative order: this ensures that the let binding is evaluated before its body (since it desugars to a lambda with the expression in the binding as the argument)!

-- Add a maybe special form to the language. The expression (maybe e1 e2) either evaluates e1 and returns its value, or e2; the choice is random.

-- Add the following feature to the language: the expression (outer v), where v is a name, is like the expression v, except rather than evaluating v in the innermost frame, it evaluates it in the one that encloses it -- in environment model terms, the frame it points to. If the environment is the global environment, (outer v) and v should be equivalent.

-- Suppose we wanted to add procedures that can take an arbitrary number of arguments. How would you implement this?


Definitions


;***************************************************************
; BASIC UTILITIES

(define (tag-check e sym) (and (pair? e) (eq? (car e) sym)))

(define table-tag 'table)
(define (make-table) (cons table-tag '()))
(define (table? x) (tag-check x table-tag))

(define (add-assoc key val alist) (cons (list key val) alist))

(define (table-put! tbl key val)
  (set-cdr! tbl (add-assoc key val (cdr tbl))))
(define (table-get tbl key)
  (assq key (cdr tbl)))
(define binding-value cadr)

(define (application? e) (pair? e))
(define (lambda? e) (tag-check e 'lambda*))
(define (define? exp) (tag-check exp 'define*))
(define (if? exp)     (tag-check exp 'if*))

;******************************************************************
; DATA ABSTRACTIONS FOR PROCEDURES

; PRIMITIVE PROCEDURES

(define prim-tag 'primitive)
(define (make-primitive scheme-proc)(list prim-tag scheme-proc))
(define (primitive? e)              (tag-check e prim-tag))
(define (get-scheme-procedure prim) (cadr prim))

; COMPOUND PROCEDURES
; ADT that implements the "double bubble"

(define compound-tag 'compound)
(define (make-compound parameters body env)
                    (list compound-tag parameters body env))
(define (compound? exp)  (tag-check exp compound-tag))

(define (parameters compound) (cadr compound))
(define (body compound)       (caddr compound))
(define (env compound)        (cadddr compound))

;******************************************************************
; ENVIRONMENT DATA ABSTRACTION
; Environment = list<table>

(define (extend-env-with-new-frame names values env)
  (let ((new-frame (make-table)))
    (make-bindings! names values new-frame)
    (cons new-frame env)))

(define (make-bindings! names values table)
  (for-each
     (lambda (name value) (table-put! table name value))
     names values))

; the initial global environment
(define GE
  (extend-env-with-new-frame
     (list 'plus* 'greater* 'true*)
     (list (make-primitive +) (make-primitive >) #t)
     '()))

; lookup searches the list of frames for the first match
(define (lookup name env)
  (if (null? env)
      (error "unbound variable: " name)
      (let ((binding (table-get (car env) name)))
        (if binding
            (binding-value binding)
            (lookup name (cdr env))))))

; define changes the first frame in the environment
(define (eval-define exp env)
  (let ((name          (cadr exp))
        (defined-to-be (caddr exp)))
    (table-put! (car env) name (eval defined-to-be env))
    'undefined))

;******************************************************************
; EVALUATOR

(define (eval exp env)
  (cond
   ((number? exp)       exp)
   ((symbol? exp)      (lookup exp env))
   ((define? exp)      (eval-define exp env))
   ((if? exp)          (eval-if exp env))
   ((lambda? exp)      (eval-lambda exp env))
   ((application? exp) (appl (eval (car exp) env)
                              (map (lambda (e) (eval e env))
                                   (cdr exp))))
   (else
    (error "unknown expression " exp))))

(define (eval-lambda exp env)
  (let ((args (cadr exp))
        (body (caddr exp)))
    (make-compound args body env)))

(define (eval-if exp env)
  (let ((predicate   (cadr exp))
        (consequent  (caddr exp))
        (alternative (cadddr exp)))
    (let ((test (eval predicate env)))
      (cond
       ((eq? test #t)  (eval consequent env))
       ((eq? test #f)  (eval alternative env))
       (else           (error "val not boolean: "
                              predicate))))))

(define (appl operator operands)
  (cond ((primitive? operator)
         (apply (get-scheme-procedure operator)
                       operands))
        ((compound? operator)
         (eval (body operator)
               (extend-env-with-new-frame
                           (parameters operator)
                           operands
                           (env operator))))
        (else
         (error "operator not a procedure: " operator))))
 



Daniel Jackson
October 27, 1999