Definitions:
(1) A binding occurrence of an identifier is an appearance of
the identifier where its binding gets established.
(2) An applied occurrence of an identifier is an appearance
of the identifier where its binding gets used.
(3) The scope of (a binding occurrence of) an identifier is
the region of the program where applied occurrences refer back to this
binding occurrence.
Here's the example:
begin
const pi; real pi := 3.14159; real x := 0.0;procedure foobar(real z) is ...;
function tan(real x):real;
begin
real arg := x mod (2.0*pi);
return sin(arg)/cos(arg)
end;... foobar(x); ...
end;
(1) "pi" is bound to a constant real value. "x" is bound twice,
once to a real-valued variable, and once to a real-valued parameter.
(2) There are three environments involved here: the global environment which has bindings for "pi", "x", "foobar", and "tan", and two extended environments which also include a bindings for a parameter identifier.
(3) There are two related binding occurrences of "pi" and two unrelated binding occurrences of "x".
(4) There are two unrelated applied occurrences of "x".
(5) The scope of the binding occurrences of "pi" is the whole program.
The scope of the first binding occurrence of "x" is the main program body.
The scope of the second binding occurrence of "x" is the body of "tan".
Remember the definition: The "scope" of (a binding occurrence of) an identifier is the region of the program where applied occurrences refer back to this binding occurrence.
Under nested block-structured scoping, the essential rules are that: (1) the scope of a binding is the entire block in which the binding happens, (2) except a binding in an inner block hides a binding of the same identifier in an enclosing block.
Nested block-structured scoping says that free variables are understood
to refer to a syntactically-enclosing binding. Thus it is usually called
"static scoping".
Recursion among definitions can cause difficulties. Consider two types to keep track of the white and black squares on a chessboard:
Most languages have ad hoc syntax for coping with mutual recursion. For example in Pascal, procedures can have "forward" bodies, and in the type "pointer to X" the type X does not have to be already defined.type white = record
n1, n2, n3, n4: ^black;
end;
type black = record
n1, n2, n3, n4: ^white;
end;
Note the phrase "free variable" should really be "free identifier": a free variable may in fact be a constant or any other entity denoted by an identifier.
For example this function "scale" has one free variable, namely "s", and one non-free (bound) variable, namely the local variable "x":
"Alpha-conversion" is the rule that the meaning of a block is unchanged if the name of a bound variable is changed everywhere inside the block. Clearly alpha-conversion is a valid rule under static scoping.const s = 10.0;
function scale (x: real): real;
begin
return x*s;
end;
Static scoping says that the "s" local to "update" is irrelevant to the function "scale", so the vector v will be magnified tenfold, not normalized.procedure update (v: vector);
begin
var s := norm(v);
for j := 1 to length(v) do scale(v[i])
end;
"Dynamic scoping" is a different scoping discipline. It says that an applied occurrence refers to the binding occurrence in the most recently entered scope.
Under dynamic scoping, the function "update" would normalize a vector v.
Dynamic scoping violates alpha-conversion: if the name "s" in the "update"
procedure body was changed to "t", under dynamic scoping a different effect
is obtained.