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

Streicher, Thomas

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.

Reviewer: Jörg Desel (Eichstätt)

MSC:

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

Keywords:

semantics of functional programs; Scott domains