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

MURDOCH J. GABBAY∗

THE π-CALCULUS IN FM

ABSTRACT: FM (Fraenkel Mostowski) techniques are an approach to metaprogramming on syntax in the presence of binding. We develop novel FM theory and with it develop theory of π-calculus syntax and its operational semantics. Technicalities of name binding and also of name generation in transitions are smoothly handled.

1 INTRODUCTION

Fraenkel-Mostowski (FM) techniques were introduced in [Gabbay, 2000; Gabbay and Pitts, 2001]. They were developed to allow us to reason inductively about syntax with binding. Consider a de Bruijn-style datatype of λ-terms:

Λdbdef= Var of N + App of Λdb × Λdb + Lam of Λdb. (1)

Here α-equivalence is equality and this is good but the inductive principle is ‘twisted’:

(∀i. φ(Var(i)) ∧∀t1, t2. φ(t1) ∧φ(t2) →φ(App(t1, t2)) ∧∀t. φ(t) →φ(Lam(t)))→∀t. φ(t)(2)

In the clause φ(t) →φ(Lam(t)) the subterm t of Lam(t) is not what we would normally consider a subterm of the λ-term corresponding to Lam(t).

FM techniques allow α-equivalence to be logical equality, and simultaneously deliver natural induction schemes, as we shall see in this paper for the theory of the π-calculus.

Process calculi abound and many of them involve term-formers for locality, encryption, and so on. These might interact with name-generation and scope extrusion in complicated ways and involve side-conditions on bound and free names. It would be interesting and useful if we could show that FM techniques could simplify these presentations, and perhaps also their proofs.

This paper starts with a brief account of basic FM theory which expands into quite a detailed account of some novel theory which we shall find useful: some improved proofs and definitions of known constructions like abstraction types, and new material on what we call abstractive functions, which turn out to be quite a powerful unifying tool in FM.

We then take a simple π-calculus (without matching or replication) and indicate how to specify its syntax, operational semantics, and some standard operational and syntactic equivalence relations on it. We outline details of the proofs and see that the entire development can be made very close to normal informal practice, only that thanks to FM the treatment of names and binding in syntax and name-generation in operational semantics, is completely rigorous.

We conclude with a brief survey of other techniques, and outline possible future research.

2 A-PERMUTATION

Hypothesise some set of atoms a, b, c, . . . ∈A, which we shall use throughout this document to represent object-level variable names. Also write Pfin(A) for the set of finite subsets of A. Now consider a name-carrying datatype of λ-terms:

Λ = Var of A + App of Λ × Λ + Lam of A × Λ (3)

Capture-avoiding name for name substitution might be defined as:

[b/a]Var(n) = Var([b/a](n))[b/a]App(t1, t2) = App([b/a]t1, [b/a]t2)[b/a]Lam(n, t) = Lam(n, [b/a]t) a, b ≠ n

(4)

[b/a]Lam(a, t) = Lam(a, t)[b/a]Lam(b, t) = Lam(n, [b/a][n/b]t) n = gsym(FV (t) ∪{a, b})

Here gsym(S) takes S ∈Pfin(A) and returns some x ∉S. The notation [b/a](n) denotes the function [b/a] : A →A acting on n, where [b/a]n = n for n ≠ a and [b/a](a) = b.

This is almost a function which distributes through the syntax of a term and acts on the atoms inside it, only we must take account of the fact that Lam(n, t) abstracts n in t.

Now write (a b):A →A for the function such that (a b)(a) = b, (a b)(b) = a, and (a b)(n) = n for n ≠ a, b, and call this a transposition. Using it we can define a form of capture-avoiding name for name substitution more simply:

(b a) · Var(n) = Var((b a)(n))(b a) · App(t1, t2) = App((b a) · t1, (b a) · t2)(b a) · Lam(n, t) = Lam((b a)(n), (b a) · t).(5)
LEMMA 1.

For t ∈ Λ and b, a : A, if b ∉FV (t) then [b/a]t =α (b a).t.

Here we write α-equivalence as =α.

Proof.

By induction on term size using the observation that for c, d ∉ FV(t) (but possibly occurring bound in t), (c d) · t =α t. ■

For example:

(c d) · Lam(d, Lam(c, Var(c))) = Lam(c, Lam(d, Var(d)))

and Lam(c, Lam(d, Var(d))) =α Lam(d, Lam(c, Var(c))) .

DEFINITION 2.

Write π, κ ∈AΠ for the subgroup of functions generated by (a b). Write Id for the identity λa : A.a and ◦ for the group composition, which is functional composition.

Let an FM set be a pair (X, ·) of a set X with an AΠ permutation action · : AΠ × X →X (written infix) satisfying

∀x : X. ∃S ∈Pfin(A). ∀a, b ∉S. (a b) · x = x. (6)

We shall tend to write just X for the FM set (X, ·). We call (6) the finite support property, we shall see why below.

Write FM-Sets for the category of FM sets with objects FM sets X, Y and arrows functions f : X →Y such that ∀a, b. f((a b) · x) = (a b) · f(x).

A permutation action is a function AΠ × X →X which we write infix π · x, satisfying Id · x = x and π · π′ · x = π ◦π′ · x.

DEFINITION 3.

Say x ∈X is equivariant when (a b) · x = x for all a, b.

Thus x is equivariant when we can take S = ∅ in (6) above.

A is an FM set with the natural action (a b) · n = (a b)(n). Any ordinary set, such as B = {⊤, ⊥} boolean truth values, N the natural numbers, or R the reals, can be made an FM set with the trivial action (a b) · x = x for all x, thus such that every element is equivariant.

Given FM sets X and Y the permutation action naturally extends to functions f : X →Y by conjugation, so

((a b) · f)(x) = (a b) ·(f((a b) · x)). (7)

It is not necessarily the case that such a function satisfies (6). For example a choice function Pfin(A) →A cannot, and it is interesting to verify this (see [Gabbay and Pitts, 2001, Remark 4.6] for a discussion). Note that equivariant functions are precisely the arrows of FM-Sets.

2.1 Set-theoretic model of FM-Sets

We obtain a concrete model of FM-Sets as follows. We construct a set-theoretic cumulative hierarchy starting with atoms a ∈A as base elements: in the standard notation V0 = A.

Given Vi we construct Vi+1 by collecting the subsets U ⊆Vi that satisfy (6). This is a model of ZF set theory with atoms (A in this case), along with the extra axiom (6), see [Gabbay, 2000; Gabbay and Pitts, 2001] for a full development.

The permutation action is given by the pointwise action on the elements: formally π·a = π(a) and π·x = {π·y|⏐y∈x} (this is clearly a permutation action).

