SI413 Class 14: Nested Scopes, Declaration Order

Reading

Section 3.3 of Programming Language Pragmatics

Homework

P. 132, Questions 12, 15, 18, 20 of Section 3.3.3.

Nested scopes

Consider the following fragment of code, in a Java/C++-ish language:

int t = 0;
int a, b;
read a;
read b;
if (a > b)
{
  int t = a;
  a = b;
  b = t;
}
	

The then-block of the if is an example of a "nested scope": nested inside whatever scope this chunk comes from. The variable t in the outer scope is not visible in the inner scope because it is masked by the "new" t. That original t varible is said to have a hole it its scope. In C++, the "scope-resoution operator" :: allows you to refer to the global binding of a name, even when it's hidden by a local variable. So ::x refers to the global variable x.

Nested function definition

Many languages allow nested function definitions. This is handy, but it makes for more scope issues. Let's consider an example, where we'll assume lexical scoping:

void foo(int p, int n)
{
  int inv(int x)
  {
    int g,s,t;
    egcd(x,p,&g,&s,&t);
    if (s < 0) { s = s + p; }
    return s;
  }

  int sum() 
  {
    int t = 0;
    for(int i = 2; i ≤ n; ++i)
      t = (t + inv(i)) % p;
    return (1 + t) % p;
  }

  int H = sum();
  •
  •
  •  
}

Notice that inv and sum are defined inside the body of foo. That means that variables local to foo, like p and n, ought to be in scope for inv and sum, as is reflected in the code. We do have to think a bit about what this should mean, though. During the call foo(7,20), if we call sum() then the p and n referred to in sum should be 7 and 20, respectively. During that call to sum, calls to inv(i) are made, and inside those calls p and n should still be referring to 7 and 20. If foo is recursive, we may have many calls to foo on the stack, each with their own p's and n's. How do we handle this?

The following theorem (which I won't prove) tells us something about this:

Theorem: Assuming a lexically scoped language: If function g is visible to function f, i.e. can be called inside f, then either

1. the body of the function f is the scope of the name g, or
2. the name g is visible in the scope of the name f.

In the context we've outlined, scope-nestings form a tree structure, and the only visible names at node N are those that appear the nodes along a path from the root node (global scope) down to N.

Now let's say function g has been called from function f, and g references a non-local name "bar". What do we do? Let's assume functions are not first class objects, and that the only name that refers to a given function is the name given to it at its point of definition. That means that what was in scope when the name g was defined is the same as what was in scope when the body of g was defined. Moreover, if non-global variable x is in scope, the function in whose body x is declared must be active or on hold lower down on the stack. If we're in case one of the theorem, we simply look for the value of "bar" in the call of function f from whence this call to g came. If we're in case two of the theorem, we look for the value of "bar" in the call of the function from whence came the call to f from whence came this call to g. A picture is easier to look at: ADD PICTURE.

Declaration order

Our scoping questions are not finished with yet! In C a name's scope starts from the point of its declaration. Thus, names must be declared before they are used. In C++ and Java this is true for locals (in C++ for globals as well). This is decidedly not true for scheme! At any rate, it causes some problems. What about this familiar-ish code:

void exp() { atom(); etail(); }
•
•
•
void atom() {
  switch(peek()) {
  case  LP: match(LP); exp(); match(RP); break;
  case  ID: match(ID); break;
  case NUM: match(NUM); break; 
  default:  exit(1); // parse error!
  }
}

Since exp calls atom and the name atom hasn't been declared, we've violated our declare-before-use rule. On the other hand, if we reverse the our definitions we'll still violate the rule, because atom() calls exp(). Mutually recursive functions like this are useful, so what do we do?

One solution is to define the scope of a name to be the whole block containing the declaration. Thus, in the above, "atom" would be in scope when it is called in exp(), even though it hasn't been declared yet. Pascal works that way, as does C#. In fact, the book gives this nice example:

// From page 122 of Programming Language Pragmatics
class A {
  const int N = 10;
  void foo() {
    const int M = N;
    const int N = 20;
•
•
•

Surprisingly, this gives an error: N is used before it is declared. Why, because the inner N's scope is the whole block!

In C/C++ the problem, i.e. how do we handle mutual recursion given the declare-before-use rule, is solved by "forward declarations". We can decouple declarations from definitions, and so declare a function before we actually give its definition, e.g.:

void atom(); // This is a *declaration*, not a definition

void exp() { atom(); etail(); }
•
•
•
void atom() {
  switch(peek()) {
  case  LP: match(LP); exp(); match(RP); break;
  case  ID: match(ID); break;
  case NUM: match(NUM); break; 
  default:  exit(1); // parse error!
  }
}

It should be noted that inside class definitions, both C++ and Java dispense with declare-before-use. So the following is OK:

class Foo {
public:
  void exp() { atom(); etail(); }
  •
  •
  •
  void atom() {
    switch(peek()) {
    case  LP: match(LP); exp(); match(RP); break;
    case  ID: match(ID); break;
    case NUM: match(NUM); break; 
    default:  exit(1); // parse error!
    }
  }
};