Normalisation by Traversals
C.-H. Luke Ong
University of Oxford

arXiv:1511.02629v1 [cs.PL] 9 Nov 2015

Abstract
We present a novel method of computing the β-normal η-long form of a simply-typed
λ-term by constructing traversals over a variant abstract syntax tree of the term. In contrast to β-reduction, which changes the term by substitution, this method of normalisation
by traversals leaves the original term intact. We prove the correctness of the normalisation
procedure by game semantics. As an application, we establish a path-traversal correspondence theorem which is the basis of a key decidability result in higher-order model
checking.

Contents
1 Introduction
1.1 Traversals: an example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Correctness of normalisation by traversals . . . . . . . . . . . . . . . . . . . . . .

1
2
4

2 Technical preliminaries
6
2.1 Arenas, direct arena morphisms and justified sequences . . . . . . . . . . . . . . 6
2.2 Game semantics of the lambda calculus . . . . . . . . . . . . . . . . . . . . . . . 10
3 Traversals over long forms
3.1 Long form of a lambda term . . . . . . . . . . . .
3.2 Explicit arenas, succinct arenas and succinct long
3.3 Traversals over a long form . . . . . . . . . . . .
3.4 Proof of the strong bijection theorem . . . . . . .

. . .
form
. . .
. . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

10
10
13
16
19

4 Application
24
4.1 Interpreting higher-order recursion schemes . . . . . . . . . . . . . . . . . . . . . 24
4.2 The traversal-path correspondence theorem . . . . . . . . . . . . . . . . . . . . . 25

1

Introduction

This paper is about a method of computing the normal form of a lambda-term by traversing
a slightly souped up version of the abstract syntax tree of the term, called its long form. A
traversal is a certain justified sequence of nodes of the tree i.e. sequence of nodes such that each
(non-initial) node is equipped with a justification pointer to an earlier node. Each traversal
may be viewed as computing a path in the abstract syntax tree of the β-normal η-long form of
the term. Note that a term-tree, such as the normal form of a term, is determined by the set
of its paths. The usual (normalisation by) β-reduction changes the term by substitution. By
contrast, our method of normalisation by traversals does not perform β-reduction, thus leaving
the original term intact. In this sense, normalisation by traversals uses a form of reduction that
is non-destructive and local [Danos and Regnier, 1993].
1

Normalisation by Traversals

1.1

C.-H. Luke Ong

Traversals: an example

We first illustrate traversals with an example. Take the term-in-context,
g : (o → o) → o → o, a : o ⊢ N P R : o,
where
N = λϕ(o→o)→o→o z o→o .ϕ (λx.ϕ (λx′ .x) a) (z a)
P = λf o→o y o .f (g (λb.b) y)
R = g (λb′ .b′ )
which has normal form g (λb.b) (g (λb′ .b′ ) a). To normalise the term N P R by traversal, we first
construct its long form, written hN P Ri, which is the following term


 

 
λw.g(λb′ .b′ )(λ.w)
λf y.f λ.g(λb.b)(λ.y)
λ.@ λϕz.ϕ λx.ϕ (λx′ .x) (λ.a) λ.z (λ.a)

The long form is obtained by η-expanding the term fully1 , and then replacing the (implicit)
binary application operator of each redex by the long application operator @.
Now consider the abstract syntax tree of hN P Ri, as shown in Figure 1. Notice that nodes
on levels 0, 2, 4, etc., are labelled by lambdas; and those on levels 1, 3, 5, etc., are labelled by
either variables or the long application symbol @. The dotted arrows (pointing from a variable
to its λ-binder) indicate an enabling relation between nodes of the tree: n ⊢ n′ (read “n′ is
ww
enabled by n′ ”) just if n
n′ . By convention, (nodes labelled by) free variables are enabled
by the root node, as indicated by the dotted arrows. Further, every lambda-labelled node,
except the root, is enabled by its parent node in the tree (we omit all such dotted arrows from
the figure to avoid clutter).
Traversals are justified sequences (i.e., sequences of nodes whereby each (non-initial) node
has a justification pointer to an earlier node) that strictly alternate between lambda and nonlambda labels. The long form hN P Ri has three maximal traversals, one of which is the
following:

3
2
2
2

1

1

1
1
1

2

λ @ λϕz ϕ λf y f λx ϕ λf y

f

5

10

λx′ x λ g

λ

15

y λ z λw

g
20

λb′ b′

(1)

The five rules that define traversals are displayed in Table 1. The rule (Root) says that the
root node is a traversal. The rule (Lam) says if a traversal t ends in a λ-labelled node n, then
t extended with the child node of n, n′ , is also a traversal. Note that every node of a traversal
in an even position is constructed by rule (Lam). The rule (App) justifies the construction of
the third node of traversal (1). If a traversal ends in a node labelled with a variable ξi , then
1 Somewhat nonstandardly, every ground-type subterm that is not in a function position is also expanded (to
a term with a “dummy lambda”) t 7→ λ.t. For example, λxo→o→o .x a fully η-expands to λxo→o→o z o .x (λ.a) (λ.z);
and g (λb.b) (g (λb′ .b′ ) a) fully η-expands to λ.g (λb.b) (λ.g (λb′ .b′ ) λ.a).

2

Normalisation by Traversals

C.-H. Luke Ong

there are two cases, corresponding to whether ξi is (hereditarily justified2 by) a bound (BVar)
or free (FVar) variable in the long form.
(BVar): If the traversal has the form t · n · λξ · · · ξi where ξ = ξ1 · · · ξn , and ξi is hereditarily justified by a @, then there are two subcases.
i

- If n is (labelled by) a variable then t · n · λξ · · · ξi · λη is a traversal, whereby the pointer
label i means that the node λη is the i-th child of n. For example, this rule justifies the
construction of the 11th node λx′ and 13th node λ of traversal (1).
i+1

- If n is (labelled by) @ then t · @ · λξ · · · ξi · λη is a traversal. For example, this rule
justifies the construction of the 5th node λf y, 9th node λf y and 19th node λw of traversal
(1). meaning that the node is the (i + 1)-th child of @.
Intuitively the rule (BVar) captures the switching of control between caller and callee, or between formal and actual parameters. See Remark 3.15 for further details.
(FVar): If the traversal has the form t · λξ · · · ξi and ξi is hereditarily justified by the
j

opening node ǫ, then t · λξ · · · ξi · λη is a traversal, for each child-node λη of ξi (so j ranges
over { 1, · · · , ar (ξi ) } where ar (ξi ) is the arity (branching factor) of ξi ). For example, the 15th
node λ and the 21st node λ of traversal (1) are constructed by this rule.
As mentioned earlier, each traversal computes a path in the abstract syntax tree of the
β-normal η-long form of the term N P R, which is shown in Figure 2. With reference to the
Figure, notice that each path of the tree is actually an alternating justified sequence, in fact,
a P-view (about which more anon). Such a justified path is obtained from the traversal by
projecting to those nodes that are hereditarily justified by the root node. Thus we obtain
1

2

the following projected justified subsequence from traversal (1), λ g λ g λb′ b′ , which is a
maximal path of λ.g (λb.b) (λ.g (λb′ .b′ ) (λ.a)), the β-normal η-long form of N P R.
The other maximal traversals of hN P Ri are:

3
2
1

2
2
1

1

1

1

2

2

λ @ λϕz ϕ λf y f λx ϕ λf y

f

5

10

λx′ x λ g

g
20

15

λ w λ a

(2)

1

1

1

y λ z λw

1

2
2

λ

1

λ @ λϕz ϕ λf y
5

f λx ϕ λf y

f
10

λx′ x λ g λb b
15

(3)

2 We say that a node-occurrence n in a justified sequence is hereditarily justified by another n′ if there is a
chain of pointers from n to n′ .

3

Normalisation by Traversals

C.-H. Luke Ong

EE λSS WW kk
❩
❚❩
t @ ❚❚❩❚❩❚❩❚❩❚❩❩❩❩❩❩❩❩
t
t
❩❩❩❩❩❩❩
❚❚❚❚
t
t
❩❩❩❩❩❩❩
t
❚❚
❩ λw
λϕz
λf
y
hh
XX ``
BB KK PP

33 λx

λx′
x

ϕ
tt ■■■■
t
t
■■
■
ttt

ϕ ❏❏
❏❏❏
✉✉
✉✉
❏❏❏
✉
✉

f
λb′ZZ

λ

λ

z

