Environments

The semantics of the program are represented not by a single value, but by a set of values corresponding to identifiers whose values have been defined, or bound, by assignments. For example, the program 
     a := 2 + 3;
     b := a * 4;
     a := b – 5
results in the bindings b=20 and a=15 when it finishes, and so the set of values representing the semantics of the program is {a=15, b=20}. Such a set is essentially a function from identifiers to integer values, with all identifiers that have not been assigned a value undefined. Such a function is called an environment, which is a collection of bindings of values to variables. An environment is written as 
Env: Identifier → Integer ∪ {undef}
to denote a particular environment Env. For example, the Env function given by the program example can be defined as follows: 
Env(I) =
 
15  if  I = a
20  if  I = b
undef  otherwise
The operation of looking up the value of an identifier I in an environment Env is then simply described by function evaluation Env(I). The operation of adding a new value binding to Env can also be defined in functional terms. We will use the notation Env & {I = n} to denote the adding of the new value n for I to Env. In terms of functions, 
(Env & {I=n})(J) =
 
n  if  J = I
Env(J)  otherwise
Finally, we also need the notion of the empty environment, which we will denote by Env0: 
Env0(I) = undef for all I