Power domains

From Wikipedia, the free encyclopedia

In denotational semantics and domain theory, power domains are domains of nondeterministic and concurrent computations.

The idea of power domains for functions is that a nondeterministic function may be described as a deterministic set-valued function, where the set contains all values the nondeterministic function can take for a given argument. For concurrent systems, the idea is to express the set of all possible computations.

Roughly speaking, a power domain is a domain whose elements are certain subsets of a domain. Taking this approach naively, though, often gives rise to domains that don't quite have the desired properties, and so one is led to increasingly complicated notions of power domain. There are three common variants: the Plotkin, upper, and lower power domains. One way to understand these concepts is as free models of theories of nondeterminism.

For most of this article we use the terms "domain" and of "continuous function" quite loosely, meaning respectively some kind of ordered structure and some kind of limit-preserving function. This flexibility is genuine; for example, in some concurrent systems it is natural to impose the condition that every message sent must eventually be delivered. However, the limit of a chain of approximations in which a message was not delivered, would be a completed computation in which the message was never delivered!

A modern reference to this subject is the chapter of Abramsky and Jung [1994]. Older references include those of Plotkin [1983, Chapter 8] and Smyth [1978].

Contents

[edit] Power domains as free models of theories of non-determinism

Domain theorists have come to understand power domains abstractly as free models for theories of non-determinism. Just as the finite-powerset construction is the free semilattice, the powerdomain constructions should be understood abstractly as free models of theories of non-determinism. By changing the theories of non-determinism, different power domains arise.

The abstract characterisation of powerdomains is often the easiest way to work with them, because explicit descriptions are so intricate. (One exception is the Hoare powerdomain, which has a rather straightforward description.)

[edit] Theories of non-determinism

We recall three theories of non-determinism. They are variations of the theory of semilattices. The theories are not algebraic theories in the conventional sense, because some involve the order of the underlying domain.

All theories have one sort X, and one binary operation ∪. The idea is that the operation ∪:X×X→X takes two combinations and returns the non-deterministic choice of them.

The Plotkin powertheory (after Gordon Plotkin) has one sort, X, and the following axioms:

  • Idempotency: x∪x=x
  • Commutativity: x∪y=y∪x
  • Associativity: (x∪y)∪z=x∪(y∪z)

The lower (or Hoare, after Tony Hoare) powertheory consists of the Ploktin powertheory augmented with the inequality

  • x≤x∪y.

The upper (or Smyth, after M. B. Smyth) powertheory consists of the Ploktin powertheory augmented with the inequality

  • x∪y≤x.

[edit] Models of the powertheories

A model of the Plotkin powertheory is a continuous semilattice: it is a semilattice whose carrier is a domain and for which the operation is continuous. Note that the operator need not be a meet or join for the order of the domain. A homorphism of continuous semilattices is a continuous function between their carriers that respects the lattice operator.

Models of the lower powertheory are called inflationary semilattices; there is an additional requirement that the operator behave a little like a join for the order. For the upper powertheory, models are called deflationary semilattices; here, the operator behaves a little like a meet.

[edit] Power domains as free models

Let D be a domain. The Plotkin powerdomain on D is the free model of the Plotkin powertheory over D. It is defined to be (when it exists) a model P(D) of the Plotkin powertheory (ie a continuous semilattice) equipped with a continuous function X→P(D) such that for any other continuous semilattice L over D, there is a unique continuous semilattice homomorphism P(D)→L making the evident diagram commute.

Other powerdomains are defined abstractly in a similar manner.

[edit] Explicit descriptions of power domains

Let D be a domain. The lower power domain can be defined by

  • P[D] = {closure[A] | Ø∈A⊆D} where
closure[A] = {d∈D | ∃X⊆D, X directed, d = \vee X, and ∀x∈X ∃a∈A x≤a}.

In other words, P[D] is the collection of downward-closed subsets of D that are also closed under existing least upper bounds of directed sets in D. Note that while the ordering on P[D] is given by the subset relation, least upper bounds do not in general coincide with unions.

It is important to check which properties of domains are preserved by the power domain constructions. For example, the Hoare powerdomain of an ω-complete domain is again ω-complete.

[edit] Power domains for concurrency and Actors

[edit] Clinger's power domain

Clinger [1981] constructed a power domain for the Actor model building on the base domain of Actor event diagrams, which is incomplete. See Clinger's model.

[edit] Timed diagrams power domain

Hewitt [2006] constructed a power domain for the Actor model (which is technically simpler and easier to understand than Clinger's model) building on a base domain of timed Actor event diagrams, which is complete. The idea is to attach an arrival time for each message received by an Actor. See Timed Diagrams Model.

[edit] Connections with topology and the Vietoris space

Domains can be understood as topological spaces, and, in this setting, the power domain constructions can be connected with the space of subsets construction introduced by Leopold Vietoris. See, for instance, [Smyth 1983].

[edit] References

  • Irene Greif. Semantics of Communicating Parallel Professes MIT EECS Doctoral Dissertation. August 1975.
  • Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Semantics. MIT Press, Cambridge, Massachusetts, 1977. (A classic if dated textbook.)
  • Gordon Plotkin. A powerdomain construction SIAM Journal of Computing September 1976.
  • Carl Hewitt and Henry Baker Actors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1-5, 1977.
  • Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
  • Michael Smyth. Power domains Journal of Computer and System Sciences. 1978.
  • George Milne and Robin Milner. Concurrent processes and their syntax JACM. April, 1979.
  • CAR Hoare. Communicating Sequential Processes CACM. August, 1978.
  • Nissim Francez, CAR Hoare, Daniel Lehmann, and Willem de Roever. Semantics of nondeterminism, concurrency, and communication Journal of Computer and System Sciences. December 1979.
  • Jerald Schwartz Denotational semantics of parallelism in Semantics of Concurrent Computation. Springer-Verlag. 1979.
  • William Wadge. An extensional treatment of dataflow deadlock Semantics of Concurrent Computation. Springer-Verlag. 1979.
  • Ralph-Johan Back. Semantics of Unbounded Nondeterminism ICALP 1980.
  • David Park. On the semantics of fair parallelism Proceedings of the Winter School on Formal Software Specification. Springer-Verlarg. 1980.
  • Will Clinger, Foundations of Actor Semantics. MIT Mathematics Doctoral Dissertation, June 1981.
  • Gordon Plotkin. Domains (Pisa notes). 1983. Available from [[1]].
  • M. B. Smyth, Power domains and predicate transformers: A topological view, LNCS 154, Springer, 1983.
  • S. Abramsky, A. Jung: Domain theory. In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, vol. III. Oxford University Press, 1994. (ISBN 0-19-853762-X) (download PDF PS.GZ)