# 域理论

## 动机和直觉

Dana Scott 在 1960 年代后期发起对域的研究的主要动机是为 lambda 演算找寻指称语义。在这种形式化中，认为“函数”通过在这个语言中的特定项指定。在纯粹语法方式下，可以得到从简单函数到接受其他函数作为它的输入参数的函数。再次只使用在这种形式化中的可获得的语法变换，可以获得所谓的不动点组合子(其中最著名的是 Y 组合子)；通过定义，它们有如下性质，对于所有函数 f 都有 f(Y(f)) = Y(f)。

Scott 通过形式化"部分"或"不完全"信息的概念来表示仍未返回一个结果的计算来克服这个困难。通过对计算的每个域(比如自然数)考虑一个额外的元素，表示“未定义”输出，就是永不结束的计算的"结果"来建模。此外，计算的域被装备了一个“次序关系”，在其中"未定义结果"是最小元素

## 形式定义指南

### 远低于关系

y ≤ sup D

xd

x << y

xy

{0}, {0, 1}, {0, 1, 2}, ...

x << x

## 文献

Probably one of the most recommendable books on domain theory today, giving a very clear and detailed view on many parts of the basic theory:

• G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott, Continuous Lattices and Domains, In Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003. ISBN 0-521-80338-1

One of Scott's classical papers:

• D. S. Scott. Data types as lattices. In G. Muller et al., editors, Proceedings of the International Summer Institute and Logic Colloquium, Kiel, volume 499 of Lecture Notes in Mathematics, pages 579-651, Springer-Verlag, 1975.

A general, easy-to-read account of order theory, including an introduction to domain theory as well:

• B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2nd edition, Cambridge University Press, 2002. ISBN 0-521-78451-4

A readable account of the Laws for Actor systems and how they can be used to prove Scott's continuity criterion:

• Carl Hewitt and Henry Baker Actors and Continuous Functionals Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1-5, 1977.

A general, easy-to-read account of the Actor model of concurrent computation, using only elementary domain theory:

• W. Clinger. Foundations of Actor Semantics MIT Mathematics Doctoral Dissertation. June 1981.

## 参见

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.

Back to homepage

Please click Allow in the top-left corner,
then click Install Now in the dialog
then click Install
then click Install

#### Install Wikiwand

Install on Chrome Install on Firefox

#### Enjoying Wikiwand?

Share on Gmail Share on Facebook Share on Twitter Share on Buffer