Slide 8.2: Operational semantics (cont.)
Slide 8.4: Logical inference rules
Home

A Reduction Machine

The machine we use for operational semantics is more of a mathematical model, namely, a “reduction machine,” which is a collection of permissible steps in reducing programs by applying their operations to values. In principle, an abstract machine can be viewed as consisting of three parts: a program, a control, and a store or memory:


An operational semantic specification of a programming language specifies how the control of this abstract machine reacts to an arbitrary program in the language to be defined, and in particular, how storage is changed during the execution of a program. The reduction machine is similar in spirit to the notion of a Turing machine, in which actions are precisely described in a mathematical way. The Turing machine is
A model of computation that uses an underlying finite-state automaton but also has an infinite tape to use as memory.
The reduction machine operates directly on a program to reduce it to its semantic “value.” For example, given the expression (3 + 4) * 5 of the reduction machine will reduce it to its numeric value (which is its semantic content) using the following sequence of steps: 
 (3 + 4) * 5 ⇒ (7) * 5  — 3 and 4 added to get 7
             ⇒ 7 * 5    — the parentheses around 7 dropped
             ⇒ 35       — 7 and 5 multiplied to get 35
In general, of course, the semantic content of a program will be more than just a numeric value, but as we will see, the semantic content of a program can be represented by a data value of some structured type, which operational semantic reductions will produce.