Logical Methods in Computer Science
Vol. 4 (1:4) 2008, pp. 1–33
www.lmcs-online.org

Submitted Apr. 19, 2007
Published Mar. 18, 2008

GENERATIVE UNBINDING OF NAMES ∗
ANDREW M. PITTS a AND MARK R. SHINWELL b
a

University of Cambridge Computer Laboratory, Cambridge CB3 0FD, UK
e-mail address: Andrew.Pitts@cl.cam.ac.uk

b

CodeSourcery, Ltd
e-mail address: mark@three-tuns.net
Abstract. This paper is concerned with the form of typed name binding used by the
FreshML family of languages. Its characteristic feature is that a name binding is represented by an abstract (name,value)-pair that may only be deconstructed via the generation
of fresh bound names. The paper proves a new result about what operations on names can
co-exist with this construct. In FreshML the only observation one can make of names is
to test whether or not they are equal. This restricted amount of observation was thought
necessary to ensure that there is no observable difference between alpha-equivalent name
binders. Yet from an algorithmic point of view it would be desirable to allow other operations and relations on names, such as a total ordering. This paper shows that, contrary
to expectations, one may add not just ordering, but almost any relation or numerical
function on names without disturbing the fundamental correctness result about this form
of typed name binding (that object-level alpha-equivalence precisely corresponds to contextual equivalence at the programming meta-level), so long as one takes the state of
dynamically created names into account.

1. Introduction
FreshML and the language systems that it has inspired provide some user-friendly
facilities within the context of strongly typed functional programming for computing with
syntactical data structures involving names and name binding. The underlying theory
was presented in [PG00, SPG03] and has been realised in the Fresh patch of Objective
Caml [Shi05b]. FreshML has also inspired Pottier’s Cαml tool [Pot05] for Objective Caml
and Cheney’s FreshLib library [Che05] for Haskell. The approach taken to binding in all
these works is “nominal” in that the user is given access to the names of bound entities
and can write syntax manipulating programs that follow the informal practice of referring
to α-equivalence classes of terms via representatives. However, in FreshML the means of
access to bound names is carefully controlled by the type system. It has been shown [Shi05a,
SP05b] that its static and dynamic properties combine to guarantee a certain “correctness
1998 ACM Subject Classiﬁcation: D.3.1, D.3.3, F.3.2.
Key words and phrases: Abstract syntax, binders, alpha-conversion, meta-programming.
∗
This paper is a revised and expanded version of [PS07].
a
Research supported by UK EPSRC grant EP/D000459/1.

l

LOGICAL METHODS
IN COMPUTER SCIENCE

c
DOI:10.2168/LMCS-4 (1:4) 2008

CC

A.M. Pitts and M.R. Shinwell
Creative Commons

2

A.M. PITTS AND M.R. SHINWELL

type
type
val
val
val
val

atm
α bnd
fresh : unit → atm
bind : atm ∗ α → α bnd
unbind : α bnd → atm ∗ α
(=) : atm → atm → bool

Figure 1: A signature for name binding.
of representation” property: data structures representing α-equivalent syntactical terms
(that is, ones diﬀering only in the names of bound entities) always behave the same in any
program. So even though programs can name names, as it were, α-equivalence of name
bindings is taken care of automatically by the programming language design.
Of course such a correctness of representation property depends rather delicately upon
which operations on bound names are allowed. At the heart of this approach to binding
is an operation that we call generative unbinding. To explain what it involves, consider a
simpliﬁed version of Fresh Objective Caml with a single type atm of bindable names and
a parametric family of types α bnd classifying abstractions of single names over values of
type α. To explain: both atm and α bnd are abstract types that come with the signature
of operations shown in Figure 1. The closed values of type atm are drawn from a countably
inﬁnite set A of symbols that we call atoms. Programs only get access to atoms by evaluating
the expression fresh() to get a fresh one; and hence program execution depends upon a state
recording the atoms that have been created so far. Given a type τ , closed values of type τ bnd
are called atom bindings and are given by pairs «a»v consisting of an atom a : atm and a
closed value v : τ . Atom bindings are constructed by evaluating bind(a , v). Fresh Objective
Caml provides a very convenient form of generative pattern-matching for deconstructing
atom bindings. To keep things simple, here we will avoid the use of pattern-matching and
consider an equivalent mechanism for deconstructing atom binding via an unbind function
carrying out generative unbinding: unbind «a»v evaluates by ﬁrst evaluating fresh() to
obtain a fresh atom a′ and then returning the pair (a′ , v{a′ /a}), where in general v{a′ /a}
denotes the value obtained from v by renaming all occurrences of a to be a′ . The instance
of renaming that arises when evaluating unbind «a»v is special: the fresh atom a′ does
not occur in v and so v{a′ /a} is equivalent to the result of applying to v the semantically
better behaved operation of swapping a and a′ . Although implementing such an atom
swapping operation on all types of values is the main extension that the Fresh patch makes
to Objective Caml, we have not included a swap : atm → atm → α → α operation in the
signature of Figure 1. This is because it is possible for users to deﬁne atom swapping
themselves for speciﬁc types on a case-by-case basis. Although this approach has some
limitations, is enough for our purposes here. (The approach is more useful in the presence
of Haskell-style type classes—see [Che05].)
The type α bnd is used in data type declarations in the argument type of value constructors representing binders. To take a familiar example, the terms of the untyped λ-calculus
(all terms, whether open or closed, with variables given by atoms a ∈ A)
t ::= a | λa.t | t t

GENERATIVE UNBINDING OF NAMES

3

can be represented by closed values of the type term given by the declaration
type term = V of atm
| L of term bnd
| A of term ∗ term .

(1.1)

The value ptq : term representing a λ-term t is deﬁned by
paq , V a
pλa.tq , L «a»ptq
pt1 t2 q , A(pt1 q , pt2 q)

(1.2)

and satisﬁes:
Correctness of Representation: two λ-terms are α-equivalent, t1 =α t2 ,
iff pt1 q and pt2 q are contextually equivalent closed values of type term,
i.e. can be used interchangeably in any well-typed Fresh Objective Caml program without affecting the observable results of program execution.
Since it is also the case that every closed value of type term is of the form ptq for some
λ-term t, it follows that there is a bĳection between α-equivalence classes of λ-terms and
contextual equivalence classes of closed values of type term. The Correctness of Representation property is not easy to prove because of the nature of contextual equivalence, with its
quantiﬁcation over all possible program contexts. It was established in [Shi05a, SP05b] using denotational methods that take permutations of atoms into account. The same methods
can be used to generalise from the example of λ-terms to terms over any nominal signature
in the sense of [UPG04].
Contribution of this paper. For the signature in Figure 1, the only operation on atoms
apart from bind is a test for equality: a = a′ evaluates to true if a and a′ are the same atom
and to false otherwise. Adding extra operations and relations for atoms may well change
which program phrases are contextually equivalent. Is it possible to have some relations
or operations on atoms in addition to equality without invalidating the above Correctness
of Representation property? For example it would be very useful to have a linear order
(<) : atm → atm → bool, so that values of type atm could be used as keys in eﬃcient data
structures for ﬁnite maps and the like. We show that this is possible, and more. This is a
rather unexpected result, for the following reason.
The proof of the Correctness of Representation property given in [Shi05a, SP05b] relies
upon equivariant properties of the semantics, in other words ones whose truth is invariant
under permuting atoms. Atom equality is equivariant: since a permutation is in particular
bĳective, it preserves and reﬂects the value of a = a′ . At ﬁrst it seems that a linear order
on atoms cannot be equivariant, since if a < a′ is true, then applying the permutation
swapping a and a′ we get a′ < a, which is false. However, equivariance is a global property:
when considering invariance of the truth of a property under permutations, it is crucial to
take into account all the parameters upon which the property depends. Here there is a
hidden parameter: the current state of dynamically created atoms. So we should permute
the atoms in this state as well as the arguments of the relation. We shall see that it is
perfectly possible to have a state-dependent equivariant ordering for the type atm without
invalidating the Correctness of Representation property. Indeed we prove that one can
add any n-ary function from atm to numbers (or to booleans, for that matter) whose

4

A.M. PITTS AND M.R. SHINWELL

semantics is reasonable (we explain what is reasonable in Section 3), without invalidating
the Correctness of Representation property for any nominal signature.
We have to work quite hard to get this result, which generalises the one announced in
[SPG03] (with a ﬂawed proof sketch) and ﬁnally proved in [SP05b, Shi05a]; but whereas
those works uses denotational techniques, here we use an arguably more direct approach
based on the operational semantics of the language. We obtain the correctness result (Theorem 5.3) as a corollary of more general result (Propositions 5.7 and 5.10) showing that, up to
contextual equivalence, the type τ bnd behaves like the atom-abstraction construct of [GP01,
Sect. 5]. Along the way to these results we prove a Mason-Talcott-style “CIU” [MT91] characterisation of contextual equivalence for our language (Theorem 4.4). This is proved using
Howe’s method [How96] applied to a formulation of the operational semantics with Felleisenstyle evaluation contexts [FH92], via an abstract machine with frame stacks [Pit02]. The
proof technique underlying our work is rule-based induction, but with the novel twist that
we exploit semantic properties of freshness of names that are based on the use of name
permutations and that were introduced in [GP01] and developed in [Pit03, UN05, Pit06].
2. Generative Unbinding
We use a version of FreshML that provides the signature in Figure 1 in the presence
of higher order recursively deﬁned functions on user declared data structures. Its syntax is
given in Figure 2.
Variable binding. The syntax of expressions and frame stacks in Figure 2 involves some
variable-binding constructs. Speciﬁcally:
• free occurrences of f and x in e are bound in fun(f x = e);
• free occurrences of x in e are bound in let x = e′ in e;
• for i = 1..n, free occurrences of xi in ei are bound in match v with (C x1 → e1 | · · · |
C xn → en );
• free occurrences of x in e are bound in S ◦ (x.e).
As usual, we identify expressions and frame stacks up to renaming of bound variables. We
write fv(e) for the ﬁnite set of free variables of an expression e (and similarly for frame
stacks); and we write
e[v, . . . /x, . . .]
(2.1)
for the simultaneous, capture avoiding substitution of values v, . . . for all free occurrences
of the corresponding variables x, . . . in the expression e (well-deﬁned up to α-equivalence of
bound variables).
Reduced form. The expressions in Figure 2 are given in a “reduced” form (also called
“A-normal” form [FSDF93]), in which the order of evaluation is made explicit through
let-expressions. This is not essential: the use of reduced form makes the development
of properties of the language’s dynamics more succinct and that is mostly what we are
concerned with here. However, when giving example expressions it is convenient to use the
“unreduced” forms given in Figure 3.

GENERATIVE UNBINDING OF NAMES

Variables
Atoms
Data types
Constructors
Observations
Values

f, x ∈ V
a∈A
δ∈D
C∈C
obs ∈ O

v ∈ Val
variable
unit
pair
recursive function
data construction
atom
atom binding

countably inﬁnite set (ﬁxed)
countably inﬁnite set (ﬁxed)
ﬁnite set (variable)
ﬁnite set (variable)
ﬁnite set (variable)
::=
x
()
(v , v)
fun(f x = e)
Cv
a
«v»v

Expressions

e ∈ Exp
value
sequencing
ﬁrst projection
second projection
function application
data deconstruction
fresh atom
generative unbinding
atom observation

::=
v
let x = e in e
fst v
snd v
vv
match v with (C x → e | · · · )
fresh()
unbind v
obs v · · · v

S ∈ Stk
empty
non-empty
States
~a ∈ State
Machine configurations
Types
τ ∈ Typ
unit
pairs
functions
data type
atoms
atom bindings

::=
Id
S ◦ (x.e)
, ﬁnite lists of distinct atoms
h~a, S, ei
::=
unit
τ ∗τ
τ →τ
δ
atm
τ bnd

Frame stacks

fin

Typing environments Γ ∈ V → Typ
Typing judgements
expressions & values Γ ⊢ e : τ
frame stacks Γ ⊢ S : τ → τ ′
Initial basis
natural numbers nat ∈ D
zero (Zero : unit → nat) ∈ C
successor (Succ : nat → nat) ∈ C
atom equality eq ∈ O (arity = 2)

Figure 2: Language syntax.

5

6

A.M. PITTS AND M.R. SHINWELL

(e, e′ ) , let x = e in let x′ = e′ in (x, x′ )
λx. e , fun(f x = e)

(f ∈
/ fv(e), f 6= x)

k e , let x = e in k x
′

(x ∈
/ fv(e′ ), x′ 6= x)
(k = C, fst, snd)

′

′

′

«e»e , let x = e in let x = e in «x»x

(x ∈
/ fv(e′ ), x′ 6= x)

e e′ , let x = e in let x′ = e′ in x x′

(x ∈
/ fv(e′ ), x′ 6= x)

match e with (· · · ) , let x = e in match x with (· · · )
if e then e′ else e′′ , match e with
(Zero() → e′ | Succ x → e′′ )

