Domain-theoretic Foundations of Functional Programming

✍ Scribed by Thomas Streicher

• Publisher: World Scientific Publishing Company
• Year: 2006
• Tongue: English
• Leaves: 124
• Category: Library

✦ Synopsis

This textbook provides a basis for a PhD course on domain-theoretic semantics of functional programming languages and their meta-mathematical properties. It introduces basic domain theory and the technique of logical relations as developed by Scott and Plotkin. The solution of recursive domain equations is explained in detail. A complete discussion of the famous full abstraction problem for PCF (a functional Kernel language due to Scott and Plotkin) is given including a construction of the fully abstract Milner model using Kripke logical relations. A final chapter introduces computability in Scott domains and shows that this model is fully abstract and universal for appropriate extensions of PCF by parallel language constructs.

✦ Table of Contents

Contents......Page 6
Preface......Page 8
1. Introduction......Page 10
2. PCF and its Operational Semantics......Page 21
3. The Scott Model of PCF......Page 31
3.1 Basic Domain Theory......Page 33
3.2 Domain Model of PCF......Page 40
3.3 LCF - A Logic of Computable Functionals......Page 42
4. Computational Adequacy......Page 45
5. Milner's Context Lemma......Page 50
6. The Full Abstraction Problem......Page 52
7. Logical Relations......Page 57
8. Some Structural Properties of the Dσ......Page 62
9. Solutions of Recursive Domain Equations......Page 70
10. Characterisation of Fully Abstract Models......Page 82
11. Sequential Domains as a Model of PCF......Page 91
12. The Model of PCF in S is Fully Abstract......Page 98
13. Computability in Domains......Page 102
Bibliography......Page 120
Index......Page 122