(define rec-extend
  (lambda (M env)
    (local 
       [(define var (rec-let-lhs M))
        (define rhs (rec-let-rhs M))
	(define renv (extend env var (void)))]
      ; (void) is a dummy value for var
      ; Is renv the appropriate environment yet?  No.
      (set-first-pair-val! renv (MEval rhs renv)))))

(define set-first-pair-val!
  (lambda (env val)
     (local
        [(define first-pair (first env))]
       (set-pair-val! first-pair val))))

   [(void? M) (error 'MEval 
                 "variable referenced before definition in rec-let")]

Exercise Generalize the code from the previous exercise to allow an arbitrary expression as the right hand side of a rec-let. Hint: it is much simpler than the code above.

Detour: Finding Fixed-Points

Say we have functions from R to R (where R denotes the set of real numbers. We might have a function like

f(x) = 2x + 1

Does every function from R to R have a fixed-point? No: consider g(x) = x + 1. Substituting x and reducing, we get 0 = 1, which is a contradiction. On the other hand, h(x) = x has an infinite number of solutions. Hence, a function from R to R could have zero, one, several, or an infinite number of fixed-points. However, we will show that for every function from environments to environments, we can construct a fixed-point.

We can use fixed-points to assign a mathematical meaning to any recursive definition expressed in a computational framework. For example, we can assign a mathematical meaning to any recursive definition of a function in terms of already defined functions.

Consider the equation

fact(n) = if zero?(n) then 1 else n * fact(n - 1)

fact

fact = map n to if zero?(n) then 1 else n * fact(n - 1)

FACT(f) = map n to if zero?(n) then 1 else n * f(n - 1)

How do we find the fixed-point of such an equation? We interpret F as an inductive definition of the graph of the partial function fix(F).

A partial function mapping N to N is any a subset G of N x N such that (a,b) in G and (a,c) in G imply that b = c. A (total) function mapping N to N is a partial function F such that for every a in N, there exists b such that (a,b) in F. Computed functions correspond to partial functions rather than total functions because they may diverge on some inputs.

We use the term graph of a function to indicate that we are interpreting the function simply as a set of ordered pairs.

Let us restate the definition of the fixed-point fact of FACT as an inductive definition of the graph of a function.

Given a, b in N, the pair (a,b) belongs to the graph of fact iff either:

We just showed how the recursive definition of factorial could be interpreted as an inductive definition of its graph. It is suggestive of a more general construction that enables us to build the least fixed-point of a computable function F mapping Pow(NxN) (graphs of functions on N) into Pow(NxN). By repeatedly applying the function F to the empty set we can build the least fixed point of F. The fixed-point f of F is

Union {Fk(empty) | k = 0,1,...}

Consider the FACT example above.

FACT1(empty) = {(0,1)}
FACT2(empty) = {(0,1), (1,1)}
FACT3(empty) = {(0,1), (1,1), (2,2)}
...
FACTN+1(empty) = {(0,1), (1,1), (2,2), ..., (N,N!)}
...

Any recursive definition of a function from N to N can be interpreted in this way. How do we apply this idea to solving our recursion equation over environments? If we represent envivronments as functions, then exactly the same technique works. The only difference is that the function FENV maps environments to environments instead of N to N.

If environments are represented some other way, then the representation must permit us to find a non-empty least fixed-point for FENV. Otherwise, the representation is incorrect.

Consider the function FADD on sets of N defined by

FADD(S) = {s+1 | s in S}

x = x + 1

bottom = bottom + 1

Memory Management, Part 0

At this point in the course, we have explained several language constructs, such as procedures and applications, in terms of their Scheme counterparts. A notable exception is environments, which we have represented explicitly. Indeed, since we explicitly manage variable-value associations in our interpreters, we can analyze some of the lower-level behavior of the language such as its memory management.

Consider the evaluation of

(let (x 1)
  (let (y 2)
    (let (z 3)
      ...)))

Consider this expression:

((lambda (x) (lambda (y) (y x))) 10)

((lambda (z) (lambda (w) (+ z w))) 20)

We begin with the empty environment; the first application is performed and the environment is extended with the binding [x = 10]. The closure is now created, and the environment is emptied. Then we evaluate the second expression, which adds the binding [z = 20]. The second closure (call it C2) is produced, and the environment is emptied again.

At this point, we are ready to perform the desired application. When we do, the environment has the bindings [x = 10] and [y = C2]. Now C2 is applied, which has the effect of replacing the current environment with its own, which contains the bindings [z = 20]. The application adds the binding [w = 10], at which point the addition is performed, 30 is returned, and the environment is emptied again.

The moral of this example is that environments for LC programs, no matter how we choose to represent them, branch out like trees, and a simple stack discipline is insufficient for maintaining them. In many programming languages (such as Fortran, Pascal, and C/C++), it is often the programmer's job to manage memory and the collection of environments in existence at any point in the program must be representable by a stack. Such languages prohibit language constructions that can create a collection of environments that cannot represented by a stack. In our interpreters for LC, we have left the task of managing the storage for LC environments to Scheme's run-time system. Otherwise, our interpreters would have been much more complex programs.