The parallel intensionally fully abstract games model of PCF

Simon Castellan, Pierre Clairambault, Glynn Winskel

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

15 Citations (Scopus)

Abstract

We describe a framework for truly concurrent game semantics of programming languages, based on Rideau and Winskel's concurrent games on event structures. The model supports a notion of innocent strategy that permits concurrent and non-deterministic behaviour, but which coincides with traditional Hyland-Ong innocent strategies if one restricts to the deterministic sequential case. In this framework we give an alternative interpretation of Plot kin's PCF, that takes advantage of the concurrent nature of strategies and formalizes the idea that although PCF is a sequential language, certain sub-computations are independent and can be computed in a parallel fashion. We show that just as Hyland and Ong's sequential interpretation of PCF, our parallel interpretation yields a model that is intensionally fully abstract for PCF.

Original languageEnglish
Title of host publicationProceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015
Pages232-243
Number of pages12
ISBN (Electronic)9781479988754
DOIs
Publication statusPublished - 31 Jul 2015
Event30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015 - Kyoto, Japan
Duration: 6 Jul 201510 Jul 2015

Publication series

NameProceedings - Symposium on Logic in Computer Science
Volume2015-July
ISSN (Print)1043-6871

Conference

Conference30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015
CountryJapan
CityKyoto
Period6/07/1510/07/15

Keywords

  • games
  • semantics
  • computational modeling
  • concurrent computing
  • mathematical modelling
  • programming language semantics

Fingerprint Dive into the research topics of 'The parallel intensionally fully abstract games model of PCF'. Together they form a unique fingerprint.

  • Cite this

    Castellan, S., Clairambault, P., & Winskel, G. (2015). The parallel intensionally fully abstract games model of PCF. In Proceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015 (pp. 232-243). [7174885] (Proceedings - Symposium on Logic in Computer Science; Vol. 2015-July). https://doi.org/10.1109/LICS.2015.31