SI413 Class 15: More on scope, lifetime & binding

Reading

Section 3.5 of Programming Language Pragmatics.

Homework

1. Draw the Central Reference Table after each call to function foo (e.g. right after the call is made and the CRT is updated, but before the code for foo actually stats executing) in the following code. Note that because foo is recursive there are 3 such calls:

   {
     new x := 10;
     new i := 5;
     new foo := lambda x { if (x = 1) { res := 3; } else { res := 3*foo(x-1); } };
     write foo(3);
   }
   

2. How is it possible (in some languages ) to have a variable whose scope is local to some function f but which does not die when the function returns? Is it possible in C? In Scheme?

Shallow vs. deep binding

It's a good idea top look at some examples of programs and see how our SPL interpreter from Lab 8/9 works. We might learn something. Here's a curious program:

SPL code	C-like (with nested functions)
{ new x := 0; new f := lambda p { new i := x; x := x + 1; if (i > 0) { res := p(0); } else { new g := lambda z { res := i; }; res := f(g); } }; write f(lambda y {res := 0;}); }	int x = 0; int f(int->int p) { int i = x; x = x + 1; if (i > 0) { return p(0); } else { int g(int y) { return i; } return f(g); } } int main() { int h(int z) { return 0; } print(f(h)); }

We have two questions: What should happen? What does happen? Essentially, the result i returned by function g can either refer to the i in the first call to f or the i in the second call to f. Our implementation follows the later, which is in keeping with our definition of dynamic scope. It's worth following our symbol table data structure (which is called a central reference table) through this computation to see how it enforces this scope.

Now, here's a slight variation:

{
  new t := 0;
  new x := 0;
  new i := -1;
  new g := lambda z { write i; };

  new f := lambda p 
           {
             new i := x;
             if (i > 0) 
             { 
               t := p(0); 
             }
             else 
             {
               x := x + 1;
               i := 3;
               t := f(g);             
             }
           };

  t := f(lambda y {res := 0;});
}
	  

The issue here is, perhaps, a bit clearer because we see three different i's that the "write i" might refer to:

1. the i that's in scope when the function g is defined,
2. the i that's in scope when the function g is bound to the parameter name p, and
3. the i that's in scope when the function g is actually called.

Our definitions of static and dynamic binding clearly give us option 1 for static binding, and option 3 for dynamic binding. Option 2 is referred to as "deep" binding, and our definition of dynamic binding is sometimes called "shallow" binding.

Binding with first-class functions

Recall that "first-class" objects in a language are those that can be passed as a parameter, returned from a function, or assigned to a variable (and I add created dynamically, which the book does not). "Second-class" objects may only be passed as parameters. You can't do any of those things with "third-class" objects. With functions as first-class objects, we've got some interesting possiblities.

Consider the following Scheme and SPL programs, which are pretty much direct translations of one another"

;;; Scheme code
(define f (lambda (x) 
	    (let ((g (lambda (y) (* x y))))
	      g)))
(define h (f 2))
(h 3)
	

# SPL Code
{
  new f := lambda x 
           {
	     new g := lambda y { res := x*y; };
             res := g;
           };

  new h := f(2);
  write h(3);
}
	

If you execute the Scheme code, you'll get 6, which is what you ought to expect. If you execute the SPL code, you get ... "Undefined variable x", which is probably not what you expected. What happened? Well, "x" is local to the function f, so under our SPL (and C/C++/Java/etc) semantics, "x" dies after f's execution is finished. However, the object returned by f is a function that refers to "x". When that function (saved in variable h) gets exectued, it looks for a variable "x" and ... it's not there. The problem here is that with first-class functions the lifetime (also called "extent") of our variables can't be tied to the simple stack regieme we use to implement function calls. All of the sudden, local variables have "unlimited extent" rather than "local extent".

Consider what this might mean in a statically (a.k.a. lexically) scoped language. We have the usual stack of function calls. Some function foo has local variable z, and foo returns a function that references z. Upon returning, the activation record for foo is popped off the stack. Later, the returned function is actually called, and it expects to find z! From an implementation perspective, this means that local variables (like z) cannot necessarily be stack-allocated, i.e. cannot necessarily be part of the function's activation record. Some will live on after the function call terminates, so these must be heap allocated. That has performance, as well ass complexity, implications.

C places a premium on performance, and is designed to avoid operations with hidden costs, so heap-allocated local variables would really be a problem given its design goals. So ... C does not allow nested functions, and this problem is avoided. Other languages avoid having to deal with heap-allocated locals by limiting the usage of non-local subroutines. Ada 95, for instance, allows nested subroutines to be returned from a function, but only if the scope in which the returned function was declared contains the scope of the variable or expression that is recieving the returned object. Thus, creating and returning a function, as in our example, is not allowed.

An aside to Scheme and closures

What our previous example shows (we hope!) is that when functions are first-class objects we have to take some pains to keep a function and the referencing environment in which it should be executed tied together. In that example, the "x" is not local to the function stored in h, but neither is it part of any active or future referencing environment ... it's only accessible when the function stored in h is executed. As many of these kinds of functions get created, we may have many "function + referencing-environments" to keep track of. The combination of a function and its referencing environment is called a closure.

To really see the effects of closures in Scheme it's time for me to come clean: Scheme is not a pure functional language. I just never told you about loops, modifying variables, and all the other non referentially-transparant facilities. So here's the biggie: set!. That's how you modify variable values. Here's a few examples. BTW: in the body of a let or a lambda you can include several expressions; they will be evaluated sequentially and the value of the let/lambda is simply the value of the last expression in the sequence.

> (define a 5)
> a
5
> (set! a 0)
> a
0
> (map (lambda (x) (set! a (+ a x)) x) '(1 2 3 4 5 6 7 8 9 10))
(1 2 3 4 5 6 7 8 9 10)
> a
55

So now you know, you've seen Scheme's dark-side. Anyway, with set! we can really put closures to good use ... in highly non-functional ways.

> (define (make-totaler val) (lambda (x) (set! val (+ val x)) val))
> (define A (make-totaler 100))
> (A 5)
105
> (A -20)
85
> (define B (make-totaler 0))
> (map B '(1 2 3 4 5 6 7 8 9 10))
(1 3 6 10 15 21 28 36 45 55)
> (B 0)
55
> (A 0)
85