3.5 Describing the Meanings of Programs: Dynamic Semantics 145In the following sections, we present the denotational semantics descrip-
tions of a few simple constructs. The most important simplifying assumption
made here is that both the syntax and static semantics of the constructs are
correct. In addition, we assume that only two scalar types are included: integer
and Boolean.
3.5.2.2 The State of a Program
The denotational semantics of a program could be defined in terms of state
changes in an ideal computer. Operational semantics are defined in this way,
and denotational semantics are defined in nearly the same way. In a further
simplification, however, denotational semantics is defined in terms of only
the values of all of the program’s variables. So, denotational semantics uses
the state of the program to describe meaning, whereas operational semantics
uses the state of a machine. The key difference between operational semantics
and denotational semantics is that state changes in operational semantics are
defined by coded algorithms, written in some programming language, whereas
in denotational semantics, state changes are defined by mathematical functions.
Let the state s of a program be represented as a set of ordered pairs, as
follows:
s = {<i 1 , v 1 >, <i 2 , v 2 >,... , <in, vn>}
Each i is the name of a variable, and the associated v’s are the current values
of those variables. Any of the v’s can have the special value undef, which indi-
cates that its associated variable is currently undefined. Let VARMAP be a
function of two parameters: a variable name and the program state. The value
of VARMAP (ij, s) is vj (the value paired with ij in state s). Most semantics
mapping functions for programs and program constructs map states to states.
These state changes are used to define the meanings of programs and program
constructs. Some language constructs—for example, expressions—are mapped
to values, not states.
3.5.2.3 Expressions
Expressions are fundamental to most programming languages. We assume here
that expressions have no side effects. Furthermore, we deal with only very
simple expressions: The only operators are + and *, and an expression can have
at most one operator; the only operands are scalar integer variables and integer
literals; there are no parentheses; and the value of an expression is an integer.
Following is the BNF description of these expressions: