domain theory
<theory> A branch of mathematics introduced by Dana Scott in 1970 as a
mathematical theory of programming languages, and for nearly a quarter of a
century developed almost exclusively in connection with denotational semantics
in computer science.
In denotational semantics of programming languages, the meaning of a program is
taken to be an element of a domain. A domain is a mathematical structure
consisting of a set of values (or "points") and an ordering relation, <= on
those values. Domain theory is the study of such structures.
("<=" is written in LaTeX as \subseteq)
Different domains correspond to the different types of object with which a
program deals. In a language containing functions, we might have a domain X -> Y
which is the set of functions from domain X to domain Y with the ordering f <= g
iff for all x in X, f x <= g x. In the pure lambda-calculus all objects are
functions or applications of functions to other functions. To represent the
meaning of such programs, we must solve the recursive equation over domains,
D = D -> D
which states that domain D is (isomorphic to) some function space from D
to itself. I.e. it is a fixed point D = F(D) for
some operator F that takes a domain D to D -> D. The
equivalent equation has no non-trivial solution in
set theory.
There are many definitions of domains, with different properties and suitable
for different purposes. One commonly used definition is that of Scott domains,
often simply called domains, which are omega-algebraic, consistently complete
CPOs.
There are domain-theoretic computational models in other branches of mathematics
including dynamical systems, fractals, measure theory, integration theory,
probability theory, and stochastic processes.
See also abstract interpretation, bottom, pointed domain.
(1999-12-09)
Nearby terms:
domain selection « Domain Software Engineering
Environment « domain-specific language « domain
theory » DOMF » Donald Knuth » dongle
|