CSE 130 Lecture Notes

CSE130 LECTURE NOTES

October 25, 1999

ADMINISTRATION

Are you thinking about continuing in grad school and doing research in computer science? Here is excellent information from Professor Andrew Black at the Oregon Graduate Institute.

EXPRESSIONS, DECLARATIONS, AND COMMANDS

Traditional programming languages have three big categories of program fragments: definitions, expressions, and commands.

Definition:

An expression is a program fragment that yields a value when evaluated.
A declaration is a program fragment that creates a binding between an identifier and a value.
A command is a program fragment that changes one or more bindings between existing identifiers and values.

Declarations are also called definitions. A declaration can be of a variable, a function, a macro, a type, etc. Remember that functions are values so declaring a function is really not so different from declaring a conventional variable. In some experimental PLs, even types and macros are themselves first-class values.

In typical languages like C, a variable declaration creates a binding between an identifier and a storage location. The declaration may or may not also initialize the variable, i.e. bind the location to a value.

The most fundamental variety of command is the assignment command. An assignment changes the value that is bound to a storage location.

SYNTAX FOR DECLARATIONS

Reminder: Many languages have many different syntaxes for declarations even when the bindings being produced are quite similar.
Consider:

type boolean = {false, true};
const not1: array [boolean] of boolean := [true, false];
function not2 (x: boolean): boolean;
begin
if x then return false else return true;
end;

Conceptually not1 and not2 both have the same mapping type, i.e. boolean -> boolean.

In ML the syntax for constant declarations is more regular: 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.

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

BINDINGS AND ENVIRONMENTS

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

In other words, an environment is a set of bindings where each binding is an ordered pair <name, value>. The simplest way to implement an environment is to use a list of pairs. This is adequate theoretically but for practical use a more efficient data structure must be used.

Environments are ubiquitous in PLs. A PL implementation must keep track of environments both at compile-time and at run-time.

IMPLEMENTING ENVIRONMENTS IN ML

Here is an ML function that searches for the value that an identifier is bound to in a list of bindings. If no binding exists, an exception is raised. (For details on exceptions, see later in the course.)

exception Free_Variable
fun lookup v [] = raise Free_Variable
| lookup v ((w, n) :: env) = if v = w then n else lookup v env

The syntax (w, n) :: env is ML pattern-matching for a list whose head is the ordered pair (i.e. tuple)(w, n) and whose tail is env.

The next function evaluates an arithmetic expression according to an environment:

fun eval (Lit n) env = n
| eval (Var v) env = lookup v env
| eval (Plus (exp1,exp2) ) env = (eval exp1 env)+(eval exp2 env)
| eval (Times (exp1,exp2) ) env = (eval exp1 env)*(eval exp2 env)
- val b1 = ("x", 2); - val b2 = ("y", 3);
- eval (Times((Var "x"), (Var "y"))) [b1,b2]; val it = 6 : int

Be sure that you understand the ML code above completely before you start writing code for the second project.