Consider the following example:
let f = proc (x)
if x then (f -(x,1)) else 0
in (f 3)
Shouldn't this work? Try typing it into the interpreter from the last lecture and see for yourself that it doesn't.
The reason this doesn't work is that the expression
proc (x) if x then (f -(x,1)) else 0 is evaluated before the variable
f is created. This doesn't directly cause a problem when you define the function,
but consider what happens when you call the function f:
When we get to the recursive call to f, we look in the environment to see what
f is. It's not one of the formal parameters, so we look in the environment our current environment
is an extension of--i.e., the environment stored in the closure. But the environment stored in the closure is the
environment before the new environment for the let is created (the one containing f).
So, no f is found there!
This situation looks like this:
Remember, Scheme's own let expression works the same way and has
the same limitation. Scheme defines a letrec expression that has
to work a little harder to make recursion work.
The key to making recursion work is that the closures for recursive functions have to refer to the environment in which the function itself is defined. This recursive situation looks like this:
Let's implement our own version
of something like Scheme's letrec.
Here's the syntax we'll use to define recursive functions. Notice that we define the name, the formal parameters, and the body at the same time.
| The BNF for <expression> (with recursive functions) |
|---|
|
Again, the notation "{ ... }*(,)" means zero or more occurrences separated by commas.
For example,
letrec fact(x) = if zero?(x) then 1 else *(x,(fact sub1(x))) in (fact 6)
or
letrec
even(x) = if zero?(x) then 1 else (odd sub1(x))
odd(x) = if zero?(x) then 0 else (even sub1(x))
in (odd 13)
The abstract syntax record (variant of expression) returned when a letrec is parsed is
(letrec-exp (procnames (list-of symbol?)) (idss (list-of (list-of symbol?))) (bodies (list-of expression?)) (letrec-body expression?))
The key to making recursion work is to build the closures so that they store the
environment created by the letrec, not the preceding environment.
To do this, we'll have to use a slightly different form of environment. In particular,
let's assume we have a function in the environment handling code that looks like this:
(define extend-env-recursively
(lambda (proc-names idss bodies env)
...
))
Unlike the normal extend-env, to which you just pass variable names and values,
extend-env-recursively takes the unevaluated components that make up the procedure
definitions: the formal parameters for each function (the idss
list of lists) and the bodies for each of the functions (the bodies
list). It then builds the necessary closures and binds them to the newly created
environment. The result looks something like the second figure
above.
The new case in eval-expression for letrec-exp thus looks a lot like the one for let-exp, except that we use this new recursive-environment builder to build the new local environment:
(define eval-expression
(lambda (exp env)
(cases expression exp
(lit-exp (datum) datum)
(var-exp (id) (apply-env env id))
(primapp-exp (prim rands)
(let ((args (eval-rands rands env)))
(apply-primitive prim args)))
(if-exp (test-exp true-exp false-exp)
(if (true-value? (eval-expression test-exp env))
(eval-expression true-exp env)
(eval-expression false-exp env)))
(let-exp (ids rands body)
(let ((args (eval-rands rands env)))
(eval-expression body (extend-env ids args env))))
(proc-exp (ids body) (closure ids body env))
(app-exp (rator rands)
(let ((proc (eval-expression rator env))
(args (eval-rands rands env)))
(if (procval? proc)
(apply-procval proc args)
(eopl:error 'eval-expression
"Attempt to apply non-procedure ~s" proc))))
;; new case for letrec-exp
(letrec-exp (proc-names idss bodies letrec-body)
(eval-expression letrec-body
(extend-env-recursively proc-names idss bodies env)))
)))
The main change that we'll make to cause recursion to work is to implement this
new extend-env-recursively function. Your textbook describes a few ways
to do it, depending on how environments are implemented. There are two main variations
in these approaches, regardless of the data structures used:
We'll take this latter approach.
First, we'll build the environments using the implementation from Lecture 12 that used defined datatypes:
(define-datatype environment environment?
(empty-env-record)
(extended-env-record
(syms (list-of symbol?))
(vals vector?)
(env environment?)))
Notice one change from the implementation in Lecture 12: instead of storing the values (vals)
in a list, we'll use a vector for random access.
The apply-env function is the same as before (just using vector instead of list operations on vals):
(define apply-env
(lambda (env sym)
(cases environment env
(empty-env-record ()
(eopl:error 'empty-env "No binding for ~s" sym))
(extended-env-record (syms vals old-env)
(let ((pos (rib-find-position sym syms)))
(if (number? pos)
(vector-ref vals pos)
(apply-env old-env sym)))))))
The constructor for empty environments is the same:
(define empty-env
(lambda ()
(empty-env-record)))
When we extend an environment, the process is also the same--we create a
new extended-env-record:
(define extend-env
(lambda (syms vals env)
(extended-env-record syms (list->vector vals) env)))
These first three functions are the ones we implemented previously (slightly
modified to use a vector for the values (vals)).
Now, we need to implement the extend-env-recursively function:
(define extend-env-recursively
(lambda (proc-names idss bodies old-env)
(let ((len (length proc-names)))
(let ((vec (make-vector len)))
(let ((env (extended-env-record
proc-names vec old-env)))
(for-each
(lambda (pos ids body)
(vector-set! vec pos (closure ids body env)))
(iota len) idss bodies)
env)))))
Here is where we implement the main changes required to make recursion work.
We use the make-vector function to make a vector the same
length as the number of procedures we're defining (the proc-names
list), but we don't put anything in it just yet. We now build the
new environment (extended-env-record) and store it as a local variable.
We can now create the closures and store the new environment in them. After we do this,
we can use vector-set! to change the contents of the vals
vector to contain the new closures. Thus, the environment stores the closures, and
each closure stores a reference back to the environment--the essential component
in making recursive functions work.
Finally, a few helper functions used by these functions (you don't really need to know how these work):
Here are their implementations:
(define rib-find-position
(lambda (sym los)
(list-find-position sym los)))
(define list-find-position
(lambda (sym los)
(list-index (lambda (sym1) (eqv? sym1 sym)) los)))
(define list-index
(lambda (pred ls)
(cond
((null? ls) #f)
((pred (car ls)) 0)
(else (let ((list-index-r (list-index pred (cdr ls))))
(if (number? list-index-r)
(+ list-index-r 1)
#f))))))
(define iota
(lambda (end)
(let loop ((next 0))
(if (>= next end) '()
(cons next (loop (+ 1 next)))))))
The complete interpreter for Lecture 19.
Last updated at 9:23 am on Friday, July 15, 2005.