Functions f are implemented in sets as graphs {⟨x, f(x)⟩}. Applying a permutation according to this action, (a b) · f = {⟨(a b) · x, (a b) · f(x)⟩}, and translating that back into functional notation this is precisely (7).

Recall that the action on a set is pointwise on its elements. Thus an equivariant set X is one such that X = {(a b) · x|⏐ x ∈X} . Equivariant sets can be seen as objects in FM-Sets and arrows as equivariant function- sets between them.

THEOREM 4.

The construction above gives a model of FM-Sets.

COROLLARY 5.

FM-Sets is a boolean topos.

We see why permutation is better-behaved than atom-for-atom substitution [b/a]. If we try giving that a similar inductive interpretation on the set-universe, so [b/a]n = [b/a](x) for x ∈A and [b/a]x = {[b/a]y|⏐ y ∈x} for x ∉A, things do not work out smoothly. For example f = {⟨c,c⟩|⏐c∈A} denotes the identity λx : A.x and (b a) · f = f. However we see that [b/a]f = {⟨c,c⟩|⏐c∈A\{a}} is not equal to f and is no longer even a total function-set fromA to A.

2.2 Support and apartness

DEFINITION 6.

For S ∈Pfin(A) write Fix(S) for the set of π fixing S pointwise:

π ∈Fix(S)def⇔ ∀n ∈S. π(n) = n.

Say π fixes x : X when π ·x = x. Say S ⊆A supports x : X when if π fixes pointwise S then π · x = x:

(S supports x)def⇔ ∀π ∈Fix(S). π · x = x.

Note that Fix(S) is a group; this will be useful later. (6) says in this terminology that every x has a finite supporting set of atoms.

THEOREM 7.

Any x : X has a unique minimal supporting set of atoms. Write it S(x) and call it the support of x.

Proof.

Construct S(x) as ⋂ {S ∈Pfin(A)|⏐ S supports x} . The lemma below proves this supports x. ■

LEMMA 8.

If S and S′ support x then so does S ∩S′.

Proof.

Suppose κ fixes S ∩S′. We must show κ · x = x. Choose some injection ι : S′ \ S ↪→A \ (S ∪S′) and make it into a bijection π by letting π(ιa) = a for a in the image of S′ \ S (note that π ◦π = Id). Since π ∈Fix(S) we know π · x = x. Observe also that π ◦κ ◦π fixes S′, so π ◦κ ◦π · x = x. It follows by group algebra that κ · x = x. ■

In other works S(x) is written ‘Supp(x)’. We prefer a more compact notation here for typographical reasons.

DEFINITION 9.

For x : X and y : Y write

x#ydef⇔ S(x) ∩S(y) = ∅.

We read this as x is (A-)apart from y.

We can verify by calculation that S(a ∈A) = {A}. Two useful results follow: a#b if and only if a ≠ b, and if a, b#x then (a b) · x = x.

S(S ∈Pfin(A)) = S. Write L ∈Pcofin(A) for the set of cofinite sets of atoms. L is cofinite when A \ L is finite. S(L) = A \ L. If U ⊆A is neither finite nor cofinite then S(U) = A so in FM-Sets P(A) = Pfin(A)∪Pcofin(A).

If P is a predicate A →B we can write Иa. P(a) for P ∈Pcofin(A), this is the FM И-quantifier (pronounced ‘New’), familiar from [Gabbay and Pitts, 2001, p.8]. The observation on powersets becomes the some/any property of FM atoms: ¬Иa. P (a) ⇔Иa. ¬P(a). We shall see И as an instance of a very general construction in the next subsection.

Recall that arrows in FM-Sets are equivariant functions f on underlying sets, so f(π · x) = π · f(x). It is then easy to show that S(fx) ⊆ S(x). Again, it is interesting to verify these facts. We shall use them often.

2.3 Abstractive functions and abstractions

DEFINITION 10.

For a : A and y : Y define

[a]ydef=⋂ {U ⊆A × Y|⏐ ⟨a, y⟩∈U ∧S(U) ⊆S(y) \ {a}} . (8)

At least one such U always exists since U = A × Y is equivariant. By calculation S(a) = {a} so the last part of this formula could be read as S(y)\S(a). (8) is an instance of a general construction [x]y whose definition is identical except that we write S(y) \ S(x).

LEMMA 11.

For a, y, and [a]y as above, [a]y is precisely the orbit E of

⟨a, y⟩ under permutations π ∈Fdef= Fix(S(y) \ {a}).

Proof.

Suppose π ∈F. Then π · E = {⟨π·a′,π·y′⟩|⏐⟨a′,y′⟩∈E} . But ⟨a′, y′⟩∈E precisely when a′ = π′ · a andy′ = π′ · y for π′ ∈F, and since F is a group π · E = E. Therefore [a]y ⊆E.

By construction ⟨a, y⟩∈ [a]y. Also π · [a]y = [a]y for all π ∈F, so ⟨π(a), π · y⟩∈ [a]y for all these π. Therefore E ⊆ [a]y. ■

As a corollary, S([a]y) = S(y) \ {a}.

DEFINITION 12.

Define A-abstraction by

[A]Ydef={[a]y|⏐ a : A, y : Y} . (9)

See [Gabbay and Pitts, 2001, Section 5]. The canonical map abs:A×Y → [A]Y ‘binds’ a (or more properly the support of a) in y. abs is otherwise injective:

LEMMA 13.

If [a]y = [a]y′ then y = y′.

Proof.

By easy calculation. ■

COROLLARY 14.

abs : A × Y → [A]Y is universal amongst F : A × Y →Z such that ∀a, y. a#F(a, y). Thus [a]y ‘y with a bound’. Since a is bound—abs is not injective and for any b#y, (a b) · [a]y = [a]y—we introduce a nameless notation ˆy for an arbitrary element of [A]Y .

Abstraction types with their universal properties are an example of an abstractive function.

2.4 Abstractive functions

Any f : X →Y induces an inverse map f ∗ : Y →P(X)

f ∗: y : Y↦ −→{x : X|⏐ f(x) = y} .

f ∗(y) partitions into orbits under Fix(S(y)) (as well as any other subgroup of AΠ). Write Of (y) for this particular set.

Each orbit O has a breadth |S(z ∈O)| the cardinality of S(z) of a representative z ∈O. Write this |O|.

DEFINITION 15.

Suppose f is such that for all y there is a unique orbit M of greatest breadth:

∃M ∈Of(y). ∀O ∈Of(y). |O| ≥|M| =⟹O = M

Write Mf (y) for this orbit when it exists and say f has orbits of maximal breadth.

The set ⋃y Mf(y) is an FM set, write it just Mf.

