Games and Full Abstraction for a Functional Metalanguage with Recursive Types

The Distinguished Dissertation series is published on behalf of the Conference of Professors and Heads of Computing and The British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. In this way computer scientists with significantly different interests are able to grasp the essentials - or even find a means of entry - to an unfamiliar research topic. This book develops a theory of game semantics, a recently discovered setting for modelling and reasoning about sequential programming languages, suitable for interpreting higher-order functional languages with rich type structure, and applies it to constr uct a fully abstract model of the metalanguage FPC.
TOC: Introduction.- Full Abstraction.- Game Semantics.- Historical Perspective.- Contribution of This Book.- Prerequisites.- Preliminaries.- Enriched Category Theory.- Intrinsic Preorder.- Games.- Arenas, Views and Legal Positions.- Games and Strategies.- The Category.- Exponential.- A Cartesian Closed Category.- An Alternative Category.- The Extensional Category.- Sums.- Lifting.- Rational Categories and Recursive Types.- Rational Categories.- Recursive Types.- Invariant Relations.- Parameterized Invariant Relations.- IP-Categories.- Axioms for Rationality.- FPC and its Models.- The Language FPC.- Models of FPC.- Semantics of the Recursion Combinator.- Formal Approximation Relations.- Computational Adequacy.- Full Abstraction.- Conclusions.