6.001 Recitation – April 9, 2003

 

RI: Konrad Tollmar

 

•The m-eval / m-apply loop

•Syntax procedures

 

•New environment model – dynamic scoping

 

•Anayze before apply

 

 

 

 

 

1. Introduce a new special form

We would like to introduce a new special form to our evaluator called same?. Same? always takes three arguments, and returns #t if all three arguments are eq?. Same?, however is smart in that if the first two arguments are different, then the third argument is not evaluated. Here are some examples of using same?. 

 
(same? 'x 'x 'x)       ==>  #t
(same? 'x 'x 'y)       ==>  #f
(same? 'x 'y 'y)       ==>  #f
(same? 'x 'y (/ 1 0))  ==>  #f
(same? 'x 'x (/ 1 0))  ==>  Divide by Zero Error
 

To add this special form to the evaluator, we need to define some data abstraction. Define the function same?? that checks to see if an expression is a same? expression.

 

Define the functions same?-first and same?-second that select out the first and second sub-expressions (assume someone else defined same?-third).

 

Next, write the appropriate clause to add to the cond clause of eval, assuming that we have the function eval-same? that will evaluate a same? expression. 

 

Finally, write the eval-same? function that takes a same? expression and an environment and implements the special form as described above. 

 

 

 

 

 

 

 

 

 

 

 

2. Derived expressions

 

Make cond a derived expression of the special form if, i.e. convert the cond expression to an if expression and evalute it as such.

 

(cond      ((> x 0) x)

((= x 0) (display ’zero) 0)

           (else (- x)))

 

 

 

 

 

(if (> x 0)

           x

           (if (= x 0)

                      (begin (display ’zero) 0)

                      (- x)))

 

 

 

 

3. Dynamic scope

 

 

How could we implement Dynamic scope, ie. Look up free variables in the caller's environment rather than the surrounding lexical environment Example:

Trick -  pass in the env when we apply instead of when we define the proc (make-procedure).

 

(define (m-eval exp env)

 (cond

   ((self-evaluating? exp) exp)

   ((variable? exp) (lookup-variable-value exp env))

   ...

   ((lambda? exp)

    (make-procedure (lambda-parameters exp)

                                 (lambda-body exp)

                                 '*no-environment*))  ;CHANGE: no env

   ...    

   ((application? exp)

    (d-apply (m-eval (operator exp) env)

            (list-of-values (operands exp) env) env)) ;CHANGE: add env

   (else (error "Unknown expression -- M-EVAL" exp))))

 

 

(define (d-apply procedure arguments calling-env)

  (cond ((primitive-procedure? procedure)

         (apply-primitive-procedure procedure

                                    arguments))

        ((compound-procedure? procedure)

         (eval-sequence

          (procedure-body procedure)

          (extend-environment

                      (procedure-parameters procedure)

                      arguments

                      calling-env))) ;CHANGE: use calling env

       (else (error "Unknown procedure" procedure))))

 

 

 

 

 

4. Speed-up with analyze

 

A/ Why could meval / mapply be unnessesary slow sometimes?

 

B/ Consider evaluating the following expressions with and without using analyze.

 

 

(define foo (lambda () (+ 1 2))) 

 

 

(foo) 

(foo) 

 

 

 

 

(define (eval exp env)

  ((analyze exp) env))

 

(define (analyze exp) 

  (cond ((self-evaluating? exp) (analyze-self-evaluating exp))   

                             ((variable? exp) (analyze-variable exp))       

                             ((definition? exp) (analyze-definition exp))       

                             ((lambda? exp) (analyze-lambda exp))       

                             ((cond? exp) (analyze (cond->if exp)))       

                             ((application? exp) (analyze-application exp)))) 

 

(define (analyze-self-evaluating exp) (lambda (env) exp)) 

 

(define (analyze-variable exp) 

  (lambda (env)     

    (lookup-variable-value exp env))) 

 

(define (analyze-lambda exp) 

  (let ((bproc (analyze (lambda-body exp))))   

    (lambda (env)      

      (make-procedure (lambda-parameters exp) bproc env))))

 

(define (analyze-application exp)

                             (let (fproc (analyze (operator exp)

                                                          (aprocs (map analys (operands exp))))

                                                          (lambda (env)

                                                                                       (execute-application (fproc env)

                                                                                                                    (map (lambda (aproc) (aproc env) aprocs)

 

(define (execute-application proc args) 

  (cond ((primitive-procedure? proc)

                             (apply-primitive-procedure proc arguments))

        ((compound-procedure? proc)

                                                            (procedure-body proc )

                                                              (extend-environment

                                                                                       (procedure-parameters proc )

                                                                                       arguments

                                                                                       (procedure-environment proc ))))

        (else

         (error

          "Unknown procedure type – execute-application " proc ))))

 

 

 

M-Eval / M-Apply

 

(set! *unparser-list-depth-limit* 10)

(set! *unparser-list-breadth-limit* 10)

(define apply-in-underlying-scheme (access apply '()))

(define (meval exp env)

  (cond ((self-evaluating? exp) exp)

        ((variable? exp) (lookup-variable-value exp env))

        ((quoted? exp) (text-of-quotation exp))

        ((assignment? exp) (eval-assignment exp env))

        ((definition? exp) (eval-definition exp env))

        ((if? exp) (eval-if exp env))

        ((lambda? exp)

         (make-procedure (lambda-parameters exp)

                         (lambda-body exp)

                         env))

        ((begin? exp)

         (eval-sequence (begin-actions exp) env))

        ((cond? exp) (meval (cond->if exp) env))

 

        ((application? exp)

         (mapply (meval (operator exp) env)

                          (list-of-values (operands exp) env)))

        (else

         (error "Unknown expression type -- MEVAL" exp))))

(define (mapply procedure arguments)

  (cond ((primitive-procedure? procedure)

         (apply-primitive-procedure procedure arguments))

        ((compound-procedure? procedure)

             (eval-sequence

              (procedure-body procedure)

              (extend-environment

               (procedure-parameters procedure)

               arguments

               (procedure-environment procedure))))

        (else

         (error

          "Unknown procedure type -- APPLY" procedure))))

 

(define (list-of-values exps env)

  (if (no-operands? exps)

      '()

      (cons (meval (first-operand exps) env)

            (list-of-values (rest-operands exps) env))))

 

(define (eval-if exp env)

  (if (true? (meval (if-predicate exp) env))

      (meval (if-consequent exp) env)

      (meval (if-alternative exp) env)))

 

(define (eval-sequence exps env)

  (cond ((last-exp? exps) (meval (first-exp exps) env))

        (else (meval (first-exp exps) env)

              (eval-sequence (rest-exps exps) env))))

 

(define (eval-assignment exp env)

  (set-variable-value! (assignment-variable exp)

                       (meval (assignment-value exp) env)

                       env)

  'ok)

 

(define (eval-definition exp env)

  (define-variable! (definition-variable exp)

                    (meval (definition-value exp) env)

                    env)

  'ok)

 

(define (self-evaluating? exp)

  (cond ((number? exp) true)

        ((string? exp) true)

            ((boolean? exp) true)

        (else false)))

(define (quoted? exp)

  (tagged-list? exp 'quote))

(define (text-of-quotation exp) (cadr exp))

(define (tagged-list? exp tag)

  (if (pair? exp)

      (eq? (car exp) tag)

      false))

(define (variable? exp) (symbol? exp))

(define (assignment? exp)

  (tagged-list? exp 'set!))

(define (assignment-variable exp) (cadr exp))

(define (assignment-value exp) (caddr exp))

(define (definition? exp)

  (tagged-list? exp 'define))

(define (definition-variable exp)

  (if (symbol? (cadr exp))

      (cadr exp)

      (caadr exp)))

(define (definition-value exp)

  (if (symbol? (cadr exp))

      (caddr exp)

      (make-lambda (cdadr exp)

                   (cddr exp))))

(define (lambda? exp) (tagged-list? exp 'lambda))

(define (lambda-parameters exp) (cadr exp))

(define (lambda-body exp) (cddr exp))

(define (make-lambda parameters body)

  (cons 'lambda (cons parameters body)))

(define (if? exp) (tagged-list? exp 'if))

(define (if-predicate exp) (cadr exp))

(define (if-consequent exp) (caddr exp))

(define (if-alternative exp)

  (if (not (null? (cdddr exp)))

      (cadddr exp)

      'false))

(define (make-if predicate consequent alternative)

  (list 'if predicate consequent alternative))

(define (begin? exp) (tagged-list? exp 'begin))

(define (begin-actions exp) (cdr exp))

(define (last-exp? seq) (null? (cdr seq)))

(define (first-exp seq) (car seq))

(define (rest-exps seq) (cdr seq))

(define (sequence->exp seq)

  (cond ((null? seq) seq)

        ((last-exp? seq) (first-exp seq))

        (else (make-begin seq))))

(define (make-begin seq) (cons 'begin seq))

(define (application? exp) (pair? exp))

(define (operator exp) (car exp))

(define (operands exp) (cdr exp))

(define (no-operands? ops) (null? ops))

(define (first-operand ops) (car ops))

(define (rest-operands ops) (cdr ops))

(define (cond? exp) (tagged-list? exp 'cond))

(define (cond-clauses exp) (cdr exp))

(define (cond-else-clause? clause)

  (eq? (cond-predicate clause) 'else))

(define (cond-predicate clause) (car clause))

(define (cond-actions clause) (cdr clause))

(define (cond->if exp)

  (expand-clauses (cond-clauses exp)))

(define (expand-clauses clauses)

;; exercise

)

 

(define (true? x)

  (not (eq? x false)))

(define (false? x)

  (eq? x false))

(define (make-procedure parameters body env)

  (list 'procedure parameters body env))

(define (compound-procedure? p)

  (tagged-list? p 'procedure))

(define (procedure-parameters p) (cadr p))

(define (procedure-body p) (caddr p))

(define (procedure-environment p) (cadddr p))

(define (enclosing-environment env) (cdr env))

(define (first-frame env) (car env))

(define the-empty-environment '())

(define (make-frame variables values)

  (cons variables values))

(define (frame-variables frame) (car frame))

(define (frame-values frame) (cdr frame))

(define (add-binding-to-frame! var val frame)

  (set-car! frame (cons var (car frame)))

  (set-cdr! frame (cons val (cdr frame))))

(define (extend-environment vars vals base-env)

  (if (= (length vars) (length vals))

      (cons (make-frame vars vals) base-env)

      (if (< (length vars) (length vals))

          (error "Too many arguments supplied" vars vals)

          (error "Too few arguments supplied" vars vals))))

(define (lookup-variable-value var env)

  (define (env-loop env)

    (define (scan vars vals)

      (cond ((null? vars)

             (env-loop (enclosing-environment env)))

            ((eq? var (car vars))

             (car vals))

            (else (scan (cdr vars) (cdr vals)))))

    (if (eq? env the-empty-environment)

        (error "Unbound variable" var)

        (let ((frame (first-frame env)))

          (scan (frame-variables frame)

                (frame-values frame)))))

  (env-loop env))

(define (set-variable-value! var val env)

  (define (env-loop env)

    (define (scan vars vals)

      (cond ((null? vars)

             (env-loop (enclosing-environment env)))

            ((eq? var (car vars))

             (set-car! vals val))

            (else (scan (cdr vars) (cdr vals)))))

    (if (eq? env the-empty-environment)

        (error "Unbound variable -- SET!" var)

        (let ((frame (first-frame env)))

          (scan (frame-variables frame)

                (frame-values frame)))))

  (env-loop env))

(define (define-variable! var val env)

  (let ((frame (first-frame env)))

    (define (scan vars vals)

      (cond ((null? vars)

             (add-binding-to-frame! var val frame))

            ((eq? var (car vars))

             (set-car! vals val))

            (else (scan (cdr vars) (cdr vals)))))

    (scan (frame-variables frame)

          (frame-values frame))))

(define (setup-environment)

  (let ((initial-env

         (extend-environment (primitive-procedure-names)

                             (primitive-procedure-objects)

                             the-empty-environment)))

    (define-variable! 'true true initial-env)

    (define-variable! 'false false initial-env)

    (define-variable! 'null false initial-env)

    initial-env))

;[do later] (define the-global-environment (setup-environment))

(define (primitive-procedure? proc)

  (tagged-list? proc 'primitive))

(define (primitive-implementation proc) (cadr proc))

(define primitive-procedures

  (list (list 'car car)

        (list 'cdr cdr)

        (list 'cons cons)

            (list 'list list)

        (list 'null? null?)

            (list '+ +)

            (list '- -)

            (list '/ /)

            (list '= =)

            (list 'eq? eq?)

            (list '< <)

            (list '> >)

            (list '>= >=)

            (list '<= <=)

            (list 'display display)

            (list 'apply mapply)

        ))

(define (primitive-procedure-names)

  (map car

       primitive-procedures))

(define (primitive-procedure-objects)

  (map (lambda (proc) (list 'primitive (cadr proc)))

       primitive-procedures))

(define (apply-primitive-procedure proc args)

  (apply (primitive-implementation proc) args))

(define input-prompt ";;; M-Eval input:")

(define output-prompt ";;; M-Eval value:")

(define (driver-loop)

  (prompt-for-input input-prompt)

  (let ((input (read)))

    (let ((output (meval input the-global-environment)))

      (announce-output output-prompt)

      (user-print output)))

  (driver-loop))

(define (prompt-for-input string)

  (newline) (newline) (display string) (newline))

(define (announce-output string)

  (newline) (display string) (newline))

(define (user-print object)

  (cond ((compound-procedure? object)

             (display (list 'compound-procedure

                                     (procedure-parameters object)

                                     (procedure-body object)

                                     '<procedure-env>)))

            (else

             (display object))))

;;;Following are commented out so as not to be evaluated when

;;; the file is loaded.

;; (define the-global-environment (setup-environment))

;; (driver-loop)

(define (start-meval)

  (set! the-global-environment (setup-environment))

  (driver-loop))

'METACIRCULAR-EVALUATOR-LOADED