liveBook · Manning

Abstract state machine

As explained in Modern C, Third Edition

An abstract computational model that describes program execution through states and state transitions independently of a particular machine implementation.

double x = 5.0;
double y = 3.0;
...
x = (x * 1.5) - y;
printf("x is %g\n", x);

Here, x starts at 5.0 and y at 3.0. The assignment gives x the value 4.5, which the printf call then displays. section 5.1

C’s abstract state machine describes execution in terms of states and changes between them. A state includes values held by variables; output is observable too. Values, types, and binary representations determine the transitions. This is a way to reason about what a program does without requiring a particular sequence of machine instructions. section 5.1 section 5.1.3

In the example, the compiler could calculate 4.5 in advance and print a fixed string. If x is needed later, it must still have the required value when used, but the assignment need not occur at the position suggested by the source code. The requirement is to reproduce observable states, not every apparent intermediate step. section 5.1

x += 5;
/* Do something else without x in the meantime. */
x += 7;

The two additions illustrate the limit: if nothing observes or uses the intermediate value of x, a compiler may be able to combine them into one addition of 12. section 5.1.4

TAKEAWAY: Programs execute as if they follow the abstract state machine. An optimization is valid only when it preserves observable behavior. The type of x matters: possible overflow or termination can prevent the compiler from combining operations that otherwise appear equivalent. section 5.1.3 section 5.1.4

Reason primarily about values rather than how a particular computer stores them. A value’s object representation becomes relevant when inspecting stored objects or communicating across differing platform models; it is not normally needed to follow the abstract state machine. section 5.0 section 5.1.3

How Modern C, Third Edition covers it

How deep it goes
Defines states and transitions through values, types, and representations, then works through optimizations; defers inspecting stored object representations.
Examples
Uses a floating-point assignment followed by printf and two additions that may be combined when their intermediate value is unused.
What it assumes
Assumes familiarity with C expressions and assignments but introduces values, types, and representations as the basis for reasoning about execution.
What you can do after
Evaluate/understand whether a proposed change in execution order preserves observable behavior and whether type-dependent overflow blocks it.
How it connects
Connects values, types, binary representation, object representation, observable behavior, overflow, and compiler optimization.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Modern C, Third Edition. The section links point to the parts of the book it draws on.