(x ∈
/ fv(· · · ))
(x ∈
/ fv(e′′ )

fresh x in e , let x = fresh() in e
let «x1 »x2 = e in e′ , let x = e in
let x′ = unbind x in
let x1 = fst x′ in
let x2 = snd x′ in e′
obs e1 · · · en , let x1 = e1 in
···
let xn = en in obs x1 · · · xn

(x, x′ ∈
/ fv(e′ )
′
x 6= x, x1 6= x2 )

(x1 , . . . , xn ∈
/ fv(e1 , . . . , en )
x1 , . . . , xn distinct).

Figure 3: Some “unreduced” forms of expression.
Remark 2.1 (Object-level binding). As well as variables (standing for unknown values),
the language’s expressions and frame stacks may contain atoms drawn from a ﬁxed, countably inﬁnite set A. As discussed in the introduction, atoms are used to represent names
in the object-level languages that are being represented as data in this programming metalanguage. In particular a value of the form «a»v is used to represent the object-level binding
of a name a in the value v. However, note that there are no atom-binding constructs at the
programming meta-level. The reader (especially one used to using lambda-abstraction to
represent all forms of statically-scoped binding) may well ask why? Why cannot we factor
out by « »-bound atoms and thereby trivialise (one half of) the Correctness of Representation result referred to in the Introduction? The reason is that it does not make semantic
sense to try to regard «a»(−) as a form of meta-level binding and identify all expressions up
to an α-equivalence involving renaming « »-bound atoms. For example, if a and a′ are two
diﬀerent atoms, such an α-equivalence would identify fun(f x=«a»x) with fun(f x=«a′ »x).
However, these are two semantically diﬀerent values: they are not contextually equivalent
in the sense discussed in Section 4. For example, the operational semantics described below
gives observably diﬀerent results (0 and 1 respectively) when we place the two expressions
in the context
let «x1 »x2 = [−] a in eq x1 x2
(where eq ∈ O is the observation for atom-equality that we always assume is present—see
Remark 3). The reason for this behaviour is that variables in FreshML-like languages stand
for unknown values that may well involve atoms free at the object level. We may get capture
of such atoms within the scope of an atom-binding «a»(−) during evaluation. In the example, we replaced the hole in [−] a with fun(f x = «a»x) and fun(f x = «a′ »x) respectively,
yielding expressions that evaluate to «a»a and «a′ »a—the ﬁrst involving capture and the
second not; and such capturing substitution does not respect naive α-equivalence. So the

GENERATIVE UNBINDING OF NAMES

Γ(x) = τ
Γ⊢x:τ

Γ ⊢ () : unit

C:τ →δ
Γ⊢v:τ
Γ ⊢ Cv : δ
Γ⊢e:τ
Γ, x : τ ⊢ e′ : τ ′
Γ ⊢ let x = e in e′ : τ ′

Γ, f : τ → τ ′ , x : τ ⊢ e : τ ′
Γ ⊢ fun(f x = e) : τ → τ ′

Γ ⊢ v1 : τ1
Γ ⊢ v2 : τ2
Γ ⊢ (v1 , v2 ) : τ1 ∗ τ2
a∈A
Γ ⊢ a : atm
Γ ⊢ v : τ1 ∗ τ2
Γ ⊢ fst v : τ1

7

Γ ⊢ v1 : atm
Γ ⊢ v2 : τ
Γ ⊢ «v1 »v2 : τ bnd

Γ ⊢ v : τ1 ∗ τ2
Γ ⊢ snd v : τ2

Γ ⊢ v1 : τ → τ ′
Γ ⊢ v2 : τ
Γ ⊢ v1 v2 : τ ′

δ = C1 of τ1 | · · · | Cn of τn
Γ⊢v:δ
Γ, x1 : τ1 ⊢ e1 : τ · · · Γ, xn : τn ⊢ en : τ
Γ ⊢ match v with (C1 x1 → e1 | · · · | Cn xn → en ) : τ

Γ ⊢ fresh() : atm

Γ ⊢ v : τ bnd
Γ ⊢ unbind v : atm ∗ τ

Γ ⊢ Id : τ → τ

arity(obs) = k
Γ ⊢ v1 : atm · · · Γ ⊢ vk : atm
Γ ⊢ obs v1 . . . vk : nat
Γ, x : τ ⊢ e : τ ′
Γ ⊢ S : τ ′ → τ ′′
Γ ⊢ S ◦ (x.e) : τ → τ ′′

Notation:
• Γ, x : τ indicates the typing environment obtained by extending the ﬁnite partial function
Γ by mapping a variable x to the type τ (we always assume that x ∈
/ dom(Γ)).
• In the typing rule for match-expressions, the hypothesis “δ = C1 of τ1 | · · · | Cn of τn ” refers
to the top-level data type declaration (2.2); in other words, the only constructors whose
result type is δ are C1 , . . . , Cn and τi is the argument type of Ci (for i = 1..n).

Figure 4: Typing relation.
relation of contextual equivalence that we deﬁne in Section 4 does not contain this naive
α-equivalence that identiﬁes all (open or closed) expressions up to renaming of « »-bound
atoms.1 However, we will show (Theorem 5.3) that when we restrict to closed expressions
representing object-level languages, then contextual equivalence does contain (indeed, coincides with) this form of α-equivalence: this is the correctness of representation result
referred to in the Introduction.
Data types and observations. The language deﬁned in Figure 1 is parameterised by the
choice of a ﬁnite set O of function symbols that we call observations on atoms and whose
role is discussed in Section 3, by a ﬁnite set D of data type symbols, and by a ﬁnite set C of
constructor symbols. Each constructor C ∈ C is assumed to come with a type, C : τ → δ,
where τ ∈ Typ and δ ∈ D. The choice of D, C and this typing information constitutes an
1Since the problematic possibly-capturing substitution is part of the dynamics of FreshML, there remains
the possibility that the end results in the dynamics of expression evaluation can be made more abstract
by identifying them up to renaming bound atoms: see Remark 2.5. There are also less naive versions
of object-level α-equivalence that respect possibly-capturing substitution, such as the one developed in
[UPG04] involving hypothetical judgements about freshness of atoms for variables; contextual equivalence
and “contextual freshness” should form a model of this notion, but we do not pursue this here.

8

A.M. PITTS AND M.R. SHINWELL

ML-style top-level declaration of some (possibly mutually recursive) data types:
type
and

δ1 = C1,1 of τ1,1 | · · · | C1,n1 of τ1,n1
..
.

(2.2)

δm = Cm,1 of τm,1 | · · · | Cm,nm of τm,nm .

Here δi (for i = 1..m) are the distinct elements of the set D of data type symbols and
Ci,j (for i = 1..m and j = 1..ni ) are the distinct elements of the set C of constructor
symbols. The above declaration just records the typing information C : τ → δ that comes
with each constructor, grouped by result types: δi appears as the result type of precisely
the constructors Ci,1 , . . . , Ci,ni and their argument types are τi,1 , . . . , τi,ni . For the moment
we place no restriction on these types τi,j : they can be any element of the set Typ whose
grammar is given in Figure 2. However, when we consider representation of object-level
languages up to α-equivalence in Section 5, we will restrict attention to top-level data type
declarations where the types τi,j do not involve function types.
We consider observations on atoms that return natural numbers. (The eﬀect of admitting some other types of operation on atoms is discussed in Section 6.2.) So we assume
D always contains a distinguished data type nat for the type of natural numbers and that
correspondingly C contains constructors Zero : unit → nat and Succ : nat → nat for zero and
successor. Each obs ∈ O denotes a numerical function on atoms. We assume it comes with
an arity, specifying the number of arguments it takes: so if arity(obs) = k and (v1 , . . . , vk )
is a k-tuple of values of type atm, then obs v1 . . . vk is an expression of type nat. The typing
of the language’s values, expressions and frame stacks takes place in the presence of typing
environments, Γ, each assigning types to ﬁnitely many variables. The rules in Figure 4 for
the inductively deﬁned typing relation are entirely standard, given that we are following
the signature in Fig 1.
As well as an arity, we assume that each obs ∈ O comes with a speciﬁed interpretation:
the form this takes is discussed in Section 3.
Example 2.2 (Swapping atoms). Examples of programming in FreshML using its characteristic feature of generatively unbinding atom-binding values may be found in [SPG03,
SP05a]. Another feature of FreshML, the operation of swapping atoms, has been left out of
the grammar in Figure 2. However, as we mentioned in the introduction, there is a typedirected deﬁnition of swapping, swapτ : atm → atm → τ → τ , for this language. For example,
when τ is the type atm of atoms we can make use of the observation eq ∈ O for atomequality that we always assume is present (see Remark 3) together with the abbreviations
in Figure 3 and deﬁne
swapatm , λx.λy.λz. if eq z x then y else if eq z y then x else z.

(2.3)

At unit, product, function and atom-binding types we can make use of standard deﬁnitions
of permutation action for these types of data (see [Pit06, Section 3], for example):
swapunit , λx.λy.λz. z
swapτ1 ∗τ2 , λx.λy.λz. (swapτ1 x y (fst z), swapτ2 x y (snd z))
swapτ1 →τ2 , λx.λy.λz.λx1 . swapτ2 x y (z (swapτ1 x y x1 ))
swapτ bnd , λx.λy.λz. let z = «z1 »z2 in «swapatm x y z1 »(swapτ x y z2 ).

(2.4)
(2.5)
(2.6)
(2.7)

At data types we have to make recursive deﬁnitions corresponding to the inductive nature
of the data types. For example, if we assume that in addition to the data type nat for

GENERATIVE UNBINDING OF NAMES

9

h~a, S, ei −→ h~a′ , S ′ , e′ i
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)

•
•
•
•
•

h~a, S ◦ (x.e), vi −→ h~a, S, e[v/x]i
h~a, S, let x = e1 in e2 i −→ h~a, S ◦ (x.e2 ), e1 i
h~a, S, match C v with (· · · | C x → e | · · · )i −→ h~a, S, e[v/x]i
h~a, S, fst(v1 , v2 )i −→ h~a, S, v1 i
h~a, S, snd(v1 , v2 )i −→ h~a, S, v2 i
h~a, S, v1 v2 i −→ h~a, S, e[v1 , v2 /f, x]i if v1 = fun(f x = e)
h~a, S, fresh()i −→ h~a < a′ , S, a′ i if a′ ∈
/ atom(~a)
h~a, S, unbind «a»vi −→ h~a < a′ , S, (a′ , v{a′ /a})i if a′ ∈
/ atom(~a)
h~a, S, obs a1 . . . ak i −→ h~a, S, pmqi if arity(obs) = k, (a1 , . . . , ak ) ∈ atom(~a)k and
JobsK~a (a1 , . . . , ak ) = m
Notation:
′
v{a /a} is the result of replacing all occurrences of an atom a by an atom a′ in the value v;
atom(_) is the ﬁnite set of all atoms occurring in _ ;
~a < a′ is the state obtained by appending an atom a′ not in atom(~a) to the right of the ﬁnite
list of distinct atoms ~a;
pmq is the the closed value of type nat corresponding to m ∈ N: p0q , Zero() and pm+1q ,
Succ pmq;
JobsK is the meaning of obs: see Section 3.

Figure 5: Transition relation.
natural numbers we just have a data type term as in (1.1), then we can deﬁne
swapnat , λx.λy.fun(f z = match z with (Zero() → Zero() | Succ z1 → Succ(f z1 ))) (2.8)
swapterm , λx.λy.fun(f z = match z with (V z1 → V(swapatm x y z1 )
| L z1 → let «z2 »z3 = z1 in
L(«swapatm x y z2 »(f z3 ))
| A z1 → A(f (fst z1 ), f (snd z1 )) )).

(2.9)

(The fact that values of type nat do not involve atoms means that the above systematic
deﬁnition of swapnat is in fact contextually equivalent to λx.λy.λz. z.)
Operational semantics. The abstract machine that we use to deﬁne the language’s dynamics has conﬁgurations of the form h~a, S, ei. Here e is the expression to be evaluated, S is
a stack of evaluation frames and ~a is a ﬁnite list of distinct atoms that have been allocated
so far. Figure 5 deﬁnes the transition relation between conﬁgurations that we use to give
the language’s operational semantics. The ﬁrst six types of transition are all quite standard. Transition 7 deﬁnes the dynamic allocation of a fresh atom and transition 8 deﬁnes
generative unbinding using a freshly created atom; we discuss transition 9 for observations
on atoms in the next section. For the atom a′ in 7 to really be fresh, we need to know that
it does not occur in S; similarly, in 8 we need to know that a′ does not occur in (S, a, v).
These requirements are met if conﬁgurations h~a, S, ei satisfy that all the atoms occurring
in the frame stack S or the expression e occur in the list ~a. Using the notation atom(−)
mentioned in Figure 5, we write this condition as
atom(S, e) ⊆ atom(~a).

(2.10)

10

A.M. PITTS AND M.R. SHINWELL

