×

Concrete domains. (English) Zbl 0809.68085

This is a complete and detailed version of “Domaines concrets” (G. Kahn, G. D. Plotkin, Raport 336, IRIA-LABORIA, 1978) and of other previous communications by the same authors. Following the general framework of complete partial ordered sets for semantical domains (of programming languages), the paper introduces a special kind of such “computation structures” called “concrete domains”. “The purpose of this theory is to find a satisfactory framework for the notions of coroutine computation and sequentiality of evaluation”. The first five sections are mainly introductory \((\S 1\) – Domains of computation; \(\S 2\) – Concrete domains of computation; \(\S 3\) – The covering relation; \(\S 4\) – The incompatibility relation; \(\S 5\) – The projectivity relation), while in the following two, the essential facts of the “representations of the concrete domains” are exposed \((\S 6\) – The information matrix; \(\S 7\) – The representation theorem, and this is Theorem 7.1: “Every concrete domain is isomorphic to the set of configurations of an information matrix”). In \(\S 8\) – Basic operations and \(\S 9\) – Inverse limit constructions, the main general constructive ways for obtaining “complex” concrete domains from “simpler” ones, are studied. Finally, \(\S 10\) is dedicated to the study of a particular case – very important for practical applications – namely the “distributive concrete domains”. For historical considerations and scientifical impact on the world of computer science general research of this article, see also S. Brookes, ibid. 121, 179-186 (1993; see the paper reivewed below)].

MSC:

68Q55 Semantics in the theory of computing
68N15 Theory of programming languages
06B35 Continuous lattices and posets, applications

Citations:

Zbl 0809.68081

Software:

LCF; Lucid
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ashcroft, E. A.; Wadge, W. W., Lucid, a nonprocedural language with iteration, Comm. ACM, 20, 519-526 (1977) · Zbl 0358.68033
[2] Birkhoff, G., Lattice Theory, Vol. 25 (1967), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0126.03801
[3] Gordon, M. J.; Milner, R.; Wadsworth, C., Edinburgh LCF: A Mechanized Logic of Computation, (Lecture Notes in Computer Science, Vol. 78 (1978), Springer: Springer Berlin) · Zbl 0421.68039
[4] Landin, P. J., The next 700 programming languages, Comm. ACM, 9, 157-164 (1976) · Zbl 0149.12505
[5] Lévy, J.-J., Réductions correctes et optimales dans le λ-calcul, (Ph.D. Dissertation, 7 (1978), Université Paris)
[6] Maeda, Symmetric Lattices (1972), Springer: Springer Berlin · Zbl 0219.06002
[7] Milner, R., Models of LCF, (Artificial Intelligence Memo, 186 (1973), Stanford Univ., Computer Science Dep) · Zbl 0364.02018
[8] Plotkin, G. D., \(T^ω\) as a universal domain, J. Comput. System Sci., 17, 209-236 (1978) · Zbl 0419.03007
[9] Reynolds, J. C., Definitional interpreters for higher-order programming languages, ACM 25th National Conf., 717-740 (1972)
[10] Scott, D. S., Outline of a mathematical theory of computation, 4th Ann. Princeton Conf. on Informations Sciences and Systems, 169-176 (1970)
[11] Scott, D. S., Data type as lattices, SIAM J. Comput., 5, 157-164 (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.