CSE 341 -- Static and Dynamic Scoping (Extra Topics)

These are some supplemental notes regarding procedures as parameters -- you won't be responsible for this material on the final.

Nested Procedures and Recursion

Nesting procedures inside of other procedures interacts in interesting ways with recursion:

begin
integer global, n;

procedure laurel(n: integer);
   begin
   procedure hardy;
        begin
        print(global);
        print(n);
   end;

   if n<4 then laurel(n+1);
          else hardy;
end;

global := 99;
n := 100;
laurel(1);
end;

Here the output is:

99
4

Scheme example:

(define global 99)
(define n 100)

(define (laurel n)
  (define (hardy)
    (display global)
    (newline)
    (display n)
    (newline))
  (if (< n 4) (laurel (+ n 1))
      (hardy)))

(laurel 1)

Note that when we finally call hardy, there are 5 different n's on the stack: the global one (with value 100), then 4 different invocations of laurel (with n=1, n=2, n=3, and n=4).

Again, this prints

99
4

Procedures as Parameters

In Algol, Pascal, and Scheme, you can pass procedures or functions as parameters. To pass a procedure as a parameter, the system passes a closure: a reference to the procedure body along with a pointer to the environment of definition of the procedure.

In Algol and Pascal, we can only pass procedures in as parameters -- we can't return a procedure or a function as a value from another function. We can do this in Scheme, however -- it means that Scheme can't always use a stack for storage allocation for local variables.

Here's an example of passing a function as a parameter in Scheme, in which we capture a local variable:

(define n 100)

(define (laurel n f)
  (define (hardy)
    (* n n))
  (cond ((= n 5) (laurel (+ n 1) hardy))
        ((< n 10) (laurel (+ n 1) f))
        (else (f))))

(laurel 1 (lambda () "whatever"))

The last expression evaluates to 25!

There isn't anything about this example that is peculiar to Scheme -- here is an equivalent function in Miranda:

n = 100

laurel n f = laurel (n+1) hardy, if n=5
           = laurel (n+1) f, if n<10
           = f, otherwise
             where hardy = n*n

If we evaluate laurel 1 1000, we get 25 again.