---

 Copyright 1994 Paul R. Wilson

You may use these notes freely for noncommercial purposes, as long as this
notice is preserved in all copies.

---

Scheme examples and explanations.

By the way, the illustrations of Scheme environments and closures below
are NOT in the preferred style---it was just easier to do it this way
to generate ASCII quickly.  When you draw environments and closures,
they should look more like the box-and-arrow style of earlier class
notes.

---

Scheme facts you should integrate into your worldview if you haven't yet:

  0. executing a LET creates one binding environment, and then executes
     the body code in that environment.  A let does not create closures.
     Of course, code in the body of a let can create environments
     or closures when it's executed.

      (let ((x 10))   ; this creates one binding environment and no closures
         (+ x x))   

      (lambda (x)     ; this creates one closure and NO binding environments
         (+ x x))     ; (although the closure could create environments
                      ; if called later).

      (let ((y 0))    ; this creates one binding environment and then
         (lambda (x)  ; one closure (which could create more environments
            (+ x x))) ; if it gets called).  The closure is the last (only)
                      ; value computed by the body of the let, so it is
                      ; returned as the value of the let.  The closure and
                      ; its environment look something like this, assuming
                      ; that the let was executed as a toplevel form (in a
                      ; toplevel environment):
                      ;
                      ;  [t-l-envt] <-- [y 0] <-- [closure]


      (lambda (y)     ; here one closure and NO environments are created
         (let (x)     ; y will not be bound until the closure is called
            (+ x x))) ; When it is called, it will bind y (because it's
                      ; an argument variable), then enter the let and
                      ; bind x (because the let is the body of the procedure).


     REMEMBER THAT CALLING A CLOSURE RESTORES THE ENVIRONMENT WHERE THE
     CLOSURE WAS CREATED.  THE ENVIRONMENT OF THE CALLER IS NOT USED!
     (If it's a non-tail call, the environment of the caller will be
     saved in a partial continuation.  If it's a tail call, the environment
     pointer of the caller (in the environment register) will simply be
     clobbered when the closure's environment is restored.)

     Now a sequence of things:

      (define foo                  ; this creates a variable and initializes it
              (lambda (z)          ; to hold the closure created by executing
                 (let ((y 10))     ; the lambda expression.  It DOES NOT
                    (lambda (x)    ; create any environments, and it only
                       (+ y z))))) ; creates ONE closure.  The LET and the
                                   ; inner LAMBDA do NOT create any
                                   ; environments at this point.

      (define bar (foo 22))   ; this calls the above closure, and uses
                              ; the result as the initial value of a
                              ; new variable BAR.  Calling foo creates
                              ; two binding environments and a closure:
                              ; first it binds the (argument) variable
                              ; z, intializing it with the actual argument
                              ; value 22.  Then it binds the let variable
                              ; y, then it executes the inner lambda of
                              ; foo to create a closure in that environent.
                              ; That closure is returned and used as the
                              ; initial value of BAR.

      (bar 3)                 ; this calls the closure created by the inner
                              ; lambda.  This creates one new environment
                              ; to bind the argument variable x and give
                              ; it the actual argument value 3.


  2. Environments are very different from continuations.

     The chain of continuations (hanging off of the continuation
     register) reflects the dynamic pattern of (non-tail) procedure
     calls.  For the most part, the chain of continuations acts
     a lot like the activation stack of a conventional language.
     One difference is that continuations are suspension records,
     i.e., the top continuation in the chain represents the state
     of the caller of the currently-executing procedure.  The
     currently-executing procedure's state is held in the registers.

     The chain of environments (hanging off of the current-environment
     registers) holds the bindings of currently VISIBLE variables,
     where visibility is determined by lexical scope rules.  It
     DOES NOT reflect the whole stack of dynamic procedure calls.
     (By the way, tail recursion has nothing to do with whether
     an environment is created at a procedure call.  If the procedure
     binds arguments, an environment will be created.  The tail
     call optimization stuff is about continuations, not binding
     environments.)

     At a given point in the execution of a program, the lexical
     scope chain contains two things:  the lexically visible
     variable of the currently-active procedure, and the lexically
     visible variables of the site where the currently active procedure
     was created.  When a closure is created, the environment at
     that moment (when the lambda is executed) is captured.  When
     the closure is executed, that environment is restored;  as
     the procedure executes, it may bind more variables.

     You should understand why this means that the dynamic depth
     of the lexical scope chain (at run time) is always exactly
     the same as the nesting of binding constructs in the source code.

     Consider the following example (assuming that all of the forms
     are executed at the top level, so evaluation starts out in a
     flat toplevel environment):

     (define quux
             (let ((a 1))
                (let ((b 2))
                   (lambda (c)
                      (let (d 4)
                         (+ (+ a b)
                            (+ c d)))))))

     When we define the variable quux, we first evaluate the outer let to
     compute the initial value.   The outer let binds a, then executes
     its body expression in that environment.  The body is itself a let,
     which binds b, scoped inside the environment that binds a.  Then
     it executes its body expression, the lambda.  The lambda creates
     a closure which pairs the environments we just created with a procedure.
     IT DOES NOT CREATE ANY ENVIRONMENTS---at this point, we have two
     environments and a closure, which is returned as the value of the
     lambda, then returned as the value of the second let, then returned
     as the value of the outer let and used to intialize quux.

     At this point, our closure and its environment look like this:

     [t-l-envt] <-- [ a 1 ] <-- [ b 2 ] <-- [closure]

     Now suppose we call quux and use the value to initialize a new
     variable, v1:

     (define v1 (quux 3))

     the call to quux restores the environment in which the lambda
     was executed---on entry into the procedure, the environment
     will be the one with bindings for a and (scoped inside that)
     for b.  In this environment, a new binding will be created
     for the argument variable c, which will receive the actual
     argument value 3.  In that environment, the body of the
     original lambda expression will be executed.  That body is
     just a let, which binds d and evaluates the expression
     (+ (+ a b) (+ c d)).  At this point, our environment looks
     like this:

     [t-l-envt] <-- [ a 1 ] <-- [ b 2 ] <-- [ c 3 ] <-- [ d 4 ] <-- curr-envt

     The values of a, b, c, and d are 1, 2, 3, and 4 at this point,
     so the result of the let and of the procedure is 10.

     Now suppose we define another variable, calling quux again
     to compute its initial value, but this time we hand quux
     the value 5.

     (define v2 (quux 5))

     On entry into quux, the environment of the orginal lambda
     expression is again restored, so again the environment consists
     of an environment binding b inside an environment binding a.
     (Those variables still have the original values they had when
     the lets were executed the first and only time.)

     [t-l-envt] <-- [ a 1 ] <-- [ b 2 ] <-- [closure]

     Now we bind the argument variable c again, this time giving
     it the value 5.  Then we enter the let and again bind d and
     give it the value 4.  Notice that unlike a and b, we have
     bound b and d again, because we are executing the procedure
     containing them again:

     [t-l-envt] <-- [ a 1 ] <-- [ b 2 ] <-- [ c 5 ] <-- [ d 4 ] <-- curr-envt

     Now we evaluate (+ (+ a b) (+ c d)) and this time we get 12. 

     Notice that however many times we call quux, it will always
     start out in an environment nested 3 deep (including the
     outer toplevel environment, and the 2 nested local environments).
     It will then bind c and d, so that when the addition is actually
     done the environment will be 5 lexical scopes deep.

     If we're just worried about scoping, a let and a lambda are pretty
     much equivalent---it's just that a let is executed immediately
     in the current scope and a lambda creates a closure that WILL
     BE executed in that scope.  Either way, however you get into
     the body, the runtime environment will have the same shape.

     Suppose we take our original expression and interchange the inner
     lambda with the enclosing let, and swap the names of the variables
     they bind, thus:

     (define quux
             (let ((a 1))
                (lambda (b)
                   (let ((c 3))
                      (let (d 4)
                         (+ (+ a b)
                            (+ c d)))))))

     At the point where we execute the arithmetic expressions, the
     environment will have the same structure as in the original
     expression:  nested environments binding a, b, c, and d.
     Multiple calls to this procedure will exhibit a different
     pattern of environment sharing, however.  In this case all
     calls to the closure created by the lambda will share
     one environment, binding a, which is captured when the
     closure is created defined and restored when it is called.
     Calls to the closure will restore this environment and then
     bind the argument b, and then the nested lets will bind c
     and d.


  4. Suppose we want a loop that will print out the integers 0 to 2,
     and we write it as a letrec that creates a tail-calling
     closure and tail-calls it:

     (letrec ((loop (lambda (i)
                 (if (<i 3)
                     (begin (display x)
                            (loop (+ i 1))))))
       (loop 0))

     Assume that this form is executed in a top-level scope.
     The letrec will create a binding for loop, scoped inside the
     top-level environment, and execute the lambda to create a closure
     that captures that environment.  After initializing the binding
     of loop, and before the call (loop 0), the environment looks
     like this:

           [ THIS PICTURE WILL BE DRAWN OR HANDED OUT IN CLASS...
             BUT YOU SHOLD BE ABLE TO FIGURE IT OUT ]

     When the iteration is started by the tail-call (loop 0),
     the closure's environment is restored (in this case, it happens
     not to change anything, because it's being called from the same
     environment).  Then the argument variable i is bound and initialized
     to 0.  The body of the lambda expression is executed, and ends
     by tail-calling loop again, passing 1 (i.e., (+ i 1)) as its
     argument.  On entry into the loop closure, the original environment
     (binding loop) is again restored.  Then the argument variable
     i is rebound.  This continues for another couple of iterations
     (tail calls), printing out the sequence 0, 1, 2.

     Notice that loop is bound exactly once, and that i is bound
     four times.  Each environment that binds i holds a pointer to
     the very same environment that binds the variable loop.
      

  5. The following points should be obvious by now, but if they're
     not, maybe they'll dispel some misconception:

     Calling a procedure always restores exactly the same environment
     as the one in which it was defined---not just one with the same
     shape, but the actual one that was the "current environment" at
     the moment a lambda was executed to create the closure.

     Entering a let inside a procedure always creates an environment
     with the same shape, each time.  That's because the procedure
     always starts executing in the same environment, and to reach
     the same point within the code of a procedure you always have
     to bind the same argument variables (if any) and enter the same
     lets, creating an environment with the same shape.  That's why
     the nesting of the runtime environments corresponds exactly
     to the nesting of binding constructs (lets and lambdas) in the
     source code.

     Closures always have pointers to environments they're created in,
     but the environments don't generally have pointers back to the
     closures---except, of course, that closures are first-class and
     you can make a variable binding in an environment point to
     a closure if you want to.  When we use a letrec to create an
     environment where a procedure can see its own name (e.g., to
     implement iteration by tail-calling), the fact that that the
     closure holds a pointer to its environment is simply because
     that's the way closures work.  The fact that the environment
     happens to hold a pointer back to the closure is a choice we
     made in writing the LETREC.

     Closures contain pointers to code, but not vice versa.  (In
     many implementations, including ours, closures actually contain
     pointers to templates, which contain literals as well as the
     actual pointer to the code.)