CS 15-859 Domain Theory

Brief Overview of Domain Theory

What is a domain?: Basically, domains are "convenient sets" on which to define functions in order to have recursive definitions. The trick is to find which functions.
Why not use ordinary sets?: Ordinary (total functions) between sets are not closed under recursion.
Why not use partial functions?: We will, but it is not so clear how to treat partial functions of partial functions.
Why not use integers and standard partial recursive functions?: We could, but all the Gödel numbering is pretty messy and not general enough. Moreover, functionals are confusing.
What is the best theory of domains?: The answer is not yet known! The theory is evolving, and there may be no "best".
What is the problem?: The difficulty lies in finding good closure conditions on the category of domains so there can be sufficiently many domain constructions and finding good methods of proving properties, e.g, of recursively defined relations on the domains.
Why all the emphasis on recursion?: Because the idea is mathematically basic and central to understanding the semantics of programming languages.
Where in the world did the idea of domains come from?: The original motivation (in 1969) was to give a typed calculus of recursive functionals with many models using known idea from recursive function theory. It took some time to realize that the approach also modelled untyped functions.
Does domain theory give a satisfactory approach to the semantics for programming languages?: Yes and no. Not all aspects of program equivalence can be easily modelled by domain-theoretic methods.
What is the right view of the relative merits of operational vs. denotational semantics?: Both are needed.
What are continuous lattices?: They are a kind of complete lattice satisfying an infinite distributive law. Continuous mappings are easily defined as directed-sup-preserving functions. They can be used as domains generalizing earlier models.
What is so good about continuous lattices?: They are also quite generally defined as a kind of injective T0-space or absolute retracts. They form a cartesian closed category which is closed under some very flexible inverse limits.
So what is wrong with continuous lattices?: Understanding then takes too much topology!
There are too many of them.
The top element is too hard to interpret.
The bottom element is not always wanted.
There are too many continuous functions.
The relation to computability is perhaps obscure.
They are not closed under all necessary constructions. They do not capture all that is necessary about partial functions.
Can these difficulties be overcome?: We hope so particularly using partial equivalence relations.
Are there new mathematical applications of the theory?: Yes, new applications of continuous domain theory are being found to: fractal image compression, statistical physics, neural nets, stochastic processes, computation in chaos theory, exact evaluation of integrals. The basic insight (found by Abbas Edalat) was that the probabilistic power domain of the upper space of a locally compact metric space provides effective computations of Borel measures and integrals.
What are some vexing questions for the future?: Must we deal with category theory?
Must we deal with linear logic?
Would domains make better sense under a change of logic?
Do we want types in programming languages at all?
Do domains and quotients give us sufficiently many types?
Is "polymorphism" perhaps the name of a perversion?
Are impredicative types really necessary for computational practice?
How can we resolve the conflict between total and partial functions?
Is the extensional notion of function the correct kind of abstraction?
What is the proper rôle of continuity in semantics?
Do we always need the idea of finite approximations?
Do we have a sufficient grasp of computability?
Would it help to formalize the language of semantics?
How can we give students and researchers (in, say, computer science) the mathematical background to understand the problems and the subtleties?: This is a very tiresome question!

Page maintainers: Dana Scott and Andrej Bauer