Dana Scott

From http://www.cs.bham.ac.uk/~axj/pub/papers/handy.ps.gz :

[...] DomainTheory? proper, at least as we understand the term, began in 1969, and was unambiguously the creation of one man, Dana Scott [...]. In particular, the following key insights can be identified in his work:

  1. Domains as types. The fact that suitable categories of domains are cartesian closed, and hence give rise to models of typed lambda-calculi. More generally, that domains give mathematical menaing to a broad class of data-structuring mecahnisms.
  2. Recursive types. Scott's key construction was a solution to the "domain equation" D corresponds to [D -> D] thus giving the first mathematical model of the type-free LambdaCalculus. This led to a general theory of solutions of recursive domain equations. In conjunction with (1), this showed that domains form a suitable universe for the semantics of ProgrammingLanguages. In this way, Scott provided a mathematical foundation of the work of ChristopherStrachey on DenotationalSemantics [...]. This combination of descriptive richness and a powerful and elegant methamatical theory led to DenotationalSemantics becoming a dominant paradigm in Theoretical ComputerScience.
  3. Continuity vs. Computability. Continuity is a central pillar of DomainTheory?. It serves as a qualitiative approximation to computability. In other words, for most purposes to detect whether some construction is computationally feasible it is sufficient to check that it is continuous; while continuity is an "algebraic" condition, which is much easier to handle than computability. [...]
  4. Partial information. A natural concomitant of the notion of approximation in domains is that they form the basis of a theory of partial information, which extends the familiar notion of PartialFunction? to encompass a whole spectrum of "degrees of definedness". This has important applications to the semantics of programming languages, which such multiple degrees of definition play a key role in the analysis of computational notions such as LazyEvaluation vs. EagerEvaluation?, and CallByName vs. CallByValue ParameterPassing mechanisms for procedures. General considerations from RecursionTheory? dictate that PartialFunction?s are unavoidable in any discussion of computability. DomainTheory? provides an appropriately abstract, structural setting in which these notions can be lifted to higher types, RecursiveType?s, etc.

Recipient of 1976 TuringAward.


View edit of January 1, 2005 or FindPage with title or text search