HTML reading edition · 16 source pages · Open the source PDF

Leaving the Nest: Nominal techniques for variables with interleaving scopes

Murdoch J. Gabbay1, Dan R. Ghica2, and Daniela Petrişan3

1 Heriot-Watt Univesity, UK 2 University of Birmingham, UK 3 Radboud University, Netherlands

Abstract

We examine the key syntactic and semantic aspects of a nominal framework allowing scopes of name bindings to be arbitrarily interleaved. Name binding (e.g. λx.M) is handled by explicit name-creation and name-destruction brackets (e.g. ⟨xMx⟩) which admit interleaving. We define an appropriate notion of alpha-equivalence for such a language and study the syntactic structure required for alpha-equivalence to be a congruence. We develop denotational and categorical semantics for dynamic binding and provide a generalised nominal inductive reasoning principle. We give several standard synthetic examples of working with dynamic sequences (e.g. substitution) and we sketch some preliminary applications to game semantics.

1998 ACM Subject Classification D.3.1 Formal Definitions and Theory

Keywords and phrases nominal sets, scope, alpha equivalence, dynamic sequences

Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p

1 Introduction and motivation

In the syntax of formal languages it is common to see names created by locally-scoped operators such as λa.(st) and ∀a.(φ⇒ψ). The binders λ and ∀ have scope from the left-hand ( to the matching right-hand ) and scope is determined at the site of binding in the structure of the term. However, dynamically-scoped binding is an often encountered phenomena occurring whenever resources are allocated and freed explicitly. The most common situation is that of memory in C-like languages, but this also applies to other resources such as opening and closing files or network sockets. In general, a physical resource will be handled using a name which can be used by the program. The choice of name, between the allocation and the release of the resource, is irrelevant, leading to notions similar to binding and α-equivalence, but more finely grained, to account for possible scope interleaving.

Nominal techniques [15, 12, 24] provide a state-of-the-art formalism for reasoning about abstract syntax with statically-scoped binding. However, existing techniques do not accommodate syntax with dynamically-scoped binding. This paper addresses this issue by introducing a syntactic notion of dynamic sequences and suitable denotational and categorical models.

In dynamic sequences, scope is managed by name-creation and name-destruction brackets ‘create a’ and ‘destroy a’, written as ⟨a and a⟩, respectively. These may be interleaved and need not match up; ⟨a⟨ba⟩b⟩, ⟨a⟨bb⟩a⟩, and indeed just ⟨a and a⟩ are perfectly valid sequences. In the special case of a well-matched name-creation/-destruction pair the theory specialises back to something that models nominal-style atoms-abstraction. For instance, ⟨aaa⟩, just as the nominal atoms-abstraction [a]a, models the α-equivalence behaviour of λa.a.

To define a mathematically well-behaved notion of α-equivalence, the basic notions of free and bound names require generalisation, and a notion of freshness arity emerges (Sec. 2), generalising the freshness side-conditions of nominal terms. In Sec. 3 we provide a relational semantics for dynamic sequences and in Sec. 4 we take stock of the monoid structure on dynamic sequences. We give an equational axiomatisation for a notion of dynamic binding monoid, that is, a monoid equipped with compatible nominal set structure and with left and right binders. We then prove that dynamic sequences form a free such dynamic binding monoid and obtain as a corollary a structural induction principle and a simpler characterisation for the α-equivalence relation.

Dynamic sequences have a ‘flat’ monoid structure, as opposed to the syntax trees one encounters in nominal abstract syntax. We use this ‘flatness’ to our advantage, as it allows us to interpret the non-hierarchical structure of interleaved scope. Thus one interpretation of dynamic sequences is as the structures used in game semantics. As an application, Sec. 6 gives a resource-sensitive formulation of pointer sequences as used in game semantics. We conclude in Sec. 7 with an overview of related work and directions for future research.

2 Dynamic sequences

2.1 Preliminaries

Let 𝔸 be a countably infinite set of names or atoms. Given a bijection (permutation) π : 𝔸 →𝔸 define its support by supp(π) = {a ∈𝔸 | πa ≠ a}. Write Perm(𝔸) for the set of all permutations with finite support. Write ι for the identity permutation and (a b) for the swapping or transposition of a and b.

If X is a set with a Perm(𝔸)-action, write this action infix as −·−. An element x ∈X is supported by A ⊆𝔸 when for all π ∈ Perm(𝔸), ∀a ∈A.πa = a implies π·x = x. Given π ∈ Perm(𝔸) and x ∈X, we say that π fixes x when π·x = x. A nominal set is a set with a Perm(𝔸)-action where every element x has finite support. It is a fact that if X is a nominal set then every x ∈X has a least finite support, which we write supp(x).1 We are interested in elements with finite support. If a ∈𝔸 such that a ∉ supp(x) we write a#x. If X, Y are sets with Perm(𝔸)-action, call f : X →Y equivariant when f(π·x) = π·(fx) for every π ∈ Perm(𝔸) and x ∈X. Finally, if φ(c) is a predicate on names, write Иc.φ for “φ(c) holds for all but finitely many c ∈𝔸”; this is the NEW-quantifier and we may read it as “for fresh c, φ(c)”. For more on the theory above see [15, 12, 24].

Definition 1

Fix disjoint sets 𝔸 of atoms and 𝕂 of constants, writing a, b, c ∈𝔸 and k ∈𝕂. Define sets 𝕋 of tokens and RSeq of raw sequences, writing m ∈𝕋 and e ∈ RSeq, inductively by: m ::= a | a⟩| ⟨a | k, e ::= ε | em.

RSeq is equivalently the set of lists of tokens and is the free monoid on 𝕋. The set 𝕂 can be equipped with a trivial Perm(𝔸)-action: every permutation fixes all the elements of 𝕂. The permutation actions on 𝔸 and 𝕂 can be extended pointwise on the elements of raw sequences; for instance, (c a)·cc⟩b⟩a⟩⟨c = aa⟩b⟩c⟩⟨a. Then RSeq is a nominal set and the support of a sequence is the set of names occurring in it. The set RSeq also has a monoid structure given by concatenation, which is compatible with the permutation action (monoid multiplication is equivariant and ε has empty support and thus is fixed by all permutations.)

Our notation and terminology suggest we should read the raw sequence ⟨aaa⟩ as “create a, use a (in some manner), then destroy it”—so if we assume a constant λ ∈𝕂 then λ⟨aaa⟩ shall, informally, model the syntax λa.a.