Theorem 2.4 shows that this property of conﬁgurations is invariant under transitions, as is
well-typedness. Before stating this theorem we introduce some useful terminology.
Definition 2.3 (Worlds). A (possible) world w is just a ﬁnite subset of the the ﬁxed set
A of atoms. We write World for the set of all worlds.
In what follows we will index various relations associated with the language we are
considering by worlds w ∈ World that make explicit the atoms involved in the relation.
Sometimes (as in the following theorem) this is merely a matter of notational convenience;
world-indexing will be more crucial when we consider program equivalence: see Remark 4.7
below.
Theorem 2.4 (Type Safety). Write ⊢w h~a, S, ei : τ to mean that atom(S, e) ⊆ atom(~a) =
w and that there is some type τ ′ with ∅ ⊢ S : τ ′ → τ and ∅ ⊢ e : τ ′ . The type system has the
following properties.
Preservation: if ⊢w h~a, S, ei : τ and h~a, S, ei −→ h~a′ , S ′ , e′ i, with atom(~a′ ) = w′ say,
then w ⊆ w′ and ⊢w′ h~a′ , S ′ , e′ i : τ .
Progress: if ⊢w h~a, S, ei : τ , then either S = Id and e ∈ Val, or h~a, S, ei −→ h~a′ , S ′ , e′ i
holds for some ~a′ , S ′ and e′ .
Proof. The proof of these properties is routine and is omitted.
Remark 2.5 (Alternative operational semantics). It is worth remarking that there
are alternative approaches to representing object-level binding of a name a in a value v
in FreshML-like languages. In the original paper on FreshML [PG00], the authors make
a distinction between non-canonical expressions a.v for atom-binding and the “semantic
values” abs(a, val) to which they evaluate. That paper gives an operational semantics in
the style of the Deﬁnition of Standard ML [MTHM97] in which programming language expressions are separate from semantic values. It is possible to identify such semantic values
up to α-equivalence of abs(a, −)-bound atoms without the kind of inconsistency illustrated
in Remark 2.1. (Such semantic values in which abs(a, −) is a binder are used by Pottier [Pot07], albeit for ﬁrst-order values.) However, this does not help to simplify the type
of Correctness of Representation result in which we are interested here, because programs
are written using expressions, not semantic values. For example, identifying semantic values
in this way, abs(a, a) and abs(a′ , a′ ) are identical and hence trivially contextually equivalent; however the expressions a.a and a′ .a′ (that here we write as «a»a and «a′ »a′ ) are not
equal and there is something to be done to prove that they are contextually equivalent.
In the operational semantics of [PG00] these expressions evaluate to the same semantic
value up to α-equivalence; so one would need to prove that contextual equivalence for that
language contains “Kleene equivalence”—for example by proving a “CIU” theorem like our
Theorem 4.4 below. So it is probably possible to develop the results of this paper using
this slightly more abstract style of operational semantics with semantic values identiﬁed up
to α-equivalence of bound atoms. However our experience is that the style of operational
semantics we use here, in which semantic values are identiﬁed with certain canonical expressions (but necessarily not identiﬁed up α-equivalence of bound atoms, for the reasons
discussed in Remark 2.1) leads to a simpler technical development overall.

GENERATIVE UNBINDING OF NAMES

h~a, S, ei↓n

h~a, Id, vi↓0

11

h~a, S, ei↓

h~a, S, ei −→ h~a′ , S ′ , e′ i
h~a′ , S ′ , e′ i↓n
h~a, S, ei↓n+1

h~a, S, ei↓n
h~a, S, ei↓

Figure 6: Termination relations.
3. Observations on Atoms
The language we are considering is parameterised by a choice of a ﬁnite set O of
numerical functions on atoms. We assume that each obs ∈ O comes with a speciﬁed
meaning JobsK. As mentioned in the introduction, we should allow these meanings to be
dependent on the current state (the list of distinct atoms that have been created so far).
So if arity(obs) = k, for each ~a ∈ State we assume given a function JobsK~a : atom(~a)k → N
mapping k-tuples of atoms occurring in the state ~a to natural numbers. These functions
are used in the transitions of type 9 in Figure 5. Not every such family (JobsK~a | ~a ∈
State) of functions is acceptable as an observation on atoms: we require that the family be
equivariant. To explain what this means we need the following deﬁnition.
Definition 3.1 (Permutations). A ﬁnite permutation of atoms is a bĳection π from the
set A of atoms onto itself such that supp(π) , {a ∈ A | π(a) 6= a} is a ﬁnite set. We write
P for the set of all such permutations. If π ∈ P and ~a ∈ State, then π · ~a denotes the ﬁnite
list of distinct atoms obtained by mapping π over the list ~a; if e is an expression, then π · e
denotes the expression obtained from it by applying π to the atoms in e; and similarly for
other syntactical structures involving ﬁnitely many atoms, such as values and frame stacks.
We require the functions (JobsK~a | ~a ∈ State) associated with each obs ∈ O to satisfy
an equivariance property: for all π ∈ P, ~a ∈ State and (a1 , . . . , ak ) ∈ atom(~a)k (where k is
the arity of obs)
JobsK~a (a1 , . . . , ak ) = JobsKπ·~a (π(a1 ), . . . , π(ak )) .
(3.1)
We impose condition (3.1) for the following reason. In Figure 5, the side conditions on
transitions of types 7 and 8 do not specify which of the inﬁnitely many atoms in A−atom(~a)
should be chosen as the fresh atom a′ . Any particular implementation of the language will
make such choices in some speciﬁc way, for example by implementing atoms as numbers
and incrementing a global counter to get the next fresh atom. We wish to work at a
level of abstraction that is independent of such implementation details. We can do so by
ensuring that we only use properties of machine conﬁgurations h~a, S, ei that depend on the
relative positions of atoms in the list ~a, rather than upon their identities. So properties of
conﬁgurations should be equivariant: if h~a, S, ei has the property, then so should hπ · ~a, π ·
S, π · ei for any π ∈ P. The main property of conﬁgurations we need is termination, deﬁned
in Figure 6, since as we see in the next section this determines contextual equivalence of
expressions. With condition (3.1) we have:
Lemma 3.2. If h~a, S, ei↓n , then hπ · ~a, π · S, π · ei↓n for any π ∈ P.
Proof. In view of the deﬁnition of termination in Figure 6, it suﬃces to show that the
transition relation is equivariant:
h~a, S, ei −→ h~a′ , S ′ , e′ i ⇒ hπ · ~a, π · S, π · ei −→ hπ · ~a′ , π · S ′ , π · e′ i .

12

A.M. PITTS AND M.R. SHINWELL

Equality, eq (arity = 2):
JeqK~a (a, a′ ) ,

