Domain-theoretic foundations of functional programming. (English) Zbl 1111.68020

Hackensack, NJ: World Scientific (ISBN 981-270-142-7/hbk; 978-981-277-259-6/ebook). x, 120 p. (2006).
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 discussion of the 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.


68N18 Functional programming and lambda calculus
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q55 Semantics in the theory of computing
06B35 Continuous lattices and posets, applications
Full Text: DOI Link