
arXiv: 1311.6125
An intensional model for the programming language PCF is described, in which the types of PCF are interpreted by games, and the terms by certain "history-free" strategies. This model is shown to capture definability in PCF. More precisely, every compact strategy in the model is definable in a certain simple extension of PCF. We then introduce an intrinsic preorder on strategies, and show that it satisfies some striking properties, such that the intrinsic preorder on function types coincides with the pointwise preorder. We then obtain an order-extensional fully abstract model of PCF by quotienting the intensional model by the intrinsic preorder. This is the first syntax-independent description of the fully abstract model for PCF. (Hyland and Ong have obtained very similar results by a somewhat different route, independently and at the same time). We then consider the effective version of our model, and prove a Universality Theorem: every element of the effective extensional model is definable in PCF. Equivalently, every recursive strategy is definable up to observational equivalence.
50 pages
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Game semantics, intensional model, Semantics in the theory of computing, fully abstract model, programming language, GAMES, recursive strategy, Theoretical Computer Science, Enriched categories (over closed or monoidal categories), linear logic, full abstraction, programming language semantics, Applications of game theory, sequentiality, Combinatory logic and lambda calculus, functional computation, Functional programming and lambda calculus, Logic in computer science, SEQUENTIAL ALGORITHMS, Models of computation (Turing machines, etc.), Computer science (mathematics), game semantics, PCF, Recursive functions and relations, subrecursive hierarchies, Computer Science Applications, Logic in Computer Science (cs.LO), definability, Categorical semantics of formal languages, Computational Theory and Mathematics, Information Systems
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Game semantics, intensional model, Semantics in the theory of computing, fully abstract model, programming language, GAMES, recursive strategy, Theoretical Computer Science, Enriched categories (over closed or monoidal categories), linear logic, full abstraction, programming language semantics, Applications of game theory, sequentiality, Combinatory logic and lambda calculus, functional computation, Functional programming and lambda calculus, Logic in computer science, SEQUENTIAL ALGORITHMS, Models of computation (Turing machines, etc.), Computer science (mathematics), game semantics, PCF, Recursive functions and relations, subrecursive hierarchies, Computer Science Applications, Logic in Computer Science (cs.LO), definability, Categorical semantics of formal languages, Computational Theory and Mathematics, Information Systems
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 285 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