(

0
1

if a = a′ ,
otherwise.

Linear order, lt (arity = 2):
(
0 if a occurs to the left of a′ in the list ~a,
JltK~a (a, a′ ) ,
1 otherwise.
Ordinal, ord (arity = 1):
JordK~a (a) , n, if a is the nth element of the list ~a.
State size, card (arity = 0):
JcardK~a () , length of the list ~a.

Figure 7: Examples of observations on atoms.
This can be proved by cases from the deﬁnition of −→ in Fig 5. Cases 1–8 follow from
general properties of the action of permutations on syntactical structures (such as the fact
that π · (e[v/x]) equals (π · e)[π · v/x]); case 9 uses property (3.1).
As a corollary we ﬁnd that termination is indeed independent of the choice of fresh
atom in transitions of the form 7 or 8.
Corollary 3.3. If h~a, S, freshi↓n+1 with atom(S) ⊆ atom(~a), then for all a′ ∈
/ atom(~a), it
is the case that h~a < a′ , S, a′ i↓n . Similarly, if h~a, S, unbind «a»vi↓n+1 with atom(S, a, v) ⊆
atom(~a), then for all a′ ∈
/ atom(~a), it is the case that h~a < a′ , S, (a′ , v{a′ /a})i↓n .
There are observations on atoms that are not equivariant, that is, whose value on some
atoms in a particular state does not depend just upon the relative position of those atoms
in the state. For example, if we ﬁx some enumeration of the set of atoms, α : N ∼
= A, it
−1
is easy to see that the unary observation given by JobsK~a (a) = α (a) fails to satisfy (3.1).
Nevertheless, there is a wide range of functions that do have this property. Figure 7 gives
some examples.
Remark 3.4 (Atom-equality test). The ﬁrst observation on atoms given in Figure 7,
eq, combined with the usual arithmetic operations for nat that are already deﬁnable in the
language, gives us the eﬀect of the function (=) : atm → atm → bool from the signature in
Figure 1; so we assume that the set O of observations on atoms always contains eq.
Remark 3.5 (Fresh Atoms Largest). Note that in the operational semantics of Figure 5
we have chosen to make “fresh atoms largest”, in the sense that the fresh atom a′ in
transitions 7 and 8 is added to the right-hand end of the list ~a representing the current
state. In the presence of observations on atoms other than equality, such a choice may
well aﬀect the properties of the notion of program equivalence that we explore in the next
section. Other choices are possible, but to insist that program equivalence is independent
of any such choice would rule out many useful observations on atoms (such as lt or ord in
Figure 7).

GENERATIVE UNBINDING OF NAMES

13

4. Contextual Equivalence
We wish to prove that the language we have described satisﬁes Correctness of Representation properties of the kind mentioned in the introduction. To do so, we ﬁrst have
to be more precise about what it means for two expressions to be contextually equivalent,
that is, to be interchangeable in any program without aﬀecting the observable results of
executing that program. What is a program, what does it mean to execute it, and what
results of execution do we observe? The answers we take to these questions are: programs
are closed well-typed expressions; execution means carrying out a sequence of transitions of
the abstract machine from an initial machine conﬁguration consisting of a state (that is, a
list of atoms containing those mentioned in the program), the empty frame stack and the
program; and we observe whether execution reaches a terminal conﬁguration, that is, one
of the form h~a, Id, vi. We need only observe termination because of the language’s strict
evaluation strategy: observing any (reasonable) properties of the ﬁnal value v results in
the same notion of contextual equivalence. Also, it is technically convenient to be a bit
more liberal about what constitutes an initial conﬁguration by allowing the starting frame
stack to be non-empty: this does not change the notion of contextual equivalence because
of the correspondence between frame stacks and “evaluation” contexts—see the remarks
after Deﬁnition 4.5 below. So we can say that e and e′ are contextually equivalent if for
all program contexts C[−], the programs C[e] and C[e′ ] are operationally equivalent in the
following sense.
Definition 4.1 (Operational Equivalence of Closed Expressions). ⊢w e ∼
= e′ : τ is
deﬁned to hold if
• atom(e, e′ ) ⊆ w;
• ∅ ⊢ e : τ and ∅ ⊢ e′ : τ ; and
• for all ~a, S and τ ′ with w ∪ atom(S) ⊆ atom(~a) and ∅ ⊢ S : τ → τ ′ , it is the case
that h~a, S, ei↓ ⇔ h~a, S, e′ i↓.
However, for the reasons given in [Pit05, Section 7.5], we prefer not to phrase the formal
deﬁnition of contextual equivalence in terms of the inconveniently concrete operation of
possibly capturing substitution of open expressions for the hole “−” in program contexts
C[−]. Instead we take the more abstract relational approach originally advocated by Gordon
[Gor98] and Lassen [Las98] that focuses upon the key features of contextual equivalence,
namely that it is the largest congruence relation for well-typed expressions that contains the
relation of operational equivalence of Definition 4.1. A congruence relation is an expression
relation that is an equivalence, compatible and substitutive, in the following sense.
Definition 4.2 (Expression Relations). An expression relation E is a set of tuples
(Γ, w, e, e′ , τ ) (made up of a typing context, a world, two expressions and a type) satisfying atom(e, e′ ) ⊆ w, Γ ⊢ e : τ and Γ ⊢ e′ : τ . We write Γ ⊢w e E e′ : τ to indicate
that (Γ, w, e, e′ , τ ) is a member of E. We use the following terminology in connection with
expression relations.
• E is an equivalence if it is reﬂexive (atom(e) ⊆ w ∧ Γ ⊢ e : τ ⇒ Γ ⊢w e E e : τ ),
symmetric (Γ ⊢w e E e′ : τ ⇒ Γ ⊢w e′ E e : τ ) and transitive (Γ ⊢w e E e′ :
τ ∧ Γ ⊢w e′ E e′′ : τ ⇒ Γ ⊢w e E e′′ : τ ).
• E is compatible if Eb ⊆ E, where Eb is the compatible refinement of E, deﬁned in
Figure 8.

14

A.M. PITTS AND M.R. SHINWELL

Γ ⊢w v1 E v1′ : τ1

Γ(x) = τ
bx:τ
Γ ⊢w x E

Γ ⊢w () Eb () : unit

Γ, f : τ → τ ′ , x : τ ⊢w e E e′ : τ ′
b fun(f x = e′ ) : τ → τ ′
Γ ⊢w fun(f x = e) E

Γ ⊢w v1 E v1′ : atm Γ ⊢w v2 E v2′ : τ
b «v1′ »v2′ : τ bnd
Γ ⊢w «v1 »v2 E

Γ ⊢w v E v ′ : τ1 ∗ τ2
Γ ⊢w fst v Eb fst v ′ : τ1

Γ ⊢w v2 E v2′ : τ2

Γ ⊢w (v1 , v2 ) Eb (v1′ , v2′ ) : τ1 ∗ τ2

Γ ⊢w v E v ′ : τ
Γ ⊢w C v Eb C v ′ : δ

C:τ →δ

Γ ⊢w e1 E e′1 : τ

a∈w
b a : atm
Γ ⊢w a E

Γ, x : τ ⊢w e2 E e′2 : τ ′
Γ ⊢w let x = e1 in e2 Eb let x = e′1 in e′2 : τ ′

Γ ⊢w v E v ′ : τ1 ∗ τ2
b snd v ′ : τ2
Γ ⊢w snd v E

Γ ⊢w v1 E v1′ : τ → τ ′

Γ ⊢w v2 E v2′ : τ

Γ ⊢w v1 v2 Eb v1′ v2′ : τ ′

δ = C1 of τ1 | · · · | Cn of τn
Γ, x1 : τ1 ⊢w e1 E e′1 : τ · · · Γ, xn : τn ⊢w en E e′n : τ
Γ ⊢w match v with (C1 x1 → e1 | · · · | Cn xn → en ) Eb match v ′ with (C1 x1 → e′1 | · · · | Cn xn → e′n ) : τ
Γ ⊢w v E v ′ : δ

b fresh() : atm
Γ ⊢w fresh() E

Γ ⊢w v E v ′ : τ bnd
b unbind v ′ : atm ∗ τ
Γ ⊢w unbind v E

Γ ⊢w v1 E v1′ : atm · · · Γ ⊢w vk E vk′ : atm
Γ ⊢w obs v1 . . . vk Eb obs v1′ . . . vk′ : nat

arity(obs) = k

Γ, x : τ ⊢w e E e′ : τ ′

Γ ⊢w Id Eb Id : τ → τ

b S ′ : τ ′ → τ ′′
Γ ⊢w S E

b S ′ ◦ (x.e′ ) : τ → τ ′′
Γ ⊢w S ◦ (x.e) E

Figure 8: Compatible reﬁnement Eb of an expression relation E.

• E is substitutive if Γ ⊢w v E v ′ : τ ∧ Γ, x : τ ⊢w e E e′ : τ ′ ⇒ Γ ⊢w e[v/x] E
e′ [v ′ /x] : τ ′ .
• E is equivariant if Γ ⊢w e E e′ : τ ⇒ Γ ⊢π·w π · e E π · e′ : τ .
• E is adequate if ∅ ⊢w e E e′ : τ ⇒ ⊢w e ∼
= e′ : τ .
e′

We extend operational equivalence (Deﬁnition 4.1) to an expression relation, Γ ⊢w e ∼
=◦
: τ , by instantiating free variables with closed values:

Definition 4.3 (∼
=◦ ). Supposing Γ = {x1 : τ1 , . . . , xn : τn }, we deﬁne Γ ⊢w e ∼
=◦ e′ : τ to
hold if
• atom(e, e′ ) ⊆ w;
• Γ ⊢ e : τ and Γ ⊢ e′ : τ ; and
• for all w′ ⊇ w and all closed values vi with atom(vi ) ⊆ w′ and ∅ ⊢ vi : τi (for
i = 1..n), it is the case that ⊢w′ e[~v /~x] ∼
= e′ [~v /~x] : τ .
Note that for closed expressions, that is, in the case that Γ = ∅, the relation ∼
=◦ agrees with
∼
=:
∅ ⊢w e ∼
(4.1)
=◦ e′ : τ ⇔ ⊢w e ∼
= e′ : τ .

GENERATIVE UNBINDING OF NAMES

15

Theorem 4.4 (CIU). Operational equivalence of possibly open expressions, ∼
=◦ , is a compatible, substitutive and adequate equivalence. It is the largest such expression relation. It
is also equivariant.
Proof. The fact that ∼
=◦ is equivariant follows from Lemma 3.2. The fact that it is an
equivalence and adequate is immediate from its deﬁnition; as is the fact that it contains
any expression relation that is adequate, substitutive and reﬂexive. So the main diﬃculty is
to show that it is compatible and substitutive. One can do this by adapting a construction
due to Howe [How96]; see Appendix A.
Definition 4.5 (Contextual Equivalence). In view of the discussion at the beginning of
this section, Theorem 4.4 tells us that ∼
=◦ coincides with a conventional notion of contextual
equivalence deﬁned using program contexts: so from now on we refer to ∼
=◦ as contextual
equivalence.
Remark 4.6 (Uses of closed instantiations). We labelled the above theorem “CIU”
because it is analogous to a theorem of that name due to Mason and Talcott [MT91]. CIU,
after permutation, stands for “Uses of Closed Instantiations”; and the theorem tells us
that to test open expressions for contextual equivalence it suﬃces to ﬁrst close them by
substituting closed values for free variables and then test the resulting closed expressions
for termination when they are used in any evaluation context [FH92]. This follows from
the deﬁnition of ∼
=◦ and the fact that termination in evaluation contexts corresponds to
termination of machine conﬁgurations via the easily veriﬁed property
h~a, S, ei↓ ⇔ h~a, Id, S[e]i↓

(4.2)

where the expression S[e] is deﬁned by recursion on the length of the stack S by:
Id[e] , e
S ◦ (x.e′ )[e] , S[let x = e in e′ ] .

(4.3)

Theorem 4.4 serves to establish some basic properties of contextual equivalence, such
as the fact that the state-independent transitions in Figure 5 (types 1–6 and 9) give rise to
contextual equivalences. For example, Γ ⊢w let x = v in e ∼
=◦ e[v/x] : τ ′ holds if Γ ⊢w v : τ
′
and Γ, x : τ ⊢w e : τ . However, we have to work a bit harder to understand the consequences
of transitions of types 7 and 8 for contextual equivalence at atom binding types, τ bnd. We
address this in the next section.
Remark 4.7 (Possible Worlds). It is immediate from the deﬁnition of ∼
=◦ that it satisﬁes
a weakening property:
(4.4)
Γ ⊢w e ∼
=◦ e′ : τ .
=◦ e′ : τ ∧ w ⊆ w′ ⇒ Γ ⊢w′ e ∼
If it also satisﬁed a strengthening property
Γ ⊢w ′ e ∼
=◦ e′ : τ ∧ atom(e, e′ ) ⊆ w ⊆ w′ ⇒ Γ ⊢w e ∼
=◦ e′ : τ

(4.5)

then we could make the indexing of contextual equivalence by “possible worlds” w implicit
by taking w = atom(e, e′ ). When O just contains eq, property (4.5) does hold; this is why
there is no need for indexing by possible worlds in [Shi05a, SP05b]. However, it is not
hard to see that the presence of some observations on atoms, such as the function card in
Figure 7, can cause (4.5) to fail. It is for this reason that we have built indexing by possible
worlds into expression relations (Deﬁnition 4.2).

16

A.M. PITTS AND M.R. SHINWELL

⊢w () =α () : unit

⊢w v1 =α v1′ : σ1
⊢w v2 =α v2′ : σ2
⊢w (v1 , v2 ) =α (v1′ , v2′ ) : σ1 ∗ σ2

C:σ→δ
⊢w v = α v ′ : σ
⊢w C v = α C v ′ : δ

a′′ ∈
/ w ⊇ atom(a, v, a′ , v ′ )
⊢w∪{a′′ } v{a′′ /a} =α v ′ {a′′ /a′ } : σ
⊢w «a»v =α «a′ »v ′ : σ bnd

a∈w
⊢w a =α a : atm

Figure 9: α-Equivalence.
5. Correctness of Representation
Recall from Section 2 that the language we are considering is parameterised by a toplevel declaration of some (possibly mutually recursive) data types:
type
and

δ1 = C1,1 of τ1,1 | · · · | C1,n1 of τ1,n1
..
.

(5.1)

δm = Cm,1 of τm,1 | · · · | Cm,nm of τm,nm .

If we restrict attention to declarations in which the argument types τi,j of the constructors
Ci,j are just ﬁnite products of the declared data types δ1 . . . , δm , then the above declaration
corresponds to a many-sorted algebraic signature; furthermore, in this case the language’s
values at each data type are just the abstract syntax trees of terms of the corresponding
sort in the signature. By allowing atoms and atom bindings in addition to products in the
argument types τi,j , one arrives at the notion of “nominal signature”, introduced in [UPG04]
and more fully developed in [Pit06]. It extends the notion of many-sorted algebraic signature
with names (of possibly many kinds) and information about name binding in constructors.
Here, for simplicity, we are restricting to a single kind of name, represented by the type
atm of atoms; but our results extend easily to the case of many kinds of name.
Definition 5.1 (Nominal Signatures). The subset Arity ⊆ Typ is given by the grammar
σ ∈ Arity ::= unit | σ ∗ σ | δ | atm | σ bnd

(5.2)

where δ ranges over the ﬁnite set D of data type symbols. (In other words Arity consists of
those types of our language that do not involve any use of the function type construction,
→.) The elements of the set Arity are called nominal arities. (The notation hhatmiiσ is used
in [UPG04, Pit06] for what we here write as σ bnd.) A nominal signature with a single sort
of atoms, atm, is speciﬁed by a data type declaration (5.1) in which the argument types τi,j
of the constructors Ci,j are all nominal arities.
The occurrences of σ bnd in a nominal signature (5.1) indicate arguments with bound
atoms. In particular, we can associate with each such signature a notion of α-equivalence,
=α , that identiﬁes closed values of nominal arity up to renaming bound atoms. The inductive deﬁnition of =α is given in Figure 9. It generalises to an arbitrary nominal signature the
syntax-directed characterisation of α-equivalence of λ-terms given in [Gun92, p. 36]. The
deﬁnition in Figure 9 is essentially that given in [Pit06], except that we have included an
indexing by possible worlds w, to chime with our form of judgement for contextual equivalence; without that indexing, the condition “a′′ ∈
/ w ⊇ atom(a, v, a′ , v ′ )” in the rule for
α-equivalence of values of atom binding type would be replaced by “a′′ ∈
/ atom(a, v, a′ , v ′ )”.
Remark 5.2 (The role of closed values). For each σ ∈ Arity, the closed values (that
is, ones with no free variables) of that type, ∅ ⊢w v : σ, correspond precisely to the ground

GENERATIVE UNBINDING OF NAMES

17

terms (with arity σ and atoms in w) over the given nominal signature, as deﬁned in [UPG04].
For example, the declaration (1.1) corresponds to the nominal signature for λ-calculus; and
closed values of type term correspond as in (1.2) to the abstract syntax trees for λ-terms—
open or closed ones, with λ-calculus variables represented by atoms. For other examples of
nominal signatures, with more complicated patterns of binding, see [Pit06, Section 2.2].
Note that the deﬁnition of =α in Figure 9 cannot be extended naively to open values with free variables, for the reasons discussed in Remark 2.1. Free variables stand for
unknown values that may well involve atoms that get captured by « »-binders upon substitution. So as we saw in that remark, it does not make semantic sense to say, for example,
that «a»x and «a»x are α-equivalent without putting some restrictions on the kind of value
x stands for. In [UPG04], Urban et al consider such restrictions consisting of assumptions
about the freshness of atoms for variables; they generalise Figure 9 to a hypothetical notion of α-equivalence between open values2, with hypotheses consisting of such freshness
assumptions. It may be possible to relate the validity of this general form of α-equivalence
to contextual equivalence, but here we content ourselves with the following result about the
straightforward notion of α-equivalence on closed values given by Figure 9.
Theorem 5.3 (Correctness of Representation). Suppose that all the observations on
atoms obs in O satisfy the equivariance property (3.1). For each nominal signature, two
closed values v, v ′ of the same nominal arity σ (with atoms contained in the finite set w,
say) are α-equivalent if and only if they are contextually equivalent:
⊢ w v =α v ′ : σ ⇔ ⊢ w v ∼
(5.3)
= v′ : σ .
The rest of this section is devoted to the proof of the bi-implication in (5.3). Before
commencing the proof we make some remarks about the relative diﬃculty of each half of
the bi-implication and about alternative approaches to the proof than the one we take.
∼ v ′ : σ). At ﬁrst sight it might seem that this
Remark 5.4 ( ⊢w v =α v ′ : σ ⇒ ⊢w v =
implication is trivial: since we identify expressions up to α-equivalence of bound variables,
contextual equivalence automatically contains that notion of equivalence. However, =α
is not that meta-level α-equivalence, it is α-equivalence at the object-level for « »-bound
atoms. As we noted in Remark 2.1, identifying all (open or closed) expressions up to
renaming « »-bound atoms is incompatible with contextual equivalence: so we cannot
trivialise the left-to-right implication in (5.3) by factoring out in this way. Note that the
restriction to nominal arities in Figure 9 means that we do not have to consider =α for
values of the form fun(f x = e) and hence for open expressions e where the naive deﬁnition
of =α would encounter the semantic problems discussed in Remarks 2.1 and 5.2.
So there really is something to do to establish the left-to-right implication in (5.3).
However, we will see that we have already done most of the heavy lifting for this half of the
theorem by establishing the CIU Theorem 4.4.
Remark 5.5 ( ⊢w v ∼
⊢w v =α v ′ : σ). This is equivalent to showing
= v′ : σ ⇒
′
that if two closed values v and v of nominal arity σ are not α-equivalent, then they are
not contextually equivalent. Proving contextual inequivalence is much easier than proving
contextual equivalence, since one just has to construct a context in which the two values have
diﬀerent operational behaviour. In this case it would suﬃce to exhibit a closed expression
aeqσ : σ → σ → nat correctly implementing =α , in the sense that for all v and v ′
2This is a slight over-simplification, since their “nominal terms” are not just the open values considered

here: they involved explicit atom-permutations as well.

18

A.M. PITTS AND M.R. SHINWELL

⊢w v =α v ′ : σ ⇒ ∀~a. w ⊆ atom(~a) ⇒ ∃~a′ . h~a, Id, aeqσ v v ′ i −→∗ h~a′ , Id, Zero()i
⊢w v 6=α v ′ : σ ⇒ ∀~a. w ⊆ atom(~a) ⇒ ∃~a′ . h~a, Id, aeqσ v v ′ i −→∗ h~a′ , Id, Succ(Zero())i.
It is indeed possible to construct such an expression aeqσ by induction on the structure of σ,
by a deﬁnition that mimics the rules in Figure 9, using the deﬁnition of atom-swapping from
Example 2.2 in the case of an atom-binding arity and using recursively deﬁned functions
at data types. The proof of the above properties of aeqσ is relatively straightforward if
tedious; one ﬁrst has to prove suitable correctness properties for the swapping expressions
swapσ from Example 2.2.
This is not the route to the right-to-left implication in (5.3) that we take. Instead
we deduce it from a general “extensionality” property of atom-binding types τ bind that
holds for all types τ , including ones that are not nominal arities, that is, ones involving
function types. This property (Propositions 5.7 and 5.10) shows that, up to contextual
equivalence, the type τ bnd behaves like the atom-abstraction construct of [GP01, Sect. 5].
It seems interesting in its own right. We are able to prove this property of general atombinding types τ bind only under a restriction on observations on atoms over and above the
equivariance property (3.1) that we always assume they possess. This is the “aﬃneness”
property given in Deﬁnition 5.8 below. The equality test eq (Figure 7) is aﬃne and we will
see that this fact is enough to prove Theorem 5.3 as stated, that is, without any restriction
on the observations present other than equivariance.
We now begin the proof of Theorem 5.3.
Proposition 5.6.
(i) ⊢w () ∼
= () : unit.
(ii) For all types τ1 , τ2 ∈ Typ, ⊢w (v1 , v2 ) ∼
= v1′ : τ1 and
= (v1′ , v2′ ) : τ1 ∗ τ2 iff ⊢w v1 ∼
′
∼
⊢w v2 = v2 : τ2 .
(iii) For each data type δi in the declaration (5.1), ⊢w Ci,j v ∼
= Ci,j ′ v ′ : δi iff j = j ′ and
′
⊢w v ∼
= v : τi,j .
(iv) ⊢w a ∼
= a′ : atm iff a = a′ ∈ w.
Proof. Part (i) and the “if” directions of (ii)–(iv) are consequences of the fact (Theorem 4.4)
that ∼
=◦ is a compatible equivalence. For the “only if” directions of (ii) and (iii) we apply
suitably chosen destructors. Thus for part (ii) we use the operational equivalences ⊢w
fst(v1 , v2 ) ∼
= v1 : τ1 and ⊢w snd(v1 , v2 ) ∼
= v2 : τ2 that are consequences of the deﬁnitions
of ∼
= and the termination relation. Similarly, part (iii) follows from the easily established
operational (in)equivalences
⊢w diverge ∼
6 v:τ
=
⊢w proji,j (Ci,j v) ∼
= v : τi,j
⊢w proj (Ci,j ′ v) ∼
= diverge : τi,j
i,j

if j 6= j ′

which make use of the following expressions
diverge , fun(f x = f x)()
proji,j v , match v with (Ci,1 x1 → dj,1 | · · · | Ci,ni xni → dj,ni )

GENERATIVE UNBINDING OF NAMES

where
dj,j ′

(
xj
,
diverge

19

if j = j ′ ,
if j =
6 j′.

Finally, for the “only if” direction of part (iv) we make use of the fact that O always contains
the atom equality function eq from Figure 7: see Lemma A.4(i) in Appendix A.
∼ has properties mirroring those of α-equivalence given
This proposition tells us that =
by the ﬁrst four rules in Figure 9. To complete the proof of the correctness theorem, we
need to prove a property of ∼
= at atom binding arities σ bnd that mirrors the ﬁfth rule in
that ﬁgure. We split this into two parts, Propositions 5.7 and 5.10.
Proposition 5.7. For any type τ ∈ Typ, suppose we are given closed, well-typed atom
binding values ∅ ⊢w «a»v : τ bnd and ∅ ⊢w «a′ »v ′ : τ bnd. If for some atom a′′ ∈
/ w we have
′′
′
′′
′
⊢w∪{a′′ } v{a /a} ∼
(5.4)
= v {a /a } : τ
then

⊢w «a»v ∼
= «a′ »v ′ : τ bnd .

(5.5)

Proof. Unlike the previous proposition, this result is not just a simple consequence of the
congruence properties of operational equivalence. It can be proved via an induction over
the rules deﬁning termination: see Appendix B.
Next we need to prove the converse of the above proposition, namely that (5.5) implies
(5.4) for any a′′ ∈
/ w. The diﬃculty is that in verifying (5.4) we have to consider the
termination behaviour of v{a′′ /a} and v ′ {a′′ /a′ } in all states ~a with atom(~a) ⊇ w ∪ {a′′ }.
The atom a′′ may occur at any position in ~a and not necessarily at its right-hand end;
whereas in assuming (5.5), all we appear to know about the termination behaviour of
v{a′′ /a} and v ′ {a′′ /a′ } is what happens when a fresh atom a′′ is placed at the end of the
state via generative unbinding (cf. Remark 3.5). In fact we are able to combine bind and
unbind operations to rearrange atoms suﬃciently to prove the result we want, but only
in the presence of observations on atoms that are insensitive to atoms being added at the
left-hand (that is, least) end of the state. The following deﬁnition makes this property of
observations precise. It uses the notation a′ < ~a for the state obtained from ~a ∈ State by
appending an atom a′ not in atom(~a) to the left of the ﬁnite list of distinct atoms ~a (cf. ~a <a′
deﬁned in Figure 5).
Definition 5.8 (Affine Observations). An observation on atoms, obs ∈ O, is affine if it
is equivariant (3.1) and satisﬁes: for all ~a ∈ State, all a′ ∈
/ atom(~a) and all (a1 , . . . , ak ) ∈
atom(~a)k (where k is the arity of obs)
JobsKa′ <~a (a1 , . . . , ak ) = JobsK~a (a1 , . . . , ak ) .

(5.6)

For example, of the observations deﬁned in Figure 7, eq and lt are aﬃne, whereas ord and
card are not.
The following property of termination follows from its deﬁnition in Figures 5 and 6,
using Corollary 3.3.
Lemma 5.9. Given a frame stack S and an expression e, suppose that only affine observations on atoms occur in them. Then for all ~a with atom(S, e) ⊆ atom(~a) and all
a′ ∈
/ atom(~a), ha < ~a, S, ei↓n ⇔ h~a, S, ei↓n .

20

A.M. PITTS AND M.R. SHINWELL

We now give a converse of Proposition 5.7, under the assumption that only aﬃne
observations are used. The proof is the technically most involved result in the paper.
Proposition 5.10. Suppose that O only contains affine observations. For any type τ ∈
Typ, suppose we are given closed, well-typed atom binding values ∅ ⊢w «a»v : τ bnd and
∅ ⊢w «a′ »v ′ : τ bnd. Then for all atoms a′′ ∈
/ w we have
⊢w «a»v ∼
(5.7)
= «a′ »v ′ : τ bnd
implies

⊢w∪{a′′ } v{a′′ /a} ∼
= v ′ {a′′ /a′ } : τ .

(5.8)

Proof. Suppose (5.7) holds and that a′′ ∈
/ w. To prove (5.8) we have to show for any
w′ ∈ World, ~a ∈ State and τ ′ ∈ Typ with atom(~a) = w′ ⊇ w ∪ {a′′ } and ∅ ⊢w′ S : τ → τ ′
that
h~a, S, v{a′′ /a}i↓ ⇔ h~a, S, v ′ {a′′ /a′ }i↓ .
(5.9)
′′
Since a ∈ atom(~a), we have
~a = ~a′ < a′′ < a0 < · · · < an−1

(5.10)

for some state ~a′ and atoms a0 , . . . , an−1 (n ≥ 0). Choose distinct atoms b0 , . . . , bn−1 not
occurring in w′ and consider the frame stack
S ′ , Id ◦ (z. let «x»y0 = z in
let «x0 »y1 = «b0 »y0 in
..
.

(5.11)

let «xn−1 »yn = «bn−1 »yn−1 in
S{x, x0 , . . . , xn−1 /a′′ , a0 . . . , an−1 }[yn ])
where z, x, x0 , . . . , xn−1 , y0 , . . . , yn are distinct variables not occurring in S. Here we have
used the notation “let «x1 »x2 = e in e′ ” from Figure 3, the notation “S[e]” from (4.3) and
the operation (−){x/a} of replacing an atom a by a variable x.
Since atom(S) ⊆ w′ = atom(~a), by deﬁnition of S ′ and from (5.10) we have atom(S ′ ) ⊆
atom(~b′ ) where
~b′ , b0 < · · · < bn−1 < ~a′ .
(5.12)
′′
Let π ∈ P be the permutation swapping each ai with bi (for i = 0..n − 1). Since a ∈
/w⊇
atom(a, v), by deﬁnition of ~b′ we have atom(π · «a»v) ⊆ atom(~b′ ). Therefore the conﬁguration h~b′ , S ′ , π · «a»vi satisﬁes the well-formedness condition needed to apply Corollary 3.3.
Noting that π · («a»v) = «π(a)»(π · v) and that π · (v{a′′ /a}) = (π · v){π(a′′ )/π(a)} =
(π · v){a′′ /π(a)}, from that corollary, property (4.2) and the deﬁnition of S ′ we get:
h~b′ , S ′ , π · («a»v)i↓ ⇔
h~b′ < a′′ < a0 < · · · < an−1 , S, (π · (v{a′′ /a})){a0 , . . . , an−1 /b0 , . . . , bn−1 }i↓ .
Note that by deﬁnition of π
(π · (v{a′′ /a})){a0 , . . . , an−1 /b0 , . . . , bn−1 }
= ((v{a′′ /a}){b0 , . . . , bn−1 /a0 , . . . , an−1 }){a0 , . . . , an−1 /b0 , . . . , bn−1 }
= v{a′′ /a} ;

GENERATIVE UNBINDING OF NAMES

21

and ~b′ < a′′ < a0 < · · · < an−1 = b0 < · · · < bn−1 < ~a by (5.10) and (5.12). So altogether we
have
h~b′ , S ′ , π · «a»vi↓ ⇔ hb0 < · · · < bn−1 < ~a, S, v{a′′ /a}i↓ .
(5.13)
A similar argument gives
h~b′ , S ′ , π · «a′ »v ′ i↓ ⇔ hb0 < · · · < bn−1 < ~a, S, v ′ {a′′ /a′ }i↓ .
(5.14)
We noted in Theorem 4.4 that operational equivalence is equivariant. So from (5.7) we have
⊢atom(~b′ ) π · «a»v ∼
= π · «a′ »v ′ : τ bnd. Since ∅ ⊢atom(~b′ ) S ′ : τ bnd → τ ′ , this operational
equivalence gives
h~b′ , S ′ , π · «a»vi↓ ⇔ h~b′ , S ′ , π · «a′ »v ′ i↓ .
Combining this with (5.13) and (5.14) yields
hb0 < · · · < bn−1 < ~a, S, v{a′′ /a}i↓ ⇔ hb0 < · · · < bn−1 < ~a, S, v ′ {a′′ /a′ }i↓ .
w′

(5.15)

atom(S, a′′ , v, v ′ )

Since b0 , . . . , bn−1 ∈
/
= atom(~a) ⊇
and O only contains aﬃne observations, we can now apply Lemma 5.9 to (5.15) to get (5.9), as required.
Example 5.11. We conjecture that Proposition 5.10 fails to hold if we drop the requirement
that observations are aﬃne (but still require them to be equivariant). For example consider
the equivariant but non-aﬃne observation ord in Figure 7 and the values
v , fun(f x = f x)
v ′ , fun(f x = match ord a with (Zero → () | Succ y → v()))
where a is some atom. We claim that
∼ «a»v ′ : (unit → unit)bnd
⊢{a} «a»v =

(5.16)

but that for any a′ 6= a
⊢{a,a′ } v{a′ /a} ∼
6 v ′ {a′ /a} : unit → unit .
=

(5.17)

The operational inequivalence (5.17) is witnessed by the state ~a , [a′ , a] and the frame
stack S , Id ◦ (x. x unit), for which one has h~a, S, v ′ {a′ /a}i↓, but not h~a, S, v{a′ /a}i↓. At
the moment we lack a formal proof of the operational equivalence (5.16), but the intuitive
justiﬁcation for it is as follows. For any state ~a containing a and any frame stack S, we
claim that in any sequence of transitions from h~a, S, «a»v ′ i the occurrence of ord a in v ′ can
only be renamed to ord a′ for atoms a′ at positions strictly greater than 0 in the current
state; and hence h~a, S, «a»v ′ i has the same termination properties as h~a, S, «a»vi.
∼ v ′ : σ by induction
Proof of Theorem 5.3. One proves that ⊢w v =α v ′ : σ implies ⊢w v =
on the the rules deﬁning α-equivalence in Figure 9, using Propositions 5.6 and 5.7.
To prove the converse implication, ﬁrst note that if ∅ ⊢ v : σ, then v contains no
instances of observations obs ∈ O. The proof of this is by induction on the structure
of the nominal arity σ; the only way observations on atoms can appear in values of the
language is via function values, fun(f x = e), and the deﬁnition of “nominal arity” excludes
function types. It follows from the deﬁnition of operational equivalence in Deﬁnition 4.1
that if ⊢w v ∼
= v ′ : σ holds for a language with observation set O, it also holds for the
sub-language with minimal observation set {eq}. Thus it suﬃces to prove the implication
⊢w v ∼
= v ′ : σ ⇒ ⊢w v =α v ′ : σ for this minimal sub-language; and this can be done by
induction on the structure of σ using Propositions 5.6 and 5.10 (the latter applies because
eq is aﬃne).

22

A.M. PITTS AND M.R. SHINWELL

6. Related and Further Work
6.1. Correctness of Representation. It is instructive to compare the Correctness of
Representation property of FreshML (Theorem 5.3) with adequacy results for type-theoretic
logical frameworks [Pfe01]. Both are concerned with the representation of expressions of
some object-language in a meta-language. For logical frameworks the main issue is surjectivity: one wants every expression at the meta-level to be convertible to a normal form and
for every normal form at certain types to be the representation of some object-level expression. The fact that α-equivalence of object-level expressions is preserved and reﬂected by
the representation is a simple matter, because equivalence in the logical framework is taken
to be αβη-conversion, which specialises on normal forms to just α-equivalence. Contrast
this with the situation for FreshML where surjectivity of the representation is straightforward, because values of the relevant FreshML data types are just ﬁrst order abstract syntax
trees; whereas the fact that α-equivalence of object-level expressions is preserved and reﬂected by the representation in FreshML is a non-trivial property. This is because we take
equivalence of FreshML expressions to be contextual equivalence. This is the natural notion
of equivalence from a programming point of view, but its properties are hard won.
One aspect of adequacy results for logical frameworks highlighted in [Pfe01] is compositionality of representations. Although important, this issue is somewhat orthogonal
to our concerns here. It refers to the question of whether substitution of expressions for
variables at the object-level is represented by β-conversion at the meta-level. From the
point of view of nominal signatures [Pit06], variables are just one kind of name. Properties
of α-conversion of all kinds of names are treated by the theory; but if one wants notions
of substitution and β-conversion for a particular kind of name, one has to give a deﬁnition (an “α-structural” recursive deﬁnition [Pit06]). For example in FreshML, using the
data type (1.1) for λ-terms one can give an appealingly simple declaration for a function
subst : term → atm → term → term for capture-avoiding substitution; see [SPG03, p. 264].
Compositionality of the representation t 7→ ptq given in the introduction then becomes
the contextual equivalence ⊢w pt1 [t2 /a]q ∼
= subst pt2 q a pt1 q : term. The CIU theorem
(Theorem 4.4) provides the basis for proving such contextual equivalences. (We believe
this particular equivalence is valid when O = {eq, lt}, but not when O = {eq, card}; see
Section 7.)
6.2. Concrete Semantics. We have explored some of the consequences of adding integervalued “observations on atoms” to FreshML over and above the usual test for equality. Such
functions allow more eﬃcient data structures to be used for algorithms involving atoms as
keys. For example, binary search trees making use of the comparison function lt from
Figure 7 could be used instead of association lists.
What about adding functions from numbers to atoms? An implementation of the
language may well represent atoms by numbers, via some ﬁxed enumeration of the set of
atoms, α : N ∼
= A. Can we give the programmer access to this bĳection? Less radically,
can we allow operations on atoms that make use of arithmetic properties of the underlying
representation? Not without breaking the invariant atom(S, e) ⊆ atom(~a) of conﬁgurations
h~a, S, ei—the property of our operational semantics that ensures that an atom’s freshness
with respect to the current state really does mean that it is diﬀerent from all other atoms
in the current context. For example, suppose we add to the language an operation suc :

GENERATIVE UNBINDING OF NAMES

23

atm→atm whose meaning is “successor function on atoms”, with transitions h~a, S, suc ai −→
h~a, S, a′ i whenever a = α(n) and a′ = α(n + 1) for some n ∈ N. Then it may well be the
case that a′ ∈
/ atom(~a) even though a ∈ atom(~a).
So exposing the numerical representation of atoms involves giving up the invariant properties of the abstract semantics we have used here. Perhaps a more interesting alternative to
actually exposing numerical representations of atoms would be to prove contextual equivalence of eﬃcient and naive implementations of the abstract semantics extended with types
of ﬁnite maps on atoms. Such abstract types form an addition to the signature in Figure 1
diﬀerent from the kind we have considered here, but certainly one worthy of investigation.
6.3. Mechanising Meta-Theory. The techniques we used here to prove the Correctness
of Representation property are operationally based, in contrast to the denotational techniques used in [Shi05a, SP05b]. The advantage of working directly with the syntax and
operational semantics of the language is that there are lower mathematical “overheads”—
various kinds of induction being the main techniques involved. The disadvantage is that
to deploy such inductive techniques often involves great ingenuity choosing inductive hypotheses and much error prone tedium checking induction steps. Furthermore, with these
methods it seems harder to predict the eﬀect that a slight change in language or formalisation may have on a proof. Although ingenuity in choosing inductive hypotheses may always
be the preserve of humans, machine assistance of the kind envisaged by the “POPLmark
challenge” [ABF+ 05] seems a very good idea for the other aspects of the operationally
based approach. The main results presented here are still a challenging target for fully
formalised and machine checked proofs. We have taken some care with the formalisation
(using a “relational” approach to contextual equivalence, for example); but results concerning coinductive equivalences, like the CIU theorem (Theorem 4.4), are quite complex
logically speaking, compared with the kind of type safety results (like Theorem 2.4) that
POPLMark has focused on so far. Systems like Isabelle/HOL [NPW02] that develop proofs
in full classical higher order logic seem appropriate to the task, in principle. But there is a
gap between what is possible in principle for an expert of any particular system and what
is currently practicable for a casual user. Urban and Berghofer [UB06] are developing a
Nominal Data Type Package for Isabelle/HOL that may be very useful for narrowing this
gap. The fact that FreshML and the Urban-Berghofer package both have to do with the
same mathematical universe of “nominal sets” [Pit06] is perhaps slightly confusing: their
Nominal Data Type Package is useful for fully formalising proofs about names and namebinding in operational semantics whether or not those proofs have to do with the particular
mechanism of generative unbinding that is the focus of this paper.
7. Conclusion
The FreshML [SPG03, Shi05b] approach to functional programming with binders combines abstract types for names and name binding with an unbinding operation that involves
generation of fresh names. In this paper we have studied some theoretical properties of this
design to do with data correctness. We showed that the addition of integer valued observations on names does not break FreshML’s fundamental Correctness of Representation
property that α-equivalence classes of abstract syntax trees (for any nominal signature)
coincide with contextual equivalence classes of user declared data values. In particular, it
is possible to give programmers access to a linear order on names without breaking the “up

24

A.M. PITTS AND M.R. SHINWELL

to α-equivalence” representation of syntax. The simple insight behind this possibly surprising result has to do with the fact that FreshML is impure—program execution mutates
the state of dynamically created names. If the state is taken into account when giving the
meaning of observations on names, then the permutation invariance properties that underly
the correctness property can be retained. The original version of FreshML [PG00] was pure
by dint of the “freshness inference” included in its type system. Subsequent experience
with the language showed that the form of freshness inference that was used there was
overly restrictive from a programming point of view. So freshness inference was dropped in
[SPG03]. However, Pottier [Pot07] has recently regained purity in a FreshML-like language
through the use of user-provided assertions. We have not investigated whether results like
those presented in this paper also apply to Pottier’s language.
This paper has been concerned with data correctness, but what about general results
on program correctness? The only restriction we placed on observations on atoms is that,
as functions of both the state and the names they operate upon, they should be invariant
under permuting names. We have seen that the Correctness of Representation property
(Theorem 5.3) remains valid in the presence of any such observation. However, we are
certainly not advocating that arbitrary equivariant observations be added to FreshML.
This is because some forms of observation may radically aﬀect the general programming
laws that contextual equivalence satisﬁes. We saw one example of this here: only for
“aﬃne” observations (which are insensitive to how many names have been created before
the arguments to which they are applied) were we able to combine Propositions 5.7 and 5.10
to get an “extensionality” result explaining contextual equivalence at type τ bnd in terms
of contextual equivalence at τ , for arbitrary higher types τ .
More investigation of program correctness properties in the presence of particular observations on atoms is needed before one can advocate adding them to the FreshML design.
The techniques we used in this paper could form the basis for such an investigation. They
combine the usual engine of structural operational semantics—namely syntax-directed, rule
based induction—with the approach to freshness of names based on name permutations
that was introduced in [GP01] and developed in [Pit03, UN05, Pit06].
Acknowledgement.
The authors are grateful for the suggestions for improvement made by the anonymous
referees.
References
[ABF+ 05]

[BL05]
[Che05]

[FH92]

B. E. Aydemir, A. Bohannon, M. Fairbairn, J. N. Foster, B. C. Pierce, P. Sewell, D. Vytiniotis, G. Washburn, S. Weirich, and S. Zdancewic. Mechanised metatheory for the masses: The
POPLmark challenge. In J. Hurd and T. Melham, editors, 18th International Conference on Theorem Proving in Higher Order Logics: TPHOLs 2005, volume 3603 of Lecture Notes in Computer
Science, pages 50–65. Springer-Verlag, 2005. www.cis.upenn.edu/group/proj/plclub/mmm/.
P. N. Benton and X. Leroy, editors. ACM SIGPLAN Workshop on ML (ML 2005), Tallinn,
Estonia, Electronic Notes in Theoretical Computer Science. Elsevier, September 2005.
J. Cheney. Scrap your nameplate (functional pearl). In Tenth ACM SIGPLAN International
Conference on Functional Programming (ICFP’05), Tallinn, Estonia, pages 180–191. ACM
Press, September 2005.
M. Felleisen and R. Hieb. The revised report on the syntactic theories of sequential control and
state. Theoretical Computer Science, 103:235–271, 1992.

GENERATIVE UNBINDING OF NAMES

[FSDF93]

25

C. Flanagan, A. Sabry, B. F. Duba, and M. Felleisen. The essence of compiling with continuations. In Proceedings ACM SIGPLAN Conference on Programming Language Design and
Implementation, PLDI’93, Albuquerque, NM, USA, pages 237–247. ACM Press, June 1993.
[Gor98]
A. D. Gordon. Operational equivalences for untyped and polymorphic object calculi. In Gordon
and Pitts [GP98], pages 9–54.
[GP98]
A. D. Gordon and A. M. Pitts, editors. Higher Order Operational Techniques in Semantics.
Publications of the Newton Institute. Cambridge University Press, 1998.
[GP01]
M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal
Aspects of Computing, 13:341–363, 2001.
[Gun92]
C. A. Gunter. Semantics of Programming Languages: Structures and Techniques. Foundations
of Computing. MIT Press, 1992.
[How96]
D. J. Howe. Proving congruence of bisimulation in functional programming languages. Information and Computation, 124(2):103–112, 1996.
[Las98]
S. B. Lassen. Relational reasoning about contexts. In Gordon and Pitts [GP98], pages 91–135.
[MT91]
I. A. Mason and C. L. Talcott. Equivalence in functional languages with effects. Journal of
Functional Programming, 1:287–327, 1991.
[MTHM97] R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Deﬁnition of Standard ML (Revised).
MIT Press, 1997.
[NPW02] T. Nipkow, L. C. Paulson, and M. Wenzel. Isabelle/HOL—A Proof Assistant for Higher-Order
Logic, volume 2283 of Lecture Notes in Computer Science. Springer-Verlag, 2002.
[Pfe01]
F. Pfenning. Logical frameworks. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, chapter 17, pages 1063–1147. Elsevier Science and MIT Press, 2001.
[PG00]
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.
[Pit02]
A. M. Pitts. Operational semantics and program equivalence. In G. Barthe, P. Dybjer, and
J. Saraiva, editors, Applied Semantics, Advanced Lectures, volume 2395 of Lecture Notes in Computer Science, Tutorial, pages 378–412. Springer-Verlag, 2002. International Summer School,
APPSEM 2000, Caminha, Portugal, September 9–15, 2000.
[Pit03]
A. M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186:165–193, 2003.
[Pit05]
A. M. Pitts. Typed operational reasoning. In B. C. Pierce, editor, Advanced Topics in Types
and Programming Languages, chapter 7, pages 245–289. The MIT Press, 2005.
[Pit06]
A. M. Pitts. Alpha-structural recursion and induction. Journal of the ACM, 53(3):459–506, 2006.
[Pot05]
F. Pottier. An overview of Cαml. In Benton and Leroy [BL05], pages 27–52.
[Pot07]
F. Pottier. Static name control for FreshML. In Twenty-Second Annual IEEE Symposium on
Logic In Computer Science (LICS’07), pages 356–365, Wroclaw, Poland, July 2007. IEEE Computer Society Press.
[PS07]
A. M. Pitts and M. R. Shinwell. Generative unbinding of names. In 34th Annual ACM SIGPLANSIGACT Symposium on Principles of Programming Languages (POPL 2007), Nice, France,
pages 85–95. ACM Press, January 2007.
[Shi05a]
M. R. Shinwell. The Fresh Approach: Functional Programming with Names and Binders. PhD
thesis, University of Cambridge Computer Laboratory, 2005. Available as University of Cambridge Computer Laboratory Technical Report UCAM-CL-TR-618.
[Shi05b]
M. R. Shinwell. Fresh O’Caml: Nominal abstract syntax for the masses. In Benton and Leroy
[BL05], pages 53–76.
[SP05a]
M. R. Shinwell and A. M. Pitts. Fresh Objective Caml user manual. Technical Report UCAMCL-TR-621, University of Cambridge Computer Laboratory, February 2005.
[SP05b]
M. R. Shinwell and A. M. Pitts. On a monadic semantics for freshness. Theoretical Computer
Science, 342:28–55, 2005.
[SPG03]
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, pages 263–274. ACM Press, August 2003.

26

[UB06]

[UN05]

[UPG04]

A.M. PITTS AND M.R. SHINWELL

C. Urban and S. Berghofer. A recursion combinator for nominal datatypes implemented in
Isabelle/HOL. In 3rd International Joint Conference on Automated Reasoning (ĲCAR 2006),
Seattle, USA, volume 4130 of Lecture Notes in Computer Science, pages 498–512. SpringerVerlag, 2006.
C. Urban and M. Norrish. A formal treatment of the Barendregt Variable Convention in rule
inductions. In Proceedings of the 3rd ACM SIGPLAN Workshop on Mechanized Reasoning about
Languages with Variable Binding (MERLIN ’05), Tallinn, Estonia, pages 25–32. ACM Press,
2005.
C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. Theoretical Computer Science,
323:473–497, 2004.

Appendix A. Proof of Theorem 4.4
We wish to show that the expression relation ∼
=◦ of Deﬁnition 4.3 is compatible and
substitutive (see Deﬁnition 4.2). We use an adaptation of “Howe’s method” [How96] to do
so. Let the expression relation ∼
=∗ be inductively deﬁned from ∼
=◦ by the rule
c∗ e′ : τ
Γ ⊢w e′ ∼
Γ ⊢w e ∼
=
=◦ e′′ : τ
.
(A.1)
Γ ⊢w e ∼
=∗ e′′ : τ

In making this inductive deﬁnition, we are implicitly relying upon the easily proved fact
b is a monotone operation on expression relations, that
that compatible reﬁnement, E 7→ E,
b
b
is, E1 ⊆ E2 ⇒ E1 ⊆ E2 .

Lemma A.1.
(i) Γ ⊢w e ∼
=∗ e′ : τ ∧ Γ ⊢w e′ ∼
=◦ e′′ : τ ⇒ Γ ⊢w e ∼
=∗ e′′ : τ .
∗
∼
(ii) = is compatible and substitutive.
(iii) atom(e) ⊆ w ∧ Γ ⊢ e : τ ⇒ Γ ⊢w e ∼
=∗ e : τ .
c∗ S : τ → τ ′ .
(iv) atom(S) ⊆ w ∧ Γ ⊢ S : τ → τ ′ ⇒ Γ ⊢w S ∼
=
∗
′
′
∗
′
∼
∼
(v) Γ ⊢w v = e : τ ⇒ ∃v . Γ ⊢w v = v : τ ∧ Γ ⊢w v ′ ∼
=◦ e′ : τ .

Proof. These properties of ∼
=∗ are simple consequences of its deﬁnition and the deﬁnition
of the extension of compatible reﬁnement to a relation between frame stacks given by the
last two rules in Figure 8.
Lemma A.2.
(i) ∼
=∗ is equivariant.
(ii) Γ ⊢w e ∼
=∗ e′ : τ .
=∗ e′ : τ ∧ w ⊆ w′ ⇒ Γ ⊢w′ e ∼
c∗ S ′ : τ → τ ′ .
c∗ S ′ : τ → τ ′ ∧ w ⊆ w′ ⇒ Γ ⊢w′ S ∼
(iii) Γ ⊢w S ∼
=
=

Proof. Part (i) follows from the fact that ∼
=◦ is equivariant, which in turn is a consequence
of Lemma 3.2. Parts (ii) and (iii) are consequences of the fact that world weakening is built
into the deﬁnition of operational equivalence in Deﬁnition 4.1.
Lemma A.3. Γ ⊢w e ∼
=◦ e′ : τ ⇒ Γ ⊢w e ∼
=∗ e′ : τ .
Proof. If Γ ⊢w e ∼
=◦ e′ : τ , then in particular atom(e) ⊆ w and Γ ⊢ e : τ , so that by
Lemma A.1(iii) we have Γ ⊢w e ∼
=∗ e : τ ; so from part (i) of that lemma we get Γ ⊢w e ∼
=∗
e′ : τ .

GENERATIVE UNBINDING OF NAMES

27

We wish to show that ∼
=∗ coincides with ∼
=◦ . In view of the previous lemma, it just
∗
◦
∼
∼
remains to show that = ⊆ = . Lemma A.5 provides the key to this. Before stating that
lemma we give some simple properties of ∼
= that are needed to prove it.
Lemma A.4.
(i) ⊢w a ∼
= a′ : atm ⇒ a = a′ .
(ii) ⊢w v ∼
= v ′ : τ bnd ⇒ ⊢w unbind v ∼
= unbind v ′ : atm ∗ τ .
(iii) If ⊢w v ∼
= v ′ : τ1 → τ2 , then for any world w′ ⊇ w and value v1 with atom(v1 ) ⊆ w′
and ⊢ v1 : τ1 , it is the case that ⊢w′ v v1 ∼
= v ′ v1 : τ2 .
Proof. For part (i) we make use of the fact that O always contains the atom equality function
eq from Figure 7. Consider the frame stack
Sa , Id ◦ (x. let y = eq x a in
match y with (Zero → () | Succ z → diverge)) .
If a 6= a′ are distinct elements of w, then choosing some ~a ∈ State with atom(~a) = w, it is not
hard to see that h~a, Sa , ai↓ holds whereas h~a, Sa , a′ i↓ does not hold. So if ⊢w a ∼
= a′ : atm
′
it cannot be the case that a 6= a .
For part (ii), given any ~a, S and τ ′ with w ∪ atom(S) ⊆ atom(~a) and ∅ ⊢ S : τ → τ ′ ,
then
h~a, S, unbind vi↓ ⇔ h~a, S ◦ (x. unbind x), vi↓
⇔ h~a, S ◦ (x. unbind x), v ′ i↓

by deﬁnition of ↓
since ⊢w v ∼
= v ′ : τ bnd

⇔ h~a, S, unbind v ′ i↓

by deﬁnition of ↓

and thus ⊢w unbind v ∼
= unbind v ′ : atm ∗ τ .
The proof of part (iii) is similar to that for (ii), using the frame (x. x v1 ) in place of
(x. unbind x).
Lemma A.5. For all n ≥ 0 and all w, S, S ′ , τ, τ ′ , e, e′ ,~a
c∗ S ′ : τ → τ ′ ∧ ∅ ⊢w e ∼
∅ ⊢w S ∼
=
=∗ e′ : τ ∧ atom(~a) = w ∧ h~a, S, ei↓n

⇒ h~a, S ′ , e′ i↓ . (A.2)

Proof. The lemma is proved by induction on n. The base case n = 0 follows from the
c∗ S ′ : τ → τ ′ can only hold when S ′ = Id),
b (which implies that ∅ ⊢w Id ∼
deﬁnition of −
=
combined with Lemma A.1(v) and the deﬁnition of ∼
=◦ . For the induction step, assume
(A.2) holds and that
c∗ S ′ : τ → τ ′
(A.3)
∅ ⊢w S ∼
=
∅ ⊢w e ∼
=∗ e′ : τ

(A.4)

atom(~a) = w

(A.5)

h~a, S, ei −→ h~a1 , S1 , e1 i

(A.6)

h~a1 , S1 , e1 i↓
h~a, S ′ , e′ i↓

n

(A.7)

We have to prove
and do so by an analysis of (A.6) against the possible cases
1–9 in the deﬁnition of the transition relation in Figure 5.

28

A.M. PITTS AND M.R. SHINWELL

Case 1. In this case S = S1 ◦ (x. e2 ), e = v ∈ Val, ~a1 = ~a, and e1 = e2 [v/x], for some e2
c∗ it must be the case that S ′ = S ′ ◦ (x. e′ ) for
and v. For (A.3) to hold, by deﬁnition of ∼
=
2
1
′
′
some S1 and e2 with
{x : τ } ⊢w e2 ∼
(A.8)
=∗ e′ : τ2
2

c∗ S ′ : τ2 → τ ′
∅ ⊢ w S1 ∼
=
1

(A.9)

for some type τ2 . Since e = v is a value, applying Lemma A.1(v) to (A.4) we get
∅ ⊢w v ∼
=∗ v ′ : τ
⊢w v ∼
=e :τ
′

′

(A.10)
(A.11)

for some v ′ ∈ Val. Since ∼
=∗ is substitutive (Lemma A.1(ii)), from (A.8) and (A.10) we get
∼∗ e′ [v ′ /x] : τ2 .
(A.12)
∅ ⊢w e2 [v/x] =
2
Applying the induction hypothesis (A.2) to (A.9), (A.12), (A.5) and to (A.7), we get
h~a, S1′ , e′2 [v ′ /x]i↓; hence h~a, S1′ ◦ (x.e′2 ), v ′ i↓, that is, h~a, S ′ , v ′ i↓; and therefore by (A.11)
we also have h~a, S ′ , e′ i↓, as required.
Case 2. In this case we have e = let x = e1 in e2 , ~a1 = ~a and S1 = S ◦ (x. e2 ) for some e2 .
Since (A.4) holds, by deﬁnition of ∼
=∗ , there must exist some e′1 , e′2 and τ1 with
∅ ⊢w e1 ∼
(A.13)
=∗ e′1 : τ1
∗
′
∼ e :τ
{x : τ1 } ⊢w e2 =
(A.14)
2

⊢w (let x = e′1 in e′2 ) ∼
= e′ : τ

(A.15)

and then from (A.3) and (A.14) we get
c∗ S ′ ◦ (x. e′ ) : τ1 → τ ′ .
∅ ⊢w S ◦ (x. e2 ) ∼
=
2

(A.16)
h~a, S ′ ◦(x. e′2 ), e′1 i↓

The induction hypothesis (A.2) applied to (A.16), (A.13) and (A.5) gives
and hence h~a, S ′ , let x = e′1 in e′2 i↓. This and (A.15) then give h~a, S ′ , e′ i↓, as required.

Case 3. This follows from the deﬁnition of ∼
=∗ using its substitutivity property, much as
for case 1.
Case 4. In this case τ = τ1 ∗ τ2 , e = (v1 , v2 ), ~a1 = ~a and e1 = v1 , for some τ1 , τ2 ∈ Typ
c∗ , for (A.4) to hold it must be the case that
and v1 , v2 ∈ Val. By deﬁnition of ∼
=
∅ ⊢w vi ∼
(A.17)
=∗ vi′ : τi (for i = 1, 2)
′
′ ∼ ′
⊢w (v , v ) = e : τ1 ∗ τ2
(A.18)
1

v1′

2

v2′ .

By the induction hypothesis (A.2) applied to (A.3), (A.17), (A.5)
and
for some
and (A.7), we get h~a, S ′ , v1′ i↓ and hence also h~a, S ′ , fst(v1′ , v2′ )i↓. Hence by (A.18) we have
h~a, S ′ , e′ i↓, as required.
Case 5. This is similar to the previous case.

GENERATIVE UNBINDING OF NAMES

29

Case 6. In this case e = v1 v2 , ~a1 = ~a, S1 = S and e1 = e2 [v1 , v2 /f, x] for some v1 =
fun(f x = e2 ) and v2 . Since (A.4) holds, by deﬁnition of ∼
=∗ together with Lemma A.4(iii),
′
′
there must exist some e2 , v2 and τ1 with
{f : τ1 → τ, x : τ1 } ⊢w e2 ∼
(A.19)
=∗ e′ : τ
2

∅ ⊢w v2 ∼
=∗ v2′ : τ1
⊢w fun(f x =

e′2 ) v2′

(A.20)
∼
= e : τ1 → τ .
′

(A.21)
∗
∗
∼
∼
Since = is compatible (Lemma A.1(ii)), from (A.19) we get ∅ ⊢w v1 = fun(f x = e′2 ) :
τ1 → τ ; and since ∼
=∗ is also substitutive, this together with (A.19) and (A.20) gives ∅ ⊢w
e2 [v1 , v2 /f, x] ∼
=∗ e′2 [fun(f x = e′2 ), v2′ /f, x] : τ . Therefore by the induction hypothesis (A.2)
applied to (A.3), this, (A.5) and (A.7), we get h~a, S ′ , e′2 [fun(f x = e′2 ), v2′ /f, x]i↓. Hence
h~a, S ′ , fun(f x = e′2 ) v2′ i↓ and thus by (A.21), h~a, S ′ , e′ i↓ as required.
Case 7. In this case τ = atm, e = fresh(), ~a1 = ~a < a, S1 = S and e1 = a, for some
a∈
/ atom(~a) = w. Since (A.4) holds, by deﬁnition of ∼
=∗ we have
⊢w fresh() ∼
(A.22)
= e′ : atm .
c∗ S ′ : atm → τ ′ ; and by
By Lemma A.2(iii) applied to (A.3), we have ∅ ⊢w∪{a} S ∼
=
∗
∼
Lemma A.1(iii) we also have ∅ ⊢w∪{a} a = a : atm. So by the induction hypothesis
(A.2) applied to these, atom(~a < a) = w ∪ {a} and (A.7), we get h~a < a, S ′ , ai↓. Hence
h~a, S ′ , freshi↓ and hence from (A.22) we also have h~a, S ′ , e′ i↓, as required.
Case 8. In this case τ = atm ∗ τ1 , e = unbind «a»v, ~a1 = ~a < a1 , S1 = S, and e1 =
(a1 , v{a1 /a}), for some τ1 , a, v and a1 with a1 ∈
/ atom(~a) = w. Since (A.4) holds, by
deﬁnition of ∼
=∗ together with parts (i) and (ii) of Lemma A.4, there must exist some v ′
with
∅ ⊢w v ∼
(A.23)
=∗ v ′ : τ1
⊢w unbind «a»v ′ ∼
= e′ : atm ∗ τ1 .

(A.24)

We now appeal to the easily veriﬁed fact that since a1 ∈
/ w ⊇ atom(v, v ′ ), the renamed
′
values v{a1 /a} and v {a1 /a} are respectively equal to the permuted values (a a1 ) · v and
(a a1 ) · v ′ (where (a a1 ) denotes the permutation swapping a and a′ ). Therefore by parts (i)
and (ii) of Lemma A.2 applied to (A.23) and by parts (ii) and (iii) of Lemma A.1, we have
(A.25)
∅ ⊢w∪{a } (a1 , v{a1 /a}) ∼
=∗ (a1 , v ′ {a1 /a}) : atm ∗ τ1 .
1

By applying Lemma A.2(iii) to (A.3) we also have
c∗ S ′ : atm ∗ τ1 → τ ′ .
∅ ⊢w∪{a1 } S ∼
=

Then applying the induction hypothesis (A.2) to this, (A.25), atom(~a < a1 ) = w ∪ {a1 }
and (A.7) yields h~a < a1 , S ′ , (a1 , v ′ {a1 /a})i↓. Therefore h~a, S ′ , unbind «a»v ′ i↓; and hence
by (A.24), we also have h~a, S ′ , e′ i↓, as required.

30

A.M. PITTS AND M.R. SHINWELL

Case 9. In this case τ = nat, e = obs a1 . . . ak for some a1 , . . . , ak ∈ w, ~a1 = ~a, S1 = S,
and e1 = pmq where m = JobsK~a (a1 , . . . , ak ). Since (A.4) holds, by deﬁnition of ∼
=∗ together
with Lemma A.4(i), we must have
⊢w obs a1 . . . ak ∼
(A.26)
= e′ : nat .
Note that by Lemma A.1(iii) we also have ∅ ⊢w pmq ∼
=∗ pmq : nat. So by the induction
hypothesis (A.2) applied to this, (A.3), (A.5) and (A.7) we get h~a, S ′ , pmqi↓. Since m =
JobsK~a (a1 , . . . , ak ), this implies that h~a, S ′ , obs a1 . . . ak i↓; and hence from (A.26) we have
that h~a, S ′ , e′ i↓ holds, as required.
This completes the proof of Lemma A.5.
Lemma A.6. Let (∼
=∗ )+ denote the transitive closure of ∼
=∗ . Then
Γ ⊢w e ∼
=∗ e′ : τ ⇒ Γ ⊢w e′ (∼
=∗ )+ e : τ .
Proof. This can be proved by induction on the derivation of Γ ⊢w e ∼
=∗ e′ : τ from the
rule in (A.1) and the rules for compatible reﬁnement in Figure 8, using the fact that ∼
=◦ is
symmetric and using Lemmas A.3 and A.1(iii).
∼◦ is compatible and
We can now complete the proof of Theorem 4.4 by showing that =
substitutive (Deﬁnition 4.2). Since ∼
=∗ has those properties by Lemma A.1(ii), it suﬃces
∗
◦
∼
∼
to show that = coincides with = . We already noted in Lemma A.3 that ∼
=◦ is contained
∗
∗
∼
∼
in = . For the reverse inclusion, since = is substitutive and reﬂexive (Lemma A.1), it is
closed under substituting values for variables; so by Deﬁnition 4.3, it suﬃces to show that
(A.27)
∅ ⊢w e ∼
= e′ : τ .
=∗ e′ : τ ⇒ ⊢w e ∼
To see this, note that by Lemma A.5 (together with Lemmas A.1(iv) and A.2(ii)) we have:
∅ ⊢w e ∼
=∗ e′ : τ ⇒ ∀~a, S, τ ′ . w ∪ atom(S) ⊆ atom(~a) ∧ ∅ ⊢ S : τ → τ ′ ∧ h~a, S, ei↓
⇒ h~a, S, e′ i↓ . (A.28)
Since the right-hand side of the implication in (A.28) is a transitive relation between expressions e, e′ , we also have
∅ ⊢w e ∼
=∗+ e′ : τ ⇒ ∀~a, S, τ ′ . w ∪ atom(S) ⊆ atom(~a) ∧ ∅ ⊢ S : τ → τ ′ ∧ h~a, S, ei↓
⇒ h~a, S, e′ i↓
and therefore Lemma A.6 gives
{} ⊢w e ∼
=∗ e′ : τ ⇒ ∀~a, S, τ ′ . (w ∪ atom(S) ⊆ atom(~a) ∧ ∅ ⊢ S : τ → τ ′ ∧ h~a, S, e′ i↓
⇒ h~a, S, ei↓ . (A.29)
Combining (A.28) and (A.29) gives (A.27).

GENERATIVE UNBINDING OF NAMES

31

Appendix B. Proof of Proposition 5.7
Let E be the closure under compatible reﬁnement (Figure 8) of the pairs of closed atom
binding values that we wish to show are operationally equivalent. In other words E is the
expression relation inductively deﬁned by the following two rules.
a′′ ∈
/ w ⊆ atom(a, v, a′ , v ′ )
⊢w∪{a′′ } v{a′′ /a} ∼
Γ ⊢w e Eb e′ : τ
= v ′ {a′′ /a′ } : τ
(B.1)
∅ ⊢w «a»v E «a′ »v ′ : τ bnd
Γ ⊢w e E e′ : τ

Lemma B.1.
(i) E is compatible and substitutive.
(ii) atom(e) ⊆ w ∧ Γ ⊢ e : τ ⇒ Γ ⊢w e E e : τ .
b S : τ → τ ′.
(iii) atom(S) ⊆ w ∧ Γ ⊢ S : τ → τ ′ ⇒ Γ ⊢w S E
′
′
(iv) Γ ⊢w v E e : τ ⇒ e ∈ Val.

Proof. These properties of E are simple consequences of its deﬁnition in (B.1), the deﬁnition
of compatible reﬁnement in Figure 8, and the deﬁnition of its extension to a relation between
frame stacks given by the last two rules in that ﬁgure.
Lemma B.2.
(i) E is equivariant.
(ii) Γ ⊢w e E e′ : τ ∧ w ⊆ w′ ⇒ Γ ⊢w′ e E e′ : τ .
(iii) Γ ⊢w S Eb S ′ : τ → τ ′ ∧ w ⊆ w′ ⇒ Γ ⊢w′ S E S ′ : τ → τ ′ .

Proof. This is the analogue of Lemma A.2 for E, and is proved in the same way as that
lemma.
Lemma B.3. For all n ≥ 0 and all w, S, S ′ , τ, τ ′ , e, e′ ,~a
∅ ⊢w S Eb S ′ : τ → τ ′ ∧ ∅ ⊢w e E e′ : τ ∧ atom(~a) = w ∧ h~a, S, ei↓n ⇒ h~a, S ′ , e′ i↓ . (B.2)

Proof. The lemma is proved by induction on n. The base case n = 0 follows directly from
Lemma B.1(iii) and the deﬁnition of Eb (which implies that {} ⊢w Id Eb S ′ : τ → τ ′ can only
hold when S ′ = Id). For the induction step, assume (B.2) holds and that
∅ ⊢w S Eb S ′ : τ → τ ′
(B.3)
∅ ⊢w e E e′ : τ

(B.4)

atom(~a) = w

(B.5)

h~a, S, ei −→ h~a1 , S1 , e1 i

(B.6)

h~a1 , S1 , e1 i↓

n

(B.7)

We have to prove h~a, S ′ , e′ i↓ and do so by an analysis of (B.6) against the possible cases
1–9 in the deﬁnition of the transition relation in Figure 5. Cases 1, 3 and 6 follow from
the deﬁnition of E and its substitutivity property; we give the details for the ﬁrst one and
omit the other two. Cases 4, 5 and 9 also follow easily from the deﬁnition of E (using
Lemma B.1(ii) in the third case). So we give the proofs just for cases 1, 2, 7 and 8.

32

A.M. PITTS AND M.R. SHINWELL

Case 1. In this case S = S1 ◦ (x. e2 ), e = v ∈ Val, ~a1 = ~a, and e1 = e2 [v/x], for some e2
and v. For (B.3) to hold, by deﬁnition of Eb it must be the case that S ′ = S1′ ◦ (x. e′2 ) for
some S1′ and e′2 with
{x : τ } ⊢w e2 E e′2 : τ2

(B.8)

∅ ⊢w S1 Eb S1′ : τ2 → τ ′

(B.9)

∅ ⊢w e2 [v/x] E e′2 [v ′ /x] : τ2 .

(B.10)

for some type τ2 . Since e = v is a value, applying Lemma B.1(iv) to (B.4) we get e′ = v ′
b is substitutive (Lemma B.1(i)), from (B.4) and (B.8) we get
for some v ′ ∈ Val. So since E

Applying the induction hypothesis (B.2) to (B.9), (B.10), (B.5) and to (B.7), we get
h~a, S1′ , e′2 [v ′ /x]i↓; hence h~a, S1′ ◦ (x.e′2 ), v ′ i↓, that is, h~a, S ′ , e′ i↓, as required.

Case 2. In this case e = let x = e1 in e2 , ~a1 = ~a and S1 = S ◦ (x. e2 ) for some e2 . For (B.4)
to hold, by deﬁnition of Eb it must be the case that e′ = let x = e′1 in e′2 for some e′1 , e′2 and
τ1 with
{} ⊢w e1 E e′1 : τ1

(B.11)

{x : τ1 } ⊢w e2 E e′2 : τ .

(B.12)

From (B.3) and (B.12) we get ∅ ⊢w S ◦ (x. e2 ) Eb S ′ ◦ (x. e′2 ) : τ → τ ′ ; and the induction
hypothesis (B.2) applied to this, (B.11), (B.5) and (B.7) gives h~a, S ′ ◦ (x. e′2 ), e′1 i↓. Hence
h~a, S ′ , let x = e′1 in e′2 i↓, that is, h~a, S ′ , e′ i↓, as required.
Case 7. In this case τ = atm, e = fresh(), ~a1 = ~a < a, S1 = S and e1 = a, for some
atom a ∈
/ w. For (B.4) to hold, by deﬁnition of E it must be the case that e′ = fresh().
Now Lemma B.2(iii) applied to (B.3) gives ∅ ⊢w∪{a} S Eb S ′ : τ → τ ′ ; and Lemma B.1(ii)
gives ∅ ⊢w∪{a} a E a : atm. Applying the induction hypothesis (B.2) to these two facts,
atom(~a < a) = w ∪ {a} and (B.7) gives h~a < a, S ′ , ai↓. Hence h~a, S ′ , fresh()i↓, that is,
h~a, S ′ , e′ i↓, as required.
Case 8. In this case τ = atm ∗ τ1 , e = unbind «a»v, ~a1 = ~a < a1 , S1 = S, and e1 =
(a1 , v{a1 /a}), for some τ1 , a, v and a1 with a1 ∈
/ w. For (B.4) to hold, by deﬁnition of E it
must be the case that e′ = unbind «a′ »v ′ with
either (a): a = a′ ∧ ∅ ⊢w v E v ′ : τ1
(B.13)
or (b): ∃a′′ ∈
/ w. ⊢w∪{a′′ } v{a′′ /a} ∼
= v ′ {a′′ /a} : τ1
If (B.13)(a) holds, then as in the proof of Lemma A.5 we now appeal to the easily
veriﬁed fact that since a1 ∈
/ w ⊇ atom(v, v ′ ), the renamed values v{a1 /a} and v ′ {a1 /a} are
respectively equal to the permuted values (a a1 ) · v and (a a1 ) · v ′ (where (a a1 ) denotes
the permutation swapping a and a′ ). Therefore from the fact that ∅ ⊢w v E v ′ : τ1 holds,
from parts (i) and (ii) of Lemma B.2 we get ∅ ⊢w∪{a1 } v{a1 /a} E v ′ {a1 /a} : τ1 . Then since
a = a′ , by Lemma B.1(ii) we have ∅ ⊢w∪{a1 } (a1 , v{a1 /a}) E (a1 , v ′ {a1 /a′ }) : atm ∗ τ1 .
Applying the induction hypothesis (B.2) to this, (B.3) (weakened using Lemma B.2(iii)),
atom(~a < a1 ) = w ∪ {a1 } and (B.7) yields h~a < a1 , S ′ , (a1 , v ′ {a1 /a})i↓ with a1 ∈
/ atom(~a).
Therefore by deﬁnition of ↓, we also have h~a, S ′ , unbind «a′ »v ′ i↓.

GENERATIVE UNBINDING OF NAMES

33

If (B.13)(b) holds, then by Theorem 4.4, so does
∼ (a′′ , v ′ {a′′ /a}) : atm ∗ τ1
⊢w∪{a′′ } (a′′ , v{a′′ /a}) =

(B.14)

Lemma 3.2 applied to (B.7) with π = (a1 a′′ ) gives h~a < a′′ , S, (a′′ , v{a′′ /a})i↓n . Combining
this with (B.3) (weakened using Lemma B.2(iii)), ∅ ⊢w∪{a′′ } (a′′ , v{a′′ /a}) E (a′′ , v{a′′ /a}) :
atm ∗ τ1 (by Lemma B.1(ii)), atom(~a < a′′ ) = w ∪ {a′′ } and the induction hypothesis (B.2),
we get h~a < a′′ , S ′ , (a′′ , v{a′′ /a})i↓. Then by deﬁnition of ∼
=, from this and (B.14) we get
h~a < a′′ , S ′ , (a′′ , v ′ {a′′ /a})i↓ with a′′ ∈
/ ~a. Therefore as before, by deﬁnition of ↓, we also
have h~a, S ′ , unbind «a′ »v ′ i↓.
So in either case in (B.13), since e′ = unbind «a′ »v ′ , we get h~a, S ′ , e′ i↓, as required.
This completes the proof of Lemma B.3.
We can now complete the proof of Proposition 5.7. For any type τ ∈ Typ, suppose we
are given closed, well-typed atom binding values ∅ ⊢ «a»v : τ bnd and ∅ ⊢ «a′ »v ′ : τ bnd
with atom(a, v, a′ , v ′ ) ⊆ w and satisfying
⊢w∪{a′′ } v{a′′ /a} ∼
(B.15)
= v ′ {a′′ /a′ } : τ
for some atom a′′ ∈
/ w. By deﬁnition of E this implies
∅ ⊢w «a»v E «a′ »v ′ : τ bnd .
For any

w′ ,

~a, S, and

τ′

with atom(~a) =
∅ ⊢w ′

by Lemma B.1(iii) and

w′

⊇ w ∪ atom(S) and ∅ ⊢ S : τ →
S Eb S : τ → τ ′

(B.16)
τ ′,

we have
(B.17)

(B.18)
∅ ⊢w′ «a»v E «a′ »v ′ : τ bnd
by Lemma B.2(ii) applied to (B.16). So Lemma B.3 applied to (B.17), (B.18) and atom(~a) =
w′ , we have
h~a, S, «a»vi↓ ⇒ h~a, S, «a′ »v ′ i↓ .
Since ∼
= is symmetric, the same argument shows that (B.15) implies
h~a, S, «a′ »v ′ i↓ ⇒ h~a, S, «a»vi↓ .
Thus (B.15) implies that «a»v and «a′ »v ′ are operationally equivalent, as required.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view
a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a
letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

