Pl Semantics

Programming language semantics is the study of what programs mean.

10 frameworks, from 1930 to today · Programming Languages · Computer Science

still a working view ended · each leads to its entry below

Overview

Programming language semantics is the study of what programs mean1. A program is a string of symbols, and a compiler or interpreter must decide what that string does—which values it computes, which effects it performs, which observations an outside world can make of it1. Semantics is the part of programming-languages research that answers this question precisely, in mathematics rather than in prose1. The stakes are practical as well as intellectual: if you can define a language's meaning exactly, you can prove that a compiler preserves it, that two programs are interchangeable, that a type system is sound, or that a program never does something forbidden. The history of the field is a history of successive attempts to make "meaning" rigorous—and of the discoveries that each attempt made possible.

Lambda calculus and the prehistory of formal meaning

Before there were programming languages there was a notation for functions. In the 1930s Alonzo Church developed the lambda calculus, a tiny language with variables, function abstraction (written λx2. M, "the function of x that returns M"), and application. Church used it to investigate the foundations of mathematics, and with Stephen Kleene he showed that the computable functions it defines coincide with those of Turing machines. The calculus turned out to be the purest possible programming language: every functional language descends from it, and its two great reduction rules—substituting an argument for a parameter, and renaming bound variables to avoid capture—are the prototype of every evaluation strategy.

The lambda calculus gave the field its first worked-out notion of equational meaning: two terms mean the same thing when one can be transformed into the other by the reduction rules. That idea—that meaning is an equivalence on programs—runs through everything that follows.

Operational semantics: meaning as computation

When programming languages arrived in the late 1950s, the first need was to say what a program does step by step. The dominant early answer was operational semantics: define an abstract machine and give rules for how it moves from state to state. The approach was crystallized in the 1980s by Gordon Plotkin's structural operational semantics, which specifies the meaning of a compound construct in terms of the meanings of its parts—so the rules for a while loop refer to the rules for its condition and body3. A companion style, reduction semantics, describes computation as rewriting a term until no rule applies1.

Operational semantics is the workhorse of the field because it is close to how implementations actually behave. Its weakness is equally clear: it tells you how a program runs, not what it is. Two programs that compute the same answer by different routes are not obviously equal under an operational definition, and reasoning about programs requires a separate theory of equivalence.

Axiomatic semantics: meaning as proof

The first serious attempt to reason about programs directly was axiomatic semantics, introduced by C. A. R. Hoare in 1969 with his logic of pre- and postconditions. A Hoare triple {P} S {Q} says: if assertion P holds before statement S runs, then Q holds afterward4. Hoare gave rules for each construct—for assignment, sequencing, conditionals, loops—so that a program's correctness could be proved by deriving triples. Robert Floyd had earlier proposed assigning assertions to points in a flowchart, and the two ideas together became Floyd–Hoare logic5.

The approach's great virtue is that it reasons about programs without a machine model, and it remains the basis of modern program verification and of tools like separation logic for reasoning about memory. Its limitation is that it characterizes programs only through the properties one can state in its assertion language; it does not by itself give a notion of program equivalence, and the loop rule requires an invariant supplied by the human.

Denotational semantics: meaning as mathematical object

The most ambitious answer came from Christopher Strachan and Dana Scott in the late 1960s and early 1970s. Denotational semantics assigns to each program phrase a mathematical object—a number, a function, a set—and defines the meaning of a compound phrase as a function of the meanings of its parts16. A program's meaning is then a function from inputs to outputs, and two programs are equal when their denotations are equal.

The obstacle was recursion. A recursive definition like the factorial function refers to itself, and naively the meaning is the solution of an equation that may have no solution in ordinary sets. Scott's breakthrough was to build mathematical domains—now called Scott domains—in which such equations do have least solutions, using the theory of continuous functions and fixed points. This made denotational semantics rigorous for a whole class of languages, and it gave the field its first fully compositional account of meaning: the meaning of the whole is built from the meanings of the parts.

Denotational semantics also produced the monadic style, in which effects such as state, exceptions, input/output, and nondeterminism are modeled as a parameterized notion of computation. Eugenio Moggi's work in the late 1980s and early 1990s showed that many effects share a common algebraic structure—a monad—and that a single framework could give semantics to languages with side effects7. The idea crossed into practice when Philip Wadler popularized monads as a programming idiom in Haskell, where they became the standard way to sequence effects in a pure language.

Game semantics: meaning as interaction

A later rival to the domain-theoretic picture was game semantics, developed from the late 1980s onward by researchers including Samson Abramsky, Radha Jagadeesan, Pasquale Malacaria, and Martin Hyland. Instead of mapping a program to a function, game semantics models it as a strategy in a dialogue between a program and its environment: the environment asks questions, the program answers, and the meaning is the set of possible plays8. This "interactive" view handles features that classical denotational semantics struggled with—higher-order functions, references, control operators like call/cc—and it yields full abstraction, meaning that two programs are denotationally equal exactly when they are observationally indistinguishable. Full abstraction had been an open problem for decades; game semantics supplied it for several important languages.

Concurrency: process calculi and bisimulation