We can call the binding of raw sequences, which we will make formal shortly, dynamic in the sense that scope is not determined by a single binder but by bracket-pairs; ⟨a does not ‘know’ where its matching a⟩ is, or vice versa, and indeed ⟨a on its own and unpaired with any a⟩ is also a valid raw sequence, as are a⟩, ⟨aa⟨aaa⟩, and so forth.

We endow raw sequences with a binding structure using the following ideas, which will be illustrated in Ex. 6:

Bound: An atom is bound if it is in the scope of a creation well-paired with a destruction.

Created: An atom may appear following a creation operation which is not followed by a matching destruction.

Destructed: Conversely, a destruction operation may appear without a matching creation.

Free: An atom may be used without being created or destructed.

An atom occurrence cannot be characterised as merely ‘free’ or ‘bound’, but we need the more refined notion of freshness arities. We define a freshness arity as an element of a monoid B, which we call the binding monoid, and which is the free monoid over carrier {c, f, d} modulo the following equations:

f·f = f absorption (1)c·f = c pre-absorption (2)f·d = d post-absorption (3)c·d = ε cancellation (4)

The freshness arity is assigned by a monoid homomorphism Fa: RSeq →B defined by:

Fa = {⟨a↦ →c, ⟨b↦ →ε, a↦ →f, b↦ →ε, a⟩↦→d, b⟩↦→ε, k↦ →ε} where (a ≠ b ∈𝔸, k ∈𝕂).

The set of finitely supported functions denoted by B𝔸 has a nominal monoid structure, with the multiplication of functions defined pointwise. The proof of the next lemmas is immediate.

Lemma 2

The map F : RSeq →B𝔸 defined by e↦ →λa.Fa(e) is an equivariant monoid morphism.

Lemma 3

For any β ∈B there are unique m, p ∈ℕ and n ∈{0, 1} such that β =B dm· fn· cp.

Definition 4

Call the unique representation of β ∈B its normal form.

Definition 5

Given a sequence e and a name a it is helpful to introduce some notational shortcuts regarding the arity of a in e:

We write ae when Fae = dm· fn, for some m, n ∈ℕ, i.e. there are no pending unmatched name creations ⟨a in e.

We write ae when Fae = fn· cm, for some m, n ∈ℕ, i.e. there are no pending unmatched destructors a⟩ in e.

We write ae, and call a balanced in e, when ae ∧ae. That is, there are no un-matched a-creations or a-destructions, so any occurrence of a is, informally, either ‘bound’ (Fae = ε) or ‘free’ (Fae = f) in the conventional sense.

•• •• • • • • •• • • • •••• •• •• • • • • •• •• • • • • • ••• • • •
Figure 1 Pointer sequence illustration of dynamic sequences with Fa(e) = ε
Example 6

Here are some 3-long sequences involving atom a, showing various arities.

Fa(⟨a⟨a⟨a) = c3Fa(a⟩⟨a⟨a) = dc2Fa(⟨aa⟩a⟩) = d Fa(a⟩aa⟩) = d2Fa(a⟩a⟩a) = d2f Fa(aaa) = fFa(⟨aa⟩a) = f Fa(⟨aaa⟩) = ε

2.2 α-equivalence

The pairing of atom creation and atom destruction operations creates a phenomenon similar to binding. The concrete choice of a name, between its creation and its destruction, should not matter. This leads directly to a dynamic version of the α-equivalence relation, illustrated by the following examples and non-examples.

⟨aa⟩⟨bb⟩=α ⟨aa⟩⟨aa⟩ (5)⟨a⟨ba⟩b⟩=α ⟨b⟨cb⟩c⟩ (6)⟨a⟨aa⟩a⟩=α ⟨b⟨cc⟩b⟩ (7)⟨a⟨ca⟩⟨bc⟩b⟩=α ⟨a⟨ca⟩⟨ac⟩a⟩ (8)⟨a⟨bba⟩b⟩≠α ⟨a⟨bbb⟩a⟩ (9)⟨a⟨babb⟩a⟩≠α ⟨a⟨bbab⟩a⟩. (10)

These sequences, in general sequences where Fa(e) = ε for any atom occurring in the sequence, can be informally illustrated using “pointer sequences”: a node with a left-pointing arrow corresponds to a name creation, one with a right-pointing arrow to a name destruction, and an arrow-less dot to a name mention. Thus the pairs of α-equivalent sequences in (5)–(8) can be represented as the pointer sequences on the left column in Fig. 1, while the inequivalent pairs of sequences in (9) and (10) are represented on the right column in Fig. 1.

We now give a syntax-directed definition of α-equivalence.

Definition 7

Define alpha-equivalence =α⊆ RSeq×RSeq inductively by:

ε =α ε (αε)e1 =α e2m ∈𝕋 e1m =α e2m(αm)Иc. e1⟨c (c a)·e2 =α e′ 1⟨c (c b)·e′ 2ae2, be′ 2e1⟨ae2a⟩=α e′ 1⟨be′ 2b⟩(αα)

(In (αα) (c a)·e2 denotes the action of the permutation (c a) on e2, and similarly for (c b)·e′ 2.) For other characterisations of =α see Thm. 18 and Cor. 24.

The next two lemmas are instrumental in establishing that =α is an equivalence relation and a congruence.

Lemma 8

If e1 =α e2 then F(e1) = F(e2).

Lemma 9

e1⟨ae2a⟩=e′ 1⟨ae′ 2a⟩ and ae2, e′ 2 imply e1=e′ 1 and e2=e′ 2.

Lemma 10

=α is an equivalence relation.

Proof sketch

Transitivity is proved inductively using a case analysis of the possible rules ending the derivations. For example, assume that ea⟩=α ga′⟩ and ga′⟩=α ha′′⟩ are both obtained using (αα). Then we have e = e1⟨ae2, g = g1⟨a′g2 with ae2, a′g2 such that Иc.e1⟨c (c a)·e2 =α g1⟨c (c a′)·g2. Similarly, g = g′ 1⟨a′g′ 2, h = h1⟨a′′h2 with a′g′ 2, a′′h2 such that Иc.g′ 1⟨c (c a′)·g′ 2 =α h1⟨c (c a′′)·h2. Using Lem. 9 it follows that gi = g′ i from which we derive Иc.e1⟨c (c a)·e2 =α h1⟨c (c a′′)·h2 with ae2, a′′h2. Thus ea⟩=α ha′′⟩ is obtained using (αα). ◀

