Advanced Methods in Programming Languages (201-2-4411-01)
Notes Week 4 - Michael Elhadad
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?)
An example program in L4 is:
letrec fact(x) = if zero?(x) then 1 else *(x, fact(sub1(x))) in
fact(6)
The computation rule for letrec
expressions is:
(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)))
...)))
The new procedure extend-env-recursively
completes the env
ADT interface as follows:
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)
If we use a procedural implementation of environments, the definition of
extend-env-recursively
uses letrec
:
(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)))
If we use the record-based implementation of environments, then the
definition does not make letrec appear directly:
(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)))))))
Note that this implementation does not use letrec. Instead it relies
on a form of assignment (in the record field). Actually, for a single
variable, if we allow assignment (as will be discussed below in L5),
we can rewrite letrec as a let expression as follows:
(letrec ((p (lambda (x) ...(p y) ...)))
body)
rewrites to:
(let ((p '*))
(begin
(set! p (lambda (x) ... (p y) ...))
body))
(This transformation is not correct in the case of several bindings in
the letrec body -- therefore, in Scheme, letrec is not a syntactic variant
of let.)
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
We now introduce assignment in the object language. Variables must now denote
the address of mutable locations in memory. This means the domain of Denoted Values
must be modified -- it cannot be the same as expressed values anymore. We start with
the following domain structure:
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)
The reference ADT can be implemented in Scheme using the "closure as objects"
style used in PPL (for example read Section 3.3.2 of Abelson and Sussman
"Representing Queues").
;; 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)))
The new syntax we introduce in L5 is the following:
<expr> ::= set! <var> = <expr>
| begin { <expr> }*
With the corresponding abstract syntax:
(set-expr (var symbol?)
(val expr?))
(begin-expr (seq (list-of expr?)))
Note that set! is the first construct in the language which has a side-effect.
Before we introduced side-effects, there was no point in introducing begin
as well.
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)))))
Last modified Mar 17, 2003
Michael Elhadad