Typed lambda syntax and capture-free term-family extraction
DefinitionBergerSchwichtenberg1991V2_SyntaxThe raw syntax of the simply typed lambda calculus, typing, substitution, -equivalence via binding trees, and long -normal forms. Standardization replaces bound names by indexed names derived from binding positions. Extraction chooses a fresh prefix beyond the length of every indexed name in its two samples.
import Std
/-!
# Syntax, Long β-Normal Forms, and α-Standardization (Berger–Schwichtenberg 1991, Sections 1–2)
Source: Ulrich Berger and Helmut Schwichtenberg,
"An inverse of the evaluation functional for typed λ-calculus",
*Proceedings of the Sixth Annual IEEE Symposium on Logic in Computer Science (LICS 1991)*,
pp. 203–211, Sections 1–2 (pp. 204–205).
This module formalizes:
- Simple types (`Ty`) built from ground type `o` (`Ty.base`) by `→` (`Ty.arr`).
- Binary indices `k, l ∈ {0,1}*` (`Index`), indexed variables `x_k^ρ`, and general typed
variables (`Var`).
- Concrete typed λ-terms (`Term`), typing (`HasType`), capture-avoiding substitution (`substTerm`),
α-conversion (`AlphaEq`), βη-equality (`BetaEtaEq`), and long β-normal forms (`IsLongBetaNormal`,
`IsLongBetaNeutral`).
- The bound-variable standardization mapping `α_k(r)` (`alphaRename`, p. 204), the term-family
embedding `EMB : Λ → Λ^{{0,1}*}` (`EMB`, p. 204), and the extraction functional
`EXTRACT : Λ^{{0,1}*} → Λ` (`EXTRACT`, pp. 204–205).
-/
namespace BergerSchwichtenberg1991V2
/-- Simple types built from a single ground type `o` by `→` (Section 1, p. 204):
`ρ, σ ::= o | ρ → σ`. -/
inductive Ty where
| base : Ty
| arr : Ty → Ty → Ty
deriving DecidableEq, Repr
namespace Ty
/-- Iterated function type `σ₁ → ⋯ → σₖ → τ` associated to the right (p. 204). -/
def arrMany : List Ty → Ty → Ty
| [], τ => τ
| σ :: σs, τ => .arr σ (arrMany σs τ)
/-- Argument types `[σ₁, ..., σₖ]` of a type `ρ = σ₁ → ⋯ → σₖ → o`. -/
def argTypes : Ty → List Ty
| .base => []
| .arr σ τ => σ :: argTypes τ
end Ty
/-- Finite 0–1 sequence `k ∈ {0, 1}*` used as a binding position index (Section 2, p. 204). -/
abbrev Index := List Bool
/-- The empty 0–1 sequence `ε` (p. 205). -/
def epsIdx : Index := []
/-- The singleton sequence `0` (p. 205). -/
def zeroIdx : Index := [false]
/-- The singleton sequence `1` (p. 204). -/
def oneIdx : Index := [true]
/-- Concatenation `k * l` of 0–1 sequences (p. 204). -/
def appendIdx (k l : Index) : Index := k ++ l
/-- `IsPrefixOf k m` holds if `m = k * l` for some `l ∈ {0, 1}*` ("`m` extends `k`", p. 204). -/
def IsPrefixOf (k m : Index) : Prop :=
∃ l : Index, m = k ++ l
/-- Variable identifier: either an indexed variable `x_k` (`k ∈ {0,1}*`, Section 2, p. 204)
or an ordinary named variable `y_n` (`n : Nat`). -/
inductive VarName where
| indexed : Index → VarName
| named : Nat → VarName
deriving DecidableEq, Repr
/-- Typed variable `x^ρ` (Section 1, p. 204). -/
structure Var where
name : VarName
ty : Ty
deriving DecidableEq, Repr
/-- Indexed variable `x_k^ρ` of type `ρ` with index `k ∈ {0, 1}*` (Section 2, p. 204). -/
def indexedVar (ρ : Ty) (k : Index) : Var :=
⟨.indexed k, ρ⟩
/-- Concrete typed λ-terms (Section 1, p. 204):
constructed from typed variables `x^ρ` by application `(t^{ρ→σ} r^ρ)^σ` and abstraction
`(λx^ρ. s^σ)^{ρ→σ}`. -/
inductive Term where
| var : Var → Term
| app : Term → Term → Term
| lam : Var → Term → Term
deriving DecidableEq, Repr
namespace Term
/-- Left-associated iterated application `r s₁ ... sₖ` (Section 1, p. 204). -/
def appMany : Term → List Term → Term
| r, [] => r
| r, s :: ss => appMany (.app r s) ss
/-- Iterated lambda abstraction `λx₁ ... xₙ. r`. -/
def lamMany : List Var → Term → Term
| [], r => r
| x :: xs, r => .lam x (lamMany xs r)
end Term
/-- Typing relation `r ∈ Λ^ρ` (`HasType r ρ`, Section 1, p. 204). -/
inductive HasType : Term → Ty → Prop where
| var (x : Var) :
HasType (.var x) x.ty
| app {t r : Term} {ρ σ : Ty} :
HasType t (.arr ρ σ) →
HasType r ρ →
HasType (.app t r) σ
| lam (x : Var) {s : Term} {σ : Ty} :
HasType s σ →
HasType (.lam x s) (.arr x.ty σ)
/-- Free variable occurrences of a term `r`. -/
def freeVarOccurrences : Term → List Var
| .var x => [x]
| .app r s => freeVarOccurrences r ++ freeVarOccurrences s
| .lam x r => (freeVarOccurrences r).filter (· != x)
/-- Set of free variables `FV(r)` (duplicate-free list). -/
def freeVars (r : Term) : List Var :=
(freeVarOccurrences r).eraseDups
/-- A term `r` is closed if `FV(r) = ∅`. -/
def IsClosed (r : Term) : Prop :=
freeVars r = []
/-- List of indices `l ∈ {0, 1}*` such that `x_l^σ` occurs free in `r` for some `σ`
(Section 2, p. 204: `{l ∈ {0,1}* | x_l free in r}`). -/
def freeIndices (r : Term) : List Index :=
(freeVars r).filterMap (fun v =>
match v.name with
| .indexed l => some l
| .named _ => none)
/-- All variables (both free and bound) occurring in `r`. -/
def allVars : Term → List Var
| .var x => [x]
| .app r s => allVars r ++ allVars s
| .lam x r => x :: allVars r
/-- Maximum named-variable id occurring anywhere in `r`. -/
def maxNamedId : Term → Nat
| .var ⟨.named n, _⟩ => n
| .var ⟨.indexed _, _⟩ => 0
| .app r s => Nat.max (maxNamedId r) (maxNamedId s)
| .lam ⟨.named n, _⟩ r => Nat.max n (maxNamedId r)
| .lam ⟨.indexed _, _⟩ r => maxNamedId r
/-- Maximum named-variable id across a list of terms. -/
def maxNamedIdList : List Term → Nat
| [] => 0
| t :: ts => Nat.max (maxNamedId t) (maxNamedIdList ts)
/-- Replace free occurrences of variable `x` with variable `y` in `r`. -/
def renameFreeVar (r : Term) (x y : Var) : Term :=
match r with
| .var v => if v == x then .var y else .var v
| .app t s => .app (renameFreeVar t x y) (renameFreeVar s x y)
| .lam v body =>
if v == x then .lam v body else .lam v (renameFreeVar body x y)
/-- Structural size of a raw term `r`. -/
def rawSize : Term → Nat
| .var _ => 1
| .app r s => rawSize r + rawSize s + 1
| .lam _ r => rawSize r + 1
theorem renameFreeVar_rawSize (r : Term) (x y : Var) :
rawSize (renameFreeVar r x y) = rawSize r := by
induction r with
| var v => simp only [renameFreeVar]; split <;> rfl
| app t s iht ihs => simp [renameFreeVar, rawSize, iht, ihs]
| lam v body ih =>
simp only [renameFreeVar]
split
· rfl
· simp [rawSize, ih]
/-- Capture-avoiding substitution `r[s/x]` (Section 2, p. 204). -/
def substTerm (r : Term) (x : Var) (s : Term) : Term :=
match r with
| .var v => if v == x then s else .var v
| .app t u => .app (substTerm t x s) (substTerm u x s)
| .lam v body =>
if v == x then
.lam v body
else if v ∈ freeVarOccurrences s then
let freshId := Nat.max (maxNamedId body) (Nat.max (maxNamedId s) (maxNamedId (.var x))) + 1
let v' : Var := ⟨.named freshId, v.ty⟩
.lam v' (substTerm (renameFreeVar body v v') x s)
else
.lam v (substTerm body x s)
termination_by rawSize r
decreasing_by
all_goals
simp_wf
simp [rawSize, renameFreeVar_rawSize]
try omega
/-- Type-respecting simultaneous substitution `θ : Var → Term` (Section 3, p. 205 & Section 4, p. 207). -/
abbrev Substitution := Var → Term
/-- A substitution `θ` is well-typed (`IsWellTypedSubst θ`) if `θ(x^ρ) ∈ Λ^ρ` for every variable `x^ρ`. -/
def IsWellTypedSubst (θ : Substitution) : Prop :=
∀ x : Var, HasType (θ x) x.ty
/-- Identity substitution `θ_id(x) = x` (Section 4, p. 208). -/
def idSubst : Substitution := fun x => .var x
/-- Update a substitution `θ[x ↦ t]` (Section 4, p. 207). -/
def updateSubst (θ : Substitution) (x : Var) (t : Term) : Substitution :=
fun y => if y == x then t else θ y
/-- Apply a simultaneous substitution `rθ` (with capture avoidance via fresh named variables). -/
def applySubst (θ : Substitution) (r : Term) : Term :=
match r with
| .var x => θ x
| .app t u => .app (applySubst θ t) (applySubst θ u)
| .lam v body =>
let fvBody := (freeVars body).filter (· != v)
let imgTerms := fvBody.map θ
let imgFVs := imgTerms.foldr (fun t acc => freeVarOccurrences t ++ acc) []
if v ∈ imgFVs then
let freshId :=
Nat.max (maxNamedId body)
(Nat.max (maxNamedId (.var v)) (maxNamedIdList imgTerms)) + 1
let v' : Var := ⟨.named freshId, v.ty⟩
.lam v' (applySubst (updateSubst θ v (.var v')) body)
else
.lam v (applySubst (updateSubst θ v (.var v)) body)
termination_by rawSize r
decreasing_by
all_goals
simp_wf
simp [rawSize]
try omega
/-- A term with free variables named and bound variables identified by the path to their
binder. In both applications and abstractions, `0` descends to the first subterm and `1`
descends to the second subterm of an application. -/
inductive BindingTerm where
| free : Var → BindingTerm
| bound : Ty → Index → BindingTerm
| app : BindingTerm → BindingTerm → BindingTerm
| lam : Ty → BindingTerm → BindingTerm
deriving DecidableEq, Repr
/-- Look up the path of the innermost binder of a variable in a scope. -/
def binderPath (v : Var) : List (Var × Index) → Option Index
| [] => none
| (x, p) :: scope => if v = x then some p else binderPath v scope
/-- Record the binder paths of a term, given the scope and path of its root. -/
def abstractBindings (scope : List (Var × Index)) (p : Index) : Term → BindingTerm
| .var v =>
match binderPath v scope with
| none => .free v
| some q => .bound v.ty q
| .app r s =>
.app (abstractBindings scope (p ++ zeroIdx) r) (abstractBindings scope (p ++ oneIdx) s)
| .lam x r => .lam x.ty (abstractBindings ((x, p) :: scope) (p ++ zeroIdx) r)
/-- α-equivalence is equality of the trees of binder positions and free variables. -/
def AlphaEq (r s : Term) : Prop :=
abstractBindings [] [] r = abstractBindings [] [] s
/-- Provable equality `r =_{βη} s` in the typed βη-calculus (Sections 1–2, pp. 203–204). -/
inductive BetaEtaEq : Term → Term → Prop where
| of_alpha {r s : Term} : AlphaEq r s → BetaEtaEq r s
| refl (r : Term) : BetaEtaEq r r
| symm {r s : Term} : BetaEtaEq r s → BetaEtaEq s r
| trans {r s t : Term} : BetaEtaEq r s → BetaEtaEq s t → BetaEtaEq r t
| app {r r' s s' : Term} :
BetaEtaEq r r' → BetaEtaEq s s' → BetaEtaEq (.app r s) (.app r' s')
| lam (x : Var) {r s : Term} :
BetaEtaEq r s → BetaEtaEq (.lam x r) (.lam x s)
| beta (x : Var) (r s : Term) :
BetaEtaEq (.app (.lam x r) s) (substTerm r x s)
| eta (x : Var) (r : Term) :
x ∉ freeVars r →
BetaEtaEq (.lam x (.app r (.var x))) r
mutual
/-- Long β-normal forms (Section 2, p. 204):
`λx₁^{ρ₁} ... λxₙ^{ρₙ}. y^{σ₁ → ⋯ → σₖ → o} s₁^{σ₁} ... sₖ^{σₖ}` with `s₁, ..., sₖ` in
long β-normal form and body `y s₁ ... sₖ` of ground type `o`. -/
inductive IsLongBetaNormal : Ty → Term → Prop where
| baseNeutral {t : Term} :
IsLongBetaNeutral .base t →
IsLongBetaNormal .base t
| lam (x : Var) {σ : Ty} {r : Term} :
IsLongBetaNormal σ r →
IsLongBetaNormal (.arr x.ty σ) (.lam x r)
/-- Neutral spine `y s₁ ... sₖ` whose arguments are in long β-normal form. -/
inductive IsLongBetaNeutral : Ty → Term → Prop where
| var (y : Var) :
IsLongBetaNeutral y.ty (.var y)
| app {t s : Term} {σ τ : Ty} :
IsLongBetaNeutral (.arr σ τ) t →
IsLongBetaNormal σ s →
IsLongBetaNeutral τ (.app t s)
end
/-- Name every binder and its bound occurrences by prefixing its path with `k`. -/
def nameBindings (k p : Index) : BindingTerm → Term
| .free v => .var v
| .bound ρ q => .var (indexedVar ρ (k ++ q))
| .app r s => .app (nameBindings k (p ++ zeroIdx) r) (nameBindings k (p ++ oneIdx) s)
| .lam ρ r => .lam (indexedVar ρ (k ++ p)) (nameBindings k (p ++ zeroIdx) r)
/-- The bound-variable standardization `α_k(r)` of Section 2. The prefix `k` is
chosen fresh when an α-variant is needed. -/
def alphaRename (k : Index) (r : Term) : Term :=
nameBindings k [] (abstractBindings [] [] r)
/-- Section 2 (p. 204): Term family representation `EMB : Λ → (Index → Λ)` defined by
`EMB r k := α_k(r)`. -/
def EMB (r : Term) (k : Index) : Term :=
alphaRename k r
/-- Maximum length among a list of 0–1 sequences. -/
def maxIdxLength : List Index → Nat
| [] => 0
| l :: ls => Nat.max l.length (maxIdxLength ls)
/-- Indices of all variables in a term, including variable occurrences that a sample
standardization may have placed under a binder with the same name. -/
def allIndices (r : Term) : List Index :=
(allVars r).filterMap (fun v =>
match v.name with
| .indexed l => some l
| .named _ => none)
/-- Pick an all-zero prefix longer than every index in the two samples `F ε` and `F 0`.
Bounding every sampled occurrence gives a conservative bound on the indices of the
unchanged occurrences used by the paper. -/
def canonicalFreshIndex (F : Index → Term) : Index :=
let len := Nat.max (maxIdxLength (allIndices (F epsIdx)))
(maxIdxLength (allIndices (F zeroIdx))) + 1
List.replicate len false
/-- Section 2 (p. 205): Extraction functional `EXTRACT : Λ^{{0,1}*} → Λ` defined by
`EXTRACT(F) := F(k̂)`. -/
def EXTRACT (F : Index → Term) : Term :=
F (canonicalFreshIndex F)
end BergerSchwichtenberg1991V2
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
Types, indices and terms
The types are generated by the base type and a binary arrow constructor . For a list of types and result type , iterated arrow construction sends to and to . The argument types of form the empty list. The argument types of are followed by the argument types of .
An index is any finite list of Boolean bits. The distinguished indices are , and , and index append is ordinary list concatenation . The prefix predicate for holds exactly when there exists an index with . It allows equality of and and gives the empty index as a prefix of every index.
A variable name is either indexed by such a list or named by a natural number. A variable consists of its name and a type , both of which enter variable equality. Write for the variable with indexed name and type . Raw terms are the occurrence of a variable, the application of two raw terms, and the abstraction of a raw term over a variable. Repeated application over an argument list starts with at the empty list and, for a head , continues with on the rest of the list. Repeated abstraction over an empty variable list returns the body. For a head it constructs an outer over the repeated abstraction on the rest of the list.
Typing is the inductively generated relation with the following rules. The term has type . If has type and has type , then has type . If has type , then has type .
Variables and substitution
The list of free variable occurrences is for , the concatenation of the two lists for , and the body's list with every entry equal to filtered out for . The list of free variables is this list with duplicate variables erased. A term is closed exactly when this latter list is empty. The free indices of a term are the indices of the indexed variables in its free-variable list, dropping natural-number names. Different free variables of different types with the same index can contribute that index more than once.
The list of all variables is for , the left list concatenated with the right list for , and prepended to the body's list for . It includes binders and repeated occurrences. The maximum natural-number name is the name at a natural-number-named leaf, at an indexed leaf, the maximum of the two maxima at application, the maximum of a natural-number-named binder and the body's maximum at its abstraction, and the body's maximum at an indexed binder. On a list of terms, take the maximum of their maxima, with for the empty list.
Free-variable renaming from to changes the variable at a leaf to if , and otherwise keeps . It recurses in both children at an application. It keeps the binder of , leaving the body intact if and recursing into the body otherwise. This operation accepts arbitrary raw terms and pairs of variables. Raw size gives at a variable, the sum of child sizes plus at an application, and the body size plus at an abstraction. The free-variable renaming theorem states, for every raw and variables , that the raw size after this renaming equals the raw size of .
To substitute for in , replace leaf with , keep other leaves, and recurse on both children of an application. Under , keep the entire abstraction when . When and occurs free in , take the variable of type with natural-number name . Freely rename to in , continue the substitution in that renamed body, and abstract over . When and is absent from the free occurrences of , continue under the unchanged binder .
A substitution is any function from variables to raw terms. It is well typed exactly when has type for every . The identity substitution sends to . The update of any substitution sends to and every to .
Simultaneously applying a substitution to a raw term sends to and recurses separately in the two children of an application. To apply it to , let be the list obtained by mapping over the free-variable list of filtered to remove . If is free in any term of , choose of the same type as with natural-number name . Otherwise choose . Return the abstraction over whose body is the simultaneous substitution into using . The definitions of both single and simultaneous substitution apply to raw terms.
Binding trees and term relations
A binding tree is a free-variable leaf storing a full variable, a bound-variable leaf storing a type and an index, an application of two binding trees, or an abstraction storing a type and body tree. To look up a variable in a scope list of variable–index pairs, take the index of the first pair whose variable equals , with no result if there is no such pair. To abstract the bindings of a term relative to a scope and a current path , send a variable leaf for to its free leaf if the lookup fails and to a bound leaf storing and the looked-up path if it succeeds. In an application, recurse on the left at and on the right at with the same scope. In , record an abstraction of type and recurse on at with prepended to the scope. Two raw terms are -equivalent exactly when their binding trees with initial empty scope and empty path are equal.
The inductive relation on raw terms includes every -equivalent pair and has reflexivity, symmetry and transitivity. It is closed under application in both children and under abstraction over the same variable. Its rule relates to the result of the specified single substitution of for in , for all raw and variables . Its rule relates to for any raw term and variable absent from the free-variable list of .
Long -normal and long -neutral forms are mutually inductive predicates of a type and term. A neutral term at is normal at . If is normal at , then is normal at . A variable occurrence is neutral at its variable's type. If is neutral at and is normal at , then is neutral at .
Reconstructing binders and extracting a term
Naming a binding tree with prefix and current path sends a free leaf for to and a bound leaf with type and stored path to . For an application it reconstructs the two trees at and respectively, with the same . For an abstraction with stored type , it names the binder and reconstructs its body at with the same . Renaming a raw term at index builds its binding tree with empty scope and path and then names the tree with prefix and empty path. The embedding is the function of returning this renaming of .
The maximum index length of a list of indices is for the empty list and the maximum of the first index length and the tail's maximum for a nonempty list. The list of all indices of a raw term is obtained from the list of all variables, keeping the index of every indexed variable and dropping natural-number names. For any index-to-raw-term function , the canonical index is the list of zeros where is the maximum of the maximum index lengths of all indices of and . Thus these two samples determine the index, and when neither sample has an index of positive length it is . The extraction operation is evaluated at this canonical index.