Denotational Semantics

Denotational semantics interprets programs as mathematical objects, typically functions over structured domains, giving a compositional and machine-independent account of meaning.

Definition

Denotational semantics assigns to each program a mathematical object (its denotation), defined compositionally from the denotations of its parts, with recursion interpreted via least fixed points in domains.

Scope

This topic covers the Scott-Strachey approach, in which each program phrase denotes an element of a mathematical domain. It includes domain theory, complete partial orders, continuous functions, and least-fixed-point interpretations of recursion, as well as full abstraction, which concerns how closely denotational meaning matches observable behavior.

Core questions

• What mathematical structures can model arbitrary recursion and non-termination?
• How is meaning built compositionally from the meanings of subprograms?
• What is full abstraction and why is it hard to achieve?
• How does denotational meaning relate to operational behavior?

Key theories

Domain theory and fixed-point semantics

Scott's domain theory provides ordered structures and continuous functions in which recursive definitions are interpreted as least fixed points, solving the problem of giving meaning to self-referential programs.

Full abstraction

Plotkin's study of LCF framed the full-abstraction problem of whether denotational equality coincides exactly with observational equivalence, exposing a gap that motivated decades of further research.

Clinical relevance

Denotational models give a precise, compositional reference for language meaning, support reasoning about program equivalence and optimization, and inform the design of features like recursion and higher-order functions. Domain theory also connects programming languages to broader mathematics and logic.

History

Strachey's work on mathematical descriptions of languages and Scott's 1969 construction of domain models launched denotational semantics, formalized in their 1971 paper. Scott's domain theory matured through the 1970s, and Plotkin's analysis of LCF crystallized the full-abstraction problem, which drove later developments such as game semantics.

Debates

The full-abstraction problem

A central question is whether a denotational model can capture exactly the observable behavior of a language, no more and no less; classical domain models fail this for higher-order sequential languages, prompting alternative models.

Key figures

• Dana Scott
• Christopher Strachey
• Gordon Plotkin
• Glynn Winskel

Seminal works

• scott1971
• scott1976
• plotkin1977
• winskel1993

Frequently asked questions

What is a domain in denotational semantics?

A domain is a mathematical structure, typically a partially ordered set with limits of increasing chains, that provides a setting where recursive and partial computations can be modeled as least fixed points of continuous functions.

What is full abstraction?

A semantics is fully abstract when two programs have the same denotation exactly when they are observationally equivalent, meaning the model neither distinguishes behaviorally identical programs nor conflates distinguishable ones.