6.001 Recitation # 15 – April 4, 2003

 

RI: Konrad Tollmar

 

•The Scheme Interpreter

•Eval review

 

 

 

 

 

 

1. Parse tree – scheme’s reader
Construct the parse tree for:

(eval '(define* z* (plus* 1 3)) GE)

 

(eval '(define* mpy* (lambda* (x* y*) (times* x* y*))) GE)

 

(eval '(mpy* 3 z*) GE)

 

 

 

 

 

 

 

 

2. Refine define*

 

 

 

 

 

 

Modify our language so define* also return the defined value.

 

 

(define (eval-define exp)

  (let ((name          (cadr exp))

        (defined-to-be (eval (caddr exp))))

    (table-put! environment name defined-to-be)

    defined-to-be))

 

 

3. Add a new operator

 

Extend our language with the and* operator.

(and* <exp1> <exp2> .. <expn>)

 

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

(define (and? e) (tag-check e 'and*))

 

(define (eval exp)

  (cond

   ((number? exp) exp)

   ((boolean? exp) exp)

   ((and? exp) (eval-and exp))

   (else

    (error "unknown expression " exp))))

 

(define (eval-and exp)

  (define (try-next terms)

    (if (null? terms)

#t

           (let ((first-term (eval (car terms))))

                      (if first-term

                                 (try-next (cdr terms))

                                 #f))))

  (try-next (cdr exp)))

 

(eval '(and* #t #t))

 

 

4. Change the language syntax

Add a new combination form.

 

 

(+ 1 2)    (call + 1 2)
          

(call square 3)

 

 

 

(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))

         ((call? exp) (apply

                             (eval (cadr exp) env)

                             (map (lambda (e) (eval e env))

                                     (cddr exp))

                             ))

         (else (error "unknown expression " exp)))

Of course we also would like to change the wired prefix notation to good-old postfix style. Modify the interpreter so we can write postfix assignments instead.

(define myVar 10)

(myVar := 10)

 

 

         ((:=? exp)

             (eval-define

              (cons ’define

                        (cons (car exp) (cddr exp))) env))

 

 

Or maybe we would like to add a new procedure definition form.

(lambda (x) x)

 

(procedure (params: x) (body: x))

 

 

 

(lambda (x y) (+ x y) (* x y))

 

(procedure (params: x y)

           (body: (+ x y) (* x y)))

 

 

 

 

         ((proc? exp)

        (list compound-tag

                                                              (cdadr exp)(cdaddr exp) env)

 

 

5. Example of Eval-6

 

1

(eval '(define* z* (plus* 1 3)) GE)

 

(define* z* (plus* 1 3))    | GE

 

 

(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) (apply (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))))

         (else (error "unknown expression " exp))))

 

 

 

 

(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 defined-to-be))

 

 

 

2

(eval '(define* z* (plus* 1 3)) GE)

 

(define* z* (plus* 1 3))    | GE

(plus* 1 3)              | GE

 

 

(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) (apply

                                  (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))

                              ))

         (else (error "unknown expression " exp))))

 

3

(eval '(define* z* (plus* 1 3)) GE)

 

(define* z* (plus* 1 3))    | GE

(plus* 1 3)                          | GE

            1                        | GE

            3                        | GE

 

(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) (apply

                                                              (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))))

         (else (error "unknown expression " exp))))

 

4

(eval '(define* z* (plus* 1 3)) GE)

 

(define* z* (plus* 1 3))    | GE

(plus* 1 3)              | GE

            1           | GE  ==> 1

            3           | GE  ==> 3

 

(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) (apply

                                  (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))

                              ))

         (else (error "unknown expression " exp))))

 

(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) (apply

                                  (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))

                              ))

         (else (error "unknown expression " exp))))

 

5

(eval '(define* z* (plus* 1 3)) GE)

 

(define* z* (plus* 1 3))    | GE

(plus* 1 3)              | GE

            1           | GE  ==> 1

            3           | GE  ==> 3

            plus*       | GE

 

(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) (apply (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))))

         (else (error "unknown expression " exp))))

 

6

(eval '(define* z* (plus* 1 3)) GE)

 

(define* z* (plus* 1 3))    | GE

(plus* 1 3)              | GE

            1           | GE  ==> 1

            3           | GE  ==> 3

            plus*       | GE         ==> (primitive [prim +])

 

(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) (apply

                                  (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))

                              ))

         (else (error "unknown expression " exp))))

 

(define scheme-apply apply)

 

(define (apply operator operands)

  (cond ((primitive? operator)

         (scheme-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))))

 

7

(eval '(define* z* (plus* 1 3)) GE)

 

(define* z* (plus* 1 3))    | GE

(plus* 1 3)              | GE

            1           | GE  ==> 1

            3           | GE  ==> 3

            plus*       | GE         ==> (primitive [prim +])

(scheme-apply [prim +] 1 3) ==> 4

 

(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) (apply (eval (car exp) env)

                                  (map (lambda (e) (eval e env))

                                         (cdr exp))))

         (else (error "unknown expression " exp))))

 

 

 

 

(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))

 

8

(eval '(define* z* (plus* 1 3)) GE)

 

(define z* (plus* 1 3))   | GE

(plus* 1 3)              | GE

            1           | GE  ==> 1

            3           | GE  ==> 3

            plus*       | GE         ==> (primitive [prim +])

(scheme-apply [prim +] 1 3) ==> 4

(table-put! (car GE) ‘z* 4)

;modified environment!