CSE 341 -- Static and Dynamic Scoping

Scope rules define the visibility rules for names in a programming language. What if you have references to a variable named k in different parts of the program? Do these refer to the same variable or to different ones?

Most languages, including Algol, Ada, C, Pascal, Scheme, and Miranda, are statically scoped. A block defines a new scope. Variables can be declared in that scope, and aren't visible from the outside. However, variables outside the scope -- in enclosing scopes -- are visible unless they are overridden. In Algol, Pascal, Miranda, and Scheme (but not C or Ada) these scope rules also apply to the names of functions and procedures.

Static scoping is also sometimes called lexical scoping.

Simple Static Scoping Example


    begin
    integer m, n;

    procedure hardy;
        begin
        print("in hardy -- n = ", n);
        end;

    procedure laurel(n: integer);
        begin
        print("in laurel -- m = ", m);
        print("in laurel -- n = ", n);
        hardy;
        end;

    m := 50;
    n := 100;
    print("in main program -- n = ", n);
    laurel(1);
    hardy;
    end;

The output is:

in main program -- n = 100
in laurel -- m = 50
in laurel -- n = 1
in hardy -- n = 100    /* note that here hardy is called from laurel */
in hardy -- n = 100    /* here hardy is called from the main program */

Blocks can be nested an arbitrary number of levels deep.

Dynamic Scoping

Dynamic scoping was used in early dialects of Lisp, and some older interpreted languages such as SNOBOL and APL. It is available as an option in Common Lisp. Using this scoping rule, we first look for a local definition of a variable. If it isn't found, we look up the calling stack for a definition. (See Lisp book.) If dynamic scoping were used, the output would be:

in main program -- n = 100
in laurel -- m = 50
in laurel -- n = 1
in hardy -- n = 1    ;; NOTE DIFFERENCE -- here hardy is called from laurel 
in hardy -- n = 100  ;; here hardy is called from the main program

Scopes and Procedures

In Algol, Pascal, Simula, and other languages in the Algol family, you can also nest procedure and function declarations inside of other procedure and function declarations. The same static scope rules apply. (You can't do this in Ada or C though.)

    begin
    integer m, n;


    procedure laurel(n: integer);
        begin
	procedure hardy;
	    begin
	    print("in hardy -- n = ", n);
	    end;

        print("in laurel -- m = ", m);
        print("in laurel -- n = ", n);
        hardy;
        end;

    m := 50;
    n := 100;
    print("in main program -- n = ", n);
    laurel(1);
    /* we can't call hardy here, since the name isn't visible */
    end;

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

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).

Procedures as Parameters

In Algol, Pascal, Scheme, and Miranda, 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.

  begin

  procedure test(n: integer, p: procedure);
  begin

    procedure rose;
    begin
      print("in procedure rose -- n="); print(n);
    end;

    print("in procedure test -- n="); print(n);
    p;
    if n<10 then
      begin
        if n=3 then test(n+1,rose) else test(n+1,p)
      end
  end;

  procedure violet;
  begin
    print("in procedure violet"); 
  end;


test(1,violet);

end;

Output:

in procedure test -- n=1
in procedure violet

in procedure test -- n=2
in procedure violet

in procedure test -- n=3
in procedure violet

in procedure test -- n=4
in procedure rose -- n=3

in procedure test -- n=5
in procedure rose -- n=3

in procedure test -- n=6
in procedure rose -- n=3

in procedure test -- n=7
in procedure rose -- n=3

in procedure test -- n=8
in procedure rose -- n=3

in procedure test -- n=9
in procedure rose -- n=3

in procedure test -- n=10
in procedure rose -- n=3

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 and Miranda, however -- it means that Scheme and Miranda can't always use a stack for storage allocation for local variables.

Blocks in Smalltalk also are lexically scoped, and include their environment of definition. Blocks can be returned from methods, assigned to global variables, and so forth -- so that storage for local variables can't always be allocated on a stack in Smalltalk either.

Example:

| a sum |
a := Array new: 3.
a at: 1 put: 10.  a at: 2 put: 20.  a at: 3 put: 30.
sum := 0.
a do: [:n | sum := sum+n].

More complicated example: suppose we evaluate the following Smalltalk code.

| k |
B1 := [k].
B2 := [:n | k := n+2].
k := 100.

After we do this, the two global variables B1 and B2 are bound to blocks. The local variable k is no longer visible, but is still accessible and is shared by the two blocks. So B1 value will return 100. If we evaluate B2 value: 5, this will assign 7 to k. After that evaluating B1 value will return 7.