Abstract

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

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.