b′
t g ❏❏❏❏
tt
❏
t
❏❏❏
t
tt
λb [[
λ

λ

λ

a

a

b

g
tt ❍❍❍❍
t
t
❍❍
❍
ttt

λ
w

y

Figure 1: The abstract syntax tree of the long form hN P Ri in Section 1.1.
λ [[iikk

λb [[

g■
tt ■■■■
tt
■■
t
t

b
λb′[[

λ

g❊
✇✇ ❊❊❊
✇✇
❊❊
✇
✇

b′

λ
a

Figure 2: The abstract syntax tree of hg (λb.b) (g (λb′ .b′ ) a)i in Section 1.1.

2

2

1

which respectively project to the maximal paths, λ g λ g λ a and λ g λb b , of the βnormal η-long form of N P R.

1.2

Correctness of normalisation by traversals

We state the correctness theorem.
Theorem 1.1 (Correctness). Given a term-in-context Γ ⊢ M : A, there is a bijection between
the following sets of justified sequences:
- TravhM i ↾ ǫ, traversals over hM i projected to nodes hereditarily justified by the root node ǫ
4

Normalisation by Traversals

C.-H. Luke Ong

- Pathhβ(M )i, justified paths in the abstract syntax tree of the long form hβ(M )i, where β(M )
is the β-normal form of M .
Furthermore the bijective map is strong in the sense that every projected traversal and its image
as path are isomorphic as justified sequences. Thus, normalisation by traversals is correct: the
set of projected traversals over hM i determine the β-normal η-long form of M .
The proof is via game semantics [Hyland and Ong, 2000]. The game-semantic denotation
of a sequent, [[ Γ ⊢ M : A ]], is an innocent strategy, represented as a certain prefix-closed set of
justified sequences called plays. Innocent means that the strategy is generated by the subset
p[[ Γ ⊢ M : A ]]q of plays which are P-views. (Intuitively the P-view of a play is a certain justified
subsequence consisting only of those moves which player P considers relevant for determining his
next move. See Section 2.1 for the definitions.) We prove the correctness theorem by showing
that the following three sets of justified sequences are strongly bijective:
TravhM i ↾ ǫ

ℓ̂∗

// p[[ Γ ⊢ M : A ]]q

G

// Pathhβ(M )i

(4)

The strong bijection on the right, G, is a well-known fundamental result of game semantics,
and the essence of the definability result [Hyland and Ong, 2000]. The strong bijection on the
left, ℓ̂∗ , is the main technical result of the paper, Theorem 3.18. The key intuition is that
traversals correspond to a certain collection of uncovered plays (of an innocent strategy) or
plays-without-hiding. Given a term-in-context Γ ⊢ M : A, we formalise the long form, hM i, as
a Σ-labelled binding tree, in the sense of Stirling [2009]. We then identify two arenas associated
with hM i, viz., explicit arena ExpAr hM i, and succinct arena SucArhM i. The enabling relation
⊢ between nodes of the long form hM i (as discussed in Section 1.1) is defined as the enabling
relation of the arena ExpAr hM i, whose underlying set consists of nodes of the (binding) tree
hM i. Traversals over hM i are then defined as justified sequences over ExpAr hM i by induction
over a number of rules.
To interpret traversals over hM i as uncovered plays, we define the succinct arena SucArhM i
as a disjoint union of
- a “revealed” arena, consisting of the arena over which [[ Γ ⊢ M : A ]] is defined as a strategy,
and
- a “hidden” arena, for interpreting the moves that are hereditarily justified by an @ in hM i.
We then define a map ℓ̂ : ExpArhM i → SucArhM i, called direct arena morphism, which preserves initial moves, and preserves and reflects the enabling relation. Furthermore the morphism
extends to a function ℓ̂∗ that maps justified sequences of ExpArhM i to those of SucArhM i.
Theorem 3.18 then asserts that the map ℓ̂∗ defines a strong bijection from TravhM i ↾ ǫ to
p[[ Γ ⊢ M : A ]]q.

Application to higher-order model checking
We apply normalisation by traversals to higher-order model checking [Ong, 2015]. The Higherorder Model Checking Problem [Knapik et al., 2002] asks, given a higher-order recursion scheme
G and a monadic second-order formula ϕ, whether the tree generated by G, written [[ G ]], satisfies
ϕ?
This problem was first shown to be decidable by Ong [2006]. Ong’s proof uses a transference
principle: instead of reasoning about the parity winning condition of infinite paths in the
generated tree [[ G ]], he considers traversals over the computation tree of G, λ(G), which is a tree
5

Normalisation by Traversals

C.-H. Luke Ong

obtained from G by first transforming the rewrite rules into long forms, then unfolding these
transformed rules ad infinitum, but without performing any β-reduction (i.e. substitution of
actual parameters for formal parameters). The argument uses a key technical lemma, presented
in the following as Theorem 4.5, which states that paths in the generated tree [[ G ]] on the one
hand, and traversals over the computation tree λ(G) projected to the terminal symbols from Σ
on the other, are the same set of finite and infinite sequences over Σ. In this paper, we apply
Theorem 3.18 to prove Theorem 4.5.

2

Technical preliminaries

We write N = { 1, 2, · · · }, X0 = { 0 } ∪ X for X ⊆ N, [n] = { 1, · · · , n } for n ∈ N, X ⋆ for
the set of finite sequences of elements of X, ≤ for the prefix ordering over sequences, and
|x1 · x2 · · · xn | = n for the length of sequences. By a tree T , we mean a subset of N⋆ that is
prefix-closed (i.e. if α ∈ T and α′ ≤ α then α′ ∈ T ) and order-closed (i.e. if α · n ∈ T and
1 ≤ n′ < n then α · n′ ∈ T ). A path in T is a sequence of elements of T , α1 · α2 · · · αn , such that
α1 = ǫ, αn = i1 · i2 · · · in−1 , and αj+1 = αj · ij for each 1 ≤ j ≤ n − 1. We write Path(T ) for
the set of paths in the tree T . A ranked alphabet Σ is a set of symbols such that each symbol
f ∈ Σ has an arity ar (f ) ≥ 0. A Σ-labelled tree is a function F : T → Σ such that (i) T is a
tree, and (ii) for each α ∈ T , if ar (F (α)) = n then { 1, · · · , n } = { i | α · i ∈ T }. By definition,
Σ-labelled trees are ordered, i.e., the set of children of each node is a (finite) linear order. Let T
be a tree, and let α ∈ T . The tree T rooted at α, denoted T@α , is the set { γ ∈ N∗ | α · γ ∈ T }.
Types (ranged over by A, B, etc.) are defined by the grammar: A ::= o | (A → B). A type
can be written uniquely as (by convention → associates to the right), A1 → · · · → An → o,
which we abbreviate to (A1 , · · · , An , o). The order of a type A, ord (A), which measures how
deeply nested a type is on the left of the arrow, is defined as ord (o) := 0, and ord (A → B) :=
max(ord (A) + 1, ord (B)). The arity of a type A = (A1 , · · · , An , o), written ar (A), is defined to
be n.
We assume an infinite set Var of typed variables, ranged over by Φ, Ψ, ϕ, ψ, x, y, z, etc.
Raw terms (ranged over by M, N, P, Q, etc.) of the pure lambda calculus are defined by the
grammar: M ::= x | λxA .M | (M N ); by convention, applications associate to the left. Typing
judgements (or terms-in-context) have the form, Γ ⊢ M : A, where the environment Γ is a list
of variable bindings of the form x : A. Henceforth, by a term M (respectively, M : A) we mean
a well-typed term (respectively, of type A), i.e., Γ ⊢ M : A is provable for some environment Γ
and type A. We write FV(M ) for the set of variables that occur free in M .

2.1

Arenas, direct arena morphisms and justified sequences

Definition 2.1 (Arena). An arena is a triple A = (|A|, ⊢A , λA ) such that |A| is a set (of
moves), ⊢A ⊆ (|A| + { ⋆ }) × |A| is the enabling relation, and λA : |A| −→ { O, P } is the
ownership function that partitions moves into O-moves and P-moves, satisfying:
• For every m ∈ |A|, there exists a unique m′ ∈ (|A| ∪ { ⋆ }) such that m′ ⊢A m; we call m′
2
the enabler of m, or m′ enables m. Writing ⊢c
A for the inclusion of ⊢A in ({ ⋆ } ∪ |A|) , we
∗
∗
say that m is hereditarily enabled by m′ if m′ ⊢c
A m, writing ρ for the reflexive, transitive
closure of a binary relation ρ).

• Whenever m ⊢A m′ then λA (m) 6= λA (m′ ).

We call a move initial if its enabler is ⋆, and write Init A for the set of initial moves of A.
An arena A is said to be O-initial if λA (m) = O for every initial m; and pointed if Init A is a
6

Normalisation by Traversals

C.-H. Luke Ong

singleton set. We define the set of O-moves as |A|O := {m ∈ |A| | λA (m) = O}, and the set
of P-moves as |A|P := {m ∈ |A| | λ(m) = P}. The opposite arena of A is A⊥ := (|A|, ⊢A , λ⊥
A)
where λ⊥
(m)
=
P
if,
and
only
if,
λ
(m)
=
O.
We
say
that
A
is
ordered
if
for
each
m
∈
|A|,
A
A
the set { m′ | m ⊢A m′ } is a linear order; and if so, we write m ⊢iA m′ , where i ≥ 1, to mean
m′ is the i-th child of m.
There is an obvious one-one correspondence between types and finite, ordered trees. For
example, the type (((o, o), o), o, (o, o, o), o) corresponds to the tree whose maximal (with respect
to ≤) elements are 1 · 1 · 1, 2, 3 · 1 and 3 · 2. We write Tree A to mean the tree that corresponds
to the type A.
Definition 2.2 (Arena determined by type A). Let A be a type. The arena determined by A,
written Ar (A), is defined as follows:
• |Ar (A)| := Tree A
• ⋆ ⊢Ar (A) ǫ, and for all α, β ∈ |Ar (A)|, α ⊢Ar (A) β ⇐⇒ (α ≤ β ∧ |β| = |α| + 1)
• λAr (A) (α) = O ⇐⇒ |α| even.
Plainly Ar (A) is a finite arena which is ordered, pointed and O-initial.
We fix a scheme for naming nodes of a given tree (and hence moves of an arena determined
by a type) using symbols of the following infinite ranked alphabet
A

Ai
n+1
1
Λ := Var ∪ { λα | α ∈ N∗ } ∪ { λxA
1 · · · xn+1 | xi ∈ Var , n ≥ 0 }
A

n+1
α
1
such that ar (xA ) := ar (A), ar (λxA
1 · · · xn+1 ) := 1 and ar (λ ) := 0. By abuse of language,
we say that the lambda λξ1A1 · · · ξnAn has type (A1 , · · · , An , o), and the dummy lambda λα has
type o.
Given a type A and an injective function, νA : { α ∈ Tree A | |α| odd } → Var, such that
whenever νA (α) = xB then (Tree A )@α = Tree B , we extend νA to a function Tree A → Λ as
i
follows. Let α ∈ Tree A be of even length. Suppose for each α·i ∈ Tree A , we have νA (α·i) = xB
i ,
and n = |{ i | α · i ∈ Tree A }|, we define
(
Bn
1
λxB
if n > 0
1 · · · xn
νA (α) :=
α
λ
if n = 0

It is straightforward to see that for every type A, the function νA : Tree A → Λ satisfies the
following: 1. νA is injective, 2. νA defines a Λ-labelled tree, 3. for all α ∈ Tree A , if νA (α) has
type B then (Tree A )@α = Tree B . We call such a function νA a Λ-representation of Tree A (and
for arena Ar(A), and type A).
Example 2.3. Take the type A → A where A = (((o, o), o), (o, o), o). We display the nodes of
Tree A→A via a naming scheme νA→A : Tree A→A → Λ in Figure 3.
Product
For arenas A and B, we define the product arean A × B by:
• |A × B| := |A| + |B|,
• ⋆ ⊢A×B m ⇐⇒ ⋆ ⊢A m or ⋆ ⊢B m,
• m ⊢A×B m′ ⇐⇒ m ⊢A m′ or m ⊢B m′ ,
7

Normalisation by Traversals

((((o,

λ1111

o),

C.-H. Luke Ong

o),

(o,

o),

o),

((o,

o),

o),

(o,

o),

o)

❝❝❝❝❝❝❢ λχΦϕ
❝❝❝❝❝❢❝❢❝❢❝❢❝❢❢❢❢❢❢rrrr
❝
❝
❝
❝
❝
❝
❝
❝
❝
❢
χ ❝❝❝❝
ϕ
Φ❢
❣❣❣②❣②❣②
②
❣
❣
②
❣
✇✇✇
❣
②
❣
❣
❣
λ31
λx
λy
λψ ❣
②
✇
①
②
✇
①
②
①
②
✇✇
ψ
x
y
s
s
s

Figure 3: A Λ-representation of Tree A→A where A = (((o, o), o), (o, o), o).

• λA×B (m) :=

(

λA (m)
λB (m)

if m ∈ |A|
if m ∈ |B|

Thus A × B is just the disjoint unionQof A and B qua labelled directed graphs. For an indexed
set {Ai }i∈I of arenas, their product i∈I Ai is defined similarly.
Function space

For arenas A and B, we define the function space arena A ⇒ B by:
• |A ⇒ B| := |A| × Init B + |B|,
• ⋆ ⊢A⇒B m ⇐⇒ ⋆ ⊢B m,
• m ⊢A⇒B m′ ⇐⇒
– m ⊢B m′ , or
– ⋆ ⊢B m and m′ = (m′A , m) and ⋆ ⊢A m′A , or
– m = (mA , mB ) and m′ = (m′A , mB ) and mA ⊢A m′A
(
if m = (mA , mB ) ∈ |A| × Init B
λ⊥
A (mA )
• λA⇒B (m) :=
λB (m)
if m ∈ |B|)
Observe that if A and B are types, then Ar(A → B) = Ar (A) ⇒ Ar(B).
Definition 2.4 (Justified sequence). A justified sequence of an arena A is a finite sequence of
moves, m1 · m2 · . . . · mn , such that for each j, if mj is non-initial then mj has a pointer to mi
such that i < j and mi ⊢A mj . Formally it is a triple s = (#s, s, ρs ) consisting of a number
#s ∈ N0 (which is the length of the justified sequence), and total functions s : [#s] → |A|
(moves function) and ρs : [#s] → [#s]0 (pointers function) such that
• ρs (k) < k for every k ∈ [#s], and
• ρs respects the enabling relation: ρs (k) = 0 implies ⋆ ⊢A s(k), and ρs (k) 6= 0 implies
s(ρs (k)) ⊢A s(k).
As usual, by abuse of notation, we often write m1 · m2 . . . mn for a justified sequence such that
s(i) = mi for every i, leaving the justification pointers implicit. Further we use m and mi as
meta-variables of move occurrences in justified sequences. We write mi x mj if ρs (j) = i > 0
and ⋆ x mj if ρs (j) = 0. We call mi the justifier of mj , and say mj is justified by mi whenever
mi x mj . We say that mj is hereditarily justified by mi if mi x∗ mj . In case A is an ordered
i

arena, we write m x m′ to mean m x m′ and m ⊢iA m′ .
8

Normalisation by Traversals

C.-H. Luke Ong

It is convenient to relax the domain [#s] = {1, 2, . . . , #s} of justified sequences to arbitrary
linearly-ordered finite sets such as a subset of [#s]. For example, given a justified sequence
(#s, s : [#s] → |A|, ρs : [#s] → [#s]0 ), consider a subset I ⊆ [#s] that respects the justification
pointers, i.e., k ∈ I implies ρs (k) ∈ I ∪ {0}. Then the restriction (I, s↾I : I → |A|, ρs ↾I : I →
{0} ∪ I) is a justified sequence in the relaxed sense. A justified sequence in the relaxed sense is
identified with that in the strict sense through the unique monotone bijection α : I → [n].
A justified sequence is alternating just if s(k) ∈ |A|O ⇐⇒ k is odd. Henceforth we assume
that justified sequences are alternating.
Definition 2.5 (P-View / O-view). Let m1 . . . mn be a justified sequence over an arena A. Its
P-view pm1 . . . mn q is a subsequence defined inductively by:
(if mn ∈ |A|P )

pm1 . . . mn q := pm1 . . . mn−1 q mn

(if ⋆ x mn ∈ |A|O )

pm1 . . . mn q := mn
pm1 . . . mn q := pm1 . . . mk q mn

(if mk x mn ∈ |A|O ).

Its O-view xm1 . . . mn y is a subsequence defined inductively by:
xm1 . . . mn y := xm1 . . . mn−1 y mn
xm1 . . . mn y := mn
xm1 . . . mn y := xm1 . . . mk y mn

(if mn ∈ |A|O )
(if ⋆ x mn ∈ |A|P )

(if mk x mn ∈ |A|P ).

Formally the P-view of a justified sequence s is a subset I ⊆ [#s]. Then psq is the restriction
of s to I; similarly for xsy. Henceforth by a P-view, we mean a justified sequence s such that
psq = s.
A P-move mk in the sequence m1 . . . mn (n ≥ k) is P-visible just if ⋆ x mk or its justifier
is in pm1 . . . mk q. Similarly, an O-move mk in the sequence m1 . . . mn (n ≥ k) is O-visible just
if ⋆ x mk or its justifier is in xm1 . . . mk y. A justified sequence s is P-visible (respectively,
O-visible) just if each P-move (respectively, O-move) occurrence in s is P-visible (respectively,
P-visible); s is visible just if it is both P- and O-visible. If s is a visible justified sequence, then
so are psq and xsy [Hyland and Ong, 2000].
Definition 2.6 (Direct arena morphism). A direct arena morphism, I : (|A|, ⊢A , λA ) →
(|B|, ⊢B , λB ), is a function I : |A| → |B| that respects:
• enabling relation: for all m, m′ ∈ |A|, ⋆ ⊢A m ⇐⇒ ⋆ ⊢B I(m), and m ⊢A m′ ⇐⇒
I(m) ⊢B I(m′ );
• ownership: for all m ∈ |A|, λA (m) = λB (I(m)).
A direct arena morphism I : A → B induces a function on justified sequences by extension in the obvious way: take a justified sequence t over A, define I ∗ (t) := (#t, t′ , ρt ) where
t′ (i) := I(t(i)) for i ∈ [#t]. It is straightforward to see that I ∗ (t) is a justified sequence over
B. In fact, t and I ∗ (t) are isomorphic as justified sequences, by which we mean that they
are isomorphic directed graphs (viewing a justified sequence as a linear tree with justification
pointers represented as back edges). I.e. writing I ∗ (t) = (#u, u, ρu ), we have #t = #u, and
ρt = ρu . (We do not, however, require the map ι from the image of t to the image of u, whereby
u(i) = ι(t(i)) for all i ∈ [#t], to be bijective.) Thus it follows that t is visible if, and only if,
I ∗ (t) is.
9

Normalisation by Traversals

C.-H. Luke Ong

Definition 2.7 (Strong bijection induced by direct arena morphism). Let L and L′ be sets of
justified sequences over arenas A and A′ respectively. Given a direct arena morphism I : A →
A′ , we say that the map I ∗ : L → L′ is a strong bijection (induced by I) if I ∗ restricted to
L, I ∗ ↾ L, is injective, and the image of I ∗ ↾ L is L′ . The adjective strong emphasises that,
in addition to the bijectivity of I ∗ , for every s ∈ L, we have s and I ∗ (s) are isomorphic as
justified sequences.
Henceforth, whenever it is clear from the context, we write I ∗ simply as I.

2.2

Game semantics of the lambda calculus

A play over an arena A is a visible justified sequence. A P-strategy over arena A, or just strategy
for short, is a non-empty prefix-closed set σ of plays over A satisfying:
• Determinacy. For every odd-length s ∈ σ, if s · a, s · b ∈ σ then a = b.
• For every even-length s ∈ σ, for every O-move a, if s · a is a play, then it is in σ.
We say that σ is total if for every odd-length s ∈ σ, there exists a such that s · a ∈ σ. We say
that σ is innocent if for every even-length s a ∈ σ and for every odd-length t ∈ σ if psq = ptq
then t · a ∈ σ. It follows from the definition that an innocent strategy σ is determined by the
set of even-length P-views in σ, written pσq; we say that σ is compact if pσq is a finite set.
We can now organise arenas and innocent strategies into a category I: objects are O-initial
arenas; and maps σ : A −→ B are innocent strategies over arena A ⇒ B.
Theorem 2.8. The category I is cartesian closed and enriched over CPOs.
Given a typing context Γ = x1 : A1 , · · · , xn : An , we define [[ Γ ]] := (([[ A1 ]]×[[ A2 ]]) · · · [[ An−1 ]])×
[[ An ]], with the empty context interpreted as the terminal object. The interpretation of a given
term-in-context Γ ⊢ M : A as a I-map [[ Γ ]] −→ [[ A ]] is standard, and we omit the definition.
Theorem 2.9 (Definability). Let A = (A1 , · · · , An , o) be a type. For every compact, total,
innocent strategy σ over [[ A ]], there is a unique η-long β-normal form, x1 : A1 , · · · , xn : An ⊢
Mσ : o, whose denotation is σ.
Proof. See [Hyland and Ong, 2000].

3

Traversals over long forms

3.1

Long form of a lambda term

The long form of a term is a kind of canonical form, which is obtained by first constructing
the η-long form of the term, and then replacing the standard binary application operators
b
by full application operators @B , which we called long application. The latter is achieved
by replacing every subterm of the η-long form that has the form (λx.P ) Q1 · · · Qm : o by
b
b
b which is a
@B (λx.P ) Q1 · · · Qm : o where m ≥ 1. The type of the function symbol @B is B,
shorthand for ((B1 , · · · , Bm , o), B1 , · · · , Bm , o) where B = (B1 , · · · , Bm , o).

Definition 3.1 (Long form in concrete syntax). Assume Γ ⊢ M : (A1 , · · · , An , o). The concrete
syntax of the long form of M , written hM i, is defined by cases as follows.
1. M is an application headed by a variable:

10

hx N1 · · · Nm i := λz1A1 · · · znAn .x hN1 i · · · hNm i hz1 i · · · hzn i
Sm
where zi ∈
6 { x } ∪ j=1 FVhNj i for each i.

Normalisation by Traversals

C.-H. Luke Ong

2. M is an application headed by an abstraction with m ≥ 1:
b

h(λx.P ) Q1 · · · Qm i := λz1A1 · · · znAn .@Ξ hλx.P i hQ1 i · · · hQm i hz1 i · · · hzn i
where Ξ = (B1 , · · · , Bm , A1 , · · · , An , o) which is the type of λx.P , and zi 6∈ FVhλx.P i ∪
S
m
j=1 FVhQj i for each i.

A1
Ai
Ai
1
3. M is an abstraction: hλxA
1 · · · xi .P i := λx1 · · · xi .hP i.

b

We shall elide the type superscript from variables xA and long application symbols @Ξ , whenever
it is clear form the context. We assume that bound variables in hM i are renamed afresh where
necessary, so that if λx.P and λy.Q are distinct subterms (i.e. they have different occurrences)
then { x1 , · · · , xm } and { y1 , · · · , yn } are disjoint. It is easy to verify that Γ ⊢ hM i : A.
If M is β-normal, and so hM i has no occurrences of @, then hM i is essentially the η-long
β-normal form of M . Note that in hM i we additionally η-expand every ground-type subterm P
of M to λ.P (we call λ a “dummy lambda”) provided P occurs at an operand position (meaning
that L P is a subterm of M for some L). By a long form, we mean the long form of a term.
Example 3.2. Consider the term-in-context ϕ : (((o, o), o, o), o, o, o), a : o ⊢ M : (o, o) where
M = ϕ (λx(o,o) .x) ((λy o .y) a). We have



hM i = λz1 .ϕ λx(o,o) z o .x (λ.z) λ.@ (λy o .y) (λ.a) λ.z1 : (o, o).
We organise the abstract syntax tree (AST) of a long form, somewhat non-standardly, as a
Λ(@)-labelled (binding) tree where
b

Λ(@) := { λx | x = x1 · · · xn ∈ Var ⋆ } ∪ Var ∪ { @A | A ∈ Types, ar (A) > 0 }
|
{z
}
{z
}
|
lambdas
non-lambdas
b

is a ranked alphabet such that ar (xA ) := ar (A); ar (λx) = 1, and ar (@A ) := ar (A) + 1. By
construction, in the AST of a long form, nodes on levels 0, 2, 4, etc., are labelled by lambdas,
and nodes on levels 1, 3, 5, etc., are labelled by non-lambdas.
Definition 3.3 (Σ-labelled binding tree). 1. A λ-alphabet is a ranked alphabet Σ which is
partitioned into Σλ , ΣVar and Σaux , such that Σλ consists of binders which have arity 1,
ΣVar consists of variables (whether bound or not), and Σaux consists of the remaining
auxiliary symbols.
2. A Σ-labelled binding tree is a triple (T, B, ℓ) where Σ is a λ-alphabet, ℓ : T → Σ is a
Σ-labelled tree, and B : T ⇀ T is a partial function called binder, satisfying: for all β ∈ T
(Bind) ℓ(β) ∈ ΣVar ⇐⇒ β ∈ dom(B); and if β ∈ dom(B) then B(β) < β and ℓ(β) ∈ Σλ .
By convention, if ℓ(β) is a free variable then B(β) = ǫ.
(Label) The labelling function ℓ maps elements in T of even lengths (including 0) into
Σλ , and elements in T of odd lengths into ΣVar ∪ Σaux .
Remark 3.4. Our definition of binding tree is slightly more permissive than the original [Stirling,
2009]: unlike Stirling, we do not assume that terms are closed.
Observe that Λ(@) is a λ-alphabet: Λ(@)λ consists of the lambdas, Λ(@)Var consists of the
variables, and Λ(@)aux consists of the long application symbols. The AST of a long form is a
Λ(@)-labelled binding tree.
11

Normalisation by Traversals

C.-H. Luke Ong

AA λz1 iiff
1

ϕ❚
❅❚❚
✉✉✉ ❅ ❚❚❚❚ ❚
✉
1
2❅❅
3 ❚❚❚
✉✉
❚❚❚
(o,o)
λ
λ
λx WW __ z
1

1

1

x

@✿
⑧⑧ ✿
⑧
1
2✿✿
⑧⑧

z1

1

λ
1

z

λy ]]

λ

1

1

y

a

Figure 4: The long form of the term M in Example 3.2
Example 3.5. Take M = ϕ (λx(o,o) .x) ((λy o .y) a) of Example 3.2. The abstract syntax tree of
the long form



hM i = λz1 .ϕ λx(o,o) z o .x (λ.z) λ.@ (λy o .y) (λ.a) λ.z1 : (o, o).

is displayed in Figure 4. Let (T, B, ℓ) be the Λ(@)-labelled binding tree representation of hM i.
uu
The binder function B is indicated by the dotted arrows in the figure i.e. m
m′ means
′
B(m ) = m. By convention (nodes that are labelled with) free variables are mapped by B to
the root node: thus B : 1 7→ ǫ, 12121 7→ ǫ.

Lemma 3.6. A finite Λ(@)-labelled binding tree (T, B, ℓ) is the long form of a term if, and
only if, it satisfies the following labelling axioms:
(Lam) If ℓ(β) = y and ℓ(B(β)) = λx then y ∈ x (i.e. y is bound in the term) or B(β) = ǫ (y
is a free variable).
(Leaf ) A node α is maximal in T if, and only if, ℓ(α) is a ground-type variable.
b

(TVar) A node labelled by @A where A = (A1 , · · · , An , o) has n + 1 children with lambda labels
of types A, A1 , · · · , An respectively (see left of Figure 5).
(T@) A node labelled by a variable ϕ : (A1 , · · · , An , o) has n children with lambda labels of
types A1 , · · · , An respectively (see right of Figure 5)
A

λξ1A1 · · · ξnAn

❤❤❤ @ ❏❏❏
❤❤❤❤ tttt
❤
❤
❤
n+1
2
❏❏❏
❤❤1
❤❤❤❤
ttt
···
ληn : An
λη1 : A1

✉ ϕ ❏❏❏❏
✉✉
✉
n❏❏
1
❏
✉✉✉
λη1 : A1
···
ληn : An

Figure 5: Labelling rules for long application symbols and variables.
Proof. The direction “⇒” can be proved straightforwardly by induction on the rules that define
hM i. For “⇐”, take a Λ(@)-labelled binding tree (T, B, ℓ) that satisfies the axioms. Because of
12

Normalisation by Traversals

C.-H. Luke Ong

(Label), ℓ(ǫ) has the form λx1 · · · xm ; and because of (Leaf), every maximal element in T has
an odd length. The base cases are therefore long forms of the shape λx.y with B : 1 7→ ǫ.
b
For the inductive cases, ℓ(1) is either @A or xA where A = (A1 , · · · , An , o) with n ≥ 1.
Suppose the former. By assumption, for all β ∈ dom(B), B(β) < β. Let α ∈ T . The
tree T rooted at α, denoted T@α , is the set { γ | α · γ ∈ T }. Define B@α : T@α ⇀ T@α by setting
dom(B@α ) := { β | α · β ∈ dom(B) }; and B@α (β) := β ′ if B(α · β) = α · β ′ , and B@α (β) := ǫ if
B(α · β) < α. Next define ℓ@α : T@α → Λ(@) by γ 7→ ℓ(α · γ). It follows that for each i ∈ [n + 1],
(T@1·i , B@1·i , ℓ@1·i ) is a Λ(@)-labelled binding tree that satisfies the axioms. By the induction
hypothesis, suppose the binding trees are the ASTs of the long forms hM i, hN1 i, · · · , hNn i
respectively. Then (T, B, ℓ) is the AST of the long form λx.@ hM i hN1 i · · · hNn i where ℓ(ǫ) = λx.
The latter case of ℓ(1) = xA is similar.

3.2

Explicit arenas, succinct arenas and succinct long form

Given a term, we identify two arenas that are associated with hM i, namely, explicit arena
ExpAr hM i, and succinct arena SucArhM i. The former arena provides the setting for traversals:
we will define traversals over hM i as justified sequences over the explicit arena ExpArhM i that
satisfy certain constraints.
Fix a term-in-context z1 : A1 , · · · , zi : Ai ⊢ M : (Ai+1 , · · · , An , o), and write A = (A1 , · · · , An , o)
and hM i = (T, B, ℓ). Furthermore assume that { (γ1 , Ξ1 ), · · · , (γr , Ξr ) } = { (γ, Ξ) | ℓ(γ) =
b
@Ξ }.
Definition 3.7 (Explicit Arena of hM i, ExpAr hM i). The explicit arena of hM i = (T, B, ℓ),
ExpAr hM i, is defined as follows. The underlying move-set |ExpAr hM i| := T . The enabling
relation, ⊢ExpAr hMi , is defined as follows:
• ⋆ ⊢ExpAr hMi ǫ; and for all i ∈ [r], ⋆ ⊢ExpAr hMi γi .
• If ℓ(α) = x(B1 ,··· ,Bm ,o) then for each i ∈ [m], α ⊢ExpAr hMi α · i.
b

• If ℓ(α) = @C where C = (C1 , · · · , Cl , o) then for each i ∈ [l + 1], α ⊢ExpAr hMi α · i.
• If ℓ(α) = λx1 · · · xm then: for all α′ ∈ B −1 (α)
– if ℓ(α′ ) = xi for some i ∈ [m] then α ⊢ExpAr hMi α′ .
– if ℓ(α′ ) 6∈ { x1 , · · · , xm } (it follows from (Lam) that α = ǫ and ℓ(α′ ) = zk ∈ FV(M )
for some k ∈ [i]) then ǫ ⊢ExpAr hMi α′ .
Finally λExpAr hMi (α) = O ⇐⇒ |α| is even.
Thus the explicit arena ExpAr hM i has the same underlying node-set T as the long form
hM i = (T, B, ℓ). Every lambda-labelled node is enabled by its predecessor in T . A variablelabelled node α is enabled by its binder B(α); by convention, a node α labelled by a free variable
is enabled by the root ǫ = B(α). A node is an O-move if and only if its label is a lambda.
The succinct arena of a long form is part of a compact representation of the long form as a
binding tree, called succinct long form.
Definition 3.8 (Succinct Arena of hM i, SucArhM i). The succinct arena of hM i, SucArhM i,
Qr
is defined to be the arena Ar(A) × i=1 Ar ⊥ (Ξbi ).

c1 ), · · · , Ar ⊥ (Ξ
cr ), qua labelled diThe arena SucArhAi is a disjoint union of Ar(A), Ar ⊥ (Ξ
rected graphs. Notice that SucArhM i depends only on the list of types (viz. A, Ξ1 , · · · , Ξr )
that occur in hM i, and not on the size of M ; furthermore, in case M is β-normal, SucArhM i =
Ar(A).
13

Normalisation by Traversals

C.-H. Luke Ong

Next we define a function ℓ̂ : |ExpAr hM i| → |SucArhM i| where
|SucArhM i| := { ǫ } × |Ar(A)| ∪

r
[

i=1

{ γi } × |Ar ⊥ (Ξbi )|

is a (convenient) representation of the underlying set of the arena SucArhM i. To aid the
definition of ℓ̂, we use a predicate S ⊆ T ×Λ(@)×|SucArhM i|. The idea is that (α, s, γ, β) ∈ S
means: (i) α ∈ T and ℓ(α) = s, and (ii) α is hereditarily enabled by γ in the arena ExpAr hM i
where γ ∈ { ǫ, γ1 , · · · , γr }, and (iii) α is mapped by ℓ̂ to (γ, β).
The predicate S is defined by induction over the following rules:
• (ǫ, ℓ(ǫ), ǫ, ǫ) ∈ S; for all i ∈ [r], (γi , ℓ(γi ), γi , ǫ) ∈ S.
• If (α, x(B1 ,··· ,B,o) , γ, β) ∈ S then for all i ∈ [m], (α · i, ℓ(α · i), γ, β · i) ∈ S.
b

• If (γ, @C , γ, ǫ) ∈ S where C = (C1 , · · · , Cl , o) then for all i ∈ [l + 1], (γ · i, ℓ(γ · i), γ, i) ∈ S.
Bm
′
−1
1
• If (α, λxB
(α)
1 · · · xm , γ, β) ∈ S then: for all α ∈ B
′
′
i
– if ℓ(α′ ) = xB
i for some i ∈ [m] then (α , ℓ(α ), γ, β · i) ∈ S
′
– if ℓ(α ) 6∈ { x1 , · · · , xm } then (by (Lam)) α = ǫ and ℓ(α′ ) = zkAk ∈ FV(M ) for some
k ∈ [i], and we have (α′ , ℓ(α′ ), ǫ, k) ∈ S

Then, by a straightforward induction over the length of α, we have: for all α ∈ T , there exist
unique γ and β such that (α, ℓ(α), γ, β) ∈ S.
Definition 3.9 (Succinct Long Form). We organise |SucArhM i| into a λ-alphabet as follows:
|SucArhM i|λ := { (ǫ, α) | α ∈ |Ar (A)|, |α| even } ∪
r
[
{ (γi , α) | α ∈ |Ar ⊥ (Ξbi )|, |α| odd }
i=1

|SucArhM i|Var := { (ǫ, α) | α ∈ |Ar (A)|, |α| odd } ∪
r
[
{ (γi , α) | α ∈ |Ar ⊥ (Ξbi )|, |α| > 0, |α| even }
i=1

|SucArhM i|aux := { (γ1 , ǫ), · · · , (γr , ǫ) }

The succinct long form of a term M is the |SucArhM i|-labelled binding tree, (T, B, ℓ̂), where
ℓ̂ : T → |SucArhM i| is given by ℓ̂(α) = (γ, β) just if (α, ℓ(α), γ, β) ∈ S.
Lemma 3.10. For every term M , the function ℓ̂ : |ExpArhM i| → |SucArhM i| gives a direct
arena morphism from ExpAr hM i to SucArhM i. In general ℓ̂ is neither injective nor surjective.
Proof. It follows from the definition that ⋆ ⊢ExpAr hMi α ⇐⇒ ⋆ ⊢SucAr hMi ℓ̂(α).
To verify α ⊢ExpAr hMi α′ ⇐⇒ ℓ̂(α) ⊢SucAr hMi ℓ̂(α′ ), we analyse the cases of ℓ(α). To
illustrate, consider the case of ℓ(α) = λx1 · · · xm . Take α′ ∈ B −1 (α). If ℓ(α′ ) = xi for some
i ∈ [m] then α ⊢ExpAr hMi α′ . Suppose ℓ̂(α) = (γ, β), say. Then ℓ̂(α′ ) = (γ, β · i), and we have
ℓ̂(α) ⊢SucAr hMi ℓ̂(α′ ) as desired. If for some k ∈ [i], ℓ(α′ ) = zk 6∈ { x1 , · · · , xm }, then α = ǫ,
and α ⊢ExpAr hMi α′ . Now ℓ̂(α) = (ǫ, ǫ) and ℓ̂(α′ ) = (ǫ, k), and we have ℓ̂(α) ⊢SucAr hMi ℓ̂(α′ ) as
desired.
Finally, to show λSucAr hMi (ℓ̂(α)) = λExpAr hMi (α), notice that λExpAr hMi (α) = O ⇐⇒ |α|
even. Let ℓ̂(α) = (γ, β) and suppose |α| is even. It is straightforward to see that if γ = ǫ then
14

Normalisation by Traversals

C.-H. Luke Ong

|α| ≡ |β| mod 2, and so λAr (A) (β) = O = λSucAr hMi (ℓ̂(α)). And if γ = γi for some i ∈ [r] then
|α| ≡ |β| + 1 mod 2, and so λAr ⊥ (Ξ
ci ) (β) = O = λSucAr hMi (ℓ̂(α)). The other case (i.e. |α| is
odd) is symmetric.

Take a term-in-context ⊢ M : A. The direct arena morphism ℓ̂ : ExpAr hM i → SucArhM i
is closely related to the game semantics of M , [[ ⊢ M ]], an innocent strategy over the arena [[ A ]].
The function ℓ̂ maps nodes of the tree |ExpArhM i| to moves of the arena [[ A ]]. We illustrate
this map in the following example.
Example 3.11. Take ⊢ M : A where M = λx.x (λy.y) (λz.x (λy ′ .y ′ ) (λz ′ .z ′ )) and A =
(((o, o), (o, o), o), o). Since M is β-normal, we have SucArhM i = Ar (A). In the following,
we display the direct arena morphism ℓ̂ : |ExpAr hM i| → |SucArhM i| by annotating ℓ̂(α) next
to the node α, separated by :.
λx : ǫ
x : 1▲
▲▲▲
rr
r
▲▲▲
r
r
r
r
λy : 11
λz : 12
y : 111

x : 1❑
❑❑❑
ss
s
❑❑❑
s
s
s
s

λy ′ : 11

λz ′ : 12

z : 121

z ′ : 121

Remark 3.12 (Every path in the long form is a P-view). Take a long form hM i = (T, B, ℓ).
Every path α1 · α2 · · · · · αn in the tree T is the underlying sequence of a (unique) P-view p
over the arena ExpAr hM i, whose pointers are defined as follows. Suppose i ≥ 3 is odd; then
the O-move αi (where ℓ(αi ) is necessarily a lambda) is justified by αi−1 ; note that we have
αi−1 ⊢ExpAr hMi αi . Suppose i is even; if ℓ(αi ) is a variable, then the P-move αi is justified by
B(αi ) – note that B(αi ) < αi ; otherwise, ℓ(αi ) = @, and αi is initial in ExpAr hM i. Since ℓ̂ is
a direct arena morphism, ℓ̂(p) is a P-view over the arena SucArhM i.
Example 3.13. Consider hKi = λf.f (λx.f (λy.f (λz.λ.x))) : (((o, o), o), o). Qua Λ(@)-labelled
binding tree (T, B, ℓ), the tree T consists of all prefixes of 17 = 1 · 1 · 1 · 1 · 1 · 1 · 1 and
B : 1 7→ ǫ, 13 7→ ǫ, 15 7→ ǫ, 17 7→ 12 . Take the P-view p whose underlying sequence of moves is
the maximal path of the tree T . (In the following, pointers from O-moves are not displayed.)
The P-view p over the explicit arena ExpAr hKi is

p = ǫ · 1 · 12 · 13 · 14 · 15 · 16 · 17

(5)
15

Normalisation by Traversals

C.-H. Luke Ong

The “justified sequence” of the Λ(@)-labels traced out by p, ℓ∗ (p), is

ℓ∗ (p) = λf · f · λx · f · λy · f · λz · x

(6)

The P-view, ℓ̂∗ (p), over the succinct arena SucArhM i = Ar (((o, o), o), o) is

ℓ̂∗ (p) = ǫ · 1 · 12 · 1 · 12 · 1 · 12 · 13

(7)

The P-view, ℓ̂∗ (p), over a Λ-representation of SucArhM i is

ℓ̂∗ (p) = λf · f · λx · f · λx · f · λx · x

(8)

Note that the set of elements that occur in p (respectively ℓ∗ (p) and ℓ̂∗ (p)) has size 8 (respectively
6 and 4).

3.3

Traversals over a long form

Henceforth we write a long form qua Λ(@)-labelled binding tree as hM i = (TM , BM , ℓM ).
Definition 3.14 (Traversals). Traversals over a long form hM i are justified sequences over the
arena ExpArhM i defined by induction over the rules in Table 1. We write TravhM i for the set
of traversals over hM i. It is convenient to refer to elements α ∈ |ExpAr hM i| = TM by their
labels ℓM (α). We shall do so in the following whenever what we mean is clear from the context.
Remark 3.15.
(i) The rule (App) says that if a traversal ends in a @-labelled node n, then
the traversal extended with the first (left-most) child of n is a traversal.
(ii) The rule (Lam) says that if a traversal t ends in a λ-labelled node n, then t extended
with the child node of n, n′ , is also a traversal. To illustrate how the pointer of n′ in t · n′ is
determined, first note that every path in the (abstract syntax tree of the) long form hM i is a
justified sequence which is a P-view (Remark 3.12). Take, for example, traversal (1) truncated
at the 15-th move—call it t · λ. By (Lam), t · λ · y is a traversal, where y is the child node of λ.
Notice that there are two occurrences of λf y (5th and 9th move respectively) in t to which y
2

1

2

could potentially point. However, in pt · λ · yq = λ @ λf y f λ g λ y , which is a path in
the long form hN P Ri, y is bound by the 3rd move. Since it is the 5th move of t · λ · y which is
mapped by p-q to the 3rd move of pt · λ · yq, (Lam) says that y in t · λ · y points to the 5th-move.
(iii) If a traversal ends in a node labelled with a variable ξi , then there are two cases,
corresponding to whether ξi is hereditarily justified by a bound (BVar) or free (FVar) variable in
i+1

the long form hM i. Observe that some pointers in (BVar) are labelled; for example, n · · · λη
means that the node λη is the (i + 1)-th child of n. Intuitively, the rules (BVar) capture the
switching of control between caller and callee, or between formal and actual parameters. Thus,
16

Normalisation by Traversals

C.-H. Luke Ong

in rule (BVar).2, ξi is the i-th formal parameter, and λη—the i-th child of n—the (root of
the) i-th actual parameter. Note, however, that in rule (Bvar).1, although λη is the (i + 1)-th
child, it is actually the i-th actual parameter because the 1st-child of @ is not the 1st actual
parameter, but rather the body of the function call itself.
(iv) The rule (FVar) is the only rule that permits traversals to branch, and grow in different
directions.

(Root ) ǫ ∈ TravhM i.
1

(App) If t · @ ∈ TravhM i then t · @ · λξ ∈ TravhM i.
(BVar ) If t · n · λξ · · · ξi ∈ TravhM i where ξ = ξ1 · · · ξn and ξi is hereditarily
justified by an @ then
i+1

1. if n is (labelled by) @ then t · n · λξ · · · ξi · λη ∈ TravhM i
i

2. if n is (labelled by) a variable then t · n · λξ · · · ξi · λη ∈ TravhM i.
(FVar ) If t · ξ ∈ TravhM i and the variable ξ is not hereditarily justified by an @
j

(equivalently, ξ is hereditarily justified by the opening node ǫ) then t · ξ · λη ∈
TravhM i, for every 1 ≤ j ≤ ar (ξ).
(Lam) If t · λξ ∈ TravhM i and let n be the (unique) child node of λξ in TM , then
t · λξ · n ∈ TravhM i. By a straightforward induction, pt · λξ · nq is a (justified)
path in the tree TM . If n is labelled by a variable (as opposed to @) then its
pointer in t · λξ · n is determined by the justified sequence pt · λξ · nq which is
guaranteed to be a path in TM . Precisely if in the P-view pt · λξ · nq, n points to
the i-th move, then n in t · λξ · n points to the j-th move, where the j-th move is
the necessarily unique move-occurrence that is mapped to the i-th move under
the P-view transformation: p-q : t · λξ · n 7→ pt · λξ · nq.
Table 1: Rules that define traversals over a long form

Example 3.16. There are three maximal traversals over the long form defined in Example 3.2
17

Normalisation by Traversals

C.-H. Luke Ong

(Figure 4) as follows:
1

λz1 · ϕ · λxz · x · λ · z
2

λz1 · ϕ · λ · @ · λy · y · λ · a
3

λz1 · ϕ · λ · z1
Lemma 3.17. Let t be a traversal over hM i = (TM , BM , ℓM ). Then t is a well-defined justified
sequence over ExpAr hM i. Further
1. The sequence underlying ptq is a path in the tree TM , and the P-view determined by this
path (Remark 3.12) is exactly ptq.
2. If t is maximal then the last node of t is labelled by a variable of ground type.
3. If M is β-normal then t is a P-view over ExpAr hM i (i.e. t = ptq).
Proof. (1) and (2) can be proved by a straightforward induction on the length of t; for (2), we
appeal to the labelling axioms of Lemma 3.6. For (3), since hM i does not have any @-labelled
nodes, the traversal t is constructed using only the rules (Root), (FVar) and (Lam). Thus t is
a path, which, thanks to Remark 3.12, determines a P-view.
Let t ∈ TravhM i and Θ ⊆ |ExpAr hM i|, define t ↾ Θ to be the (justified) subsequence of
t consisting of nodes that are hereditarily justified by some occurrence of an element of Θ
in t. If Θ is a set of initial moves, then TravhM i ↾ Θ := { t ↾ Θ | t ∈ TravhM i } is a welldefined set of justified sequences over ExpAr hM i (see e.g. [McCusker, 2000, Lemma 2.6]). Let
α ∈ |ExpArhM i|, we write TravhM i ↾ (α, Θ) to mean TravhM i ↾ ({ α } ∪ Θ).
The rest of the section is about the following theorem and its proof. Given a term-incontext Γ ⊢ M : A where Γ = x1 : C1 , · · · , xn : Cn , recall that ℓ̂ : ExpAr hM i → SucArhM i
is a direct arena morphism, and p[[ Γ ⊢ M : A ]]q is a set of justified sequences over the arena
[[ C1 → · · · → Cn → A ]] and hence over the succinct arena SucArhM i (the former is a subarena
of the latter).
Theorem 3.18 (Strong Bijection). Let Γ ⊢ M : A be a term-in-context, with long form hM i =
∼
(T, B, ℓ). The extension ℓ̂∗ : TravhM i ↾ ǫ −→ p[[ Γ ⊢ M : A ]]q induced by the direct arena
morphism ℓ̂ is a strong bijection.
In general ℓ̂ is neither injective nor surjective; nevertheless ℓ̂∗ defines a bijection from
TravhM i ↾ ǫ to p[[ Γ ⊢ M : A ]]q, which is strong, in the sense that for each t ∈ TravhM i ↾ ǫ,
the two justified sequences t and ℓ̂∗ (t) are isomorphic.
Example 3.19. To illustrate Theorem 3.18, consider the term-in-context of Example 3.2,
Γ ⊢ M : (o, o), where Γ = { ϕ : (((o, o), o, o), o, o, o), a : o } and
hM i = λz1o .ϕ (λx(o,o) z o .x (λ.z)) (λ.@ (λy o .y) (λ.a)) (λ.z1 )
The interpretaton, [[ Γ ⊢ M : (o, o) ]], is an innocent strategy over the arena Ar(B) where B =
18

Normalisation by Traversals

C.-H. Luke Ong

((((o, o), o, o), o, o, o), o, o, o). Take a Λ-representation of Ar (B) as follows:
((((o,

λ1111

o),

o,

o),

o,

o,

o),

o,

o,

o)

❤ λϕaz1
❤❧❤❧❤❧❤❧✉❧✉✉
❤
❤
❤
❤❤❤❤ ❧❧❧ ✉
z1
❣❧ ϕ ❤ a
❣
❣
❧
❣
❧
❣
②
❣❧❣❧❣❧❧❧②②②
❣
❣
❣
❣
❣❣❣ 12 ❧❧ 13
λ
λ
λxz
❧
❧
①
❧❧❧①①①
❧
❧
❧ z
tx
t
t
t

Note that when restricted to TravhM i ↾ ǫ, the image of ℓ̂∗ consists of justified sequences over
Ar(B), a subarena of SucArhM i. Thus maximal justified sequences in ℓ̂(TravhM i ↾ ǫ) are as
follows (omitting the pointers)
λϕaz1 · ϕ · λxz · x · λ1111 · z
λϕaz1 · ϕ · λ12 · a
λϕaz1 · ϕ · λ13 · z1
coninciding with the maximal P-views in the strategy denotation [[ Γ ⊢ M : (o, o) ]].

3.4

Proof of the strong bijection theorem

We first state and prove a useful lemma. Let t be a traversal over the long form
hM i = λ.@ (λξ.P ) (λη1 .Q1 ) · · · (ληn .Qn ) : o
Let θ1 , · · · , θl be a list of all the occurrences of the nodes, λξ, λη1 , · · · , ληn , in t. Then, except
for the first two nodes (i.e. λ and @) of the traversal t, every node occurrence m in t belongs
to one of the components, Comp θ1 (t), · · · , Comp θl (t), defined as follows:
• If m is hereditarily justified by θi then m belongs to Comp θi (t).
• If m is hereditarily justified by an internal @ (as opposed to the top-level @), or by the
root ǫ (i.e. by a free variable), let m′ be the last node occurrence in t which precedes m
and which is hereditarily justified by θi for some i, then m belongs to Comp θi (t).
Henceforth, by abuse of notation, by Comp θi (t) we mean the subsequence of t determined by
the set of node occurrences Comp θi (t).
Lemma 3.20 (Component Projection). Using the preceding notation, let t be a traversal over
the long form
hM i = λ.@ (λξ.P ) (λη1 .Q1 ) · · · (ληn .Qn ) : o
If the last node of t is a lambda node which belongs to Comp θ (t) then
(i) Comp θ (t) ∈ Travhθ.M i
(ii) ptq = λ · @ · pComp θ (t)q
where θ.M := λξ.P (respectively ληj .Qj ) in case θ is an occurrence of λξ (respectively ληj ).
19

Normalisation by Traversals

C.-H. Luke Ong

Proof.
(i) Let t be a traversal satisfying the premises of the lemma. It follows from the
rules of Definition 3.14 that t is a prefix of a justified sequence of the following shape:
t = λ · @ · · · θ · B1 · · · Bl

(9)

where θ is justified by @, and each Bi is a block of nodes of one of two types:
I. Two-node block ni · li where the non-lambda node ni and the lambda node li are hereditarily
justified by an @ that belongs to Comp θ (t).
II. ni m1 · · · mr li where the lambda node li is justified by ni , which belongs to Comp θ (t) and
is hereditarily justified by θ or by ǫ.
It follows that for each i, both ni and li are occurrences of nodes from the long form hθ.M i qua
subtree of hM i. Now define Bi′ to be ni · li for each i. Observe that Comp θ (t) = θ · B1′ · · · Bl′ .
It then follows that Comp θ (t) ∈ TravhΓ ⊢ θ.M i.
(ii) Immediate consequence of (9) and Comp θ (t) = θ · B1′ · · · Bl′ .
Lemma 3.21. Let Γ ⊢ M : A be in β-normal form with long form hM i = (T, B, ℓ). The
∼
extension ℓ̂∗ : TravhM i ↾ ǫ −→ p[[ Γ ⊢ M : A ]]q induced by ℓ̂ is a strong bijection.
Proof. Take the term-in-context Γ ⊢ M : o where Γ = x1 : A1 , · · · , xn : An , Ai = (B1 , · · · , Bm , o),
and M = xi (λy1 .P1 ) · · · (λym .Pm ). We prove by induction on the size of M . Observe that,
since M is β-normal, TravhM i ↾ ǫ = TravhM i. First we show that the map ℓ̂∗ is injective. Let
λ·xi ·t, λ·xi ·t′ ∈ TravhM i such that ℓ̂∗ (λ·xi ·t) = ℓ̂∗ (λ·xi ·t′ ), which implies that ℓ̂∗ (t) = ℓ̂∗ (t′ ),
∼
and t, t′ ∈ Travhλyj .Pj i for some j ∈ [m]. Since ℓ̂∗ : Travhλyj .Pj i −→ p[[ Γ ⊢ λyj .Pj : Bj ]]q is
injective, we have t = t′ and hence λ · xi · t = λ · xi · t′ as desired.
For surjectivity of ℓ̂∗ , take a P-view p ∈ p[[ Γ ⊢ M : o ]]q. Notice that p is a justified sequence
over Ar (A1 , · · · , An , o). Since the head variable of M is xi , we have p = ǫ · i · (p′ ↑ i) and
p′ ∈ p[[ Γ ⊢ λyj .Pj : Bj ]]q for some j ∈ [m]. (Given a sequence of nodes, p = α1 , · · · , αn ,
we write p ↑ i for the sequence i · α1 , · · · , i · αn .) By the induction hypothesis, there exists
t ∈ Travhλyj .Pj i such that ℓ̂∗ (t) = p′ . Thus we have λ · xi · t ∈ TravhM i, and ℓ̂∗ (λ · xi · t) = p
as desired.
Corollary 3.22 (Variable). Let hϕi = (T, B, ℓ) where ϕ is a variable. The extension ℓ̂∗ :
∼
Travhϕi ↾ ǫ −→ p[[ Γ ⊢ ϕ : A ]]q induced by ℓ̂ is a strong bijection.
Example 3.23. Consider the long form
hλχ.χi = λχΦϕ.χ (λψ.Φ (λy.ψ(λ.y))) (λx.ϕ (λ.x)).
Since there is no occurrence of @ in hλχ.χi, traversals over it coincide with paths from the root.
For example, the traversal λχΦϕ · χ · λψ · Φ · λy · ψ · λ · y (pointers are omitted) represents
a P-view in the copycat strategy [[ ⊢ λχ.χ : A → A ]]. This illustrates the strong bijection of
Lemma 3.22.
We recall the notion of interaction sequences and the associated notation from [Hyland and Ong,
2000]. Let σ : A −→ B and τ : B −→ C be innocent strategies, and let us write pσq for the
collection of P-views in σ. Given a justified sequence t over the triple (A, B, C) of arenas, let
20

Normalisation by Traversals

C.-H. Luke Ong

X range over the components (B, C) and (A, B)b where b ranges over the occurrences of initial
moves of B in t; set
(
σ if X = (A, B)b
ρX :=
τ if X = (B, C)
Similarly we define pρX q to mean pσq or pτ q depending on what X is. The set of interaction
sequences between σ and τ , IntSeq(σ, τ ), consists of justified sequences t over (A, B, C), which
are defined by induction over the rules (IS1), (IS2) and (IS3):
(IS1) c ∈ IntSeq(σ, τ ) where c ranges over the initial moves of C.
(IS2) If t · m ∈ IntSeq(σ, τ ), and m is a generalised O-move of the component X (i.e. either an
O-move of A ⇒ C or a move of B), and pt · m ↾ Xq·m′ ∈ ρX , then t·m·m′ ∈ IntSeq(σ, τ ).
(IS3) If t · m ∈ IntSeq(σ, τ ), and m is a P-move of A ⇒ C, and (t · m ↾ (A, C)) · m′ is a play
of A ⇒ C, then t · m · m′ ∈ IntSeq(σ, τ ).
Definition 3.24. The set of P-visible interaction sequences between σ and τ , IntSeqPV (σ, τ )
, consists of justified sequences over (A, B, C), defined by induction over the rules (IS1), (IS2),
and (IS4) as follows:
(IS4) If t · m ∈ IntSeqPV (σ, τ ), and m is a P-move of A ⇒ C, and m′ is an O-move justified
by m, then t · m · m′ ∈ IntSeqPV (σ, τ ).
It is straightforward to see that IntSeqPV (σ, τ ) ↾ (A, C) = pσ; τ q. Note that the definition
would still make sense if σ and τ in (IS1), (IS2) and (IS4) are replaced by pσq and pτ q respectively, and ρX replaced by pρX q. In other words IntSeqPV (pσq, pτ q) is well-defined, and
coincides with IntSeqPV (σ, τ ). Thus we have IntSeqPV (pσq, pτ q) ↾ (A, C) = pσ; τ q.
Lemma 3.25. (i) Let Γ ⊢ M : A be a term-in-context with long form hM i = (T, B, ℓ). There
∼
is a ℓ̂-induced strong bijection ℓ̂∗ : TravhM i ↾ ǫ −→ p[[ Γ ⊢ M : A ]]q.
(ii) Suppose Γ ⊢ hM i = λ.@ (λξ.P ) (λη1 .Q1 ) · · · (ληn .Qn ) : o, and hM i = (T, B, ℓ). There is
a ℓ̂-induced bijection.
∼

ℓ̂∗ : TravhM i ↾ (ǫ, Θ) −→ IntSeqPV (h p, q1 , · · · , qn i, pev q)

(10)

Qn
where Θ := { α ∈ T | ∃i . α = 1·i }, p = p[[ Γ ⊢ λξ.P : ( i=1 Bi ) ⇒ o ]]q, qi = p[[ Γ ⊢ ληi .Qi : Bi ]]q
Qn
Qn
ev //
o is the obvious copycat strategy.
Bi
Bi ) ⇒ o) ×
for each i, and ((
i=1

i=1

Remark 3.26. In (ii), since ℓ(1) = @, each t ∈ TravhM i ↾ (ǫ, Θ) is a subsequence of a traversal
over hM i consisting of nodes that are hereditarily justified by ǫ, or by an occurrence of one
of λξ, λη1 , · · · , ληn (each being a child of node 1 in the tree hM i). The bijection ℓ̂ in (ii)
would be strong if for each t ∈ TravhM i ↾ (ǫ, Θ), pointers were added from every occurrence of
λξ, λη1 , · · · , ληn to the opening node ǫ.
Proof. We shall prove (i) and (ii) by mutual induction.
(i) The term M has one of the following shapes:
(a) abstraction λξ.P
(b) variable ϕ
(c) application N L1 · · · Ln where n ≥ 1 and N has shape (a) or (b).
21

Normalisation by Traversals

C.-H. Luke Ong

First we reduce case (a) to case (b) or case (c). Let A = (A1 , · · · , An , o) and the η-long
normal form of λξ.P be λx1 · · · xn .R where R is a term of either case (b) or (c). Plainly
Travhλξ.P i = Travhλx.Ri. It remains to observe that, on the one hand, there is a strong
bijection between Travhλx.Ri and TravhRi (note that pointers from node occurrences labelled
with free variables are to the opening node); and on the other, there is a strong bijection
between p[[ Γ ⊢ λx.R : A ]]q and p[[ Γ, x : A ⊢ R : o ]]q.
Case (b) is just Corollary 3.22.
As for case (c), suppose N is an abstraction. W.l.o.g. assume
hM i = λ.@ (λξ.P ) (λη1 .Q1 ) · · · (ληn .Qn ) : o.
Then, by (ii) and using the notation therein, we have a bijection
∼

ℓ̂ : TravhM i ↾ (ǫ, Θ) −→ IntSeqPV (h p, q1 , · · · , qn i, pev q)

(11)

Observe that applying (−) ↾ ǫ on the LHS of (11) corresponds to applying (−) ↾ ([[ Γ ]], o) on the
RHS. Thus, in view of Remark 3.26, TravhM i ↾ (ǫ, Θ) ↾ ǫ = TravhM i ↾ ǫ is in strong bijection
with IntSeqPV (h p, q1 , · · · , qn i, pev q) ↾ ([[ Γ ]], o) = p[[ Γ ⊢ M : o ]]q, as desired.
Finally suppose N is a variable ϕ. W.l.o.g. assume M = ϕ(λη1 .Q1 ) · · · (ληm .Qm ) : o. Then it
follows from the respective definitions that
[
TravhM i = { λ · ϕ · t | t ∈ TravhΓ ⊢ ληi .Qi i } ∪ { ǫ, λ }
i

[
p[[ Γ ⊢ M ]]q = { ℓ̂(λ) · ℓ̂(ϕ) · t | t ∈ p[[ Γ ⊢ ληi .Qi ]]q } ∪ { ǫ, ℓ̂(λ) }
i

It follows from the induction hypothesis that there is a strong bijection
∼

ℓ̂ : TravhM i ↾ ǫ −→ p[[ Γ ⊢ M : o ]]q.
(ii) We first show that for every t ∈ TravhM i, we have ℓ̂(t ↾ (ǫ, Θ)) ∈ IntSeqPV (h p, q1 , · · · , qn i, pev q).
The proof is by induction on the length of t, with case distinction on the last node of t, using
the notation of Lemma 3.20.
Case 1. The last node of t is in the component Comp θ (t) where θ is the unique occurrence of
λξ in t. Let m be the last lambda node in t that is hereditarily justified by ǫ or θ. There are
two subcases.
Case 1.1. The traversal t = · · · m · d1 d2 · · · dl where l ≥ 0 and each di is a Type-I node (i.e. not
hereditarily justified by ǫ or θ), as defined in the proof of Lemma 3.20. Let m′ be a TypeII node (i.e. hereditarily justified by ǫ or θ) such that t · dl+1 · · · dl′ · m′ ∈ TravhM i where
l′ ≥ l and each dj is Type I. Writing t′ = t · dn+1 · · · dn′ , we claim that ℓ̂((t′ · m′ ) ↾ (ǫ, Θ)) =
ℓ̂(t′ ↾ (ǫ, Θ)) · ℓ̂(m′ ) ∈ IntSeqPV (h p, q i, pev q) by rule (IS2)-σ. By assumption ℓ̂(m′ ), which
is a P-move, belongs to the component
([[ Γ ]], (

n
Y

i=1

Bi ⇒ o) ×

n
Y

i=1

Bi )o = ([[ Γ ]],

n
Y

Bi ⇒ o)o

i=1

Qn
h p,q i Qn
ev
in the sense of the strategy composition [[ Γ ]] −−−→ ( i=1 Bi ⇒ o) × i=1 Bi −→ o. Observe
that
22

Normalisation by Traversals

C.-H. Luke Ong

Qn
(A) ℓ̂(t′ ↾ (ǫ, Θ)) ↾ ([[ Γ ]], i=1 Bi ⇒ o)o = ℓ̂(t′ ↾ (ǫ, Θ) ↾ θ),
(B) t′ ↾ (ǫ, Θ) ↾ θ = t′ ↾ θ = Comp θ (t′ ) ↾ θ, because all node occurrences in t′ hereditarily
justified by θ are in Comp θ (t′ ).
Thus we have
Qn
pℓ̂(t′ ↾ (ǫ, Θ)) ↾ ([[ Γ ]], i=1 Bi ⇒ o)q · ℓ̂(m′ )
=
(A)
′
′
pℓ̂(t ↾ (ǫ, Θ) ↾ θ)q · ℓ̂(m )
=
(B)
′
′
pℓ̂(Comp θ (t ) ↾ θ)q · ℓ̂(m )
=
m′ is a non-lambda node
′
′
pℓ̂(Comp θ (t · m ) ↾ θ)q
∈
Lemma 3.20(i) & I.H.(i)
p[[ Γ ⊢ λξ.P ]]q
as desired.
Case 1.2. The traversal t = · · · m · d1 · · · dl · m′ where l ≥ 0 and each di is of Type I (i.e. not
hereditarily justified by ǫ or θ), and m′ is a non-lambda node.
There are two subcases.
Case 1.2.1. The non-lambda node m′ is hereditarily justified by ǫ.
By rule (FVar) of the definition of traversal, for each lambda node m′′ that is justified by
m′ , we have t·m′′ ∈ TravhM i. We claim that ℓ̂(t · m′′ ↾ (ǫ, Θ)) ∈ IntSeqPV (h p, q i, pev q).
By the induction hypothesis, t ↾ (ǫ, Θ) = (t≤dl ↾ (ǫ, Θ))·m′ is mapped by ℓ̂ into IntSeqPV (h p, q i, pev q).
Since ℓ̂(m′ ) is an P-move of the arena [[ Γ ]] ⇒ o, it follows from rule (IS4) of the definition
of P-visible interaction sequence that ℓ̂(t≤dl ↾ (ǫ, Θ) · m′ ) · ℓ̂(m′′ ) = ℓ̂(t · m′′ ↾ (ǫ, Θ)) ∈
IntSeqPV (h p, q i, pev q) as required.
Case 1.2.2. The non-lambda node m′ is hereditarily justified by θ.
Suppose t = · · · m′′ · m′ · · · m · d · m′ such that m′ is explicitly i-justified by the lambda
node m′ . By rule (BVar) of the definition of traversal, m′′ is a non-lambda node in
Comp θ′ (t) where θ′ is an occurrence of some ληj in t, and t · m′′ ∈ TravhM i where m′′
is i-justified by m′′ . We claim that t · m′′ ↾ (ǫ, Θ) = (t ↾ (ǫ, Θ)) · m′′ is mapped by ℓ̂ into
t = t ↾ (ǫ, Θ), by the induction hypothesis, we have
IntSeqPV (h p, q i, pev q). Writing e
PV
e
ℓ̂(t) ∈ IntSeq (h p, q i, pev q). By rule (IS2)-τ of the definition of interaction sequence,
Qn
Qn
e
it suffices
t) ↾ (( i=1 Bi ⇒ o) × i=1 Bi , o)q · ℓ̂(m′′ ) ∈ pev q. Since projecting
Qn to show pℓ̂(Q
n
to (( i=1 Bi ⇒ o) × i=1 Bi , o) reverses the P/O polarity of moves, we have
i

pℓ̂(e
t) ↾ ((

n
Y

i=1

Bi ⇒ o) ×

n
Y

i

Bi , o)q · ℓ̂(m′′ ) = · · · · ℓ̂(m′′ ) · ℓ̂(m′ ) · ℓ̂(m′ ) · ℓ̂(m′′ )

i=1

which is in pevq as required.
It remains to show that for every u ∈ IntSeqPV (h p, q i, pev q), there exists a unique tu ∈
TravhM i such that ℓ̂(tu ↾ (ǫ, Θ)) = u.
We argue by induction on the length of u. The base case of (IS1) is trivial. For the inductive
case, suppose u · n ∈ IntSeqPV (h p, q i, pev q). With reference to Definition 3.24, there are
three cases, namely, (IS2)-σ, (IS2)-τ and (IS4), which correspond to the preceding cases of
23

Normalisation by Traversals

C.-H. Luke Ong

1.1, 1.2.2 and 1.2.1 respectively. Here we consider the case of (IS2)-σ forQillustration; the
other cases are similar and simpler. I.e. by assumption, we have pu ↾ ([[ Γ ]], ni=1 Bi ⇒ o)o q ·
n ∈ p[[ Γ ⊢ λξ.P ]]q where n is a P-move of [[ Γ ⊢ λξ.P ]]. By the induction hypothesis, there
exists a unique maximal tu ∈ TravhM i such that ℓ̂(tu ↾ (ǫ, Θ)) = u. Since ℓ̂(Comp θ (tu ) ↾ θ) =
Qn
ℓ̂(tu ↾ (ǫ, Θ)) ↾ ([[ Γ ]], i=1 Bi ⇒ o)o (which is (B) of Case 1.1), we have pℓ̂(Comp θ (tu ) ↾ θ)q ·
ℓ̂(m′ ) ∈ p[[ Γ ⊢ λξ.P ]]q where n = ℓ̂(m′ ) for some m′ . Thanks to the strong bijection of (i),
we have pComp θ (tu ) ↾ θ · m′ q ∈ Travhλξ.P i ↾ ǫ for a unique m′ . Then, because Comp θ (tu ) ∈
Travhλξ.P i by Lemma 3.20(i) and because the last node of tu is a lambda node, we have
Comp θ (tu ) · m′ ∈ Travhλξ.P i. By rule (Lam) of the definition of traversals, we have the
pComp θ (tu )q · m′ is a path in the tree hλξ.P i. It follows that λ · @ · pComp θ (tu ) · m′ q is a path
in the tree hM i. But, by Lemma 3.20(ii), ptu q · m′ = λ · @ · pComp θ (tu )q · m′ . Hence, by rule
(Lam), tu · m′ ∈ TravhM i with ℓ̂(tu · m′ ↾ (ǫ, Θ)) = u · n as desired.
Case 2. The last node of t belongs to Comp θ′ (t) where θ′ is an occurrence of ληi in t. This
case is symmetrical to Case 1.

4

Application

4.1

Interpreting higher-order recursion schemes

We assume the standard notion of higher-order recursion scheme [Knapik et al., 2002; Ong,
2006]. Fix a (possibly infinite) higher-order recursion scheme G = (Σ, N , R, F1 ) over a ranked
alphabet Σ = { a1 : r1 , . . . , al : rl } where ri is the arity of the terminal ai ; with non-terminals
N = { Fi : Ai | i ∈ I } and rules Fi → λxi .Mi for each i ∈ I, and F1 : o is the start symbol.
Note that we do not assume I to be finite. Henceforth we assume I = ω for convenience, and
regard Σ as a set of free variables.
Q
Q
We first give the semantics of G. Writing [[ Σ ]] := li=1 [[ ori → o ]] and [[ N ]] := i∈ω [[ Ai ]],
the semantics of G, [[ Σ ⊢ F1 : o ]] : [[ Σ ]] −→ [[ o ]], is the composite
Λ(g)

Y[[ N ]]

π

1
[[ o ]]
[[ Σ ]] −−−→ ([[ N ]] ⇒ [[ N ]]) −−−−
→ [[ N ]] −→

in the category I of arenas and innocent strategies, where
• g : [[ Σ ]] × [[ N ]] −→ [[ N ]] is [[ Σ, N ⊢ (λx1 .M1 , · · · , λxm .Mm , · · ·) :
currying

Q

i∈ω

Ai ]], and Λ(-) is

• YA : (A ⇒ A) → A is the fixpoint strategy (see [Hyland and Ong, 2000, §7.2]) over an
arena A
• π1 is the projection map.
Remark 4.1. Since p[[ Σ ⊢ F1 : o ]]q coincide with the branch language3 of the Σ-labelled tree
generated by G, we can identify p[[ Σ ⊢ F1 : o ]]q with [[ G ]], the tree generated by G.

3 Let m be the maximum arity of the Σ-symbols, and write [m] := { 1, · · · , m }. The branch language of
t : dom(t) −→ Σ consists of (i) infinite words (f1 , d1 )(f2 , d2 ) · · · such that there exists d1 d2 · · · ∈ [m]ω such
that t(d1 · · · di ) = fi+1 for every i ∈ ω and (ii) finite words (f1 , d1 ) · · · (fn , dn ) fn+1 such that there exists
d1 · · · dn ∈ [m]⋆ such that t(d1 · · · di ) = fi+1 for 0 ≤ i ≤ n, and the arity of fn+1 is 0.

24

Normalisation by Traversals

4.2

C.-H. Luke Ong

The traversal-path correspondence theorem

Fix a higher-order infinite recursion scheme G = (Σ, N , R, F1 ), using the same notation as
Q
before. Define an ω-indexed family of λ-terms, Ghni : i∈ω Ai with n ranging over ω, as
follows:
Gh0i := (λx1 .⊥o , · · · , λxm .⊥o , · · ·)
Ghn+1i := (λx1 .M1 [Ghni /F ], · · · , λxm .Mm [Ghni /F ], · · ·)
where ⊥A is a constant symbol of type A, and (-)[Ghni /F ] means the simultaneous substitution
(-)[π1 Ghni /F1 , · · · , πm Ghni /Fm , · · ·], and πi (s1 , s2 , · · · ) is a short hand for si . Write Ghni :=
π1 Ghni for each n ∈ ω. Note that each Ghni is a (recursion-free) λ-term of type o.
F
Lemma 4.2. [[ Σ ⊢ F1 : o ]] = n∈ω [[ Σ ⊢ Ghni : o ]].

Proof. Because A is a CCC that is enriched over the CPOs, for each type A, there is a fixpoint
strategy YA : (A ⇒ A) ⇒ A which is the least (with respect to the enriching order, namely, set
inclusion) fixpoint of the map (A ⇒ A) ⇒ A −→ (A ⇒ A) ⇒ A that is the denotation of the
λ-term
λF : (A ⇒ A) ⇒ A.λf : A ⇒ A.f (F f )
hii

Define the following family of λ-terms, YA : (A ⇒ A) ⇒ A with i ∈ ω
h0i
YA
hn+1i
YA

:= λf : A ⇒ A.⊥A
hni
:= λf : A ⇒ A.f (YA f )

Q
hni
Note that Ghni = YN (λx1 .M1 , · · · , λxm .Mm , · · ·) : N , writing N = i∈ω Ai by abuse of notation. By interpreting ⊥A as the least element of the homset AΣ (1, A), we have [[ Σ ⊢ Ghni : o ]] =
F
hni
hni
Λ(g); [[ YN ]]; π1 . By Knaster-Tarski Fixpoint Theorem, YA = n∈ω [[ YA ]]. Since comF
hni
position is continuous, we have [[ Σ ⊢ F1 : o ]] = Λ(g); Y[[ N ]] ; π1 = Λ(g); n∈ω [[ YN ]]; π1 =
F
F
hni
hni
: o ]] as desired.
n∈ω [[ Σ ⊢ G
n∈ω (Λ(g); [[ YN ]]; π1 ) =
F
Lemma 4.3 (P-view Decomposition). (i) For every (possibly infinite) P-view p = i∈ω pi ∈
[[ Σ ⊢ F1 : o ]] where each pi is a finite P-view such that p0 ≤ p1 ≤ p2 ≤ · · · , there is
an increasing sequence of natural numbers n0 < n1 < n2 < · · · such that each pi ∈
[[ Σ ⊢ Ghni i : o ]].
(ii) For every ω-indexed family of finite P-views, pi ∈ [[ Σ ⊢ Ghni i : o ]] with i ∈ ω, such that
p0 ≤ p1 ≤ p2 ≤ · · · and an
F infinite sequence of natural numbers n0 < n1 < n2 < · · · , the
(possibly infinite) P-view i∈ω pi ∈ [[ Σ ⊢ F1 : o ]].

Proof. (i) Thanks to Lemma 4.2, for every i, there exists ni ≥ 1 such that pi ∈ [[ Σ ⊢ Ghni i : o ]].
(ii) An immediate consequence of Lemma 4.2.

Given a higher-order recursion scheme G, the computation tree λ(G) is obtained by first
transforming the rewrite rules into long forms, and then unfolding the transformed rules ad
infinitum, starting from F1 , and without performing any β-reduction (i.e. substitution of actual
parameters for formal parameters); see [Ong, 2006] for a definition. By construction, the tree
λ(G) is a (possibly infinite) Λ(@)-labelled binding tree that satisfies the labelling axioms (Lam),
(Leaf), (TVar) and (T@). We write TravhGi be the set of finite and infinite traversals over λ(G),
25

Normalisation by Traversals

C.-H. Luke Ong

whereby an infinite traversal is just an infinite justified sequence over λ(G) such that every finite
prefix is a traversal.
Next we prove a similar decomposition lemma for traversals. First, notice that each hGhii i
is a Λ(@)⊥ -labelled binding tree, where Λ(@)⊥ is Λ(@) augmented by an auxiliary symbol ⊥
of arity 0. Given Λ(@)⊥ -labelled trees T and T ′ , we define T ⊑ T ′ if dom(T ) ⊆ dom(T ′ ), and
for all α ∈ dom(T ), if T (α) 6= ⊥ then T (α) = T ′ (α). Thus if i < j then hGhii i ⊑ hGhji i and
hGhii i ⊑ hGi. It follows that if t is a ⊥-free traversal over hGhii i then t is also a traversal over
hGhji i and over hGi. Conversely if t is a finite traversal over hGi, then for every n greater than
the length of t, t is also a traversal over hGhni i. To summarise, we have the following.
F
Lemma 4.4 (Traversal Decomposition). (i) For every (possibly infinite) traversal t = i∈ω ti ∈
TravhGi where each ti is a finite traversal and t0 ≤ t1 ≤ t2 ≤ · · · , there is an increasing
sequence of natural numbers n0 < n1 < n2 < · · · such that each ti ∈ TravhGhni i : oi.
(ii) Given an ω-indexed family of ⊥-free traversals, ti ∈ TravhGhni i : oi with i ∈ ω, such that
t0 ≤ t1 ≤ t2 ≤ · · · , and an F
infinite sequence of natural numbers n0 < n1 < n2 < · · · , the

(possibly infinite) traversal i∈ω ti ∈ TravhGi.

Theorem 4.5 (Traversal-Path Correspondence). Let G = (Σ, N , R, F1 ) be a possibly infinite
higher-order recursion scheme. Paths in [[ G ]] and traversals over λ(G) projected to symbols from
Σ are the same set of finite and infinite sequences over Σ.
Proof. By combining Lemma 4.3, Lemma 4.4 and Theorem 3.18, we obtain a bijection ϕ :
∼
TravhGi ↾ ǫ −→ p[[ Σ ⊢ F1 : o ]]q which is strong, in that for every t ∈ TravhGi ↾ ǫ, we have
t and ϕ(t) are isomorphic as justified sequences. Since terminal symbols from Σ are assumed
to be of order 1, justified sequences from TravhGi ↾ ǫ are completely determined by their underlying sequence over Σ; similarly for p[[ Σ ⊢ F1 : o ]]q. On the one hand, there is a one-one
correspondence between P-views in [[ Σ ⊢ F1 : o ]] and paths in the generated tree [[ G ]]: given
a P-view, the corresponding path is obtained by erasing the O-moves. On the other, there is
a one-one correspondence between TravhGi ↾ ǫ and traversals over λ(G) projected to symbols
from Σ. Hence we have the desired set equality.

References
Vincent Danos and Laurent Regnier. 1993. Local and asynchronous beta-reduction (an analysis
of Girard’s execution formula). In Proceedings of the Eighth Annual Symposium on Logic
in Computer Science (LICS ’93), Montreal, Canada, June 19-23, 1993. 296–306. DOI:
http://dx.doi.org/10.1109/LICS.1993.287578
J. M. E. Hyland and C.-H. L. Ong. 2000. On Full Abstraction for PCF: I. Models, observables
and the full abstraction problem, II. Dialogue games and innocent strategies, III. A fully
abstract and universal game model. Information and Computation 163 (2000), 285–408.
Teodor Knapik, Damian Niwinski, and Pawel Urzyczyn. 2002. Higher-Order Pushdown Trees
Are Easy. In Foundations of Software Science and Computation Structures, 5th International
Conference, FOSSACS 2002. Held as Part of the Joint European Conferences on Theory and
Practice of Software, ETAPS 2002 Grenoble, France, April 8-12, 2002, Proceedings. 205–222.
DOI:http://dx.doi.org/10.1007/3-540-45931-6_15
Guy McCusker. 2000. Games and Full Abstraction for FPC. Inf. Comput. 160, 1-2 (2000),
1–61. DOI:http://dx.doi.org/10.1006/inco.1999.2845
26

Normalisation by Traversals

C.-H. Luke Ong

C.-H. Luke Ong. 2015. Higher-Order Model Checking: An Overview. In 30th Annual
ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10,
2015. 1–15. DOI:http://dx.doi.org/10.1109/LICS.2015.9
C.-H. Luke Ong. 2006.
On Model-Checking Trees Generated by Higher-Order
Recursion Schemes. In 21th IEEE Symposium on Logic in Computer Science
(LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings. 81–90.
DOI:
http://dx.doi.org/10.1109/LICS.2006.38
Colin Stirling. 2009.
Dependency Tree Automata. In Foundations of Software Science and Computational Structures, 12th International Conference, FOSSACS 2009,
Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009. Proceedings. 92–106.
DOI:
http://dx.doi.org/10.1007/978-3-642-00596-1_8

27

