A Type Assignment System for Game Semantics ?

A Type Assignment System for Game Semantics ?

Pietro Di Gianantonio, Furio Honsell, Marina Lenisa

aDipartimento di Matematica e Informatica, Universit`a di Udine via delle Scienze 206, 33100 Udine, Italy.

{digianantonio,honsell,lenisa}@dimi.uniud.it

dedicated to Mariangiola, Mario and Simona, on the occasion of their 60

birthdays

Abstract

We present a type assignment system that provides a finitary interpretation of lambda terms in a game semantics model. Traditionally, type assignment systems describe the semantic interpretation of terms in domain theoretic models. Quite surprisingly, the type assignment system presented in this paper is very similar to the traditional ones, the main difference being the omission of the subtyping rules.

Key words: Lambda Calculus, Game Semantics, Type Assignment System

1 Introduction

About twentyfive years ago, Mario Coppo, Mariangiola Dezani, and their group, started to provide logical descriptions of models of λ-calculus, in terms of intersection type assignment systems, [8,10,7,15]. This logical approach was related explicitly to Scott Information Systems in [9], and put on firm categor- ical grounds by Abramsky in [1]. In this paper, we present a logical analysis of game models in the style of intersection types. We feel that it provides new insights both in the semantics of λ-calculus and in the fine structure of game semantics. Thus we show that the idea underpinning intersection types is an outstanding contribution to Theoretical Computer Science, which allows to reap fruitful results in any semantical framework.

? Work partially supported by UE Project IST-CA-510996 Types, and by Italian MIUR Project PRIN 2005015824 ART.

The intersection type approach can be outlined as follows. The semantics of a programming language can be given in two forms: a term can be interpreted either denotationally by a point in a particular domain, or logically by a set of properties. Stone-duality, as presented in [1], establishes an equivalence be- tween these two alternate descriptions for suitable categories of domains. In this approach, properties of terms are normally called “types”. The logical semantics consists of the set of rules, called “type assignment system”, which allow to derive the properties satisfied by a term. Type assignment systems can be seen to provide concrete, finitary approximations of the semantics of a term.

Differently from the standard case, in type assignment systems for game se- mantics, a type cannot describe simply the input-output behavior of a term, but it needs to describe a more detailed interaction of the term with the envi- ronment. In particular, a type t for a term M describes a set of moves that the Proponent and the Opponent may exchange in some phases of the interaction of the term M with the environment. Quite surprisingly, the syntax for stan- dard intersection types is used to describe sets of moves. The game-theoretic perspective is achieved by removing all structural and congruence rules from standard assignment systems. In our framework, no form of weakening rule is present and the types (t₀∧ t₁) ∧ t₂, t₀∧ (t₁∧ t₂), t₀∧ (t₂∧ t₀) are all distinct.

In this paper, we consider the game semantics framework presented by Abram- sky, Jagadeesan and Malacaria in [4], and known as AJM-games. The strate- gies that game intersection types generate are naturally history-free, the ∧ op- erator is used to model the exponential construction, the lack of associativity and commutativity rules for ∧ is connected to the use of indexes to distin- guish different instances of moves in a exponential type. As for AJM-games, it is necessary to introduce a partial equivalence relation on interpretations to recover subject reduction, due to the arbitrariness in the use of indexes.

In this paper, we focus on simply typed λ-calculus. We define a game λ-model in the standard way in a category of games and history-free strategies, and we introduce an intersection-like type system for describing such a game model.

Our approach to game intersection types is “typed”, i.e. intersection types are built inductively over games. The usual untyped intersection semantics can be recovered as a special case of the typed case. As already mentioned, in our setting, types on a game A represent sets of Opponent and Proponent moves on A. The intended meaning of a judgment in our typing system is that a set of equal number of Opponent and Proponent moves appear in the history-free strategy interpreting the term in the given environment. More- over, the moves in this set may be exchanged during the interaction between that term and that environment. The main point which allows to establish a bridge between the intersection-like types that we introduce and game seman- tics is that history-free strategies induce partial functions from Opponent to

Proponent moves, in a Geometry of Interaction (GoI) fashion, [13,2,3]. Un- der this perspective, the most informative judgments are those involving step types, where exactly two moves appear, an Opponent move and the Proponent reaction move in the graph of the partial function defining this strategy. The main result of this paper amounts to the fact that the intersection type se- mantics of a given term in context induces a partial function from Opponent to Proponent moves, which defines the strategy interpreting the term in the game model.

Our approach to game intersection types is quite general. In particular, type assignment systems for GoI combinatory algebras in “particle-style” [3] can be easily derived from game type assignment systems, simply by forgetting the distinction between Opponent and Proponent moves.

Type assignment systems like the one presented in this paper are quite useful in the context of game semantics, since they provide a more concrete and intuitive account of the interpretation of terms w.r.t. categorical game models.

In fact, deriving a concrete definition from a categorical one can be a heavy task.

The problem of giving a concrete and finitary description of game models has been also investigated in [11], where a type assignment system describing the game model of the untyped λ-calculus of [12] has been presented. However, the approach of [11] is different and more directly connected to the representation of strategies as sets of plays and to the categorical combinators involved in the game semantics.

Synopsis. In Section 2, we recall basic notions on games and strategies, we present a new alternative definition of the exponential game, and we discuss the representation of history-free strategies as partial functions. In Section 3, we present syntax and game semantics of the simply typed λ-calculus, which we use as target language. In Section 4, we introduce and study a type as- signment system giving a finitary description of the game model of Section 3.

In Section 5, we establish the connection between the type assignment system and the game model for the simply typed λ-calculus of Section 3. Finally, in Section 6, we discuss further developments.

2 Game Categories

In this section, first we recall basic notions and constructions on games and strategies in the style of [4]. Then, in Section 2.1, we present an alternative construction of the exponential game, which will be useful in order to study

the connections between our typing semantics and the game semantics. To the same purpose, in Section 2.2, we discuss the alternative representation of history-free strategies as partial functions from Opponent to Proponent moves.

The following are the usual definitions of game and strategy in the style of [4]:

Definition 2.1 (Games) A game has two participants: the Proponent and the Opponent. A game A is a quadruple (MA, λA, PA, ≈A) where

• M_A is the set of moves of the game.

• λ_A : M_A → {O, P } × {Q, A} is the labeling function: it tells us if a move is taken by the Opponent or by the Proponent, and if it is a Question or an Answer. We can decompose λ_A into λ^OP_A : M_A → {O, P } and λ^QA_A : M_A → {Q, A} and put λ_A = hλ^OP_A , λ^QA_A i. We denote by ⁻ the function which exchanges Proponent and Opponent, i.e. O = P and P = O. We also denote with λ^OP_A the function defined by λ^OP_A (a) = λ^OP_A (a). Finally, we denote with λ_A the function hλ^OP_A , λ^QA_A i.

• P_Ais a non-empty and prefix-closed subset of the set M_A^~(written as P_A ⊆^nepref M_A^~), where M_A^~ is the set of all sequences of moves which satisfy the fol- lowing conditions:

· s = at ⇒ λ_A(a) = OQ

· (∀i : 1 ≤ i ≤ |s|)[λ^OP_A (s_i+1) = λ^OP_A (s_i)]

· (∀ t v s)[|t  MA^A| ≤ |t  MA^Q|]

where M_A^A and M_A^Q denote the subsets of game moves labeled respectively as Answers and as Questions, s  M denotes the set of moves of M which appear in s and v is the substring relation. P_A denotes the set of positions of the game A.

• ≈_A is an equivalence relation on P_A which satisfies the following properties:

· s ≈_As⁰ ⇒ |s| = |s⁰|

· sa ≈_As⁰a⁰ ⇒ s ≈_A s⁰

· s ≈_As⁰ & sa ∈ P_A⇒ (∃a⁰)[sa ≈_As⁰a⁰]

In the above s, s⁰, t and t⁰ range over sequences of moves, while a, a⁰, b and b⁰ range over moves. The empty sequence is written .

In a position, questions and answers match together like open and closed parentheses in an algebraic expression.

Definition 2.2 (History-free Strategies) A strategy for the Proponent in a game A is a non-empty set σ ⊆ P_A^even of positions of even length such that σ = σ∪dom(σ) is prefix-closed, where dom(σ) = {t ∈ P_A^odd | (∃a)[ta ∈ σ]}, and P_A^odd and P_A^even denote the sets of positions of odd and even length respectively.

A strategy σ for a game A is history-free if it satisfies the following properties:

(1) sab, tac ∈ σ ⇒ b = c

(2) sab, t ∈ σ, ta ∈ P_A ⇒ tab ∈ σ

A strategy can be seen as a set of rules which tells the Proponent which move to take after the last move by the Opponent. History-free strategies are strategies which depend only on the last move by the Opponent.

The equivalence relation on positions ≈_A can be extended to strategies in the following way.

Definition 2.3 Let σ, τ be strategies, σ ≈ τ if and only if (1) sab ∈ σ, s⁰a⁰b⁰ ∈ τ, sa ≈As⁰a⁰ ⇒ sab ≈As⁰a⁰b⁰

(2) s ∈ σ, s⁰ ∈ τ, sa ≈_As⁰a⁰ ⇒ (∃b)[sab ∈ σ] iff (∃b⁰)[s⁰a⁰b⁰ ∈ τ ]

Such an extension is not in general an equivalence relation since it might lack reflexivity. If σ is a strategy for a game A such that σ ≈ σ, we write σ : A.

Game Constructions.

Definition 2.4 (Tensor product) Given games A and B, the tensor prod- uct A ⊗ B is the game defined as follows:

• M_A⊗B = M_A+ M_B

• λ_A⊗B = [λ_A, λ_B]

• P_A⊗B ⊆ M_A⊗B^~ is the set of positions, s, which satisfy the following condi- tions:

(1) the projections on each component (written as s  A or s  B) are positions for the games A and B respectively;

(2) every answer in s must be in the same component game as the matching question.

• s ≈_A⊗B s⁰ ⇐⇒ s  A ≈A s⁰  A, s  B ≈B s⁰  B, (∀i)[si ∈ M_A⇔ s⁰_i ∈ M_A] Here + denotes disjoint union of sets, that is A+B = {(l, a) | a ∈ A}∪{(r, b) | b ∈ B}, and [−, −] is the usual (unique) decomposition of a function defined on disjoint unions.

Definition 2.5 (Linear implication) Given games A and B, the compound game A ( B is defined as follows:

• M_A(B = M_A+ M_B

• λ_A(B = [λA, λB]

• P_A(B ⊆ M_A(B^~ is the set of positions, s, which satisfy the following condi- tions:

(1) the projections on each component (written as s  A or s  B) are positions for the games A and B respectively;

(2) every answer in s must be in the same component game as the matching question.

• s ≈_A(B s⁰ ⇐⇒ s  A ≈As⁰  A, s  B ≈B s⁰  B, (∀i)[si ∈ M_A ⇔ s⁰_i ∈ M_A] Definition 2.6 (Exponential) Given a game A, the game !A is defined by:

• M!A = ω × MA=^P_i∈ωMA

• λ_!A(hi, ai) = λ_A(a)

• P_!A ⊆ M_!A^~ is the set of positions, s, which satisfy the following conditions:

(1) (∀i ∈ ω)[s  Ai ∈ P_Ai];

(2) every answer in s is in the same index as the matching question.

• s ≈_!A s⁰ ⇐⇒ ∃ a permutation of indexes α ∈ S(ω) such that:

· π^∗₁(s) = α^∗(π₁^∗(s⁰))

· (∀i ∈ ω)[π^∗₂(s  α(i)) ≈ π^∗2(s⁰  i)]

where π₁ and π₂ are the projections of ω × M_A and s  i is an abbreviation of s  Ai.

The Game Category G. We define a monoidal closed category G.

Objects: games.

Morphisms: a morphism between games A and B is an equivalence class w.r.t. the relation ≈_A(B of history-free strategies σ : A ( B. We denote the equivalence class of σ by [σ].

Composition: the composition is given by the extension on equivalence classes of the following composition of strategies. Given strategies σ : A ( B and τ : B ( C, τ ◦ σ : A ( C is defined by

σ||τ = {s ∈ (M_A+ M_B+ M_C)^∗ | s  (A, B) ∈ σ & s  (B, C) ∈ τ } τ ◦ σ = {s  (A, C) | s ∈ σ||τ }^even

Identity: the identity id_A: A ( A is defined by idA = {s ∈ P_A^even | s  1 = s  2} .

The game constructions of tensor product and linear implication can be made functorial, in such a way that:

Proposition 2.1 ([4]) The category G is monoidal closed.

However, as it is well-known, G is not cartesian closed.

The Game Category K_!(G). The exponential game construction of Defi- nition 2.6 can be made functorial, by defining, for any strategy σ : A ( B, the strategy !σ :!A (!B by

!σ = {s ∈ P_!A(!B | ∀i ∃s⁰ ∈ σ. (∀s₁, s⁰₁ prefixes of s, s⁰ of the same even length.

(s₁  (A)i = s⁰₁  A & s1  (B)i = s⁰₁  B))}.

Moreover, the exponential can be endowed with a comonad structure (!, der , δ) [4], where for each game A the morphisms der_A: !A ( A and δA : !A ( !!A are defined as follows:

• der_A = [{s ∈ P_!A(A^even | ∀s⁰ even length prefix of s. (s⁰  (!A)₀ = s⁰  A & ∀i 6= 0. s⁰  (!A)i = )}]

• δA = [{s ∈ P_{!A( !!A}^even | ∀s⁰ even length prefix of s. (∀i, j. s⁰  (!A)^c(i,j) = s⁰  (!(!A)_i)_j & ∀k 6∈ codom(c). s⁰  (!A)k = )}], where c is a pairing function, i.e. an injective map c : ω × ω → ω.

Let K_!(G) be the co-Kleisli category over the comonad (!, der , δ), i.e.:

Objects of K_!(G): games.

Morphisms of K_!(G): a morphism between games A and B is an equiva- lence class of history-free strategies for the game !A ( B.

Composition on K_!(G): given strategies σ : A → B and τ : B → C, the strategy τ ◦ σ : A → C is given by the composition in the category G of the strategies σ^†:!A (!B and τ :!B ( C, where σ^† is defined by (!σ) ◦ δ_A.

The following strategies give a commutative comonoid structure on !A, [4]:

• the empty strategy weak_A:!A ( I (weakening), where I = (∅, ∅, {}, {(, )}) is the empty game;

• the contraction strategy con_A:!A (!A⊗!A,

con_A= [{s ∈ P_{!A( !A⊗!A}^even | ∀s⁰ even length prefix of s. ∀i (s⁰  (!A)d(l,i) = s⁰  ((!A)_l)_i & s⁰  (!A)d(r,i)= s⁰  ((!A)r)_i) & ∀j 6∈ codom(d). (s⁰  (A)j = )}], where d is a tagging function, i.e. an injective map d : ω + ω → ω.

Identity on K_!(G): the identity id_A:!A ( A is derA.

Using the above structure, one can define a cartesian product on K_!(G), see [4] for more details:

Proposition 2.2 ([4]) The category K_!(G) is cartesian closed.

Finally, we point out that Propositions 2.1 and 2.2 hold also if, in the defini- tion of games, we abandon the machinery of “questions and answers”, i.e. the bracketing condition. Thus, since for our purposes the bracketing condition is not relevant, in the sequel we will simply focus on games with no ques- tions/answers. This corresponds to consider games where all moves are labeled as questions. In this section we have chosen to present the questions/answers machinery, because this is standard, and also in view of possible extensions of the present work.

2.1 An Alternative Construction of the Exponential Game

In this section, we present an exponential game construction alternative to the standard one of Definition 2.6 above. The new exponential will turn out to be naturally isomorphic to the old one. This alternative definition is motivated by the fact that it makes the connection between moves on games and intersection types more direct.

The new exponential game is built using, in place of ω, a set of indexes I defined by:

Definition 2.7 Let I be the set of all indexes represented by (possibly empty) lists of symbols in {0, 1}.

In the sequel, it will be useful to view indexes in I as paths of a binary tree.

We will denote by !^IA the new exponential game. The main difference between the standard exponential game and the new one lies in the fact that the set of legal positions over the game !^IA is a proper subset of the positions over

!A. Namely, we consider as legal only those positions which use a subset of compatible indexes, in the following sense:

Definition 2.8 (Compatible Subsets of Indexes) Two indexes i, j ∈ I are compatible if neither i is a prefix of j nor j is a prefix of i. A set of indexes J ⊆ I is compatible if, for each i, j ∈ J , i and j are compatible.

Notice that the set of indexes with the compatible relation is a web and the compatible subsets of an index set I form the corresponding coherent space in

the sense of Girard.

For any pair of indexes i, j ∈ I, we can define the composition operation c^I : I × I → I simply as list concatenation. Viewing indexes as paths, the composition operation yields the index corresponding to the path obtained by appending the second path to the first one.

Coherent subsets of indexes have the following relevant property w.r.t. com- position:

Lemma 2.1 For any compatible set J of indexes, and any family of compat- ible sets {K_j}_j∈J, the set {c^I(j, k) | j ∈ J & k ∈ K_j} is compatible.

The above lemma, together with the definition of the legal positions on the game !^IA, will allow us to use the composition operation c^I as pairing function for defining the comonad structure on !^I. Namely, even if c^I is not injective in general, it is injective on compatible sets of indexes. Formally:

Definition 2.9 (Alternative Exponential) Given a game A, the game !^IA is defined by:

• M_!IA= I × M_A=^P_i∈IM_A

• λ_!^I_A(hi, ai) = λ_A(a)

• P_!^I_A⊆ M_!^~IA is the set of positions, s, which satisfy the following conditions:

(1) (∀i ∈ I)[s  Ai ∈ P_Ai];

(2) (every answer in s is in the same index as the matching question;) (3) the set of indexes appearing in the moves of s is compatible.

• s ≈_!IAs⁰ ⇐⇒ ∃ a permutation of indexes α ∈ S(I) such that:

· π^∗₁(s) = α^∗(π₁^∗(s⁰))

· (∀i ∈ I)[π₂^∗(s  α(i)) ≈ π2^∗(s⁰  i)]

The exponential game construction !^I can be naturally lifted to a functor such that:

Proposition 2.3 The exponential functor !^I is naturally isomorphic to the standard exponential functor !.

Proof. Let ι : I → ω be any injective function, e.g.

ι(i) =











0 if i = 

2 ∗ ι(i⁰) + 1 if i = 0i⁰ 2 ∗ ι(i⁰) + 2 if i = 1i⁰

Let ι⁰ : ω → I be any injective function whose codomain is a compatible set of indexes, e.g. ι⁰(i) = 1 . . . 1

| {z }

i

0.

Then ι, ι⁰ induce families of strategies

– σ^ι = {σ_A^ι :!^IA (!A}A, where σ_A^ι = {s ∈ P_!^I_{A( !A}| ∀s⁰ even length prefix of s.

s⁰  (!^IA)_ι(i)= s⁰  (!A)i};

– σ^ι0 = {σ_A^ι0 :!A (!^IA}A, where σ_A^ι0 = {s ∈ P_{!A( !}^I_A| ∀s⁰ even length prefix of s.

s⁰  (!A)ι⁰(i) = s⁰  (!^IA)_i}.

One can show that [σ^ι] and [σ^ι0] are well-defined natural isomorphisms; more- over, one is the inverse of the other. 

As a consequence of the above proposition, the exponential functor !^I can be endowed with a comonad structure (!^I, der^I, δ^I), and, for any game A, the

game !^IA can be endowed with a commutative comonoid structure (!^IA, con^I_A, weak^I_A).

For our purposes, it is useful to give explicit definitions of the morphisms der^I_A, δ_A^I, con^I_A, as equivalence classes of special strategies:

• der^I_A = [{s ∈ P_!^evenIA(A | ∀s⁰ even length prefix of s. (s⁰  (!^IA)_ = s⁰  A & ∀i 6= . s⁰  (!^IA)_i = )}]

• δ_A^I = [{s ∈ P_!^evenIA( !^I!^IA | ∀s⁰ even length prefix of s. (∀i, j. s⁰  (!^IA)_c^I_(i,j) = s⁰  (!^I(!^IA)_j)_i & ∀k 6∈ codom(c^I). s⁰  (!^IA)_k = )}], where c^I : I × I → I is the composition function defined above;

• con^I_A = [{s ∈ P_!^evenIA( !^IA⊗!^IA | ∀s⁰ even length prefix of s. ∀i. (s⁰  (!^IA)0i = s⁰  ((!^IA)_l)_i & s⁰  (!A)1i = s⁰  ((!^IA)_r)_i & s⁰  (!^IA)_ = )}].

Notice that δ_A^I is well defined by Lemma 2.1, and the tagging function d^I : I + I → I is implicitly defined by d^I(l, i) = 0i and d^I(r, i) = 1i.

From now on, we will use the symbol ! to refer to the standard or to the new exponential, indifferently. We will state it explicitly, when the new exponential comes into play.

2.2 History-free Strategies as Partial Functions

Following Definition 2.2 of Section 2, strategies are usually represented as trees, where each path corresponds to a position of the strategy. As shown in [4], history-free strategies admit also an alternative presentation as partial functions from Opponent to Proponent moves, which will be quite useful in the sequel. In this section, we study in detail such presentation. The representation of history-free strategies as partial functions will be exploited in the sequel of this paper, where a type assignment system is introduced and its connections with the game semantics are studied.

Following [4]:

Definition 2.10 Let σ be a history-free strategy. We define a partial function

f_σ : M_O^A* M_P^A by

f_σ(a) = b iff ∃s ∈ P_A. sab ∈ σ .

Vice versa, let f_σ : M_O^A * M_P^A, we define inductively the set traces(f ) as follows:

 ∈ traces(f )

s ∈ traces(f ) & sa ∈ P_A & f (a) = b =⇒ sab ∈ traces(f ).

We say that f induces the strategy σ_f = traces(f ), if traces(f ) ⊆ P_A.

Proposition 2.4 If f : M_O^A * M_P^A is a partial function inducing a strategy σ_f on A, then σ_f is history-free.

Notice that, for any partial function f , we have f_σf ⊆ f , while for any strategy τ , we have σ_fτ = τ . Thus there is always a least partial function on moves canonically inducing a history-free strategy.

Using the representation of strategies as partial functions, the morphisms from A to B on the category G are represented by partial functions f : M_A^P+M_B^O * M_A^O+ M_B^P. Such functions can be written as matrixes:

f =







f11 f12

f₂₁ f₂₂







where

f₁₁ : M_A^P * M_A^O f₁₂ : M_B^O * M_A^O f₂₁ : M_A^P * M_B^P f₂₂ : M_B^O * M_B^P Functions such as f above are amenable of a useful geometrical description in terms of “boxes and wires”, [2,3], as in Fig. 1(i).

The composition on the category G can be equivalently expressed in terms of the representation of strategies as partial functions as follows. Let f : M_A^P + M_B^O* M_A^O+M_B^P, g : M_B^P+M_C^O * M_B^O+M_C^P representing strategies, then f, g are composed in such a way that Proponent moves in B under σ get turned into Opponent moves in B for τ , and vice versa. Geometrically, we have the picture in Fig. 1(ii).

Algebraically, the composition of f and g is obtained via a Girard’s Execution Formula, see [4] for more details.

The application morphism app_A,B : (A ( B) ⊗ A ( B determined by the monoidal closed structure on G is induced by the isomorphism

((M_A^O+ M_B^P) + M_A^P) + M_B^O' ((M_A^P + M_B^O) + M_A^O) + M_B^P .

? Q

Q Q

?







(i) f11

f12

f22

f21

?

?

M_B^O

M_B^P M_A^P

M_A^O

? ?

(ii)

? ?

? ?

? ?

 -

A

A A

A A

A A

A

M_B^O

M_B^P

M_B^P

M_B^O M_A^P

M_A^O

M_C^O

M_C^P

Fig. 1. Geometrical description of strategies and strategy composition.

? ?

M_B^O M_A^P

fσ

? ?

M_B^P M_A^O

M_A^P f_τ

Fig. 2. Geometrical description of application on G.

Geometrically, the application of two strategies σ : A ( B and τ : A, i.e.

app_A,B◦ (σ ⊗ τ ) is represented as in Fig. 2.

In view of studying the connections between our type semantics and the game semantics, it is useful to give an explicit description of the application of two strategies, σ :!C ( (!A ( B) and τ :!C ( A, in the category K!(G). The application of σ, τ in K_!(G), i.e. ev ◦hσ, τ i, coincides (up-to ≈) with the strategy obtained by the following composition on the category G: app_A,B◦(σ⊗τ^†)◦con_C (see [4] for more details).

In Fig. 3 appears the geometrical description of the strategy resulting from the application of strategies σ, τ , represented by partial functions f_σ : M_!C^P + (M_!A^P + M_B^O) → M_!C^O + (M_!A^O + M_B^P) and f_τ : M_!C^P + M_!A^O → M_!C^O + M_!A^P. The final box (dash box in figure) represents a two-input/two-output function f : M_!C^P + M_B^O → M_!C^O + M_B^P. If the input enters through the wire M_B^O, then it is directly sent to f_σ, otherwise, if the input enters through the wire M_!C^P, then the contraction conC acts where the • appears, by sending the token either to f_σ or to f_τ^†, depending on the index of the move. Once the token is sent to f_σ or f_τ^†, it can possibly cycle along the wires M_!A^O and M_!A^P, and finally it exists either from the box fσ (through the wire M_!C^O or M_B^P) or from the box f_τ (through the wire M_!C^O). The contraction merges the outputs coming from the wires M_!C^O of f_σ and f_τ^† where indicated.

?s

M_!C^P M_B^O

M_B^P

?

? ?

? -

M_B^O M_!A^P

M_!C^P fσ

?

?

?

?

?

M_B^P M_!A^O M_!C^O

M_!C^P

M_!A^P M_!C^O

M_!C^O f_τ^†

? s ?

Fig. 3. Geometrical description of application on K_!(G).

3 The Simply Typed λ-calculus

In this section we recall the syntax of the simply typed λ-calculus with two ground constants, ⊥, >, and we introduce a game model for such calculus. In Section 4, we will introduce a finitary description of this game model, based on a typed assignment system.

Definition 3.1 The class SimType of simple types over a ground type o is defined by:

(SimType 3) A ::= o | A → A .

Raw Terms are defined as follows:

Λ 3 M ::= ⊥ | > | x | λx^A.M | M M ,

where ⊥, > ∈ Const are ground constants, x ∈ Var. We denote by Λ⁰ the set of closed λ-terms.

Well-typed terms. We introduce a proof system for deriving typing judge- ments of the form Γ ` M : A, where Γ is a type environment, i.e. a finite list x₁ : A₁, . . . , x_k : A_k. The rules of the proof system are the following:

