CSE 130 Lecture Notes, April 24, 2002

CSE130 LECTURE NOTES

April 24, 2002

ADMINISTRATION

We'll be handing back the first assignments on Friday or Monday.

SYNTAX FOR DECLARATIONS

In ML the syntax for constant declarations is more regular than in other languages. For example, you can write

val not2 = fn (x: bool) => if x then false else true;

Here the keyword val means this is a direct binding of an identifier to a value

The right-hand side of the = sign is an anonymous function: an expression that denotes a function. In ML any expression, denoting a value of any type, can appear in a val declaration.

IMPERATIVE VERSUS FUNCTIONAL PLS

A variable is an identifier together with the value it is bound to. Variables are created, and maybe initialized by, declarations.

In most programming languages, variables are updatable. This means that the actual value of a variable is a memory address. Assignment commands then change the value stored at this address.

Definition: In a functional language variables are not updatable. An imperative language does have updatable variables.

Since they do not have updatable variables, functional languages do not have commands. ML is a functional language.

Definition: For a functional language, an environment is a mapping from names to values.

In an imperative language like Pascal, a const declaration is the same thing as a val declaration in a functional language like ML.

NESTED ENVIRONMENTS AND SCOPES

Let's start with three definitions, and then see how the definitions work in an example.

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".

NESTED BLOCK-STRUCTURED SCOPING

All the important modern languages share the same basic scoping discipline.

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".

RECURSIVE DEFINITIONS

The scope of a binding extends to the end of the enclosing block. But usually it starts where the declaration appears, not at the start of the enclosing block.

Recursion among definitions can cause difficulties. Consider two types to keep track of the white and black squares on a chessboard:

type white = record
                n1, n2, n3, n4: ^black;
             end;
type black = record
                n1, n2, n3, n4: ^white;
             end;

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.

ALPHA-CONVERSION

An applied occurrence of an identifier in a block is called a "free variable" or "global variable" if there is no matching binding occurrence in the block.

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":

const s = 10.0;
function scale (x: real): real;
begin
return x*s;
end;

"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.

DYNAMIC SCOPING

Suppose the function scale is used inside another procedure:

procedure update (v: vector);
begin
var s := norm(v);
for j := 1 to length(v) do scale(v[i])
end;

Static scoping says that the variable named s that is local to the update procedure is irrelevant to the function scale, so the vector v will be magnified tenfold, not normalized.

Dynamic scoping is a very different scoping discipline. It says that an applied occurrence refers to the binding occurrence in the scope that was most recently entered at runtime.

Under dynamic scoping, the function update really 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.