Theorem 11 (=α is a congruence).

If e1 =α e′ 1 and e2 =α e′ 2 then e1e2 =α e′ 1e′ 2.

Proof sketch

By induction on e′ 2 with the only interesting case being when the second equivalence was obtained using (αα). In this case, we have e2 = g1⟨ag2a⟩ and e′ 2 = g′ 1⟨bg′ 2b⟩ such that ag2, bg′ 2 and Иc. g1⟨c (c a)·g2 =α g′ 1⟨c (c b)·g′ 2. By the induction hypothesis we have Иc. e1g1⟨c (c a)·g2 =α e′ 1g′ 1⟨c (c b)·g′ 2, hence by (αα) we obtain e1e2 =α e′ 1e′ 2. ◀

Definition 12

Let DSeq = (RSeq/=α) be the nominal set of sequences quotiented by α-equivalence, with the natural permutation action given by the action on representatives; call these dynamic sequences.

Note that Lem. 8 ensures that we can extend the notations of ae, ae, ae to dynamic sequences.

Lemma 13

If e ∈ DSeq and a ∈𝔸 then Fae = ε if and only if a#e.

2.3 On the congruence property of α-equivalence

The congruence of α-equivalence is an essential mathematical property which has motivated design decisions in our definition of dynamic scope. We take a moment to discuss them, and so perhaps gain a better perspective on the design space in which dynamic sequences exist. Consider the raw sequence ⟨aa⟨aaa⟩. Which of the two occurrences of ⟨a should match the destructor a⟩? Rem. 9 and the equations of the binding monoid (1)–(4) uniquely identify it as the most recent unpaired ⟨a before the a⟩ (so above, the rightmost ⟨a matches a⟩). We call this late binding.

Some diagrams for the slightly more complex example of ⟨a⟨aa⟩a⟩ illustrate this. We prefer the upper diagram to the lower diagram:

⟨a⟨aa⟩a⟩=α ⟨a⟨bb⟩a⟩= • • • •⟨a⟨aa⟩a⟩≠α ⟨a⟨ba⟩b⟩= ••• •

The lower diagram (which we might call early or eager binding) is not obviously mathematically wrong, but it is unreasonable in the sense that it invalidates congruence of α-equivalence:

▶ Remark. For any binding policy other than late binding, any reasonably defined =α is not a congruence.

Informal argument. Whatever α-equivalence is, we require ⟨aa⟩=α ⟨bb⟩. If =α is a congruence then ⟨a⟨aa⟩=α ⟨a⟨bb⟩. Given a binding policy which does not match a destructor for a with the most recent creation preceding it, it follows that ⟨a⟨aa⟩=α ⟨b⟨ab⟩≠α ⟨a⟨bb⟩, a contradiction. ◀

Late binding preserves existing dynamic bindings whereas other binding policies do not, thus α-equivalence is a congruence with late binding (Thm. 11), whereas other dynamic binding policies are, in this sense, ill-behaved.

3 Relational semantics

We now give a concrete semantics in relations. This relational semantics is sound, complete, and compositional.

Call a stack a list of pairs of atoms, i.e., an element of the set Stacks = (𝔸2)∗. Elements of 𝔸2 will be written as (a↦→b). For each S ∈ Stacks we define stack-like operations read, add and remove, written as S(a), S :: (a↦→b) and, respectively, S \a. Both reading and removal of a record involve the most recent record (a↦→b) in the stack. Formally, if S = S1 :: (a↦→b) :: S2 for stacks S1, S2, and (a↦→c) does not occur in S2 for any c, then S(a) = b and S \a = S1 :: S2. Otherwise S(a) and S \a are undefined.

Definition 14

Define a relational semantics

⟦-⟧ : RSeq →P((Stacks × (𝔸 + 𝕂)∗)2).

on raw sequences as follows:

