Large complex programs need more from an underlying language than expressions, declarations, and commands. Blocks, abstracts, and modules provide support for qualification, abstraction, and modularity, respectively.
The scope of a declaration, scope(dec), is the region of a program where the binding created by the declaration is valid. The visibility of a declaration, visibility(dec), is the region of a program where the binding created by the declaration can be accessed. The visibility of a declaration, is a sub-region of the scope. Often, visibility(dec) and scope(dec) coincide.
The extent or lifetime of a declaration, extent(dec), is the period of time that the binding created by the declaration is valid.
Qualification is the ability to limit the scope and/or extent of a declaration to the region of the program where the binding created by the declaration is needed. For example, a Java class member (field or method) can have public (global), protected, package, or private scope.
As a general rule, scopes should be as small as possible. Without qualification, a binding has global or program scope, which means it's is visible throughout the entire program. This increases the risk of unintended modification. Also, most languages prohibit multiple declarations of the same name with the same scope, which means programmers must be careful to use unique names.
Blocks allow us to limit the scope of a declaration to a single phrase.
A programming language satisfies the Qualification Principle if every type of phrase can be surrounded by a block. Delta satisfies the Qualification Principle:
<Expression> ::= <ExpBlock> | etc.
<Command> ::= <CmmdBlock> | etc.
<Declaration> ::= <DecBlock> | etc.
A block consists of a sequence of local declarations followed by a phrase:
<ExpBlock> ::= (<Let> [<Dec>+]
<Expression>)
<CmmdBlock> ::= {<Let> [<Dec>+] <Command>}
<DecBlock> ::= [<Let> [<Dec>+] <Declaration>]
Recall from Gamma:
<Dec> ::= [(const | var) <Symbol> <Expression>]
There are three types of blocks: collateral, sequential, and recursive:
<Let> ::= let | letseq | letrec
The scope of a local declaration ends at the end of the block in which it occurs. For example, assume a global variable, x, is declared:
-> [var x 10]
done
We can re-declare x in a block:
-> (+ x (let [[var x 5] [var y 2]] (+ x y)))
17 // = (+ 10 (+ 5 2))
Of course the bindings x = 5 and y = 2 are only temporary. In other words, the extent of these bindings is from the moment the local declarations are elaborated until the moment control exits the block. As soon as control exits the block, the binding x = 10 becomes visible. Inside the block, the binding x = 10 is still valid, but it is shadowed by the binding x = 5.
-> x
10
Things can get complicated. For example:
-> (let [[var x 5]
[var y (let [[var x 20] [var
y 30]] (+ x y))]]
(+ x y))
55 // = (+ 5 (+ 20 30))
The scope of a local declaration ends when the block ends, but where does it begin? That depends on the type of block:
let = collateral block = scope begins after declarations
letseq = sequential block = scope begins after declaration
letrec = recursive block = scope begins at start of declarations
For example:
-> (let [[var z x] [var x 5] [var y x]] (+ z x y))
25 // = (+ 10 5 10)
-> (letseq [[var z x] [var x 5] [var y x]] (+ z x y))
20 // = (+ 10 5 5)
-> (letrec [[var z x] [var x 5] [var y x]] (+ z x y))
15 // = (+ 5 5 5)
Of course we can invent similar examples using declaration and command blocks.
The declaration block:
[let [[var x 10] [var y 20]] [var z (+ x y)]]
is equivalent to the simple declaration:
[var z (let [[var x 10] [var y 20]] (+ x y))]
Generally, a binding comes into existence at the point of declaration and goes out of existence when control exits the block.
If the binding disappears while still in scope, then a dangling reference error may occur.
Some languages allow programmers to declare a binding with limited scope but a global lifetime. Such variables only disappear when the program ends.
This is accomplished in C using the "static" label:
int callCount() {
static int numCalls = 0; /* local
scope, global extent */
return ++numCalls;
}
C, C++, and Java allow programmers to create mixed sequential command blocks:
<Command> ::= { <Phrase> (; <Phrase>)* } | etc.
A command block may appear in any context where a single command is expected. They are also used as the bodies of functions and methods. These blocks are mixed because they can contain a mixture of declarations, commands, and expressions.
There are some subtle differences between C, C++, and Java. For example, C demands that all declarations occur at the beginning of a block. Also, the scope of a local declaration includes itself. So for example, the following is legal, but meaningless:
{ int x = x; etc }
In Java local variables are not allowed to shadow parameters or other local variables, but they are allowed to shadow fields. For example:
class Demo {
int x = 10, y = 20;
int always18() {
int x = 5;
{
int y = 3; // int x illegal
here
return x + y + this.x; // =
18 = 5 + 3 + 10
}
}
}
Scheme permits collateral, sequential, and recursive expression blocks:
-> (define x 10)
ok
-> (let ((z x) (x 5) (y x)) (+ z x y))
25
-> (let* ((z x) (x 5) (y x)) (+ z x y))
20
-> (letrec ((z x) (x 5) (y x)) (+ z x y))
15
Adding blocks to a language forces us to abandon our simple model of the environment as a single frame (symbol table). Instead, the environment must be a stack of frames. Global bindings are stored in the bottom-most frame.
When a symbol is evaluated, each frame on the stack must be searched from top to bottom until a binding is found.
When a block is entered, a new frame is created. The bindings created by elaborating the local declarations are stored in this frame. For sequential and recursive blocks the frame is pushed on the stack before the local declarations are elaborated. For collateral declarations the frame is pushed on the stack after the local declarations are elaborated.
When control exits the block, the frame is popped off of the stack.