All of the above concerns sequential programs. Concurrency demanded its own semantics. In 1980 Robin Milner introduced CCS (Calculus of Communicating Systems), and with Joachim Parrow and David Walker later π-calculus, in which processes communicate over channels and channels themselves can be passed as messages. Tony Hoare's CSP (Communicating Sequential Processes) offered a related but distinct model based on synchronous message passing and external choice.

The key semantic notion for concurrency is bisimulation, introduced by David Park in 1981 and developed by Milner. Two processes are bisimilar if every action one can take can be matched by the other, and the matching continues indefinitely9. Bisimulation gives a coinductive definition of behavioral equivalence—a notion of "same behavior" that does not require the processes to be structurally identical—and it became the standard tool for reasoning about concurrent systems, underpinning model checking and the theory of reactive systems.

Mechanized semantics: meaning checked by machine

From the 1990s, semantics moved into proof assistants. Mechanized semantics encodes the rules of a language—operational, denotational, or axiomatic—inside a machine-checked logic such as HOL, Coq, or Isabelle, so that proofs about the language are themselves checked by computer. The landmark achievement is the CompCert verified compiler, whose correctness proof (completed in the 2000s) shows that the compiled code behaves as the source semantics says. Mechanization turned semantics from a paper discipline into an engineering one: language definitions became executable artifacts that could be tested, and metatheory—type soundness, compiler correctness, program equivalence—became machine-verified.

Gradual typing: semantics for the boundary

A recurring tension in language design is between static checking and dynamic flexibility. Gradual typing, introduced by Jeremy Siek and Walid Taha in 2006, gives a semantics for languages that mix typed and untyped code10. The central idea is the type cast at the boundary: when a value crosses from untyped to typed code, a runtime check enforces the type, and the guarantee is that well-typed portions never get "stuck" in the sense of type soundness. Gradual typing is a semantics of blame and of the dynamic-typing boundary, and it has become a major research area as languages like TypeScript, Python's type hints, and Racket's typed/untyped boundary put the theory into practice.

Effect systems and the present

The newest strand in the coverage is effect systems, which extend types with descriptions of what a computation does—which regions it reads or writes, which exceptions it raises, which algebraic operations it performs11. The idea descends from type-and-effect systems of the 1980s and 1990s and from the monadic treatment of effects; today it appears in languages with effect handlers and in systems for tracking IO, state, and exceptions. Effect systems are where semantics, type theory, and practical language design now meet most directly.

The field today is plural. Operational semantics remains the default for specifying new languages and for mechanization; denotational and game semantics supply the mathematical theory of equivalence and full abstraction; axiomatic and separation logics drive verification; process calculi and bisimulation remain the theory of concurrency; monads and effect systems organize how effects are given meaning; and gradual typing addresses the boundary between checked and unchecked code364121310. The open questions are the old ones in new form: how to give compositional, fully abstract semantics to languages with increasingly rich effects and concurrency; how to make mechanized semantics scale to real languages and real compilers; and how to keep the theory close enough to practice that a working programmer's intuitions about what a program means are the same as the mathematician's.

References

  1. Semantics (programming languages) (introduction, Approaches), Wikipedia
  2. Lambda calculus (introduction, History), Wikipedia
  3. Operational semantics (Structural operational semantics, introduction), Wikipedia
  4. Axiomatic semantics, Wikipedia
  5. Hoare logic, Wikipedia
  6. Denotational semantics, Wikipedia
  7. Monad (functional programming) (introduction, History), Wikipedia
  8. Game semantics, Wikipedia
  9. Bisimulation, Wikipedia
  10. Gradual typing (introduction, History), Wikipedia
  11. Effect system, Wikipedia
  12. Process calculus, Wikipedia
  13. Monad (category theory), Wikipedia

The frameworks of Pl Semantics

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1930-Present

    Lambda calculus

    What does a function expression mean?

    Fly to its tower in Nousfarer

  2. 1960-Present

    Operational semantics

    How does a program take its steps?

    Fly to its tower in Nousfarer

  3. 1967-Present
  4. 1969-Present

    Denotational semantics

    What mathematical object is a program?

    Fly to its tower in Nousfarer

  5. 1980-Present

    Process calculus

    When do two concurrent processes behave alike?

    Fly to its tower in Nousfarer

  6. 1986-Present

    Effect system

    Which effects may a computation perform?

    Fly to its tower in Nousfarer

  7. 1989-Present

    Monad

    How can effects be modeled uniformly?

    Fly to its tower in Nousfarer

  8. 1990-Present

    Game semantics

    What does a program do in dialogue with its environment?

    Fly to its tower in Nousfarer

  9. 1990-Present

    Mechanized semantics

    Can a machine check a language's meaning?

    Fly to its tower in Nousfarer

  10. 2006-Present

    Gradual typing

    What happens where typed and untyped code meet?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Lambda calculusOperational semanticsAxiomatic semanticsDenotational semanticsProcess calculusEffect systemMonadGame semanticsMechanized semanticsGradual typing

Beyond the field

Where Pl Semantics's ideas came from in other fields, and what they led to there: the strongest 12 of 29 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Pl Semantics is a planet in Nousfarer

Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.

Land on Pl Semantics

Related fields

Fields its ideas are linked to

More in Programming Languages

See where Pl Semantics sits on the Map of Human Knowledge