Names, binding, lifetime and scope (static vs dynamic)

This section has two faces. The short-answer part: the binding time table and storage categories, memorize and done. The long part: program output under static and dynamic scope. This question is almost certain on the midterm and is solved by building a table.

Golden rules:

1. Static scope = look at the page. If a variable is not local, it is searched for in the unit enclosing where the function is written.
2. Dynamic scope = look at the invitation. If a variable is not local, it is searched for in the calling function, then in its caller.
3. If a nonlocal variable is assigned to, the variable you found changes. When you return to the caller you see the new value.
4. Scope ≠ lifetime. Visibility is about the text, lifetime is about the execution.

The six attributes of a variable

If two names access the same address, they are aliases. Pointers, references and unions in C create aliases. A reader may not notice that the value of a variable was changed through another name: reliability drops.

Binding and binding time

Binding is the association between an entity and an attribute: a variable and its type, a name and its address, a symbol and an operation. Binding time is the moment when this association is made.

Static binding happens before execution and does not change during execution. Dynamic binding happens during execution or can change.

Type binding

• Explicit declaration: int count;
• Implicit declaration: by a naming rule. In Fortran, a name starting with I-N is integer, the others real. In Perl, $ starts a scalar, @ an array.
• Type inference: the type is inferred from context. var sum = 0; in C#, almost everything in ML and Haskell.
• Dynamic type binding: the type is bound at assignment (Python, JavaScript, Ruby, PHP).

let t = 5;
t = "five";
console.log(typeof t);

string

Dynamic type binding gives flexibility (the same code works with different types) but the compiler cannot catch type errors, and run-time type checking is expensive; most of these languages are interpreted.

Lifetime and storage categories

Getting a cell is called allocation, giving it back is called deallocation. Lifetime is the time between the two.

PITFALL · a pointer and what it points to are in different categories. In the line int *p = malloc(sizeof(int));, p itself is stack-dynamic (a local variable), and the cell it points to is explicit heap-dynamic.

Scope and lifetime are not the same thing

void count() {
    static int calls = 0;
    calls++;
    printf("%d ", calls);
}
/* count(); count(); count(); */

1 2 3

The scope of calls is only the body of count, but its lifetime is the whole program: the value is kept between calls. The reverse also happens: when f calls g, f’s local variables are still alive but (under static scope) not visible from inside g.

Scope

If a variable is used in a statement and not declared in that unit, it is nonlocal. The scope rule determines where to look for it.

Static (lexical) scope

Look at the program text. First the local declarations, then the unit enclosing where the function is written (the static parent), then its parent (the static ancestors). Determined at compile time. C, Java, Python, JavaScript, Ada.

An inner declaration hides an outer variable with the same name. Blocks { ... } open their own scope:

{ var v = 1; { var v = 2; } console.log(v); }
{ let w = 1; { let w = 2; } console.log(w); }

2
1

In JavaScript, var does not recognize block scope, let does. In Java and C#, an inner block cannot redeclare the name of a local variable in the same method (compile error: variable x is already defined); in C and C++ it can, and it hides the outer one.

Dynamic scope

Look at the call chain. First the local, then the function that called me, then the one that called it… Determined at run time. Early LISP, APL, SNOBOL4 and Perl’s local declaration.

The criticism: a function’s local variables are exposed to every function it calls (reliability drops), what a nonlocal reference refers to depends on the call path (readability drops), static type checking is not possible, and access is slow. The only advantage: the caller’s variables can be used without passing parameters.

Worked example: a trace table

int n = 1;
void a() { n = n * 10; print(n); }
void b() { int n = 2; a(); }
void c() { int n = 3; b(); a(); print(n); }
main() { c(); print(n); }

The n in a is nonlocal. Trace the two rules separately:

STATIC: a's static parent is global → the n in a is always the global n
event         global n   c.n   b.n   output
c → b → a     1 → 10     3     2     10
c → a         10 → 100   3           100
c: print(n)              3           3
main          100                    100

DYNAMIC: no n in a → look at the caller
event         n searched, where found    new value   output
c → b → a     b.n (2)                    20          20
c → a         c.n (3)                    30          30
c: print(n)   c's own n                  30          30
main          global n (untouched)       1           1

Static: 10 100 3 100. Dynamic: 20 30 30 1. These two outputs can be reproduced exactly in Perl by using local instead of my.

PITFALL · looking at the definition in dynamic scope. In dynamic scope where the function is written is irrelevant; the only question is “who called me right now?” And the nearest caller wins: in the chain main → c → b → a, b’s n is found before c’s.

Referencing environment

The referencing environment of a statement is all the names visible there. Under static scope: the locals + the unhidden static ancestor variables. Under dynamic scope: the locals + the unhidden variables of all active callers.

function main() { var a, b, c;
  function sub1() { var b, d;
    function sub2() { var c, e; /* point 2 */ } }
  function sub3() { var a, d; /* point 3 */ } }

point 2: c, e (sub2) · b, d (sub1) · a (main)
point 3: a, d (sub3) · b, c (main)      sub1's variables are NOT there

Common mistakes

int x = 5;
void f() { print(x); }
void g() { int x = 7; f(); }
main() { g(); f(); }

int n = 1;
void a() { n = n * 10; print(n); }
void b() { int n = 2; a(); }
void c() { int n = 3; b(); a(); print(n); }
main() { c(); print(n); }

function main() {
  var a = 1, b = 10;
  function p() { a = a + b; print(a, b); }
  function q() { var b = 20; p(); r(); }
  function r() { var a = 100; p(); print(a); }
  q();
  print(a, b);
}

function main() {
  var a, b, c;
  function sub1() {
    var b, d;
    function sub2() {
      var c, e;
      /* point 2 */
    }
  }
  function sub3() {
    var a, d;
    /* point 3 */
  }
}

void count() {
    static int calls = 0;
    calls++;
    printf("%d ", calls);
}

public static void main(String[] args) {
    int x = 1;
    { int x = 2; System.out.println(x); }
}

{ var v = 1; { var v = 2; } console.log(v); }
{ let w = 1; { let w = 2; } console.log(w); }

let t = 5;
t = "five";
console.log(typeof t);