Foundations and Trends® in Programming Languages > Vol 2 > Issue 4

Nominal Game Semantics

By Andrzej S. Murawski, University of Warwick, UK, A.Murawski@warwick.ac.uk | Nikos Tzevelekos, Queen Mary University of London, UK, nikos.tzevelekos@qmul.ac.uk

 
Suggested Citation
Andrzej S. Murawski and Nikos Tzevelekos (2016), "Nominal Game Semantics", Foundations and TrendsĀ® in Programming Languages: Vol. 2: No. 4, pp 191-269. http://dx.doi.org/10.1561/2500000017

Publication Date: 09 Mar 2016
© 2016 A. S. Murawski and N. Tzevelekos
 
Subjects
Formal semantics,  Program verification,  Abstract interpretation
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction 
2. Elements of Nominal Set Theory 
3. GroundML 
4. ToyML: A First-Order Language with Integer References 
5. Game Model 
6. Conclusions 
References 

Abstract

These tutorial notes present nominal game semantics, a denotational technique for modelling higher-order programs.

DOI:10.1561/2500000017
ISBN: 978-1-68083-106-1
92 pp. $70.00
Buy book (pb)
 
ISBN: 978-1-68083-107-8
92 pp. $130.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Elements of Nominal Set Theory
3. GroundML
4. ToyML: A First-Order Language with Integer References
5. Game Model
6. Conclusions
References

Nominal Game Semantics

Nominal Game Semantics complements existing introductory literature to game semantics, which highlight the then new structural components necessary to model higher-order computation; for example, arenas, justification pointers, and innocence. In contrast, this monograph focuses on explaining the nominal content of our games. It begins by covering the basics of nominal sets before proceeding to introduce the programming language of study, called GroundML. GroundML is a higher-order language with references capable of storing integers, references to integers, references to references to integers, and so on. Before presenting the game model of GroundML in full detail, the reader is given a flavor of the nominal approach with the presentation of ToyML that, for the sake of simplicity, features only integer-valued references and restricted higher-order types. Because ToyML is simpler, it allows a more direct and elementary presentation of its game semantics, which will help the reader to make a transition to the full-blown model.

Nominal Game Semantics has been written in a way that will make it accessible to readers who are familiar with standard denotational semantics and types.

 
PGL-017