DEFINITION 16 (Abstractive function).

Say f : X →Y is Barendregt abstractive or just abstractive when it has orbits of maximal breadth. When Of (y) is always a singleton set, so orbits are maximal because they are unique, say f is purely abstractive.

An abstractive f:X →Y induces a purely abstractive restriction f:Mf → Y . By construction, if f is surjective, so is its restriction to Mf.

1. For f = λx.∗:A → 1 the set Of (∗) has just one orbit, A, with breadth 1. f is purely abstractive.

2. For f = λx.∗ : A2 →1 the set Of (∗) has two orbits, {⟨a,b⟩|⏐a≠b}with breadth 2 and {⟨a, a⟩|⏐ a : A ≅= A} with breadth 1.f is Barendregt abstractive.

3. For f = λx.∗ : Pfin(A) → 1 the set Of (∗) is isomorphic to N. There is no orbit of maximal breadth and f is not abstractive.

4. For f = λx.A + A : 1 the set Of (∗) has two orbits of equal breadth. f is not abstractive.

5. For f = abs : A × Y → [A]Y the set Of ([a]y) is the orbit E described in Lemma 11. abs is purely abstractive.

6. For f = π2: A × Y →Y (second projection)Of (y) has one orbit of maximal breadth {⟨a, y⟩|⏐ a#y} . f is Barendregt abstractive.

7. Recall from (3) the datatype Λ. The quotient by α-equivalence, write it α : t↦ → [t]=α : Λ → Λ/=α, is Barendregt abstractive. Mf is the set of Barendregt representative terms.

Abstractive functions give an abstract account of the Barendregt variable convention (amongst other things), because the orbit of maximal breadth consists of x representing y with the most possible different names for those ‘bound’ by the function. Abstractive functions are also related to FreshML abstraction-patterns. The interpreter generates fresh names for atoms in (possibly nested) abstraction-patterns.

If we read these example f :X →Y ‘backwards’ as ‘maps’ Y →Mf, they do the following respectively: choose a canonical atom, choose a canonical pair of distinct atoms, choose a canonical largest finite set of atoms (there is none), choose a canonical atom in a disjoint sum (there is none), choose a fresh atom for y, choose a Barendregt representative for t. Theorem 21 will make this intuition formal.

LEMMA 17.

If f : X →Y and g : X′ →Y ′ have orbits of maximal breadth then so do f + g : X + X′ →Y + Y ′ and f × g : X × X′ →Y × Y ′ (with the obvious definitions).

If f : X →Y and g : Y →Z have orbits of maximal breadth so does g ◦f : X →Z.

Proof.

(Sketch) The case of disjoint sum is very easy. For the case of products, Mf×g⟨y1, y2⟩ is the Fix(S(⟨y1, y2⟩))-orbit of ⟨z1, z2⟩∈Mf (y1) × Mg(y2) where z1 and z2 are chosen such that S(z1)\S(y1) and S(z2)\S(y2) are disjoint (which makes the cardinality of S(z1) ∩S(z2) minimal, details omitted).

The case of functional composition is also easy. Mg◦f (z) is equal to Mg(u) for a representative u ∈Mf(z). ■

COROLLARY 18.

If f:X →Y and g:X′ →Y ′ are (Barendregt) abstractive then f +g:X +X′ →Y +Y ′ is (Barendregt) abstractive and f ×g:X ×X′ → Y ×Y ′ is Barendregt abstractive. If f:X →Y and g:Y →Z are (Barendregt) abstractive then so is g ◦f : X →Z.

Proof.

Using Lemma 17. ■

DEFINITION 19.

For f :X →Y abstractive and surjective and F :X →Z, say F factors through f on orbits of maximal support when there is some h : Y →Z such that for all x ∈Mf, F(x) = hf(y).

x ∈MfF- Fx = hy.............. hy = fx.f?(10)
DEFINITION 20.

For f and F as in the previous definition, write F ≤ab f when ∀x ∈Mf. S(Fx) ⊆S(fx).

THEOREM 21.

For f and F as above, F ≤ab f if and only if F factors through f on orbits of maximal support.

Proof.

Suppose for all x ∈Mf, Fx = h ◦f(x). Then S(Fx) = S(hf(x)) ⊆ S(fx).

Conversely suppose F ≤ab f and x ∈Mf. Write y = fx and let hy be Fx. If Fx′ = y then x′ = π·x for some π ∈Fix(S(y)) and Fx′ = Fπ·x = π·(Fx). Now S(Fx) ⊆S(y) by assumption so π · (Fx) = Fx. So h is well-defined.

■

As a corollary, purely abstractive surjective f : X →Y universal amongst maps F : X →Z such that F ≤ab f. If f is Barendregt abstractive and surjective, it is universal ‘on orbits of maximal breadth’.

• For abs : A × X → [A]X the condition F ≤ab abs is S(F(a, x)) ⊆ S(x) \ S(a). We recover Corollary 14. Compare with [Gabbay and Pitts, 2001, p.15, Lemma 6.3].

• For π2 : A × X →X the condition F ≤ab f is a#F(a, x). Write Иa. F(a, x) for the unique value of F(a, x) when a#x (for fixed x). This is a functional version of the И quantifier mentioned in the last subsection.

When Z = B the condition a#F(a, x) is always satisfied since F(a, x) = ⊤ or F(a, x) = ⊥, and we obtain the И-quantifier mentioned in §2.3. (The X makes parameters explicit.)

Now suppose that F = P : A × X →B. The universality property on orbits of maximal breadth then gives Иa. P(a, x) if and only if ∀a. a#x ⇒P(a, x), a known commutativity property between И and ∀ which we shall find useful.

• Recall that for Λ defined in (3) the quotient α : Λ → Λ/=α is Barendregt abstractive. Therefore F : Λ →Z respects α-equivalence on Barendregt representative terms t precisely when for all such t and a ∈bn(t), a#F(t).

DEFINITION 22.

When f : X →Y is abstractive and F ≤ab f, write the h we construct above as ИfF : Y →Z.

We write (ИfF)(y) as Иy=f(x). Fx, this is the unique value of F at x such that f(x) = y and x is a Barendregt representative in the sense discussed above.

We call this the generalised И quantifier.

3 THE π-CALCULUS

3.1 An inductive datatype of π-calculus terms up to binding

Define an inductive FM datatype of π-calculus terms up to =α:

Πdef= 1 + Π + A2 × Π + A × [A]Π + Π2 + [A]Π P ::= 0 | x̅yP | x ˆP | (P | P) | ν ˆP(11)

To construct a term of the form ν ˆP it suffices to provide y : A, P : Π, and apply ν to the abstraction [y]P. Recall from after Corollary 14 that we can write such an abstraction namelessly as ˆP.

Π is inductively defined and has a primitive recursion scheme. For any Z, given

f0 : Z fτ : Π →Z fo : A2 × Π →Z fi : A × [A]Π →Z fp : Π2 →Z fν : [A]Π →Z

there is a unique f : Π →Z such that all of the following hold:

f(0) = f0f(τ.P) = fτP f(x̅y.P) = fo(x, y, P) f(x P̂) = fi(x, P̂ )f(P | Q) = fp(P, Q) f(ν P̂) = fν( P̂). (12)

However abstraction abs : A × Π → [A]P has special properties formalised in its being an abstractive function. We take advantage of this to write primitive recursive definitions which look like standard ones.

Recall the notations for renamings [b/a] from §2.

DEFINITION 23.

Analogously to AΠ write σ ∈AΣ ⊆AA for the monoid generated by renamings [b/a], and write Id for the identity λx.x.

By (12) we can define name substitution on Π by primitive recursion as follows:

0σ = 0 (τ.P)σ = τ.Pσ (x̅y.P)σ = x͞σyσ.Pσ(x ˆP )σ =ИˆP=[n]P. xσ[n](Pσ)(P1 | P2)σ = P1σ | P2σ (ν ˆP )σ =ИˆP=[n]P. ν[n](Pσ).(13)

We also show an induction principle derived from primitive recursion. For a predicate φ on Π, if

For all x, P, Q, ˆP φ(0) φ(P) →φ(τ.P) φ(P) →φ(x̅y.P) φ(P) ∧φ(Q) →φ(P | Q)ИˆP=[y]P. φ(P) →φ(x[y]P)ИˆP=[y]P. φ(P) →φ(ν[y]P)

hold, then ∀P. φ(P). (14)

A more usual induction scheme would have clauses for input and restriction as follows:

∀x, y, P. φ(P) →φ(x[y]P) ∀y, P. φ(P) →φ(ν[y]P)

These do not assume y fresh, and since this is the only case we care about in practice it can be useful to, in effect, build it into the datatype.

If y#σ and y ≠ x then

yσ = y (ν[y]P)σ = ν[y](Pσ), and (x[y]P)σ = xσ[y](Pσ). (15)

We read the second two clauses ‘for free’ off the appropriate clauses of (13) (input and restriction), because y#[y]P always holds. Concerning the first clause, we say of many FM results in this paper that they follow ‘by (easy) calculation’. The following useful result follows by slightly involved calculation, for once we give it in full.

LEMMA 24.

y#σ if and only if y is neither in the domain nor the image of σ as a partial function on atoms.

Proof.

Suppose y#σ. σ is finitely generated by renamings so cofinitely many atoms z are not in the domain or image of σ, or formally ∀z′. σz′ = z ⇒z = z′.

By (6) also cofinitely many z have z#σ, so choose one z such that both hold. Then (y z)(σy) = ((y z) · σ)((y z) · y) = σz = z, so σy = y. Also suppose that y = σy′ for some y′. Then z = (y z) · y = σ((y z) · y′). So (y z) · y′ = z and therefore y′ = y.

Conversely, suppose y is neither in the domain nor image of σ. Take fresh z not in the domain or image as before. Write τ = (z y) ·σ. We show τ = σ by applying them to arbitrary z′.

τz′ = (z y) · (σ(z y) · z′) by definition. τz = (z y) · σy = z = σz. τy = (z y) · σz = y = σy. Otherwise τz′ = (z y) · σz′. We know σz′ ≠ z, y, so this is just σz′. ■

COROLLARY 25.

If y#σ and y#x, then y#σx.

We shall use these results often in our proofs.

We return briefly to (13): (x ˆP)σ =ИˆP=[n]P. xσ[n](Pσ) the clause for input can be equivalently expressed by

∀x.Иn. ∀P. (x[n]P)σ = xσ[n]Pσ. (16)

(We can treat the clause for restriction similarly.) This presentation style is useful, we explore it in detail in the next subsection.

3.2 Operational semantics for Π

DEFINITION 26 (Actions).

Define a datatype of actions by

Actdef= 1 + A2 + A2α, µ ::= τ | x̅y | xy.(17)

Write ⟨P, [z]⟨l, Q⟩⟩ an element of Π × [A](Act × Π) as Pz.l→Q.

DEFINITION 27.

We define an early and late transition relations

→⊆Π × [A](Act × Π)

inductively by the rules of Figure 1.

figure1-rulesτ: ∀P.Иz. τ.Pz.τ→POut: ∀x, y, P.Иz. x̅y.Pz.x̅y→PIn: ∀x, n.Иy. ∀P. x[y]Py.xn→P[n/y]Par1: ∀P1, P2.Иz. ∀µ, Q1.P1z.µ→Q1P1 | P2z.µ→Q1 | P2Close1: ∀P1, P2, x.Иy, z. ∀Q1, Q2.P1y.x̅y→Q1P2z.xy→Q2P1 | P2z.τ→ν[y](Q1 | Q2)Com1: ∀P1, P2, x, y.Иz.P1z.x̅y→Q1P2z.xy→Q2P1 | P2z.τ→Q1 | Q2Open: ∀x.Иy. ∀P, Q.Иz.Pz.x̅y→Q ν[y]Py.x̅y→QRes: ∀µ, z.Иy. ∀P, Q.Pz.µ→Qν[y]Pz.µ→ν[y]Q(a) Early transitionsIn: ∀x.Иy. ∀P. x[y]Py.xy→PClose1: ∀P1, P2, x.Иy. ∀Q1, Q2.P1y.x̅y→Q1P2y.xy→Q2P1 | P2y.τ→ν[y](Q1 | Q2)Com1: ∀P1, P2, x, y, Q1.Иz. ∀Q2.P1z.x̅y→Q1P2z.xz→Q2P1 | P2z.τ→Q1 | Q2[z/y] (b) Late transitions as early, except for rules shown

We elide symmetric versions (Par2), (Close2), and (Com2).

Figure 1. FM presentation of late and early π-calculus transitions.

A transition in our sense is an element ⟨P, [z]⟨µ, Q⟩⟩. We model bound output by literally outputting a bound name. For example the canonical ‘output of a bound channel name’ νy.x̅yx̅(y)→ 0 which may be well-known to the reader [Milner et al., 1992], but also νy.x̅yx̅(y′)→ 0 and νy.x̅yx̅(z)→ 0, are represented by the single element ⟨νy.x̅y, [y]⟨x̅y, 0⟩⟩ which we write as νy.x̅y[y]x̅y→ 0. The restriction that y ≠ x is built into the the order of the quantifiers ∀x.Иy. ∀P, Q in (Open), which we now discuss.

By the discussion on quantifiers at the end of the previous section we can expand the quantifiers ∀x.Иy. ∀P. body of the late (In) as ∀x, y, P. y#x ⇒ body. We can expand the quantifiers ∀x, n.Иy. ∀P. body of the early (In) as ∀x, y, P. y#x, n ⇒body.

For a more complex example, the quantifiers ∀x.Иy. ∀P, Q.Иz. body of (Open) expand as ∀x, y, P, Q, z. y#x ∧z#x, y, P, Q ⇒body. Now recall that y#x is equivalent to y ≠ x and y#P equivalent to y ∉n(P). Here n(P) is the free names of P, we write it just n because in the FM datatype there are no bound names.

Thus we see how the mix of ∀ and И encodes side-conditions on free and bound names. The advantage of using Иz is that we can assume z fresh also for other parts of our context, for example a substitution σ, or perhaps a different process R. We now consider an example.

Recall the notation σ : AΣ and the renaming action, defined in and after Definition 23. Recall from Lemma 24 that if y#σ then yσ = y. [Milner et al., 1992, Lemma 3] in this framework and notation becomes:

LEMMA 28.

For σ : AΣ

∀P.Иz. ∀α, Q. Pz.α→Q =⇒Pσz.(ασ)→ Qσ.

Here ασ denotes the evident inductive action of σ on actions α.

Proof.

By induction on the transition using hypothesis

φ(t)def= ∀P.Иz. ∀α, Q. t = (Pz.α→Q) =⇒Pz.α→Q ∧Pσz.(ασ)→ Qσ.

The case (Close1). Suppose P1, P2, x, y, Q1, Q2 are such that y#P1, P2, x, and σ. Suppose also P1y.x̅y→Q1 and P2y.xy→Q2. By Lemma 24 y#P1σ, so by induction hypothesis P1σy.x͞σy→ Q1σ. Similarly for P2. y#P1σ, P2σ, xσ so we apply (Close1) to these two new transitions.

The case (Open). Suppose we have x, y, P, Q, z and y#x and z#x, y, P, Q. Suppose Pz.x̅y→Q. By induction hypothesis Pσz.x͞σy→ Qσ. Also we know that y#xσ and z#xσ, yσ, Pσ, Qσ, so we can apply (Open) to this new transition. ■

In the proof above we deconstruct a transition tr choosing suitably fresh names for the bound variables, and reconstruct it with σ applied, verifying that the appropriate freshness conditions hold. When we deconstruct we took advantage of the FM framework to choose y fresh also for σ, so that yσ = y (capture avoidance for free).

Continuing to read [Milner et al., 1992] we see that further results become trivial or easy. Lemma 4 of [Milner et al., 1992] becomes equivariance of →:

LEMMA 29.

For π : AΠ, and for P, z, µ, and Q, with z#π, P,

Pz.µ→Q =⇒π.Pz.(π.µ)→ π.Q.

Lemma 5 part (a) and the second half of (b) for bound output of [Milner et al., 1992] disappear because Π is already up to α-equivalence and because bound outputs really do bind the output name. The first half of Lemma 5 part (b) is subsumed in the FM version by Lemma 28.

We give appropriate definitions of bisimulation for the early and late calculi respectively. Early bisimulation in the early transition relation is the greatest symmetric relation closed under the rule

P ≃Q =⇒Иz. ∀α, P ′.(Pz.α→P ′ =⇒∃Q′. Qz.α→Q′ ∧P ′ ≤Q′)(18)

Late bisimulation in the late transition system is the greatest symmetric relations such that if P ≃Q then

∀z, P ′. Pz.τ→P ′ =⇒∃Q′. Qz.τ→Q′ ∧P ′ ≃Q′Иz. ∀x, y, P ′. Pz.x̅y→P ′ =⇒∃Q′. Qz.x̅y→Q′ ∧P ′ ≃Q′Иz. ∀x, P ′. Pz.xz→P ′ =⇒∃Q′. ∀y. Qz.xz→Q′ ∧P ′[y/z] ≃Q′[y/z](19)

We obtain an early version in the late transition system by swapping ∃ and ∀ in the last clause to ∀y. ∃Q′, in the way we would expect.

DEFINITION 30.

For P, Q ∈ Π, we write •≃ for the symmetric relation defined by

P•≃Q ⇐⇒∀σ : AΣ. Pσ ≃Qσ. (20)
LEMMA 31.

≃ is preserved by all term-formers except for input. •≃ is preserved by all term-formers.

Proof.

By inductions on →. We have checked the proofs in detail. They are as systematic as the proof of Lemma 28 and by simple induction. ■

3.3 Structural congruence

We can use FM to specify freshness constraints also for structural congruences. For example:

DEFINITION 32.

Define a relation ≡ on Π inductively as the smallest congruent equivalence relation closed additionally under the rules

∀P, Q, R. P | 0 ≡P P | Q ≡Q | P (P | Q) | R ≡P | (Q | R)Иy. νy.0 ≡0 ∀P.Иy. ∀Q. P | νy.Q ≡νy.(P | Q)Иy, y′. ∀P. νyνy′.P ≡νy′νy.P(21)

We call this structural congruence.

(These rules are modified from [Parrow, 2001, Table 2, p.10].)

THEOREM 33.

Structural congruence implies early bisimilarity: P ≡Q ⇒ P ≃Q.

Proof.

(Sketch) By standard FM-style induction. Let Φ≃ : P(Π × Π) → P(Π×Π) be the monotone operator on relations implicit in (18). Thus a relation R is a bisimulation when R ⊆ Φ≃(R) and ≃def= ⋃ {R|⏐ R ⊆Φ≃(R)} is the largest bisimulation.

Then

• Rdef= {⟨νy.0, 0⟩} satisfies Φ≃(R) ⊆≡.

• Rdef={⟨νu.(P | Q), P | νu.Q⟩|⏐ u#P} satisfies Φ≃(R) ⊆≡.

• Rdef={⟨νyνy′.P, νy′νy.P⟩|⏐ y′#y} satisfies Φ≃(R) ⊆≡.

• The relations

R0 = {⟨P | 0 , P⟩}, R1 = {⟨P | Q , Q | P⟩}, and R2 = {⟨(P | Q) | R , P | (Q | R)⟩} satisfy Φ≃(Ri) ⊆≡for i = 0, 1, 2.

Proofs by induction.

It is easy to prove by induction that for all P, Q : Π and substitutions σ, if P ≡Q then Pσ ≡Qσ; И avoids variable capture as in the proof of Lemma 28.

Using all of these facts we can verify that ≡⊆ Φ≃(≡) and hence ≡⊆≃.

■

τ: τ.Pτ→′ P
Out: x̅y.Px̅y→′ PIn: xy.Pxn→′ P[n/y]Par1:P1µ→′ Q1P1 | P2µ→′ Q1 | P2bn(µ) ∩fn(P2) = ∅
Close1:P1x̅(y)→′ Q1, P2xy→′ Q2P1 | P2τ→′ νy.(Q1 | Q2)y ∉fn(P2)
Com1:P1x̅y→′ Q1, P2xy→′ Q2P1 | P2τ→′ Q1 | Q2
Open:Px̅y→′ Q νy.Px̅(y)→′ Qy ≠ xRes:Pµ→′ Qνy.Pµ→′ νy.Qy ∉n(µ)

Symmetric versions (Par2), (Close2), and (Com2) are elided.

Figure 2. A conventional presentation of early π-calculus transitions.

4 EQUIVALENCE WITH CONVENTIONAL PRESENTATION

It remains to verify that the presentation of Π with its transition system → in §3 corresponds to the π-calculus as we know it from elsewhere.

Define a datatype of terms of the π-calculus not up to binding

Π′def= 1 + Π′ + A2 × Π′ + A2 × Π′ + Π′2 + A × Π′P ::= 0 | τ.P | x̅y.P | xy.P | (P | P) | νnP(22)

Define a datatype of actions by

Act′def= 1 + A2 + A2 + A2α, µ ::= τ | x̅y | x̅(y) | xy(23)
DEFINITION 34 (Conventional early transition system for Π′).

The transitions of Π′ are written Pµ→′ Q and inductively defined in Figure 2.

Abstraction inductively induces a map η : Π′ → Π:

η0 = 0 η(τ.P ′) = τ.ηP ′η(x̅y.P ′) = x̅y.ηP ′η(xn.P ′) = x[n]ηP ′η(P ′ 1 | P ′ 2) = ηP ′ 1 | ηP ′ 2η(νn.P ′) = νn.ηP ′.(24)
LEMMA 35.

For P ′: Π′, y ∉fn(P ′) ⇐⇒y#η(P ′).

Proof.

By induction on syntax for fixed y using inductive hypothesis

φ(P ′)def⇔ y ∉fn(P ′) ↔y#η(P ′).

We consider just the case of restriction. Suppose φ(P ′). We verify φ(νn.P ′).

If n ≠ y then y ∉fn(P ′) precisely when y ∉fn(νn.P ′). Also, y#P ′ precisely when y#ν[n]η(P ′). Since ν[n]η(P ′) = η(νn.P ′) the result follows.

If n = y then y ∉fn(νy.P ′) and also y#ν[y]η(P ′). Since ν[n]η(P ′) = η(νn.P ′) the result follows. ■

LEMMA 36.

η(−) is surjective. Its kernel is precisely α-equivalence on Π′.

Proof.

By inductions on syntax. ■

η is also Barendregt abstractive, by Corollary 18.

In the last section we mentioned that Π is an FM datatype and has no names of bound atoms. η and И are a formal sense in which we can give them names.

η extends pointwise to a map P(Π′ × Π′) →P(Π × Π) and hence to a map from a relation R on Π′ to a relation, write it ηR, on Π. It also gives rise to a mapη−1 from P(Π × Π) to P(Π′ × Π′), R maps to{⟨P′,Q′⟩|⏐ηP′RηQ′} .

THEOREM 37.

η≃= ≃, where ≃ is early bisimilarity or late bisimilarily on Π′ and Π respectively.

Proof.

We show that η≃ is a bisimulation in the FM sense, and that η−1≃ is a bisimulation in the traditional sense, for a notion of bisimulation as in (18) and (19). ■

THEOREM 38.

The transition relations →⊆ Π × Π and →′⊆ Π′ × Π′ are related as shown in Figure 3.

Note that (26) refers only to Barendregt representatives. This is technically convenient for the proof. Once we have it we can take advantage of results on transitions for the standard name-carrying Π′, such as [Milner et al., 1992, Lemma 5], to strengthen it to all P ′, Q′: Π′.

The proof of Theorem 38 is in two parts corresponding to (25) and (26). The first part is by induction on →′, the second by induction on →. To save space we do not re-write out the induction hypotheses in complete formality.

For any P ′, Q′: Π′, x, y : A, write P = ηP ′, Q = ηQ′. Then

figure3-equation25P ′τ→′ Q′ =⇒Pτ→Q ∧P ′xy→′ Q′ =⇒Pxy→Q ∧P ′x̅y→′ Q′ =⇒Px̅y→Q ∧P ′x̅(y)→′ Q′ =⇒Py.x̅y→Q.(25)

For any P, Q : Π, x, y, :A, choosing fresh names for the bound atoms in P and Q using И;

figure3-equation26ИP = ηP ′, Q = ηQ′. Pτ→Q =⇒P ′τ→′ Q′∧Pxy→Q =⇒P ′xy→′ Q′∧Px̅y→Q =⇒P ′x̅y→′ Q′∧Py.x̅y→Q =⇒P ′x̅(y)→′ Q′.(26)
Figure 3. Equivalence of conventional and FM presentations.
Proof.

(Of Theorem 38, first part, (25))

The case (In) of →′. Suppose xy.Pxn→′ P[n/y]. We would like to apply (In) of → to x, n, y, η(P), and some z#x, n, y, η(P). However to do so we must verify y#x, n, and this does not hold. We draw on the library of results for the conventional π-calculus to deduce that for y′#x, n, xy′.P[y′/y] xn→′ P[y′/y][n/y′]. xy′.P[y′/y] is α-equivalent to xy.P so both map to x[y]η(P). We can now proceed.

The case (Par1) of →′. We consider only the case µ = x̅(y). Suppose

P1x̅(y)→′ Q1. Suppose also y ∉fn(P2) for some P2. Then P1 | P2x̅(y)→′ Q1 | P2. By the inductive hypothesis η(P1) y.x̅y→η(Q1). It remains to apply (Par1) to deduce η(P1) | η(P2) y.x̅y→ η(Q1) | η(P2). We must verify y#η(P1), η(P2). We know y#η(P2) since y ∉fn(P2). We know y#η(P1) because y ∉fn(P1), this is inductively guaranteed in the conventional theory by the assumption that P1 can output y as a bound name.

The case (Open) of →′. Suppose Px̅y→′ Q and y ≠ x. By inductive

hypothesis we have η(P) z.x̅y→η(Q) for z#P, x, y, Q. We deduce νy.Px̅(y)→′ Q. We wish to apply (Open) of → to x, y, η(P), η(Q), z to deduce ν[y]η(P) y.x̅y→ η(Q). The freshness condition y#x reduces to y ≠ x, which is just the side-condition. ■

Proof.

(Of Theorem 38, second part, (26)) The case (In) of →. Suppose x, n, y, P, z are such that y#x, n and z#x, n, y, P. We apply (In) to deduce x[y]Pz.xn→ P[n/y]. Now choose distinct names fresh for x, n, y, P, z and for the bound atoms in P, to obtain a Barendregt representative P ′: Π′ of P, so η(P ′) = P. We wish to apply (In) of →′ to x, y, P ′, n. We can do this, there are no side conditions.

The remaining issue is whether, for example, η(xy.P ′) = x[y]P and η(P ′[n/y]) = P[n/y]. These follow from appropriate freshness hypotheses. For example, the names for bound variables in P ′ were chosen fresh for a context which included n and y, so accidental capture is impossible.

The case (Par1) of →. We consider only the case of a bound output. Suppose we have P1, P2, y, Q1, Q2 with y#P1, P2, and P1y.x̅y→Q1. By inductive hypothesis for fresh choices of bound names η(P ′ 1) = P1, η(P ′ 2) =

P2, η(Q′ 1) = Q1 we have P ′ 1x̅(y)→′ P ′ 2. The side-condition y ∉fn(P ′ 2) follows because fn(P ′ 2) = S(P2) and y#P2, so we may apply (Par1) of →′.

The case (Open) of →. Suppose x, y, P, Q, z have y#x and z#x, y, P, Q, and suppose Pz.x̅y→Q. By inductive hypothesis for fresh choices of bound names η(P ′) = P, η(Q′) = Q we have P ′x̅y→′ Q′. The side-condition y ≠ x follows from y#x. ■

5 CONCLUSIONS

FM techniques were developed to inductively represent syntax-with-binding, so that we can reason and program on it structurally. These ideas have been considered mathematically and logically [Gabbay and Pitts, 2001; Urban et al., 2003; Pitts, 2001] and also implemented as a dialect of ML [FreshML, 2003; Pitts and Gabbay, 2000; Shinwell et al., 2003]—yet until now FM literature has for simplicity only really considered the syntax of elementary λ-calculi.

The π-calculus is a natural choice for a more complex study. Its binding is more complicated and includes scope extrusion, name passing, and name-generation (also called dynamic allocation).

We have seen how standard structural specifications of transition systems translate quite directly to FM, with the equivalence being in essence just the quotient map by binding which we would hope for. We have seen how side-conditions on free and bound names are taken care of by judiciously mixing ∀ and И quantifiers.

In the course of this research we discovered the notion of an abstractive function and the generalised И quantifier described in §2.4. We needed it first to express Theorem 38, but then realising its generality we devoted some space to developing it.

In the syntax-free mathematical context of FM sets, abstractive functions and generalised И provide a unifying account of (syntax-free mathematical generalisations of) the Barendregt variable naming convention, FreshML pattern-matching, and the И quantifier.

Related work. FM techniques are related to presheaf semantics for syntax, see for example [Fiore et al., 1999; Fiore and Turi, 2001]. The presheaves used there are SetI and SetF (I the category of finite sets and injections, F that of finite sets and all maps).

Presheaves can be viewed as sets with ‘actions’ at ‘stages’, so the two presheaf categories above make injective and possibly non-injective renamings respectively intensional features of the underlying universe. An FM set X gives a presheaf mapping S ∈Pfin(A) to {x ∈X|⏐ S(x) ⊆S} . It is a special one though, such that every element appears at a unique minimal stage: its support, this is Theorem 7. In this way FM maintains a ‘first-order set-based’ presentation which we feel is particularly clear.

Approaches based on Higher-Order Abstract Syntax (HOAS) can suffer the following three problems. First, the function spaces can be too large. For this reason the Theory of Contexts has no ι unique choice [Bucalo et al., 2001]. Second, function spaces can destroy inductive structure, so there can be issues with deriving inductive principles for the datatypes. Thirdly, these problems overcome, if we need to generate names we may need to index all our predicates and relations by an explicit set of known names (called X or A, say) see for example [Bruni et al., 2002; Honsell et al., 2001, Fig.2] and [Cattani and Sewell, 2000, Fig.1]. This is a programming analogue of the the presheaf semantics mentioned above. Other more first-order set-based presentations may do this too, for example [Cattani and Sewell, 2000]. These indexes can be cleanly presented, but it would still be better if they were not there at all.

Two advantages of HOAS are that they can be implemented in existing frameworks (wheras FM based on FM sets, cannot), and that name-passing can be modelled by function application. Name-passing in this paper is modelled by substitution defined inductively on syntax in (13).

We already discussed de Bruijn approaches in the Introduction. Their ‘twisted’ inductive principles can cause great technical difficulties. In studies by Hirschkoff [Hirschkoff, 1999; Hirschkoff, 1997] 75 per cent of the technical lemmas of a full formalisation of the π-calculus regarded ‘straightening them out’.

Of all approaches to syntax, surely the benchmark is name-carrying syntax trees like the one in (3). The problems with capture-avoidance for such datatypes are well-known. This paper shows how FM approach treats names in the π-calculus in a way which is close to this elementary practice, but entirely rigorous. This will hopefully serve as a model and theoretical foundation for more complex examples.

We should mention that a lot of the problems with name-carrying syntax only appear if we insist on a purely structural approach. In [Martin and Gordon, 1993] pages 24 and 25 the authors are primarily interested in expressivity (of the spi-calculus). Accordingly they adopt a ‘chemical’ presentation after [Berry and Boudol, 1990]; transitions are defined on processes modulo scope extrusion and other structural congruence rules.

Even here, FM can help. We saw in §3.3 how it takes care of side-conditions for freshness in scope extrusion. Of course this is a simple observation, but for more complex calculi with various forms of binding, it can be useful both for presentation and theory.

Future work. The models of this paper are purely syntactic, and not semantic. It is a feature of FM abstraction that we may only choose a fresh name for the bound name. Wheras in HOAS abstraction is function abstraction, and name-passing can therefore be function application, here we use the renaming (inductively!) defined in Definition 23.

There is nothing wrong with this, but it does block an obvious abstract account of name-passing based on FM abstractions instead of functions. Other semantic models based on presheaves, such as [Fiore et al., 1996; Cattani et al., 1997], also use function spaces. [Fiore and Turi, 2001] makes the same observation of models of syntax in SetI and goes on to provide a comprehensive categorical framework to account for name and value passing. It might be interesting to carry out a similar programme using in an FM style. Even if this turns out to be equivalent to the presheaf material, which we doubt because our account would have a notion of support, it would be a different perspective and presentation.

We see the most immediate and concrete application for this work to History-Dependent (HD) Automata [Montanari and Pistore, 1997], which are a notion of model based only on syntax. An HD automaton is roughly speaking a graph of representative processes encoded in de Bruijn notation, with edges transitions annotated by permutations between the names to take care of reindexing and name-generation (the many flavours of HD automaton corresponding to different and differently-detailed implementations of this idea). This could be viewed as an FM construction and this paper is a first step towards constructing it.

A related approach to the same issue is θ-automata described in [Bruni et al., 2002]. Roughly, these models are obtained by adding a meta-level restriction operator θ to the syntax of terms, which acts only at top level and restricts certain names in a process. Name-generation is modelled by generating a name, then restricting it. This concept is clearly related to the datatype →⊆ Π × [A](Act × Π) developed in this paper, with restriction replaced by FM abstraction. The concept of model in that work corresponds to that of an HD automaton, only implemented using terms up to α-equivalence (bound by θ) instead of a de Bruijn representation.

We plan to develop an FM based structure unifying these two approaches. Since FM now comes equipped with a programming language FreshML [FreshML, 2003], datatypes and inductive definitions should translate into programs.

ACKNOWLEDGEMENTS

My grateful thanks go to Marino Miculan, Furio Honsell, and Ugo Montanari. I also recognise the support of UK EPSRC grant GR/R07615 which partly funded this research.

BIBLIOGRAPHY

[Berry and Boudol, 1990] Gerard Berry and Gerard Boudol. The chemical abstract machine. In Proceedings of the seventeenth annual ACM symposium on Principles of programming languages, pages 81–94, New York, NY, USA, 1990. ACM Press.

[Bruni et al., 2002] R. Bruni, F. Honsell, M. Lenisa, and M. Miculan. Modeling fresh names in pi-calculus using abstractions. Technical Report 21/2002, Dipartimento di Matematica e Informatica, University of Udine (Italy), April 2002.

[Bucalo et al., 2001] A. Bucalo, M. Hofmann, F. Honsell, M. Miculan, and I. Scagnetto. Consistency of the theory of contexts, 2001.

[Cattani and Sewell, 2000] Gian Luca Cattani and Peter Sewell. Models for name-passing processes: Interleaving and causal. In Logic in Computer Science, pages 322–332, 2000.

[Cattani et al., 1997] Gian Luca Cattani, Ian Stark, and Glynn Winskel. Presheaf models for the pi-calculus. In E[ugenio] Moggi and G[iuseppe] Rosolini, editors, Proceedings of the 7th International Conference on Category Theory and Computer Science (Santa Margherita Ligure, Italy, September 4–6, 1997), volume 1290 of LNCS, pages 106–126. Springer, 1997.

[Fiore and Turi, 2001] Marcelo Fiore and Daniele Turi. Semantics of name and value passing. In Proc. 16th LICS Conf., pages 93–104. IEEE, Computer Society Press, 2001.

[Fiore et al., 1996] Marcelo Fiore, Eugenio Moggi, and Davide Sangiorgi. A fully-abstract model for the π-calculus (extended abstract). In Eleventh Annual Symposium on Logic in Computer Science (LICS) (New Brunswick, New Jersey), pages 43–54. IEEE, Computer Society Press, July 1996.

[Fiore et al., 1999] M. P. Fiore, G. D. Plotkin, and D. Turi. Abstract syntax and variable binding. In 14th Annual Symposium on Logic in Computer Science, pages 193–202. IEEE Computer Society Press, Washington, 1999.

[FreshML, 2003] FreshML. FreshML homepage, 2003. http://www.freshml.org.

[Gabbay and Pitts, 2001] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13:341–363, 2001.

[Gabbay, 2000] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.

[Hirschkoff, 1997] Daniel Hirschkoff. A full formalization of pi-calculus theory in the Calculus of Constructions. In E. Gunter and A. Felty, editors, Proceedings of the 10th International Conference on Theorem Proving in Higher Order Logics (TPHOLs’97), pages 153–169, Murray Hill, New Jersey, August 1997.

[Hirschkoff, 1999] Daniel Hirschkoff. Mis en oeuvre de preuves de bisimulation. PhD thesis, École Nationale des Ponts et des Chausées (ENPC), January 1999. In French.

[Honsell et al., 2001] Furio Honsell, Marino Miculan, and Ivan Scagnetto. π-calculus in (co)inductive type theory. Theoretical Computer Science, 253(2):239–285, 2001.

[Martin and Gordon, 1993] M. Martin and D. Gordon. A calculus for cryptographic protocols : the spi calculus. Technical Report SRC-RR-149, Internationales Begegnungs und Forschungszentrum Schloss Dagstuhl, Germany, 1993.

[Milner et al., 1992] Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, II. Information and Computation, 100(1):41–77, September 1992.

[Montanari and Pistore, 1997] Ugo Montanari and Marco Pistore. An introduction to history dependent automata. In Andrew Gordon, Andrew Pitts, and Carolyn Talcott, editors, Conference Record of the Second Workshop on Higher-Order Operational Techniques in Semantics (HOOTS II, Stanford University, December 8–12, 1997), volume 10 of ENTCS. Elsevier Science Publishers, 1997.

[Parrow, 2001] Joachim Parrow. An introduction to the pi-calculus. In Jan Bergstra, Alban Ponse, and Scott Smolka, editors, Handbook of Process Algebra, pages 479–543. Elsevier Science, 2001.

[Pitts and Gabbay, 2000] A. M. Pitts and M. J. Gabbay. A metalanguage for programming with bound names modulo renaming. In R. Backhouse and J. N. Oliveira, editors, Mathematics of Program Construction. 5th International Conference, MPC2000, Ponte de Lima, Portugal, July 2000. Proceedings, volume 1837 of Lecture Notes in Computer Science, pages 230–255. Springer-Verlag, Heidelberg, 2000.

[Pitts, 2001] A. M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 2001. To appear. (A preliminary version appeared in the Proceedings of the 4th International Symposium on Theoretical Aspects of Computer Software (TACS 2001), LNCS 2215, Springer-Verlag, 2001, pp 219–242.).

[Shinwell et al., 2003] M. R. Shinwell, A. M. Pitts, and M. J. Gabbay. FreshML: Programming with binders made simple. In Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden. ACM Press, August 2003.

[Urban et al., 2003] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. In M. Baaz, editor, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings, Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2003.

Reading edition generated by PDF Reader Automator v0.2.66. Source page numbers refer to the supplied PDF.

Notes

∗M.J.Gabbay, mjg1003@cl.cam.ac.uk, Computer Laboratory, Cambridge University, UK ↩