Semantics of programming languages

Operational semantics, pioneered by Gordon Plotkin and others, defines a program’s meaning as the sequence of state transitions it causes in an abstract machine. This approach is often presented as a set of inference rules (structural operational semantics) or as a transition system (small-step semantics). Denotational semantics, developed by Dana Scott and Christopher Strachey, assigns to each program phrase a mathematical object, typically a function over a domain of values. ¹ This approach requires solving domain equations using Scott’s theory of domains. Axiomatic semantics, introduced by C. A. R. Hoare, uses Hoare triples {P} C {Q} to specify that if precondition P holds before execution of command C, then postcondition Q holds after. ² These three approaches are complementary: operational semantics is concrete and executable, denotational semantics provides abstract mathematical meaning, and axiomatic semantics is used for program verification.

Formal semantics underpins compiler correctness proofs: a compiler can be verified to preserve the semantics of the source program in the generated machine code. ³ It is also used in program verification, where tools like the Coq proof assistant or the Why3 platform rely on axiomatic or operational semantics to prove program properties. Type systems, a form of static semantics, are derived from denotational semantics and ensure that programs do not encounter certain runtime errors. ⁴ The semantics of programming languages also influences language design: languages like ML and Haskell are built on lambda calculus with denotational foundations, while Java’s memory model is specified operationally. In security research, information-flow semantics formalizes how programs handle confidential data.

Game semantics, introduced by Andreas Blass and later refined by Samson Abramsky, interprets programs as two-player games between a program and its environment, revealing deep connections to linear logic. ⁵ Categorical semantics uses category theory to unify different denotational models, showing that many programming language constructs correspond to universal constructions (e.g., products, exponentials). Another niche area is the semantics of reversible computation, where programs must be able to run backward. ⁶ The concept of a “semantic domain” itself has evolved: from Scott’s complete partial orders to metric spaces and even to the use of sheaves in topos theory. These approaches are less commonly taught but provide powerful tools for analyzing advanced language features like concurrency, continuations, and probabilistic choice.

The formal study of programming language semantics began in the 1960s with John McCarthy’s work on mathematical theory of computation and the introduction of abstract syntax. Christopher Strachey and Dana Scott laid the foundations of denotational semantics in the early 1970s, while C. A. R. Hoare published his axiomatic approach in 1969. The 1980s saw the maturation of operational semantics with Plotkin’s structural operational semantics and the development of domain theory. The field continues to evolve, incorporating concepts from type theory, category theory, and logic, and remains central to the design and verification of programming languages.

Operational semantics

A formal description of program meaning as a sequence of computational steps or state transitions.

Denotational semantics

A formal approach that assigns a mathematical meaning (a denotation) to each program construct.

Axiomatic semantics

A method that uses logical assertions (preconditions and postconditions) to specify program behavior.

Semantic domain

A mathematical structure (e.g., a complete partial order) used to interpret program phrases in denotational semantics.