Γ ` C : o Γ, x : A, Γ<sup>0</sup> ` x : A

Γ, x : A ` M : B Γ ` λx^A.M : A → B

Γ ` M : A → B Γ ` N : A Γ ` M N : B

where C ∈ {⊥, >}.

β-conversion. β-conversion between well-typed terms is the least relation gen- erated by the following rule and the rules for congruence closure (which we omit):

Γ ` (λx<sup>A</sup>.M )N = M [N/x] : B, where Γ, x : A ` M : B, and Γ ` N : A.

3.1 A Game Model

We define a game model for the λ-calculus of Definition 3.1 in the cartesian closed category K_!(G). Simple types are interpreted by the hierarchy of games over the following Sierpinski Game (without questions/answers):

Definition 3.2 (Sierpinski Game) The game O is defined as follows:

• MO = {∗, a}

• λO(∗) = O λO(a) = P

• PO = {, ∗, ∗a}

• ≈O= id_PO

The only two strategies on the Sierpinski Game are the empty strategy, which we denote by ⊥O, and the strategy >Oinduced by the partial function f>O(∗) = a. More in general, we denote by ⊥_!A1⊗...⊗!A_k(O the empty strategy on !A₁⊗ . . . ⊗!A_k ( O, and by >!A1⊗...⊗!Ak(Othe strategy induced by f_>!A1⊗...⊗!Ak(O(hr, ∗i) = hr, ai.

Types are interpreted by games over the hierarchy on the Sierpinski game.

Terms in contexts are interpreted as strategies in the usual way, i.e. x₁ : A1, . . . , xk : Ak ` M : A is interpreted as a strategy on the game ![[A1]]^G ⊗ . . . ⊗![[A_k]]^G ( [[A]]^G using standard categorical combinators as follows:

Definition 3.3 (Term Interpretation)

• [[x1 : A1, . . . , xk : Ak` ⊥ : o]]^G = ⊥

![[A₁]]^G⊗...⊗![[A_k]]^G([[A]]^G

• [[x₁ : A₁, . . . , x_k : A_k` > : o]]^G = >

![[A₁]]^G⊗...⊗![[A_k]]^G([[A]]^G

• [[x₁ : A₁, . . . , x_k : A_k` x_i : A_i]]^G = π_i :![[A₁]]^G⊗ . . . ⊗![[A_k]]^G ( [[A]]^G

• [[Γ ` λx<sup>A</sup>.M : A → B]]<sup>G</sup> = Λ([[Γ, x : A ` M : B]]^G)

• [[Γ ` M N : B]]<sup>G</sup> = ev ◦ h[[Γ ` M : A → B]]^G, [[Γ ` N : A]]^Gi where πi denotes the i-th projection.

Notice that, by abuse of notation, we have used the same symbols A, B, . . . to denote simple types and the games interpreting them.

4 The Type Assignment System

In this section, we introduce and study a type assignment system, which gives a finitary description of the game model of Section 3.1. The types involved are essentially the standard intersection types, where the intuitionistic arrow is substituted by the linear arrow type constructor, and the structural rules are missing. Our approach to intersection types is “typed”, i.e. intersection types are built inductively over games. The usual untyped intersection semantics can be recovered as a special case of the typed case (see Section 6 below for more details). In our setting, types on a game A represent sets of Opponent and Proponent moves on A. The judgments derivable in our typing system are of the shape x₁ : t^!A1, . . . , x_k : t^!Ak ` M : t^!A, whose intended meaning is to represent a set of equal number of Opponent and Proponent moves.

We will show that, for each Opponent move in such a set, there will be a corresponding Proponent answer such that the pair of moves belongs to the graph of the strategy interpreting the term.

4.1 Types and Environments

For each game A, we define the set of corresponding intersection types. At this stage, a type on A simply represents a set of moves on the game A. The intersection type constructor is used to represent sets of moves on exponential games, i.e. the moves appearing in each ∧-component correspond to moves in different components of the exponential game. This is why the ∧ constructor is not commutative neither associative nor idempotent. In Section 5, the exact correspondence between types and games is established.

Definition 4.1 (Types) We define a family of intesection type sets IntType^A, by induction on the structure of the game A via the following abstract syntax:

• Types on Sierpinski game:

t^O ::= c^O_∅ | c^O_{∗} | c^O_{a} | c^O_{∗,a}

• Types on linear arrow games:

t^A(B ::= t^A ( t^B

• Types on exponential games:

t^!A ::= t^A | t^!A∧ t^!A

In what follows, we use the symbols t^A, u^A, v^Ato denote elements in IntType^A, and we simply write t in place of t^A, when the game is irrelevant.

We use the symbols c^A(B_∅ and c_∅^!A to denote, respectively, the types c^A_∅ ( c^B∅

and c^A_∅ (which, in particular, is a type on !A). Moreover, we endow the set of types with the equivalence relation induced by c^A_∅ = c^A_∅ ∧ c^A_∅.

When related to game semantics, types represent sets of moves, in the sense presented by the following definitions. First, we define a subclass of types representing a single move. Informally, a single-move type is a type whose term structure contains a single instance of one of the two constant c^O_{a}, c^O_{∗}, while all the other instances of basic constants are in the form c^A_∅. We mark single-move types as Proponent or Opponent types, mimicking the usual game semantic definitions.

Definition 4.2 (Single-move Types) We distinguish between types where the only move is a Proponent move (p^A) and types where the only move is an Opponent move (o^A). The definition of the family of sets SingleType^A, single-move types on A, is by induction on the game A:

p^O ::= c^O_{a}

o^O ::= c^O_{∗}

p^A(B ::= c^A_∅ ( p^B | o^A( c^B∅

o^A(B ::= c^A_∅ ( o^B | p^A ( c^B∅

p^!A ::= p^A | p^!A∧ c^A_∅ | c^A_∅ ∧ p^!A o^!A::= o^A | o^!A∧ c^A_∅ | c^A_∅ ∧ o^!A

In what follows, we will use the symbol m^A to denote a single-move type p^A or o^A, indifferently.

Any intersection type can be seen as the union of single-move types by the following definition:

Definition 4.3 The family of functions S^A: IntType^A → ℘(SingleType^A) are defined, with some abuse of notation, by induction as follows:

S^A(c^A_∅) = ∅

S^A(t^A) = {t^A} if t^A∈ SingleType^A S^O(c^O_{∗,a}) = {c^O_{∗}, c^O_{a}}

S^A(B(t^A ( u^B) = (c^A_∅ ( S^B(u^B)) ∪ (S^A(t^A) ( c^B∅) S^!A(t^A) = S^A(t^A)

S^!A(t^!A∧ u^!A) = (c^A_∅ ∧ S^!A(u^!A)) ∪ (S(t^!A) ∧ c^A_∅)

where the symbols ( and ∧ on the righthand side of the equations denote the pointwise application of the corresponding constructors to a set.

As a curiosity, notice that, for any game A, the set {S(t^A)|t^A ∈ IntType^A} is the set of finite elements of a coherent space built on a web having SingleType^A as set of elements. The coherence relation on single-move types is related and similar to the compatible relation on indexes presented in Definition 2.8.

Loosely speaking, two single-move types are coherent if the corresponding expression trees are not included one into the other.

Given the above correspondence between types and sets of moves, it is natural, and for our purpose useful, to introduce on types some of the basic notions on sets.

Definition 4.4

• We say that a type t^A contains the single-move type u^A if u^A∈ S^A(t^A).

• We define the cardinality of a type t^A as the cardinality of the set S^A(t^A).

• We say that two types t^Aand u^Aare disjoint, if the sets S^A(t^A) and S^A(u^A) are disjoint.

• We define a family of partial union operations on types, {]A}A, ]A: IntType^A→ IntType^A, as follows:

t^A₁ ] t^A₂ =







u^A if S^A(t^A₁) ∪ S^A(t^A₂) = S^A(u^A) undefined if there is no such a u^A

If t ] u is defined, we say that t and u are compatible.

Notice that the union operations ]_A are well-defined, since it is easy to check that, if the union of two single-move types correspond to an intersection type u^A, then u^A is unique. Alternatively, the partial union operations can be more explicitly characterized as follows:

Lemma 4.1 The operations ]_A : IntType^A→ IntType^Aare the least partially defined functions satisfying:

c^O_X ]Oc^O_Y = c^O_X∪Y

(t^A₁ ( t^B2) ]_A(B (u^A₁ ( u^B2) = t^A₁ ]Au^A₁ ( t^B2 ]Bu^B₂ (t^!A₁ ∧ t^!A₂ ) ]_!A(u^!A₁ ∧ u^!A₂ ) = (t^!A₁ ]_!Au^!A₁ ) ∧ (t^!A₂ ]_!Au^!A₂ ) Notice that, for any A, c^A_∅ ] t^A= t^A.

To recover the history-free strategy corresponding to a term, it is useful to introduce a subclass of types consisting of exactly two moves, an Opponent move and a Proponent one. Namely, such types will represent pairs in the graph of a partial function describing a history-free strategy.

Definition 4.5 The Step types on the game A (StepType^A) are the types that can be obtained as union of a Proponent and an Opponent single-move type:

s^A::= p^A] o^A .

Lemma 4.2 Step types can be characterized by induction on games as follows:

s^O ::= c^O_{∗,a}

s^A(B ::= p^A( p^B | o^A( o^B | c^A_∅ ( s^B | s^A( c^B∅

s^!A ::= s^A | s^!A∧ c^A_∅ | c_∅^A∧ s^!A | p^!A∧ o^!A | o^!A∧ p^!A

Definition 4.6 (Environments) • Let x^A1, x^A2, . . . be a list of variables with domains A₁, A₂, . . ., ranging over simple types.

Environments are lists defined by:

Γ, ∆ ::=  | x^A: t^!A, Γ₁

where x^A does not appear in Γ₁ and, by abuse of notation, x^A : t^!A is used in place of x^A: t^![[A]]G.

We will simply write x in place of x^A, when the game is irrelevant.

• Let dom(Γ) denote the list of variables in the domain of Γ, i.e., if Γ = [x^A1 : t^!A1, . . . , x^Ak : t^!Ak], then dom(Γ) = [x^A1, . . . , x^Ak].

• Let Γ_∅ denote a generic environment, where all types are c_∅.

• Let Γ, Γ⁰ be contexts such that dom(Γ) = dom(Γ⁰). We define the disjoint union context Γ ] Γ⁰ (the intersection context Γ ∧ Γ⁰) as the pointwise ap- plication of the ] (∧) operation to the types in the contexts.

4.2 The Typing System

We introduce a typing system for deriving judgments of the shape x₁ : t^!A1, . . . , xk : t^!Ak ` M : t^!A, whose intended meaning is to represent a set of equal number of Opponent and Proponent moves. If the main connective of t^!A is not ∧, then, for each Opponent move in such a set, there is a corresponding Proponent answer such that the pair of moves belongs to the graph of the strategy interpreting the term. The most informative judgments are those involving step types, where exactly two moves appear, an Opponent move and the Proponent answer. When the type contains more than two moves, we lose the exact matching between Opponent and Proponent moves. In principle, step types would be sufficient to recover the strategy interpreting the term in the game model, however, it is useful to consider general types in the type assignment system, because this simplifies the presentation of the rule for application.

Definition 4.7 (Typing System) The typing rules for deriving judgments x^A1 : t^!A1, . . . , x^Ak : t^!Ak ` M : t^!A are almost the standard ones, i.e.:

Γ_∅ ` C : c^O_∅ (∅)

Γ∅ ` > : c^O_{∗,a} (>)

Γ∅, x^A: t^A, ∆∅ ` x<sup>A</sup>: t<sup>A</sup> (var) Γ ` M : t^A₁ ∆ ` M : t^A₂

Γ ∧ ∆ ` M : t<sup>A</sup><sub>1</sub> ∧ t<sup>A</sup><sub>2</sub> (intersection) Γ, x<sup>A</sup>: u<sup>!A</sup>, ∆ ` M : t^B t^B not a ∧-type

Γ, ∆ ` λx<sup>A</sup>.M : u<sup>!A</sup> ( t<sup>B</sup> (abs) Γ ` M : u^A( t^B ∆ ` N : u^A

Γ ∧ ∆ ` M N : t^B (app)

where C ∈ {⊥, >} and a ∧-type is a type whose main constructor is ∧.

In what follows, we will simply drop game tags from variables and types in the judgments, when the game is not relevant.

In the rest of this section, we study basic properties of the typing system.

The following definition will be useful:

Definition 4.8

• The type associated to a judgement x^A1 : t^!A1, . . . , x^Ak : t^!Ak ` M : t is the type of its curryfication i.e. the type t^!A1 ( (. . . ( (t^!Ak ( t) . . .)

• The cardinality of a judgment is the cardinality of the associated type.

• A step judgment is a judgment whose associated type is a step type.

• A ∧-judgment is a judgment Γ ` M : t^A where A is a ∧-type, i.e. the main constructor of t^A is ∧.

• A non-∧ judgment is a judgment that is not a ∧-judgment.

• Two judgments Γ ` M : t and Γ<sup>0</sup> ` M : u are compatible ( disjoint) if their associated types are compatible (disjoint).

• We say that a judgment contains a single-move type t^A if the associated type contains t^A.

The single move types contained in the conclusion of a typing rule are inherited from the single-move types contained in the premises. However, when moving from a premise to the conclusion, a single-move type partly changes its term structure. For example, when applying the (app) rule to premises x : c^C_∅ ` N : u<sup>A</sup> and x : t<sup>C</sup> ` M : u^A( t^B, where the latter contains the single-move type m^C ( c^A(B∅ , we obtain a conclusion containing the single-move type m^C ∧ c^C_∅ ( c^B∅. In the sequel of this paper, to avoid irrelevant details, we will be a little sloppy in the notation, and we denote with the same symbols single-move types appearing in premises and the corresponding single-move types in the conclusions.

Lemma 4.3 All judgments derivable in the typing system have even cardinal- ity. All derivable judgments contain equal number of Proponent and Opponent single-move types.

Proof. Straightforward, by induction on derivations. 

The following lemma collects a number of technical properties of the typing system. In particular, items (ii) and (iii) will be useful to prove Proposition 4.1 below, which expresses the fact that all derivable judgments can be “decom- posed” in step judgments. The most technical part of Lemma 4.4 below is item (v), which amounts to the counterpart in the typing system of the application between strategies as described in Section 2.2, Fig. 3.

Lemma 4.4

(i) If x^A1 : t^!A₁ ¹, . . . , x^Ak : t^!A₁ ^k ` M : t<sub>1</sub> and x<sup>A1</sup> : t<sup>!A</sup><sub>2</sub> <sup>1</sup>, . . . , x<sup>Ak</sup> : t<sup>!A</sup><sub>2</sub> <sup>k</sup> ` M : t₂ are derivable non-∧ step judgments, containing the single-move types m₁, m⁰₁ and m₂, m⁰₂, respectively, then

• m₁ = m₂ iff m⁰₁ = m⁰₂.

• m₁ is compatible with m₂ if and only if m⁰₁ is compatible with m⁰₂.

(ii) For any set {Γ_i ` M : t<sub>i</sub>|i ∈ I} of pairwise compatible non-∧ step judg- ments, the judgment <sup>U</sup><sub>i∈I</sub>Γ<sub>i</sub> ` M :^U_i∈It_i is derivable.

(iii) For any derivable non-∧ judgment Γ ` M : t, there exist decompositions of t and Γ in types t<sub>1</sub>, . . . t<sub>n</sub> and environments Γ<sub>1</sub>, . . . , Γ<sub>n</sub> such that t =<sup>U</sup><sub>i</sub>t<sub>i</sub>, Γ =<sup>U</sup><sub>i</sub>Γ<sub>i</sub>, and Γ<sub>i</sub> ` M : t_i are derivable step judgments, for all i = 1, . . . , n.

(iv) Items (i)–(iii) hold also for ∧-judgments.

(v) Given any pair of judgments Γ ` M : u ( t and ∆ ` N : u, and any single-move type m contained in the judgment Γ ∧ ∆ ` M N : t, there exist a single-move type m<sup>0</sup> contained in Γ ∧ ∆ ` M N : t and a chain of single-move types hu_ji_j∈J contained in u such that

• J is an interval of integers.

• If the chain is empty, then there exists a judgement either in the form Γ ` M : c<sub>∅</sub> ( t, or ∆ ` N : c∅, containing the single-move types m and m⁰.

• If the chain is non-empty, then

· either there exists a step judgment Γ₁ ` M : u<sub>1</sub> ( t1 containing m, and the first element in J is 1 or there exists a step judgement ∆<sub>0</sub> ` N : u₀ containing m, and the first element in J is 0.

· Γ∅ ` M : (u_2k ( c^∅) ] (u_2k+1 ( c^∅), for all 2k, 2k + 1 ∈ J , k ≥ 0.

· ∆_∅ ` N : u_2k+1] u_2k+2, for all 2k + 1, 2k + 2 ∈ J , k ≥ 0.

· Either there exists a step judgment Γ_2k ` M : u<sub>2k</sub> ( t<sup>0</sup>2k containing m<sup>0</sup> and the last element in J is 2k or there exists a step judgement ∆<sub>2k+1</sub> ` N : u_2k+1 containing m⁰ and the last element in J is 2k + 1.

Proof. First we define the complexity of a term M as the number of con- structors appearing in it. The proof of items (i)–(v) is by induction on the complexity of the terms M and N .

Basic cases: M and N have complexity 1.

• The term M is a constant: items (i)–(iii) and (v) are trivial, since the only rules usable in the derivations are the rules (∅) and (>).