⟦ε⟧ ={((S, X), (S, X)) | ∀S, X} (11)⟦ea⟧ ={((S, X), (S′, X′ :: S′(a))) | ((S, X), (S′, X′)) ∈⟦e⟧} (12)⟦ek⟧ ={((S, X), (S′, X′ :: k)) | ((S, X), (S′, X′)) ∈⟦e⟧} (13)⟦e⟨a⟧ ={((S, X), (S′ :: (a↦→b), X′ :: b)) | ((S, X), (S′, X′)) ∈⟦e⟧, b # S′, X′} (14)⟦ea⟩⟧ ={((S, X), (S′ \a, X′ :: S′(a))) | ((S, X), (S′, X′)) ∈⟦e⟧} (15)

In (12) and (15) it is assumed that S′(a) and S′ \a respectively are well-defined.

The intuition behind (S, X) ⟦e⟧ (S′, X :: X′) is quite operational. The stack S is to be thought of as a stack of name replacements, and the sequence X as a context in which e is interpreted. S′ is an updated stack, since creation and destruction of names cause it to change and X′ is a sequence which “interprets” e given the updated stack S′ and the context X. Using a name a (see (12)) extends the current sequence with its stack value S(a); creating a name ⟨a (see (14)) adds a new entry (a↦→b) to the stack and extends the current sequence with b; destroying a name a⟩ (see (15)) removes it from the stack and extends the current sequence with its dictionary value. A constant k is simply added to the sequence (see (13)).

The interpretation ⟦-⟧ is compositional, using pointwise relational composition - ◦ -.

Lemma 15

For any sequence e ∈ RSeq and token m ∈𝕋: ⟦em⟧ = ⟦e⟧ ◦⟦m⟧.

Proof

Immediate from definitions. ◀

Theorem 16

For any e, e′ ∈ RSeq, ⟦ee′⟧ = ⟦e⟧ ◦⟦e′⟧

Proof sketch

By Lemma 15 we have that for any token m ∈𝕋 we have ⟦em⟧ = ⟦e⟧ ◦⟦m⟧. Then we can use induction on the structure of e′. ◀

Proposition 17

If e1, e2 ∈ RSeq and m ∈𝕋 then ⟦em⟧ = ⟦e′m⟧ implies ⟦e⟧ = ⟦e′⟧.

Proof

By Lem. 15 and simple calculations. ◀

Theorem 18

If e1, e2∈RSeq then e1=αe2 iff ⟦e1⟧=⟦e2⟧.

In view of soundness and completeness (Thm. 18) we can also use ⟦-⟧ to interpret dynamic sequences rather than raw sequences, i.e. ⟦-⟧ : DSeq →P((Stacks × (𝔸 + 𝕂)∗)2).

4 Equational axiomatisation

We give an equational axiomatisation of the interleaved dynamic binding of this paper (Def. 19). The dynamic sequences of Def. 12 form a free dynamic binding monoid (Thm. 23), and α-equivalence gets a purely equational characterisation as an equality subject to freshness-arity side-conditions (Cor. 24).

The central idea is to use a monoid structure equipped with a compatible permutation action, left and right ‘binders’ and a function with co-domain B𝔸 that encompasses the interleaved binding laws—which we will call the freshness arity map, see Def. 19 below. We will call such structures dynamic binding monoids.

Several approaches in the literature investigate notions of algebraic theories and equational reasoning in a nominal setting [14, 7, 6, 21]. A common denominator is that equations are presented with freshness side-conditions. For example, the η-rule in untyped λ-calculus can be captured by a#x ⊢ lam([a]app(x, a)) = x. An algebraic theory of dynamic binding monoids must interpret interleaved scope, and so the freshness side-conditions familiar from e.g. nominal unification, rewriting, and universal algebra must be suitably enriched to interpret freshness-arity side-conditions. Thus, some equations in Def. 19 have side-conditions on the freshness arity of variables specified using the binding monoid B—if the reader prefers, these can also be seen as typing conditions.

Definition 19

A dynamic binding monoid is a tuple (M, ::, 1, ·, ‹, ›, γ) where (M, ·) is a nominal set, (M, ::, 1) is a monoid such that the binary operation is equivariant and 1 is an element of M with empty support, ‹, › : 𝔸 →M are equivariant functions, and γ : M →B𝔸 is an equivariant monoid morphism, satisfying equations:

γa(‹a) =c, γa(a›) = d, a#x ⊢γa(x) = ε, and b#m, γa(m)=fn ⊢‹a :: m :: a› = ‹b :: (b a)·m :: b›, n ∈{0, 1}. (16)

Above, given a ∈𝔸 we write γa : M →B for the map λm.γ(m)(a), and a› for › at a (instead of ›a). We may omit the monoid multiplication :: when clear from the context.

Lemma 20

The set DSeq can be equipped with a dynamic binding monoid structure.

A morphism between dynamic binding monoids (M, ::, 1, ·, ‹, ›, γ) and (M ′, ::, 1, ·, ‹′, ›′, γ′) is an equivariant monoid morphism f : M →M ′ that preserves the left and right binders and the freshness arity map, that is, f ◦ ‹ = ‹′, f ◦ › = ›′, respectively γ′ ◦f = γ.

Thus dynamic binding monoids form a category denoted by DBMon. Categories of nominal algebras described for example in [11, 21] have a forgetful functor to the category of underlying nominal sets Nom, and admit a free construction. That is, the forgetful functor from a category of nominal algebras to Nom has a left adjoint. Such a free construction allows for deriving structural induction principles in the presence of binding, see for example [24, Cor. 8.22]. Because of the side-conditions involving the freshness arities, dynamic binding monoids lie outside the scope of nominal universal algebra. If we consider as the underlying structure of a binding monoid, not only the carrier nominal set, but also the freshness arity map, we can still obtain a free construction and hence a structural induction principle, see Thm. 22 below.

We introduce the category BNom of underlying nominal sets with a freshness arity map:

Definition 21

Let BNom be the full subcategory of the slice category Nom/B𝔸 with objects pairs (X, γ) where X is a nominal set and γ : X →B𝔸 is an equivariant function such that a#x ⊢γa(x) = ε.

A morphism in BNom from (X, γ) to (X′, γ′) is an equivariant function f : X →X′ such that γ′ ◦f = γ.

Let the forgetful functor U : DBMon → BNom send a dynamic binding monoid (M, ::, 1, ·, ‹, ›, γ) to (M, γ).

Theorem 22

The forgetful functor U : DBMon → BNom has a left adjoint F.

Proof

Consider (X, γ) ∈ BNom, the set X + 𝔸 + 𝔸 = X ∪{⟨a|a ∈𝔸} ∪{a⟩|a ∈𝔸}. We define an equivariant map γ : X + 𝔸 + 𝔸 →B𝔸 that acts as γ on X and such that γa(⟨a) = c, γa(a⟩) = d, γa(⟨b) = ε and γa(b⟩) = ε for b ≠ a. Then γ can be extended uniquely to a monoid morphism γ∗ : (X + 𝔸 + 𝔸)∗→B𝔸. Define a relation ≡ on (X + 𝔸 + 𝔸)∗ as the congruence generated by ⟨awa⟩= ⟨b(b a)·wb⟩, where a, b ∈𝔸, w ∈ (X + 𝔸 + 𝔸)∗, b#w and γ∗ a(w) ∈{ε, f}.

Construct F(X, γ) as a dynamic binding monoid on the carrier nominal set (X+𝔸+𝔸)∗/≡. Left and right binders are defined in the obvious way and the freshness arity map function is induced by γ∗. It is easy to check that whenever w ≡w′ then γ∗(w) = γ∗(w′). We must exhibit an isomorphism DBMon((X + 𝔸 + 𝔸)∗/≡, M) ∼= BNom((X, γ), (M, γM)). Starting with a morphism f : X →M in BNom, we can uniquely extend f + ‹ + › : X + 𝔸 + 𝔸 →M to an equivariant monoid morphism f# : (X + 𝔸 + 𝔸)∗→M. We have that γ ◦f# = γ∗. It follows that for every w, w′ ∈ (X + 𝔸 + 𝔸)∗ such that w ≡w′ then f#(w) = f#(w′). Hence, f# factors through a dynamic binding monoid morphism f : (X + 𝔸 + 𝔸)∗/≡→M. Conversely, given g ∈ DBMon((X + 𝔸 + 𝔸)∗/≡, M) we consider g♭∈ BNom((X, γ), (M, γM)) given by g♭(x) = g([x]) where [x] is the ≡-equivalence class of x. ◀

Theorem 23

DSeq is the free dynamic binding monoid on (𝔸∪𝕂, γ𝔸) where γ𝔸(a)(a) = f, γ𝔸(a)(b) = ε for b ≠ a and γ𝔸(k)(a) = ε.

Proof Sketch

We have that DSeq = RSeq/=α and RSeq = (𝔸∪𝕂+𝔸+𝔸)∗. Thus it suffices that =α is equal to the relation ≡ described in the proof of Thm. 22. That ≡⊆=α follows from the proof of Lem. 20. For the other inclusion, we prove by induction on the length of e that whenever e =α e′ then e ≡e′. If the former equivalence was derived using the rules (αε) or (αm) then the proof is immediate by induction. Assume that e =α e′ was derived using (αα). That is, e = e1⟨ae2a⟩, e′ = e′ 1⟨be′ 2b⟩ such that ae2, be′ 2 and for any fresh c we have e1⟨c (c a)·e2 =α e′ 1⟨c (c b)·e′ 2. By inductive hypothesis e1⟨c (c a)·e2 ≡e′ 1⟨c (c b)·e′ 2 for fresh c; we must prove e1⟨ae2a⟩≡e′ 1⟨be′ 2b⟩.

We consider the case when e1⟨c (c a)·e2 = h1⟨dhd⟩h2 and e′ 1⟨c (c b)·e′ 2 = h′ 1⟨d′(d′ d)·hd′⟩h′ 2 such that h1 ≡h′ 1, h2 ≡h′ 2, d′#h and dh. The most interesting case is when h = g1⟨cg2. We have that

e1⟨ae2a⟩ = h1⟨dg1⟨a(a c)·g2d⟩(a c)h2a⟩≡ h1⟨dg1⟨cg2d⟩h2c⟩≡ h′ 1⟨d′(d′ d)·g1⟨c(d′ d)·g2d′⟩h′ 2c⟩≡ h′ 1⟨d′(d′ d)·g1⟨b(b c)(d′ d)·g2d′⟩(b c)h′ 2b⟩= e′ 1⟨be′ 2b⟩.

It might be the case that e1⟨c (c a)·e2 ≡e′ 1⟨c (c b)·e′ 2 was obtained using the transitivity of ≡, for example ⟨d1⟨d2⟨cd2⟩d1⟩≡⟨d′ 1⟨d′ 2⟨cd′ 2⟩d′ 1⟩ can only be derived using the transitivity of ≡. For this case the proof that e1⟨ae2a⟩≡e′ 1⟨be′ 2b⟩ requires several steps and transitivity, but it reduces to the basic case resolved above. ◀

From the proof of Thm. 23 we obtain a new characterisation of =α from Def. 7:

Corollary 24

The α-equivalence relation =α on RSeq is the least congruence closed under the following rule (ae is from Definition 5):

b#e ae ⟨aea⟩=α ⟨b (b a)·eb⟩(α).
Proof

From the proof of Thm. 23 it follows that α-equivalence on RSeq is equal to a relation ≡, defined as the least congruence closed under the rule (α). ◀

5 Examples

In the examples to follow we see our formalism at work. These examples are elementary and, because of the way our framework is set up, the definitions are suitably simple.

Def. 12 defines a data type DSeq as the quotient of an inductive data type by an α-equivalence relation. We can reason on it by taking representatives of equivalence classes and working inductively on those representatives. This comes from how we define the set.

The reader familiar with nominal techniques might ask why we do not use nominal abstract syntax [15], where α-equivalence is built into the inductive definition of the data type at every inductive stage (using atoms-abstraction; a type constructor naturally present in the nominal universe), so we can work inductively up-to-α with no need for representatives.

That is impossible for us here because by design we do not know a priori when we write ⟨a in a dynamic sequence where (if anywhere) the matching a⟩ will occur, and conversely, if we find a⟩ in a dynamic sequence then we do not a priori know where (if anywhere) a matching ⟨a will occur.

Instead we will use a technique from [10] which allows us to lift function definitions from raw terms (in our case: raw sequences) to α-equivalence classes of raw terms (in our case: dynamic sequences). The required condition for this method to work is that what we call α-equivalence has the property of being Barendregt-abstractive; that every equivalence class must contain a member with maximum support. In our case it means that in the set of all raw sequences that represent the same dynamic sequence, there is one with a maximum number of atoms. We may call a representative of such an orbit a Barendregt representative, due to the intended similarity with the Barendregt variable naming convention [2]. Def. 25 will help us to calculate Barendregt representatives:

Definition 25

Suppose e ∈ RSeq is a raw sequence and N ⊆𝔸 is a finite set of atoms. Define a function freshen(N, e) : RSeq → RSeq inductively by:

freshen(N, ε) = ε, freshen(N, e1⟨ae2a⟩) = freshen(N, e1)⟨c freshen(N, (c a)·e2) c⟩for a fresh c ∈𝔸 (so c#e1, e2and c ∉N) provided that ae2 holds, and freshen(N, em) = freshen(N, e)m otherwise.

It is easy to check that freshen(N, e) is well-defined, freshen(N, e) =α e, it has maximal support, and fresh atoms are distinct from N; the reason for this last condition will become clear in a moment.

It is convenient now to make a notational distinction between e ∈ RSeq and its equivalence class [e]α ∈ DSeq. We have:

Lemma 26

Given k, l ≥ 0, the map α(k, l) : (RSeqk × 𝔸l) → (DSeqk × 𝔸l) defined by

(e1, . . . , ek, n1, . . . , nl)↦ −→([e1]α, . . . , [ek]α, n1, . . . , nl)

is Barendregt-abstractive.

Proof

We must construct a Barendregt representative of ([e1]α, . . . , [ek]α, n1, . . . , nl). Write N = {n1, . . . , nl}. Then we take e′ 1 = freshen(N, e1), and e′ 2 = freshen(N∪supp(e′ 1), e2), and e′ 3 = freshen(N∪supp(e′ 1)∪supp(e′ 2), e3), and so on. It clear that (e′ 1, . . . , e′ k, n1, . . . , nl) has maximal support and that it is a Barendregt representative of (the inverse image of) ([e1]α, . . . , [ek]α, n1, . . . , nl). Write this representative freshen(e1, . . . , ek, n1, . . . , nl). ◀

Definition 27 ([22]).

Suppose X and Y are nominal sets and f : Y →X is a function. Define bvf(y) = supp(y) \ supp(f(y)). For instance bvα(1,0)(⟨aa⟩) = {a}.

Lem. 26 allows us to tailor [10, Thm. 27] to functions taking k dynamic sequences and l atoms as input (all our examples below will have this form) as follows:

Theorem 28

Suppose X is a nominal set and k, l ≥ 0 and F : RSeqk × 𝔸l →X, and suppose for every e1, . . . , ek ∈ RSeq and n1, . . . , nl ∈𝔸 that

bvα(k,l)(freshen(e1, . . . , ek, n1, . . . , nl))#F(freshen(e1, . . . , ek, n1, . . . , nl)).

Then the map ИF : DSeqk × 𝔸l →X defined by

ИF([e1]α, . . . , [ek]α, n1, . . . , nl) = F(freshen(e1, . . . , ek, n1, . . . , nl))

is well-defined.

Proof

From Lem. 26 and [10, Thm. 27]. ◀

We specialise Thm. 28 to k=l=1 for illustration’s sake: ИF([e]α, n) is equal to F(e′, n) where bound atoms in e′ are chosen distinct and not equal to n, and ИF([⟨aa⟩]α, a) = F(⟨bb⟩, a). An equivalent phrasing of the condition in Thm. 28 is this:

supp(F(freshen(e1, . . . , ek, n1, . . . , nl))) ⊆supp([e1]α, . . . , [ek]α, n1, . . . , nl).

When we use Thm. 28 we will tend to write ИF just as F, thus, notationally identifying the function-on-α-equivalence-classes with the function-on-representatives. We obfuscate the distinction between e and [e]α and write our definitions ‘as if’ they were by induction on dynamic sequences. Doing this is consistent with informal practice: for instance, we are used to writing size(λa.a) and saying “size of λa.a” but actually meaning “pick a representative and calculate the size of that representative”. Thus, the reader who cares about such things can unpick this obfuscation back to the raw sequences and maximally distinct representatives; the reader who does not care, should be able to read the text just as they would any ‘inductive’ definition on syntax quotiented by α-equivalence.

5.1 Operations on dynamic sequences

Example 29 (Counting name creation-destruction pairs).

Define a function |-| : DSeq →ℕ using Thm. 28 by:

|ε| = 0 ae ⇒|ea⟩| = |e|.|e⟨a| = |e| ae′ ⇒|e⟨ae′a⟩| = |ee′| + 1|ek| = |e|

To apply Thm. 28 we must check that any maximally distinct choice of bound names in the argument is fresh for the result. This is indeed the case (since a#n for any atom and any n∈ℤ). |e| counts the number of pairs of matched creation-destructors in e. The side-conditions ensure that the clauses pick out the correct creation for each destructor. We calculate |-| for an example sequence; in this example we mark instances of the atom a with subscripts to see how the answer is calculated (so a1 and a2 are the same atom; just different instances):

|⟨a1a2⟨a3a4a5⟩a6⟩| = |a2⟨a3a4a5⟩| + 1 = |a2a4| + 2 = 2.

In fact, the side-condition ae′ is superfluous, but it ensures that brackets are consumed in well-matched pairs.

▶ Remark. The clauses above actually define an inductive function on raw sequences. Thm. 28 gives us freshness-based conditions to verify that this induces a function on dynamic sequences (formally, И|e|).

Function |e| happens to make sense for all raw sequences whether bound names are maximally distinct or not; for an example of where this not the case, see Ex. 31.

Example 30 (Counting bound occurrences).

Define a function ∥-∥ : DSeq →ℕ using Thm. 28 as follows:

∥ε∥= 0 a#e′ ⇒∥e⟨ae′a⟩∥= ∥ee′∥∥ek∥= ∥e∥ a#e′, ae′′ ⇒∥e⟨ae′ae′′a⟩∥= ∥e⟨ae′e′′a⟩∥+ 1∥e⟨a∥= ∥e∥ ae ⇒∥ea⟩∥= ∥e∥.

To apply Thm. 28 we must check that any maximally distinct choice of bound names in the argument is fresh for the result. This is indeed the case.

∥ek∥ counts how many names occur ‘bound’ in a dynamic sequence, i.e. between a matched pair of a creation and destructor. For example ∥a⟨aaa⟩a∥ = 1 because there is only one occurrence of a between its creation and destruction. Two other occurrences of a are outside the scope. For the same example sequence as above we have:

∥⟨a1a2⟨a3a4a5⟩a6⟩∥= ∥⟨a1⟨a3a4a5⟩a6⟩∥+1 = ∥⟨a3a4a5⟩∥+1 = ∥⟨a3a5⟩∥+2 = ∥ε∥+2 = 2

The side-conditions ensure that brackets get ‘eaten’ in well-matched pairs, and are also used to identify the first free occurrence of the bound name.

Example 31 (Capture-avoiding substitution).

We define -[-/-] : DSeq × 𝔸 × 𝔸 → DSeq by:

ε[a/b] = ε c≠a ⇒ec[a/b] = e[a/b]cek[a/b] = e[a/b]k c≠a ⇒e⟨c[a/b] = e[a/b]⟨cea[a/b] = e[a/b]b ae ⇒ea⟩[a/b] = e[a/b]b⟩e⟨a[a/b] = e[a/b]⟨bИc.be′ ⇒e⟨ce′c⟩[a/b] = e[a/b]⟨c(e′[a/b])c⟩

Previous examples made sense on raw sequences even if bound names were not chosen maximally distinct, but this function uses more of the power of Thm. 28, licensing us in effect to rename bound atoms and so avoid accidental name-clashes: ⟨aa⟩[a/b] = ⟨cc⟩[a/b] = ⟨cc⟩= ⟨aa⟩.

In fact, no rule above can be applied in ⟨aa⟩[a/b], but we do not care because we only care about Barendregt representatives of triples (e, a, b) and such a representative will choose the bound names in e distinct from a and b. If we wish to notice that we are technically working with raw sequences and not dynamic sequences then we choose some junk value for the non-maximally-distinct cases.

For the final example we first introduce some notation, a regular-expression-like language for dynamic sequences.

Definition 32

Define functions

+, · : P(DSeq) × P(DSeq) →P(DSeq) −∗: P(DSeq) →P(DSeq) bye ∈E + F iffe ∈E or e ∈F e ∈E · F iff∃e1, e2 ∈DSeq.e = e1e2 and e1 ∈E, e2 ∈F e ∈E∗iffe = ε or e ∈E · E∗.
Example 33 (Capture-avoiding interleaving).

Another phenomenon resembling variable capture can occur when interleaving sequences. When we interleave a raw sequence such as ⟨aa⟩ with itself, we obtain the set of sequences {⟨aa⟩⟨aa⟩, ⟨a⟨aa⟩a⟩}. If we represent them diagrammatically, we have the interleaving of • • producing the sequences

• • • • and • • • • . What happened to the sequence

• • • • ? Because the names are equal the wrong creation is ‘captured’ by the wrong destructor in the course of interleaving. This can be avoided if we interleave the sequences up to α-equivalence.

Define ∥ : DSeq × DSeq →P(DSeq) using Thm. 28 and the notations from Def. 32:

ε ∥e = e = e ∥ε m#e′m′, m′#em ⇒em ∥e′m′ = (em ∥e′) · m′ + (e ∥e′m′) · m.

To use Thm. 28 it suffices to check of each clause that maximally distinct choice of bound names do not affect the result, and we can assume that bound names in e1 are chosen distinct from those in e2, since this is a Barendregt representative of the input (e1, e2) to ∥. Therefore

⟨aa⟩∥⟨aa⟩= {⟨aa⟩⟨aa⟩, ⟨a⟨aa⟩a⟩, ⟨a⟨ba⟩b⟩}

6 Application: Games with pointer sequences

In this section we sketch a potential application of dynamic sequences, a more formal and more resource-sensitive representation of pointer sequences in game semantics. Space restrictions prevent us from fully working this out but we hope it illustrates the potential of dynamic sequences to rigorously representat semantic models that require interleaved name scopes.

One of the original presentations of game semantics, by Hyland and Ong, represented plays as sequences of moves annotated with arrows between moves [18]. Formally, plays were formalised as sequences equipped with a function f from natural numbers to natural numbers indicating that the move at index n points at move at index f(n). 2

Ghica and Gabbay [9] already gave a formulation of plays using raw sequences, which turned out to streamline key definitions and simplified many proofs. This paper did not consider α-equivalence and dynamic sequences, although some of our ideas are foreshadowed.

A pointer sequence is represented diagrammatically as an ordinary sequence decorated with pointed arrows, for example

m0m1m2m3m4m5

would be represented using HO integer indices as the pair

(m0m1m2m3m4m5, (1↦→0, 2↦→0, 3↦→2, 4↦→1, 5↦→3)).

The raw sequence representation is m0[a]∗ :: m1[b]a :: m2[c]a :: m3[d]c :: m4[e]b :: m5[f]d. Each move has a name, freshly introduced, indicated in square brackets, serving as an address, and it uses a previously introduced name to indicate the point of the arrow.

Game semantics requires complex operations on pointer sequences, such as swapping moves (while preserving pointers) to model reordering of actions in asynchronous concurrency [16] or extracting sub-sequences to model restricted history sensitiveness in languages without effects (innocence [18]). With integer indices, the pointer map needs to be re-indexed, an awkward operation which can be formalised in principle but it never was in practice due to sheer tedium. Using names, the same definitions are straightforward, as the names stay attached to the moves, making a more precise formalisation possible.

Although the raw sequence formalisation is from a mathematical point of view effective, from a conceptual and operational point of view is too profligate in its use of names. This is best illustrated with a simple example. The standard interpretation of the sequencing operator in HO games for Algol-like languages [1] is the set of even-length prefixes of this

pointer sequence: rr1d1r2d2d . The operational intuition is as follows, where P is ‘the program’ and E is ‘the environment’:

r E asks P to start sequencing the two commands;

r1 P in reply to r (see arrow) asks E to execute the first command;

d1 E in reply to r1 (see arrow) eventually reports the first command’s termination;

r2 P, justified by r (see arrow), asks E to execute the second command;

d2 E, in reply to r2, eventually reports the first command’s termination;

d P, in reply to r, reports that sequencing is completed.

The raw sequence representation of this play is r[a]∗ :: r1[b]a :: d1b :: r2[d]a :: d2d :: da, which requires 3 names. Certain moves, called answers, are never pointed at, so they need not introduce a name (they can, but it will simply be wasted). In certain game models answers have the additional property that after they point to a move no other subsequent move can ever point to it either—like name destructors, in fact! Using dynamic sequences with explicit name creation and destruction and late binding, the same sequence can be represented as: r∗⟨a :: r1a⟨a :: d1a⟩ :: r2a⟨a :: d2a⟩ :: da⟩. The raw sequence representative of the dynamic sequence above uses just the name a. This is more aesthetically pleasing but it is also helpful for two reasons related to representing game models for program verification or compilation: Dynamic sequences allow an improvement of the mathematical presentation of game semantics as well, beyond the raw-sequence formalisation. For example, in [9]:

Def. 2.12, formalises the concept of “enabled sequence” e, in which any name of a move must be introduced before being used. This definition becomes just ae.

Def. 2.15(iii) “Call a play e strictly scoped when aa[b]e′ ∈e implies a ∉ supp(e′).” says that once the “answer” move a uses a name a, that name should never be used again. This condition can be removed now and plays be made strictly scoped by construction, because a can be destructed by the answer move: aa⟩⟨b :: e′.

Note that, as detailed in Sec. 5, the various raw-sequence operations used in game semantics can be lifted to dynamic sequences in an elegant way.

7 Related and future work

The main contribution of this paper is the syntactic notion of dynamic sequence that models interleaved scope by splitting binding into two more primitive syntactic constructs: a name-creation bracket ⟨a, and a name-destruction bracket a⟩. By interleaved we mean that brackets need not be perfectly nested, as in ⟨a⟨baba⟩b⟩.

The idea of splitting local binding into two brackets has been seen before. The Adbmal syntax from [17] splits λ-binding specifically in the λ-calculus into an opening bracket λa and a closing bracket λa. However that paper is focused on scope-balanced terms and assumes a jump semantics, that is, λa closes the scope of all intermediate λs occurring before the matching λa in order to avoid interleaved scope. By contrast, in this paper a⟩ lazily matches only the single most recent unmatched ⟨a. It would be interesting to develop a categorical semantics for the λ-calculus and to explore further connections with dynamic sequences. It would be certainly interesting to extend the ideas of dynamic scope to trees, as Adbmal is set up to do, but this presents significant conceptual challenges, even before considering the technical ones. For example, matching brackets in a non-linear structure seems to require a notion of traversal for the structure. This remains to be investigated.

Dynamic scope also appears in natural languages, in semantic models for indefinite articles [28]. An opening bracket corresponds to the creation of a new ‘file’ for storing subsequent information and anchoring references. A closing bracket corresponds to the deletion of the ‘file’ and the destruction of the context. That paper takes a radically different approach based on a variation of monoidal categories and Grothendieck constructions. Working out the precise connection with our setting is left as future work.

In Sec. 5 we introduced a number of concepts such as regular expressions over dynamic sequences (Def. 32). Regular expressions and Kleene algebras with statically scoping nominal-style name-binding and -generation have been studied [13, 23, 20] and it would be interesting to investigate versions with dynamic scope. Languages with allocation have been extensively studied, including in the nominal setting (e.g. [3, 25]), but those with deallocation not so much as far as we know. This too could be future work. It would also be interesting to extend nominal automata [26, 4, 19] to handle name destruction. We could then investigate whether dynamic binding monoids play a similar role in understanding the algebraic theory of languages accepted by such automata, just as orbit-finite nominal monoids do for nominal languages, see [5].

Our original motivation was to apply dynamic sequences as a notation for the pointer sequences of game semantics, to simplify the formalisation of definitions of operations on pointer sequences and proofs of their properties. Raw nominal sequences are a step in this direction [9]; dynamic sequences take this further by introducing appropriate rules for scope and α-equivalence. This may help to formalise parts of game semantics—think “game semantics in Nominal Isabelle” analogously to the current extensive implementation of nominal abstract syntax in Isabelle [27], or “rewriting on game semantics using nominal rewriting” (or a suitable generalisation with freshness side-conditions generalised to freshness-arity side-conditions) similar to [8]—and to tighten the connection between the game-semantic and abstract-machine models.

Perhaps the most significant challenge, but also the most exciting opportunity, is the use of dynamic sequences to model explicit resource management in C-like languages. Intuitively, a call to malloc() introduces a new name for a memory location, which in a dynamic trace corresponds to ⟨a, whereas a call to free() removes that name, which in a dynamic trace corresponds to a⟩. Clearly the scopes of the memory locations thus managed can be arbitrarily interleaved. However, the nominal aspects are only one aspect required to understand malloc/free. The stateful effects, the possibility of dangling pointers and garbage require significant amounts of further work. To conclude, we believe that interleaved name scopes are an interesting phenomenon which appears in several contexts: game semantics (our initial motivation), natural languages and low-level languages with explicit resource management. However, beyond these actual and potential applications, dynamic sequences seem to also be a novel nominal phenomenon, interesting in its own right.

Acknowledgements:

We thank Bertram Wheen for a partial Agda formalisation of the syntactic model.

References

1 S. Abramsky and G. McCusker. Linearity, sharing and state: a fully abstract game semantics for idealized algol with active expressions. Electr. Notes Theor. Comput. Sci., 3:2–14, 1996.

2 H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.

3 N. Benton and B. Leperchey. Relational reasoning in a nominal semantics for storage. In Typed Lambda Calculi and Applications, pages 86–101. Springer, 2005.

4 M. Bojanczyk, B. Klin, and S. Lasota. Automata theory in nominal sets. Logical Methods in Comp. Sci., 10(3), 2014.

5 M. Bojańczyk. Nominal monoids. Theory of Computing Systems, 53(2):194–222, 2013.

6 R. Clouston. Nominal lawvere theories: A category theoretic account of equational theories with names. J. Comput. Syst. Sci., 80(6):1067–1086, 2014.

7 R. A. Clouston and A. M. Pitts. Nominal equational logic. Electr. Notes Theor. Comput. Sci., 172:223–257, 2007.

8 M. Fernández and M. J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, June 2007.

9 M. Gabbay and D. R. Ghica. Game semantics in the nominal model. Electr. Notes Theor. Comput. Sci., 286:173–189, 2012.

10 M. J. Gabbay. A general mathematics of names. Information and Computation, 205(7):982– 1011, July 2007.

11 M. J. Gabbay. Nominal algebra and the HSP theorem. Journal of Logic and Computation, 19(2):341–367, April 2009.

12 M. J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.

13 M. J. Gabbay and V. Ciancia. Freshness and name-restriction in sets of traces with names. In FOSSACS, volume 6604 of Lec. Notes in Comp. Sci., pages 365–380. Springer, 2011.

14 M. J. Gabbay and A. Mathijssen. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, December 2009.

15 M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, July 2001.

16 D. R. Ghica and A. S. Murawski. Angelic semantics of fine-grained concurrency. Ann. Pure Appl. Logic, 151(2-3):89–114, 2008.

17 D. Hendriks and V. van Oostrom. adbmal. In CADE, volume 2741 of Lec. Notes in Comp. Sci., pages 136–150. Springer, 2003.

18 J. M. E. Hyland and C. L. Ong. On full abstraction for PCF: i, ii, and III. Inf. Comput., 163(2):285–408, 2000.

19 D. Kozen, K. Mamouras, D. Petrisan, and A. Silva. Nominal Kleene coalgebra. In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Proc. 42nd Int. Colloq. Automata, Languages, and Programming, Part II (ICALP 2015), volume 9135 of Lecture Notes in Computer Science, pages 290–302, Kyoto, Japan, July 6–10 2015. EATCS, Springer.

20 D. Kozen, K. Mamouras, and A. Silva. Completeness and incompleteness in nominal Kleene algebra. Technical report, Computing and Information Science, Cornell University, November 2014.

21 A. Kurz and D. Petrisan. On universal algebra over nominal sets. Math. Struc. in Comp. Sci., 20(2):285–318, 2010.

22 A. Kurz, D. Petrisan, P. Severi, and F. de Vries. Nominal coalgebraic data types with applications to lambda calculus. Logical Methods in Computer Science, 9(4), 2013.

23 A. Kurz, T. Suzuki, and E. Tuosto. On nominal regular languages with binders. In FOSSACS, volume 7213 of Lec. Notes in Comp. Sci., pages 255–269. Springer, 2012.

24 A. M. Pitts. Nominal Sets: Names and Symmetry in Comp. Sci., volume 57. Cambridge University Press, 2013.

25 M. R. Shinwell and A. M. Pitts. On a monadic semantics for freshness. Theor. Comp. Sci., 342(1):28–55, 2005.

26 N. Tzevelekos. Fresh-register automata. In POPL, pages 295–306. ACM, 2011.

27 C. Urban. Nominal reasoning techniques in Isabelle/HOL. J. of Automatic Reasoning, 40(4):327–356, 2008.

28 A. Visser, K. Vermeulen, et al. Dynamic bracketing and discourse representation. Notre Dame Journal of Formal Logic, 37(2):321–365, 1996.

Notes

1 The set Perm(𝔸) can also be seen as a nominal set with the Perm(𝔸)-action given by conjugation. The support of a permutation π is indeed the set supp(π) as defined in the previous paragraph. ↩

2 This section is best understood by readers familiar with Hyland-Ong-style game semantics, but it is written so that it can be also accessible to the casual reader. ↩