SI413 Class 17: Closures and lexical scope

Reading

The Structure and Interpretation of Computer Programs, Section 3.2.

Homework

1. Draw a picture showing all the frames and closures that get created when the following code is executed, along with the variables etc. inside them. Draw each closure as an oval and be sure to show both parts of it. Draw each frame as a rectangle and be sure to show its parent frame, if any. Finally, label each frame with the function call (including the arguments) that created it.

   new mkcd := lambda a 
               { 
                 res := lambda x 
                        { 
                          if (a < x) { res := true; } { a := a - x; res := false; }
                        };
               };
   new A := mkcd(10);
   new B := mkcd(12);
   write A(11);
   write B(11);
   

Recalling Closures

Remember closures from last class? A closure is a function plus a referencing environment. As we showed last class, when functions are first-class objects, closures become important. When functions aren't first-class objects, the referencing environment for a given function invokation is pretty simple: it's the function's local variables plus the referencing environment for some function further down the call stack. When functions are first-class objects, however, they may inherit part of their referencing environment from a function that's finished executing --- i.e. no longer "on the stack". This is what we saw last class.

Closures vs. local data

You might be tempted to say: "Fine, why don't we just take the non-local variable references in a closure and, when the referenced variable goes out of scope simply make it a new local variable in the function?" Unfortunately, consistent semantics don't allow us to do that:

> (define L (let ((a 0)) 
               (list (lambda (x) (+ a x)) 
                     (lambda (x) (* a x))
                     (lambda (x) (set! a (+ a x))))))
> ((car L) 5)
5
> ((cadr L) 5)
0
> ((caddr L) 5)
> ((car L) 5)
10
> ((cadr L) 5)
25

Do you see what's happening here? The three functions in the list L all share the variable a. So long after the let is done executing, we have three distinct functions all referencing the same object via a. Thus there's no way to make a "local" to any one of the functions, because when one of them changes a, the change must be reflected in all of them.

The power of closures

You may be tempted to look at closures as a pain in the neck. You may see them as nothing more than a complicating factor in our scope and binding discussion. However, closures are pretty useful things! For starters, they give a natural way to implement objects in the OOP sense. The idea is that data-members are closure variables so they are persistent (do you understand the term "persistent" in the computing context?) and the calls of the functions are "messages" to the object. You can implement traditional data structures this way too. See Scheme Lab 08 for examples. I'll show you a stack in class.

Implementing lexical scoping with first-class functions

So how can we implement lexical scoping with first-class functions? There's a nice discussion in The Structure and Interpretation of Computer Programs (full text online), which is based around Scheme, and written by the authors of Scheme, of how to do this. They propose the idea of lexical frames that represent referencing environment. When a function gets called, it's parameters and locals are represented in a new "frame" ... kind of like a little symbol table. When a function gets created it inherits the frame of its parent environment, i.e. the referencing environment that was active when the definition was evaluated. A frame contains a link to its "parent" frame, which is how non-local variable references are resolved. Recall our definition of lexical scope: "non-local references refer to the bindings that were active at the point of the function's definition". This plan respects that rule!

Here's a simple example program to walk through. We're going to use SPL but imagine it as statically/lexically scoped, and we'll go through how an implementation using frames might work.

new x := 3;
new y := 5;
new f := lambda x { res := x*y; };
write f(5);
write f(2*x);
	

I've annotated the abstract syntax tree with some hypothetical addresses for various nodes to faciliate the discussion.

In class, of course, we actually drew the frames and closures and talked about the calls to eval. Now, by the way, eval takes two arguements: a pointer to a node in an Abstract Syntax Tree, and the referencing environment to be used, which is simply a pointer to a Frame.

In this example the problem that brought us to this point --- lexical scoping with first-class functions --- doesn't crop up. We don't have any functions-returning-functions here. So ...

Consider this slightly more complicated example, in which function mkf returns a function.

new x := 3;
new z := 5;
new mkf := lambda y { res := lambda x { res := x*y; }; };
new f := mkf(z);
write f(2*x);

I've annotated the abstract syntax tree with some hypothetical addresses for various nodes to faciliate the discussion.