November 1, 1999
You should have all picked up copies of a sample solution report for
the first project in section today or last Friday.
Under static scoping, if all function values are created at compile-time, then identifiers can be discarded at run-time, because each use of a name can be compiled into a stack offset.
Dynamic scoping requires keeping knowledge of names at runtime. Names refer to values in the most recently entered scope, which can only be known at runtime.
Sometimes dynamic scoping is convenient. The behavior of a function can be changed without recompiling, just by calling it from inside an environment where global identifiers have different bindings.
However the same behavior can be obtained with static scoping and assignment:
Dynamic scoping makes programs harder to understand. The example above shows that assignment commands also make programs harder to understand.var s = 10.0;
function scale (x: real): real;
begin
return x*s;
end;procedure update (v: vector);
begin
var l: integer := length(v);
s := norm(v);
for j := 1 to l do scale(v[i])
end;
The fundamental advantage of functional programming languages is that they are easier to understand, because they do not have the complexity of assignment commands.
If a program is easier to understand, it is also easier for a compiler to optimize.
For example the lifetime of s above is the execution of the whole program, while the local variable l has many lifetimes. Each lifetime of l is one execution of the body of update. Conceptually, update has new local variables at each call, which just happen to have the same name as previously existing variables.
Note that the executions of blocks are always strictly nested. They
can't overlap, so lifetimes can't overlap also.
The most common persistent variables are files. Pascal programs typically use what is called a persistent variable: the file named input.
Most languages have implementation-dependent restrictions on persistent variables. For example in Pascal a persistent variable must be of the type file of X for some component type X.
These limitations were to take account of implementation constraints,
but they are excessive. For example Pascal has no random-access files.
A variable with this behaviour is called a static variable in C, or called an own variable in Algol 60.
One important use for such a variable is to keep track of the seed used by a pseudo-random number generator:
Here, we do not want the variable seed to have a new lifetime each time prng is called, but we do want this variable to be visible only inside prng.function prng (): int;
static var seed : int = initialval;
begin
seed := update(seed);
return transform(seed);
end;
"Abstraction" is an abstract word with a down-to-earth meaning: it means leaving out irrelevant details. The opposite of "abstract" is "concrete", meaning with all details specified.
A type system is a tool for abstraction: aspects of exactly how the values of the type are represented are abstracted away, i.e. these aspects are omitted by the programmer and taken care of by the compiler.
A typical type definition introduces a new type concretely. This means that the set of legal values of the type is specified directly.
An abstract data type introduces a new type indirectly, by giving a set of operations that can produce and operate on a new set of values. The new set of values is characterized by specifying the relationships between the operations introduced.
Example: consider a data type to represent monetary amounts. No concrete datatype is really adequate:
all have weaknesses. The problem is that for all conceivable concrete representations, some error-checking and normalizing must be done whenever a value is created.type money = real;
type money = record dollars, cents: integer; end;
Normalizing a value means transforming it into some standard format.
E.g., normalizing a monetary amount means changing multiples of 100 cents
into dollars: $9.120 normalizes to $10.20.