MFPS 2012
Game semantics in the nominal model
Heriot-Watt University Edinburgh, United Kingdom
Dan Ghica
Abstract
We present a model of games based on nominal sequences, which generalise sequences with atoms and a new notion of coabstraction. This gives a new, precise, and compositional mathematical treatment of justification pointers in game semantics.
Keywords: Game semantics, nominal sets, nominal abstraction and coabstraction, equivariance
1 Introduction
Game semantics is a successful collection of techniques for giving denotations to logic and computation. It came to particular prominence by solving the open problem of full abstraction for PCF [2,19] and is widely used from philosophy and logic, to model checking and synthesis of digital circuits [22,13].
The game metaphor is a dialogue between Proponent and Opponent: a play of a game records interactions between a term (the Proponent) and its context (the Opponent), and how they are scheduled.
One way to model a play is as a labelled acyclic graph called a pointer sequence. Each node in the graph is a Proponent or Opponent move and edges in the graph represent the justification for that move. Thus, a pointer sequence records what moves were made and in what order, and also why.
This paper is electronically published in Electronic Notes in Theoretical Computer Science
URL: www.elsevier.nl/locate/entcs
We propose a model of games based on nominal sets, inspired by pointer sequences, with the difference that we model edges using atoms from nominal techniques (which we may also call names). Why this is useful will become clear in a moment.
Atoms are just a countably infinite set of distinct symbols: . A diagram shows how these can model pointer sequences. The pointer sequence on the left corresponds to the nominal sequence on the right:
Questions and answers are written q and a, and atoms are used as pointers. The symbols [] and [] can be thought of as naming the questions q and and are binders into the ‘future’. So we see above that q justifies two moves: and a. Pointers (arrows, in the diagram above) are rendered as a pair of atoms. The tip of the arrow is represented by a coabstraction [] which must be unique (this is formalised by the condition atoms() in Definition 2.8). The tail of the arrow, which need not be unique, is an occurrence of the name. This deals straightforwardly with dangling pointers, which are viewed just as free names; in the sequence above is free.
Nominal sequences have the following good properties:
(i) A sub-sequence of a nominal sequence is a nominal sequence. A sub-graph of a pointer sequence is not a pointer sequence, because it might have ‘dangling pointers’. In that sense, nominal sequences generalise pointer sequences and help talk easily about ‘open sequences’ (easy handling of open elements is a typical benefit of nominal techniques).
(ii) A concatenation of two nominal sequences is a nominal sequence; names link up and there are no reindexing isomorphisms. It is not so clear how to concatenate pointer sequences.
(iii) Nominal sequences are an inductive data-type and can be manipulated with standard tools (to fully benefit would require a mechanised nominal system [26] but we shall see our sequences simplify paper-and-pencil proofs too).
There is an important, specifically nominal advantage to using names in particular: it enables a particularly efficient management of renaming pointers to avoid ‘accidental clash’. It is important and useful that we use names to name moves and not e.g. numbers, because names are by definition symmetric (i.e. can be permuted); not only can we use permutations to -convert, but taking names and their permutative symmetry as primitive saves effort since permutations propagate necessarily to the things we build using them, such as plays and strategies. 1 This style of name management is characteristic of nominal techniques and we shall see that it is effective here.
We formalise game models for PCF [19,23] and Concurrent Algol [14], at low overhead. The decoration of sequences by atoms is no more of an overhead than decoration by pointers, and equivariance is a very efficient way to manage renaming, so the overhead is low and the advantages in precision and conciseness appear to be significant.
We cannot replicate all definitions and proofs from these two large papers in this conference paper but we hope that it will be entirely obvious to the reader how this could be done. We do not claim to make the work above trivial. However, we do claim that using our formulation, game semantics can be carried out more quickly, more accurately, and more transparently.
This is important for more than good practice: we speculate that by our formulation, implementation and mechanisation of game semantics proofs are significantly easier. The reader can compare the definitions in this paper with the original versions [19,14] and judge which would be easier to work with, in a prover like Isabelle. Furthermore, game semantics can provide theoretical foundations for program verifi-cation and for hardware synthesis, where the pen-and-paper style of much previous work must be augmented by machine-checked proofs, because of scale, or for safety, or both. Here, the compositionality, computational, and symmetry properties enu-merated and discussed above really count. Finally, game semantics can reconcile the compositionality of denotational semantics with the effectiveness of operational semantics via communicating abstract machines [16]; here, the conventional repre-sentation of pointers is arguably actively counterintuitive, whereas the use of names as tags for messages carries immediate computational intuitions.
2 Nominal game semantics
2.1 Nominal sequences
Call the empty list and write for list concatenation. Call [] a coabstraction. The reminds us of the atoms-abstraction of nominal techniques [12]—but in [], is bound ‘in the future’ in whatever we might concatenate after []. We contrast the intended denotations of abstraction and coabstraction in the Conclusion.
Define coabstracted and free atoms ca() and fa() by:
Define the atoms in an expression atoms() by atoms( fa() ca().
ca( ca() ca() and fa( fa() (fa() ca()).
Define a renaming action on sequences by:
2.2 Nominal game semantics
A game is an arena (Definition 2.7) along with some set of legal plays which are lists of moves by a proponent or opponent—precisely what classes of plays are legal, determines the type of game they play.
An arena is a tuple ) of:
Disjoint sets of questions q and answers a . Write m for short and call this the set of moves.
A polarity function O P. Write O P and P O.
An enabling relation where m implies m and (m().
A set of initial questions such that: (i O for every initial i .
Recall that m . Write for the set of all proto-plays of .
Every proto-play is a sequence; not every sequence is a proto-play. It will always be clear what ranges over.
Call m[] a (named) move; will range over named moves.
A proto-play consists of a sequence of named moves, each of which consists of a move m, a justifying name and a coabstraction [] which we call the name of m. This ‘names’ its move, so that a later named move’s justifying name can point to by its name .
The freshness condition atoms() makes name its move uniquely in the sequence. This is inefficient—we cannot reuse names even if somehow we know we could—but we optimise for mathematical convenience.
In the games models of [19,23,14] only questions justify, so for the applications in this paper and we can drop the coabstractions naming answers in protoplays (so: q[] but just a). However, this complicates definitions and loses generality, so we leave in (dummy) coabstractions and take . Answers justifying moves are used to construct ‘coproduct arenas’ in game semantics for call-by-value languages [3].
Suppose and are sequences. Write when for some ; call a prefix of . Write when for some and ; call a segment of .
Define enabled() the moves enabled by by:
enabled(m [] m.
Given define its underlying sequence by:
Intuitions for Definition 2.15 are discussed in Remark 2.16:
Suppose is an arena and .
(i) Call justified when m and m implies menabled().
(ii) Call well-opened when i[] implies .
(iii) Call strictly scoped when a[] implies fa(), for every , a , and atom .
(iv) Call strictly nested when q[] [] a implies for some answering move . 2
(v) Call alternating when implies (m) ().
Intuitively, Definition 2.15 means:
is justified when every non-initial move responds to a preceding move.
is well-opened when the initial move is unique and first in the sequence.
is strictly scoped 3 when a question can receive at most one answer. If we read games as processes, this means answering a question stops the process associated with that question.
is strictly nested when questions are answered in (reverse) order. This forbids starting a process , then from inside , then stopping before .
The intuition of alternating seems clear but it does not have directly to do with names and binding, so we will not consider it further.
Definitions 2.17 and 2.18 follow [23, Sec. 2.1]:
Given justified define the proponent view and opponent view by: 4
We say that a justified proto-play satisfies visibility when q[][] implies that:
if (q P then q[] q[], and
if (q O then q[] q[].
Compare this to the more informal definition of visibility in [23, Sec. 2.1]: A well formed sequence s is legal, or is a legal position, if it also satisfies the following visibility condition:
if where is a P-move, then the justifier of occurs in .
if where is a noninitial O-move, then the justifier of occurs in . The difficulty here is that the taking of the view removes moves from a play, and so requires a complex reindexing if pointers are formalised using integers. Finding the justifier of a move in a view is not straightforward. Visibility is subtle, typical of languages that are pure or have only ground-type state. We have shown above how to formalise it in our framework, but proofs of properties involving visibility are non-trivial for reasons other than the handling of names and binding, so we will not consider this property further.
We can now characterise the plays of HO-games (the games from [19]) and GM-games (those from [14]). Suppose is an arena and is a proto-play. Then:
In HO-games, is a legal play when fa( for some and is justified, well opened, alternating, strictly nested and satisfies visibility (see [19, Def. 4.2, Def. 4.4]).
In GM-games, is a legal play when fa( as above and is justified, well-opened, strictly scoped, and strictly nested (see [14, Def. 1]).
The condition fa( implies has one free atom ; one ‘dangling pointer’. With being well-opened, this ensures names the initial question.
How do we choose above? We do not. It is a non-evident design decision that proto-plays do not have -conversion on coabstracted atoms. This preserves compositionality: if [] equals [] then [] equals [], which is nonsense. 5 In our framework -conversion lives in strategies (sets of proto-plays), which are subject to an equivariance (symmetry) condition up to the choice of atoms in the proto-plays they contain. So -equivalence does not live in the elements, it lives in the sets of elements. More on this in Remark 5.3.
3 Operations on plays
3.1 Deletion of moves from a play
We often want to delete moves from pointer sequences, reflecting ‘hiding’ of irrel-evant parts of a computation (see e.g. Definition 5.2). But pointers into and out of deleted moves need to be updated. Definition 3.1 and Proposition 3.4 make this formal for our nominal framework. The culminating result of this subsection is Theorem 3.11, which uses Proposition 3.4 amongst other constructions to show that properties of proto-plays are preserved by deletion.
Suppose is some set of moves from an arena , and . Define deletion inductively on as follows, where we take inductively (:
It will be convenient to write for (), that is, for deletion of the set of moves of . Here is first projection.
Intuitively is ‘ with the moves in deleted’. Some reindexing has to take place when we do this: e.g. if q[] is deleted then any pointers to are ‘reattached’ so that they point to whatever points to:
In the diagram above the shaded nodes (circles) are in and are deleted.
inductively generates a ‘result’ and a ‘reindexing renaming’ . It is tempting to dismiss as a by-product, but may be the more important information since can be calculated from and . This is Proposition 3.4, which is key to a nice proof of Theorem 3.11.
Suppose and . We define naive deletion - as follows:
Suppose and ). Then )-. 6
enabled(enabled().
As an immediate corollary, enabled()-enabled())-.
We now examine the impact deletion has on the legality conditions of Definition 2.15. Legality is not preserved by arbitrary deletions, but deletion is usually used in a controlled way which ensures preservation. For instance deletion of moves forming an entire sub-tree in the arena, preserves legality properties. Other kinds of deletions can be dealt with similarly.
Suppose and . Write ). Then fa() fa() and ca() ca().
Suppose . If m enabled() then atoms().
By a routine induction on the proto-play , using Definition 2.12.
If m[] and enabled() then m .
Call closed under when m and m implies .
Suppose is closed under . Suppose ). Then if m enabled() and m then m() enabled().
By Lemma 3.5 it suffices to show that if m enabled() then m() enabled(()-). We work by induction on and consider one case:
The case of m[]. Write ) and suppose enabled(m[]) and . By Lemma 3.8 m . Since it follows by closure of under that m . So ((m[]))-)-) (m()[()]) By Definition 2.12, () enabled((()-) (m()[()])).
Suppose and ).
(i) If is closed under then if is justified then so is .
(ii) If then if is well-opened then so is .
(iii) If is strictly scoped then so is .
(iv) If is closed under then if is strictly nested then so is .
(i) Suppose m() where ) and m . Using Proposition 3.4 m()-)m() for some m, and also m . Since is justified, by Lemma 2.13 it must be that q m for some q[] .
Since is closed under we know q . It follows by Proposition 3.4 that q()[()] and we are done.
(ii) By an easy argument using Proposition 3.4.
(iii) Suppose a(). Then a for some . Since is strictly scoped we know that fa(). By Lemma 3.6 also fa().
(iv) Much as the previous case.
3.2 Restriction to a hereditarily justified sub-play
The structure of this subsection resembles that of Subsection 3.1. We have a more complex operation than deletion; extracting the hereditarily justified sub-pointer sequence. In our framework the definition is absolutely routine; we just take a sub-sequence. This is Definition 3.12; then Proposition 3.14 shows how to quickly calculate the relevant sub-sequence using names, and Theorem 3.18 expresses how properties are preserved.
Suppose and . Define the hereditarily justified proto-play as follows, where we take ( and and :
Suppose and . Define @ as follows, where and (the resemblance with atoms-concretion from [12] is deliberate):
If ) then @.
Suppose ). Then:
If m[] then exists such that m[] and (m[])@m[].
If a[] then exists such that a[] and (a[])@ a[].
If q[][]a[] then and exist such that
If ) then menabled() enabled().
fa(@ fa() and ca(@ ca() .
Suppose ). Then if is justified / well-opened / strictly scoped / strictly nested then so is .
4 Combining arenas
(i) Suppose is a function on a set and is a function on a disjoint . Write [] for the co-pairing function on such that [](() and [](() for and respectively.
(ii) Suppose is a function to O P. Write for the function mapping to () (Definition 2.7).
Define product and arrow of arenas by:
Above, the symbol denotes disjoint sets union (for convenience assume sets of moves of distinct arenas are distinct), and
( i) i. So is the disjoint union of the enabling relations of and , disjoint union .
We show how from proto-plays in we recover proto-plays in and . This is Lemmas 4.3 and 4.5. These state that two important operations on proto-plays—deletion and unravelling—preserve certain well-formedness properties which define the notion of HO and GM legal plays. These operations are key to formulating composition of strategies, so preservation of legality is essential to show that composition of HO or GM strategies is well-defined.
Suppose and ). Then . If is justified, well-opened, strictly scoped, or strictly nested, then so is .
Define the unravelling of by unravel( fa()
Unravelling is key to constructing exponential games [23, Sec 2.4]. Intuitively, in a play in we can recover one play in , by deleting the moves of . Removing the moves in yields an interleaved set of plays of . Unravelling separates these plays by following pointers, as illustrated:
It is easy to see that if is justified then unravel() captures the idea of “the set of threads in ”, and if is additionally well-opened then unravel(.
If then unravel(). If is justified / well-opened / strictly-scoped / strictly-nested then so is every unravel().
Directly from Lemma 4.3.
5 Strategies
5.1 Strategies and equivariance
Call equivariant when implies for every permutation . Write : when is an equivariant subset of and call a strategy.
(The notion of strategy is usually subject to further constraints; these are discussed below.)
Recall deletion from Definition 3.1. We follow [23, Section 2.2.3]:
Suppose , , and are arenas on disjoint moves. Then for strategies : and : define their interaction and composition by:
This is the linear version of strategy composition; exponential games are con-structed using the concept of unravelling introduced earlier (Definition 4.4). The use of proto-plays, which have almost no structure, simplifies the definition of interaction () compared to the usual definition (c.f. [23, Section 2.2.3]) which needs the auxiliary concept of interaction sequences.
So proto-plays do not have -equivalence in our framework but sets of proto-plays do (cf. [10]). Thus, Theorem 5.4 becomes a one-line argument by symmetry/equivariance. This avoids arguments about -renaming, reindexing, or re-linking that would be needed if we used numbers or explicitly linked lists. So we have:
Suppose , , and are arenas and : and : are strategies. Then the set ; is equivariant, and thus is a strategy in .
By Definition 5.1 a strategy is an equivariant set of protoplays, so and are equivariant. We note that the definitions involved in specifying ; are all symmetric in atoms, and so by assumption are the inputs to those definitions and , therefore by the principle of equivariance also ; are symmetric. (A formal discussion of equivariance is elsewhere [7, Subsection 4.2].)
5.2 Associativity of composition
We will prove Theorem 5.5, that composition of strategies is associative:
Suppose , , , and are arenas on disjoint moves. Suppose : , : , and : are strategies. Then (; ); ; (; ).
This will follow immediately from Lemma 5.8. For us in this paper strategies are just sets of sequences of moves and names, and the proofs are just by routine induction and name-chasing, that is: unpacking definitions and noting that names end up in the same places on both sides of the equality (see the proof of Proposition 5.6).
Suppose is an arena and are two disjoint sets of moves, and . Suppose ) and ) and ( ().
Then and (where is functional composition, notation from Definition 2.5).
By induction on using Definition 3.1.
The case ... is easy.
The case m[] where m . By Proposition 3.4 - and -. It follows that )-(). Also by Proposition 3.4 -(). By inductive hypothesis and .
By Definition 3.1 we have that m[][()]) and it follows that (m[]) ([()])). Also, it is a fact of functions that ([()[)()].
Using Definition 3.1 we have that m[]([()]), and the result follows.
The case m[] where m . Similar to the previous case, but simpler.
Our notion of strategy is simple and it does not rely on a notion of legal play. So to study properties of composition, any strategy over an arena is also a strategy over an arena , as the two arenas have the same sets of moves—the polarities of the moves and the justification structure are different between and , but this information is not used in the definition of composition.
Similarly for defining for strategies : and : . An interaction can be viewed as a strategy in () or (), as convenient. This is correct because interaction preserves equivariance and the sets of moves in these arenas are the same.
Thus we will obtain a particularly simple proof of associativity of interaction, given below.
Suppose : , : , and : are strategies. Then ()().
5.3 Prefix- and opponent-closed
Just as for proto-plays, GM and HO strategies are subject to constraints. In the rest of this section we sketch, sometimes in detail, how these can be expressed.
Two standard conditions on strategies are being prefix-closed and opponent-closed; see [19, Section 5] (where opponent-closed is called contingent completeness) or [14, Definition 4]. These are straightforward to formalise:
Call prefix-closed and opponent-closed respectively when:
5.4 The asynchrony pre-order on proto-plays
In [14] the authors were interested in modelling asynchronous concurrency. Accord-ingly strategies must be saturated under certain move swapping [14, Subsection 2.5] (the idea goes back to [25]).
Call a relation on sequences compatible when implies and . Define on to be the least compatible pre-order such that:
Call -saturated when , and imply .
...we define a pre-order on for any arena as the least reflexive and transitive relation satisfying for all
(i) o and o , or
(ii) p and p , where o is any O move and p is any P move and the justification pointers in s are “inherited” from Nominal sequences help make these intuitions formal.
In [14, Lemma 7] a small step version is given and the equality is claimed. With what we have so far, this is a routine inductive argument:
.
We show by induction on :
Rule (smm). By (bmX) if (O and by (bXm) if (P().
Rule (). By (bmX) if (O and by (bXm) if (P().
In both cases the side-condition fa() is valid. Next we show that by induction on and the length of :
Rule (bmX). We use (smm) and () to swap m[] with the leftmost move in . The condition fa() matches the distinctness condition .
Rule (bXm). We use (smm) and () to swap m[] with the rightmost move in .
5.5 Innocence
An important notion in HO games is innocence [19, Definition 5.2], which charac-terises side-effect-free sequential computation. For us this is Definition 5.14 and with the tools we have built so far, it is quite compact: 8
Suppose and are named moves (Definition 2.9). Given HO-legal plays , in , where has even length, ca() atoms( and , there is a unique renaming ) with fa() and ca() such that (). Call : innocent when
In [19, Definition 5.2] Hyland and Ong must write in English about the manip-ulation of pointers, and that this has to be done throughout their work (and this is typical of similar papers). We propose nominal techniques as a way to deal with this quickly and elegantly.
In HO games, moves can be repeated, which leads to a need to identify particular occurrences of moves in sequences. This goes away in our setting because every question or answer is uniquely identified by a name: the coabstracted name that it introduces. So implicit in our framework is a separation of ‘move’ versus ‘occurrence’, removing a significant source of ambiguity. In this paper we have been able to implicitly identify an occurrence of a move in a proto-play with the named move in which the occurrence appears, since coabstracted atoms in proto-plays are distinct (Definition 2.8).
6 Conclusions
We have seen how pointer sequences can be modelled as nominal sequences. Pointers are split into a coabstraction [] corresponding to the head of the arrow, and a (free) atom corresponding to its tail. Unlike pointers, a name carries its identity with it; points to [] wherever we put it.
Furthermore, unlike e.g. numbers, a name is permutatively symmetric, so reindexing / renaming can be expressed at a high level of abstraction. Because of this, nominal sequences are easy to break apart, compose, and reindex.
We have considered some non-trivial operations, like deletion and hereditarily justified sub-sequences; and some important definitions, like strategy composition, asynchronous reordering, and innocence. We have seen how these operations and definitions become straightforward and precise, if we choose the right machinery. This is attractive, but we also believe it will be almost a prerequisite for the kind of mechanised treatment of game semantics that is required for games to be applied in the second author’s research programme.
We have discussed pointer sequences [19,14,23]. In contrast, the Abramsky-Jagadeesan-Malacaria (AJM) games [2] rely on tags instead of pointers. These do not raise the problems of pointers and are fully formalised, but they are a more restricted formalism which was only used for PCF. For languages with effects the flexibility of pointers was required.
Another strategy is to become more abstract: so [5,17,24,21] revise the whole game semantic paradigm per se, in categorical terms. Some readers will instinctively believe that this categorical generalisation obsoletes any concrete realisation, but this is incorrect; there will always be a need for concrete models—especially if we want to implement or mechanise theorems. We seek convenient reformulations of the impressive collection of existing game models to make them more suitable for our intended applications. The work cited above is complementary, but also orthogonal.
Representations of pointer games [18] and games models of nominal languages [20] exist, including work by the second author with others on game semantics for nominal or nominal-related languages [15,1]. However, there has been no nominal repre-sentation of pointer sequences themselves. The closest the literature gets is in the Introduction to [24] where Melliès discusses representing pointers using integer indexes acted on by two group actions.
There is more to this paper than representing pointers. We use atoms in FM sets, which have structure that ZF sets do not. Functions, predicates, and subsets have symmetry (equivariance) properties and apartness (freshness) structure which make it relatively more convenient to handle distinctness conditions (like in Definition 2.8) or to deduce symmetry properties (as in Theorem 5.4), and so on (a very general treatment is in [6, Section 5]).
In this paper, coabstraction is a syntactic token in sequences. We give a denotational intuition how this differs from nominal atoms-abstraction: suppose X is a nominal set with an internal atoms-abstraction []X X written [] (for definitions see [12,7]). Suppose X X is a relation on X. Then (briefly) [] is the least relation such that if and # then [], and [] is the least relation such that if and # then []. This is coabstraction. Nominal terms admit a similar generalisation; we would admit freshness # and cofreshness % conditions. More on this in a later paper.
We can read this paper as an exciting, if only partially articulated, commentary on semantics. The issue of dangling pointers and compositionality has not been properly addressed in the games literature and it remains to understand where the nominal model will take us. The nominal model of this paper exists in a larger context of nominal sets, substitution models, and some sophisticated logical and semantic theory [7,9], including abstract treatments of metavariables and renaming [8,11] and even e.g. trees with pointers [4]; the fruit of applying this theory, remains to be discovered.
Acknowledgements. The first author acknowledges the support of the Leverhulme trust.
References
[1] Samson Abramsky, Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong, and Ian D. B. Stark. Nominal games and full abstraction for the nu-calculus. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 150–159. IEEE Computer Society Press, 2004.
[2] Samson Abramsky, Radha Jagadeesan, and Pasquale Malacaria. Full abstraction for PCF. Information and Computation, 163(2):409–470, 2000.
[3] Samson Abramsky and Guy McCusker. Call-by-value games. In Proceedings of Computer Science Logic (CSL’97), volume 1414 of Lecture Notes in Computer Science, pages 1–17, 1998.
[4] Luca Cardelli, Philippa Gardner, and Giorgio Ghelli. Manipulating trees with hidden labels. In Proceedings of the 6th international conference on Foundations of software science and computational structures (FoSSaCS 2003), pages 216–232, 2003.
[5] Vincent Danos and Russell Harmer. The anatomy of innocence. In Proceedings of the 10th EACSL Annual Conference on Computer Science Logic (CSL 2001), pages 188–202, 2001.
[6] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982– 1011, July 2007.
[7] Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.
[8] Murdoch J. Gabbay. Meta-variables as infinite lists in nominal terms unification and rewriting. Logic Journal of the IGPL, 2012.
[9] Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.
[10] Murdoch J. Gabbay and Vincenzo Ciancia. Freshness and name-restriction in sets of traces with names. In Foundations of software science and computation structures, 14th International Conference (FOSSACS 2011), volume 6604 of Lecture Notes in Computer Science, pages 365–380. Springer, 2011.
[11] Murdoch J. Gabbay and Martin Hofmann. Nominal renaming sets. In Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), pages 158–173. Springer, November 2008.
[12] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, July 2001.
[13] Dan R. Ghica. Applications of game semantics: From software analysis to hardware synthesis. In Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS 2009), pages 17–26, 2009.
[14] Dan R. Ghica and Andrzej Murawski. Angelic semantics of fine-grained concurrency. Annals of Pure and Applied Logic, 151(2-3):89–114, 2008.
[15] Dan R. Ghica and Andrzej S. Murawski. Compositional model extraction for higher-order concurrent programs. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2006), pages 303–317, 2006.
[16] Dan R. Ghica and Nikos Tzevelekos. A system-level semantics. Electronic Notes in Theoretical Computer Science (to appear). Mathematical Foundations of Computer Science XXVIII, Bath, UK, 2012.
[17] Russell Harmer, Martin Hyland, and Paul-André Melliès. Categorical combinatorics for innocent strategies. In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), pages 379–388. IEEE Computer Society, 2007.
[18] Martin Hyland and C.-H. Luke Ong. Pi-calculus, dialogue games and PCF. In FPCA, pages 96–107, 1995.
[19] Martin Hyland and C.-H. Luke Ong. On full abstraction for PCF: I, II, and III. Information and Computation, 163(2):285–408, 2000.
[20] Jim Laird. A game semantics of names and pointers. Annals of Pure and Applied Logic, 151(2- 3):151–169, February 2008. First Games for Logic and Programming Languages Workshop.
[21] Jim Laird, Giulio Manzonetto, and Guy McCusker. Constructing differential categories and deconstructing categories of games. In Luca Aceto, Monika Henzinger, and Jiri Sgall, editors, ICALP (2), volume 6756 of Lecture Notes in Computer Science, pages 186–197. Springer, 2011.
[22] Ondrej Majer, Ahti-Veikko Pietarinen, and Tero Tulenheimo. Games: Unifying Logic, Language, and Philosophy. Springer, 2009.
[23] Guy McCusker. Games and full abstraction for FPC. Information and Computation, 160(1-2):1–61, 2000.
[24] Paul-André Melliès. Asynchronous games 2: The true concurrency of innocence. In Proceedings of the 15th International Conference on Concurrency Theory (CONCUR 2004), pages 448–465, 2004.
[25] Jan Tijmen Udding. A formal model for defining and classifying delay-insensitive circuits and systems. Distributed Computing, 1(4):197–204, 1986.
[26] Christian Urban. Nominal reasoning techniques in Isabelle/HOL. Journal of Automatic Reasoning, 40(4):327–356, 2008.
Notes
1 A general statement of this is the principle of equivariance (see [7, Subsection 4.2], [12, Lemma 4.7]). The principle of equivariance implies that, provided we permute names uniformly in all the parameters of our definitions and theorems, we then get another valid set of definitions and theorems. This is not true of numbers because our mathematical foundation equips numbers by construction with numerical properties such as less than or equal to , which can be defined from first principles with no parameters. So if we use numbers to model pointer sequences then we do not care about because we just needed a countable set of elements, but we repeatedly have to prove that we did not use an asymmetric property like . In contrast, if we assume nominal foundations and use atoms, then we do not have to explicitly prove symmetry because we can just look at our mathematical foundation and note that it is naturally symmetric under permuting names; we reserve numbers for naturally asymmetric activities, such as counting. ↩
2 What is important here is the atom . ↩
3 In [14, p. 7] ‘strictly scoped’ is called fork and ‘strictly nested’ is called join. ↩
4 The function is not a total function because it is not defined on of the form i[] where (i P. However, is defined on all justified , because i[] where (i P is not justified. ↩
5 It is possible to reconcile -conversion with proto-plays, by appending a ‘future permutation’, like so: [. Then [ equals [], not [. This is not needed here. ↩
is a nominal sequence but it might not be a proto-play because coabstracted atoms need not be distinct. Also - need not be legal because naive deletion does not update links. Proposition 3.4 shows that Definition 3.1 calculates and such that if we do these two naive operations together, then we are all right. ↩
7 This is the crux of the proof: because is fresh, changing to [()] does not change whatever we have calculated so far. ↩
8 We use McCusker’s equivalent formulation [23, Subsection 2.2.4]. ↩