Domain-theoretic Foundations Of Functional Programming

by Thomas Streicher

Overview

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.

Product Details

ISBN-13:	9789812701428
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	12/05/2006
Pages:	132
Product dimensions:	6.10(w) x 9.00(h) x 0.60(d)

Table of Contents

Preface     ix
Introduction     1
PCF and its Operational Semantics     13
The Scott Model of PCF     23
Basic Domain Theory     25
Domain Model of PCF     32
LCF - A Logic of Computable Functionals     34
Computational Adequacy     37
Milner's Context Lemma     43
The Full Abstraction Problem     45
Logical Relations     51
Some Structural Properties of the D[sigma]     57
Solutions of Recursive Domain Equations     65
Characterisation of Fully Abstract Models     77
Sequential Domains as a Model of PCF     87
The Model of PCF in S is Fully Abstract     95
Computability in Domains     99
Bibliography     117
Index     119