Building Interpreters (2)

Dealing with Recursion: L4

<expr> ::= letrec {<var> ({<var>}*) = <expr>}* in <expr>

with abstract syntax:

(letrec-exp (proc-names (list-of symbol?))
            (idss       (list-of (list-of symbol?)))
            (bodies     (list-of expr?))
            body        expr?)

letrec fact(x) = if zero?(x) then 1 else *(x, fact(sub1(x))) in
  fact(6)

(define eval-exp
  (lambda (exp env)
    (cases expr exp
      (letrec-exp (proc-names idss bodies body)
        (eval-exp body
          (extend-env-recursively proc-names idss bodies env)))
      ...)))

Let e1 = (extend-env-recursively proc-names idss bodies env) then:


If name is in proc-names, and ids and body are the corresponding formal parameter
    list and procedure body, then
    (apply-env e1 name) = (closure ids body e1)

If not, then:
    (apply-env e1 name) = (apply-env e name)

(define extend-env-recursively
  (lambda (proc-names idss bodies old-env)
    (letrec ((rec-env (lambda (sym)
                        (let ((pos (find-position sym proc-names)))
                          (if (number? pos)
                              (closure (list-ref idss pos)
                                       (list-ref bodies pos)
                                       rec-env)
                              (apply-env old-env sym))))))
      rec-env)))

(define-datatype env env?
  (empty-env)
  (extended-env (syms (list-of symbol?))
                (vals vector?)
                (env  env?))
  (recursively-extended-env
    (proc-names (list-of symbol?))
    (idss (list-of (list-of symbol?)))
    (bodies (list-of expr?))
    (env env?)))

(define apply-env
  (lambda (env sym)
    (cases env env
      (empty-env () (error "No binding"))
      (extended-env (syms vals env)
        (let ((pos (find-pos sym syms)))
          (if (number? pos)
            (vector-ref vals pos)
            (apply-env env sym))))
      (recursively-extended-env (proc-names idss bodies old-env)
        (let ((pos (find-pos sym syms)))
          (if (number? pos)
            (closure (list-ref idss pos)
                     (list-ref bodies pos)
                     env)
            (apply-env old-env sym)))))))

(letrec ((p (lambda (x) ...(p y) ...)))
  body)

rewrites to:

(let ((p '*))
  (begin
    (set! p (lambda (x) ... (p y) ...))
    body))

There exists a way to implement recursion without using recursion in the meta-language - nor assignment. It relies on the Y operator of the lambda calculus. Some explanations about the Y operator are provided here.

Dealing with Assignment: L5

    Denoted Value = Ref(Expressed Value)
    Expressed Value = Number + ProcVal
    ProcVal = Primitive + Closure
    Closure = {Symbol}* x Expr x Env
    Env = Symbol -> Expressed Value

References are also called L-values - because they generally can appear on the left-hand side of an assignment expression.

To model references, we introduce the Reference ADT:

Constructor: Ref(expressedValue)
Accessor:    content(Ref) --> expressedValue
Mutator:     setRef!(Ref, newVal)

;; Procedural implementation of the Ref ADT
(define make-ref
  (lambda (val)
    ;; A cell is an object which maintains its state in a closure
    ;; The methods of the object are invoked by passing the name
    ;; of the method to the closure.
    (lambda (msg)
      ;; Dispatch the message to the appropriate method
      (case msg
        ((content) val)
        ((setref!) (lambda (newval) (set! val newval)))
        (else      (error "Unknown method invoked on a reference"))))))

(define content
  (lambda (ref)
    (ref 'content)))

(define setRef!
  (lambda (ref newVal)
    ((ref 'setref!) newVal)))

<expr> ::= set! <var> = <expr>
       | begin { <expr> }*

With the corresponding abstract syntax:
(set-expr (var symbol?)
          (val expr?))
(begin-expr (seq (list-of expr?)))

In the code of the interpreter, we must systematically review all occurrences of apply-env and extend-env. The key point is to turn all denoted values to references. The code appears below:

(define eval-expr
  (lambda (e env)
    (cases expr e
      (lit (datum) (number datum))
      (prim-proc (prim-op) e)
      (varref (var) (content (apply-env env var)))  ;; apply-env returns a ref
      (if-exp (test then else)
        (let ((tv (eval-exp test env)))
          (if (true-val? tv)
              (eval-exp then env)
              (eval-exp else env))))
      (app (rator rands) 
        (let ((proc (eval-exp rator env))
              (args (eval-rands rands env)))
          (apply-proc proc args)))
      (let-exp (vars vals body)
        (let ((expvals (eval-rands vals env)))
          ;; Bind variables to references
          (eval-exp body
                    (extend-env vars (map make-ref expvals) env)))) 
      (proc (vars body)
        (closure vars body env))
      (begin-expr (seq)
        (map (lambda (e) (eval-expr e env)) seq))
      (set-expr (var val)
        (let ((ref (apply-env env var))
              (newVal (eval-expr val env)))
          (setRef! ref val)
          ;; Make sure we return an expressed value
          newVal)))))


(define (eval-rands rands env)
  (map (lambda (rand) (eval-exp rand env)) rands))

(define (apply-proc proc expvals)
  (cases proc
    (prim-proc (prim-op) (apply-prim-op prim-op expvals))
    (closure   (vars body c-env)
      (eval-exp body
                (extend-env vars
                            (map make-ref expvals)
                            c-env)))))

(define (apply-prim-op op args)
  (case prim-op
    ((+) (+ (car args) (cadr args)))
    ((-) (- (car args) (cadr args)))
    ((*) (* (car args) (cadr args)))
    ((/) (/ (car args) (cadr args)))))