Affine lambda calculus and reduction
DefinitionAehligSchwichtenberg2002V2_SyntaxFinite linear types, typed variables, raw terms and affine typing. Eliminations are expressed as applications, with a closed step term in list iteration. Capture-avoiding substitution avoids enclosing binder names. Reduction contracts the eight conversions and descends into either side of an application.
import Std
/-!
# Syntax, Typing, and Reductions for Aehlig–Schwichtenberg (2002, Sections 2–3), V2
V2 differs from V1 only in `substTerm`: renamed binders also avoid every enclosing binder
(see `substAux`). V1 could rename the inner binder of a tensor elimination to the outer one,
which made substitution and subject reduction fail.
Source: Klaus Aehlig and Helmut Schwichtenberg,
"A syntactical analysis of non-size-increasing polynomial time computation",
*Proceedings of the 15th IEEE Symposium on Logic in Computer Science (LICS 2000)*, pp. 84–91;
expanded version in *ACM Transactions on Computational Logic* 3(3), 2002, pp. 383–401
(arXiv:cs/0011037v2), Sections 2–3 (pp. 3–9).
This module formalizes:
- Definition 2.1: Finite linear types (`Ty`).
- Definition 2.2 & 2.3: Raw terms (`Term`) and constructor symbols (`Constructor`).
- Definition 2.4: Context-indexed affine linear typing `HasType Γ t τ` (`Γ ⊢ t^τ`), where
eliminations for `×`, `B`, `⊗`, and `L(τ)` are written in application notation.
- Definition 3.1, 3.2, 3.3: Lists (`listEntryCount`, `IsListTerm`), conversions (`ConvStep`),
one-step and multi-step reduction (`RedStep`, `RedStar`, `RedSteps`), normal forms (`IsNormal`),
and almost closed terms (`IsAlmostClosed`).
-/
namespace AehligSchwichtenberg2002V2
/-- Definition 2.1 (Finite types, p. 3):
`ρ, τ ::= ⋄ | B | τ ⊸ ρ | τ ⊗ ρ | τ × ρ | L(τ)`. -/
inductive Ty where
| diamond : Ty
| bool : Ty
| lolli : Ty → Ty → Ty
| tensor : Ty → Ty → Ty
| prod : Ty → Ty → Ty
| list : Ty → Ty
deriving DecidableEq, Repr
namespace Ty
/-- Binary numerals `L(B)` (Section 2, p. 3 & Corollary 4.9, p. 14). -/
def bin : Ty := .list .bool
/-- Iterated linear function type `τ₁ ⊸ ⋯ ⊸ τₙ ⊸ ρ`. -/
def lolliMany : List Ty → Ty → Ty
| [], ρ => ρ
| τ :: τs, ρ => .lolli τ (lolliMany τs ρ)
end Ty
/-- Typed variable `x^τ` (Section 2, p. 4). -/
structure Var where
id : Nat
ty : Ty
deriving DecidableEq, Repr
/-- Definition 2.3 (Constructor symbols, p. 4):
`tt : B`, `ff : B`, `nil_τ : L(τ)`, `cons_τ : ⋄ ⊸ τ ⊸ L(τ) ⊸ L(τ)`, `⊗_{τ,ρ} : τ ⊸ ρ ⊸ τ ⊗ ρ`. -/
inductive Constructor where
| tt : Constructor
| ff : Constructor
| nil : Ty → Constructor
| cons : Ty → Constructor
| tensorPair : Ty → Ty → Constructor
deriving DecidableEq, Repr
/-- Type assignment for constructor symbols (Definition 2.3, p. 4). -/
def Constructor.ty : Constructor → Ty
| .tt => .bool
| .ff => .bool
| .nil τ => .list τ
| .cons τ => .lolli .diamond (.lolli τ (.lolli (.list τ) (.list τ)))
| .tensorPair τ ρ => .lolli τ (.lolli ρ (.tensor τ ρ))
/-- Definition 2.2 (Terms, p. 4):
`r, s, t ::= x^τ | c | λx^τ. t | ⟨t, s⟩ | t s | {t}`. -/
inductive Term where
| var : Var → Term
| const : Constructor → Term
| lam : Var → Term → Term
| pair : Term → Term → Term
| app : Term → Term → Term
| brace : Term → Term
deriving DecidableEq, Repr
namespace Term
/-- Multi-argument application `t s₁ ... sₙ`. -/
def appMany : Term → List Term → Term
| t, [] => t
| t, s :: ss => appMany (.app t s) ss
end Term
/-- A context `Γ` is a finite set of variables (Section 2, p. 4), represented as a list. -/
abbrev Context := List Var
/-- Disjointness of two contexts `Γ₁ ∩ Γ₂ = ∅`. -/
def DisjointCtx (Γ₁ Γ₂ : Context) : Prop :=
∀ v, v ∈ Γ₁ → v ∉ Γ₂
/-- Set-extensional union `Γ = Γ₁ ∪ Γ₂` with no disjointness requirement. -/
def IsCtxUnion (Γ₁ Γ₂ Γ : Context) : Prop :=
∀ v, v ∈ Γ ↔ (v ∈ Γ₁ ∨ v ∈ Γ₂)
/-- Set-extensional disjoint union `Γ = Γ₁, Γ₂` (Section 2, p. 4:
"For two contexts `Γ₁` and `Γ₂` the notation `Γ₁, Γ₂` stands for the union, expressing that
`Γ₁` and `Γ₂` are disjoint."). -/
def IsDisjointCtxUnion (Γ₁ Γ₂ Γ : Context) : Prop :=
DisjointCtx Γ₁ Γ₂ ∧ IsCtxUnion Γ₁ Γ₂ Γ
/-- Free variable occurrences of a term `t`. -/
def freeVarOccurrences : Term → List Var
| .var x => [x]
| .const _ => []
| .lam x t => (freeVarOccurrences t).filter (· != x)
| .pair t s => freeVarOccurrences t ++ freeVarOccurrences s
| .app t s => freeVarOccurrences t ++ freeVarOccurrences s
| .brace t => freeVarOccurrences t
/-- Underlying set of free variables `FV(t)` (duplicate-free list). -/
def freeVars (t : Term) : List Var :=
(freeVarOccurrences t).eraseDups
/-- Cardinality `|FV(t)|` of the set of free variables of `t`. -/
def freeVarCard (t : Term) : Nat :=
(freeVars t).length
/-- Almost closed terms (Section 3, p. 8): terms with free variables of type `⋄` only. -/
def IsAlmostClosed (t : Term) : Prop :=
∀ v ∈ freeVars t, v.ty = .diamond
/-- Closed terms: terms with no free variables. -/
def IsClosed (t : Term) : Prop :=
freeVars t = []
/-- Maximum variable id occurring anywhere in a term. -/
def maxVarId : Term → Nat
| .var x => x.id
| .const _ => 0
| .lam x t => Nat.max x.id (maxVarId t)
| .pair t s => Nat.max (maxVarId t) (maxVarId s)
| .app t s => Nat.max (maxVarId t) (maxVarId s)
| .brace t => maxVarId t
/-- Rename free occurrences of `x` to `y` in `t`. -/
def renameFreeVar (t : Term) (x y : Var) : Term :=
match t with
| .var v => if v == x then .var y else .var v
| .const c => .const c
| .lam v body => if v == x then .lam v body else .lam v (renameFreeVar body x y)
| .pair r s => .pair (renameFreeVar r x y) (renameFreeVar s x y)
| .app r s => .app (renameFreeVar r x y) (renameFreeVar s x y)
| .brace r => .brace (renameFreeVar r x y)
/-- Structural size of a raw term used for termination of capture-avoiding substitution. -/
def rawSize : Term → Nat
| .var _ => 1
| .const _ => 1
| .lam _ t => rawSize t + 1
| .pair t s => rawSize t + rawSize s + 1
| .app t s => rawSize t + rawSize s + 1
| .brace t => rawSize t + 1
theorem renameFreeVar_rawSize (t : Term) (x y : Var) :
rawSize (renameFreeVar t x y) = rawSize t := by
induction t with
| var v => simp only [renameFreeVar]; split <;> rfl
| const c => rfl
| lam v body ih =>
simp only [renameFreeVar]
split
· rfl
· simp [rawSize, ih]
| pair r s ihr ihs => simp [renameFreeVar, rawSize, ihr, ihs]
| app r s ihr ihs => simp [renameFreeVar, rawSize, ihr, ihs]
| brace r ihr => simp [renameFreeVar, rawSize, ihr]
/-- Capture-avoiding substitution with an avoidance bound (V2 repair).
When a binder `v` is free in `s`, it is renamed to a fresh `v'` whose identifier exceeds
`bound`, the identifiers of the body and of `s`, and `x.id`. Descending under a binder raises
`bound` past that binder. Hence a renamed binder never coincides with an enclosing binder.
V1 chose the new identifier without `bound`, so the two binders of a tensor elimination
`t (λa. λb. r)` could become equal, which `(⊗⁻)` forbids. -/
def substAux (bound : Nat) (t : Term) (x : Var) (s : Term) : Term :=
match t with
| .var v => if v == x then s else .var v
| .const c => .const c
| .lam v body =>
if v == x then
.lam v body
else if v ∈ freeVarOccurrences s then
let freshId := Nat.max bound (Nat.max (maxVarId body) (Nat.max (maxVarId s) x.id)) + 1
let v' : Var := ⟨freshId, v.ty⟩
.lam v' (substAux freshId (renameFreeVar body v v') x s)
else
.lam v (substAux (Nat.max bound v.id) body x s)
| .pair r u => .pair (substAux bound r x s) (substAux bound u x s)
| .app r u => .app (substAux bound r x s) (substAux bound u x s)
| .brace r => .brace (substAux bound r x s)
termination_by rawSize t
decreasing_by
all_goals
simp_wf
simp [rawSize, renameFreeVar_rawSize]
try omega
/-- Capture-avoiding substitution `t[s/x]` (Section 2, p. 4 & Definition 3.2, p. 7). -/
def substTerm (t : Term) (x : Var) (s : Term) : Term :=
substAux 0 t x s
/-- Simultaneous substitution `r[t, s / x, y]` for two distinct variables `x, y`
(used in `⊗_{τ,ρ} t s (λx^τ, y^ρ. r) ↦ r[t, s / x, y]`, Definition 3.2, p. 7). -/
def substTwo (r : Term) (x y : Var) (t s : Term) : Term :=
if y ∈ freeVarOccurrences t then
let freshId := Nat.max (maxVarId r) (Nat.max (maxVarId t) (Nat.max (maxVarId s) (Nat.max x.id y.id))) + 1
let y' : Var := ⟨freshId, y.ty⟩
substTerm (substTerm (renameFreeVar r y y') x t) y' s
else
substTerm (substTerm r x t) y s
/-- Definition 2.4 (Typing `Γ ⊢ t^τ`, pp. 4–5). -/
inductive HasType : Context → Term → Ty → Prop where
/-- `(Var)`: `Γ, x^τ ⊢ x^τ` -/
| var {Γ Γ' : Context} (x : Var) :
IsDisjointCtxUnion Γ [x] Γ' →
HasType Γ' (.var x) x.ty
/-- `(Const)`: `Γ ⊢ c^τ` -/
| const (Γ : Context) (c : Constructor) :
HasType Γ (.const c) c.ty
/-- `(⊸⁺)`: from `Γ ∪ {x^τ} ⊢ t^ρ` infer `Γ ⊢ (λx^τ. t)^{τ⊸ρ}` -/
| lam {Γ Γ' : Context} (x : Var) {t : Term} {ρ : Ty} :
IsCtxUnion Γ [x] Γ' →
HasType Γ' t ρ →
HasType Γ (.lam x t) (.lolli x.ty ρ)
/-- `(⊸⁻)`: from `Γ₁ ⊢ t^{τ⊸ρ}` and `Γ₂ ⊢ s^τ` infer `Γ₁, Γ₂ ⊢ (t s)^ρ` -/
| app {Γ₁ Γ₂ Γ : Context} {t s : Term} {τ ρ : Ty} :
IsDisjointCtxUnion Γ₁ Γ₂ Γ →
HasType Γ₁ t (.lolli τ ρ) →
HasType Γ₂ s τ →
HasType Γ (.app t s) ρ
/-- `(×⁺)`: from `Γ ⊢ t^τ` and `Γ ⊢ s^ρ` infer `Γ ⊢ ⟨t, s⟩^{τ×ρ}` -/
| pair {Γ : Context} {t s : Term} {τ ρ : Ty} :
HasType Γ t τ →
HasType Γ s ρ →
HasType Γ (.pair t s) (.prod τ ρ)
/-- `(×₁⁻)`: from `Γ ⊢ t^{τ×ρ}` infer `Γ ⊢ (t tt)^τ` -/
| projLeft {Γ : Context} {t : Term} {τ ρ : Ty} :
HasType Γ t (.prod τ ρ) →
HasType Γ (.app t (.const .tt)) τ
/-- `(×₀⁻)`: from `Γ ⊢ t^{τ×ρ}` infer `Γ ⊢ (t ff)^ρ` -/
| projRight {Γ : Context} {t : Term} {τ ρ : Ty} :
HasType Γ t (.prod τ ρ) →
HasType Γ (.app t (.const .ff)) ρ
/-- `(B⁻)`: from `Γ₁ ⊢ t^B`, `Γ₂ ⊢ s^τ`, `Γ₂ ⊢ r^τ` infer `Γ₁, Γ₂ ⊢ (t ⟨s, r⟩)^τ` -/
| boolElim {Γ₁ Γ₂ Γ : Context} {t s r : Term} {τ : Ty} :
IsDisjointCtxUnion Γ₁ Γ₂ Γ →
HasType Γ₁ t .bool →
HasType Γ₂ s τ →
HasType Γ₂ r τ →
HasType Γ (.app t (.pair s r)) τ
/-- `(⊗⁻)`: from `Γ₁ ⊢ t^{τ⊗ρ}` and `Γ₂, x^τ, y^ρ ⊢ s^σ` infer `Γ₁, Γ₂ ⊢ (t (λx^τ, y^ρ. s))^σ` -/
| tensorElim {Γ₁ Γ₂ Γ₂' Γ : Context} {t s : Term} (x y : Var) {σ : Ty} :
x ≠ y →
IsDisjointCtxUnion Γ₂ [x, y] Γ₂' →
IsDisjointCtxUnion Γ₁ Γ₂ Γ →
HasType Γ₁ t (.tensor x.ty y.ty) →
HasType Γ₂' s σ →
HasType Γ (.app t (.lam x (.lam y s))) σ
/-- `(L(τ)⁻)`: from `Γ ⊢ t^{L(τ)}` and `∅ ⊢ s^{⋄⊸τ⊸ρ⊸ρ}` infer `Γ ⊢ (t {s})^{ρ⊸ρ}` -/
| listElim {Γ : Context} {t s : Term} {τ ρ : Ty} :
HasType Γ t (.list τ) →
HasType [] s (.lolli .diamond (.lolli τ (.lolli ρ ρ))) →
HasType Γ (.app t (.brace s)) (.lolli ρ ρ)
/-- Definition 3.1 (Lists, p. 7):
Lists `ℓ` (with `n` entries) are terms of the form `cons_τ d₁ a₁ (... (cons_τ dₙ aₙ nil_τ))`. -/
def listEntryCount : Term → Option Nat
| .const (.nil _) => some 0
| .app (.app (.app (.const (.cons _)) _) _) l =>
match listEntryCount l with
| some k => some (k + 1)
| none => none
| _ => none
/-- Predicate asserting that `l` is a list in the sense of Definition 3.1 (p. 7). -/
def IsListTerm (l : Term) : Prop :=
∃ n, listEntryCount l = some n
/-- Definition 3.2 (Conversions, p. 7): `t ↦ t'`. -/
inductive ConvStep : Term → Term → Prop where
| beta (x : Var) (t s : Term) :
ConvStep (.app (.lam x t) s) (substTerm t x s)
| projTt (t s : Term) :
ConvStep (.app (.pair t s) (.const .tt)) t
| projFf (t s : Term) :
ConvStep (.app (.pair t s) (.const .ff)) s
| ifTt (t s : Term) :
ConvStep (.app (.const .tt) (.pair t s)) t
| ifFf (t s : Term) :
ConvStep (.app (.const .ff) (.pair t s)) s
| tensorBeta (τ ρ : Ty) (t s : Term) (x y : Var) (r : Term) :
x.ty = τ → y.ty = ρ → x ≠ y →
ConvStep
(.app (.app (.app (.const (.tensorPair τ ρ)) t) s) (.lam x (.lam y r)))
(substTwo r x y t s)
| iterNil (τ : Ty) (t s : Term) :
ConvStep (.app (.app (.const (.nil τ)) (.brace t)) s) s
| iterCons (τ : Ty) (d a l t s : Term) :
IsListTerm l →
ConvStep
(.app (.app (.app (.app (.app (.const (.cons τ)) d) a) l) (.brace t)) s)
(.app (.app (.app t d) a) (.app (.app l (.brace t)) s))
/-- Definition 3.3 (Reduction `t → t'`, p. 8). -/
inductive RedStep : Term → Term → Prop where
| conv {t t' : Term} :
ConvStep t t' → RedStep t t'
| appLeft {t t' : Term} (s : Term) :
RedStep t t' → RedStep (.app t s) (.app t' s)
| appRight (t : Term) {s s' : Term} :
RedStep s s' → RedStep (.app t s) (.app t s')
/-- Reflexive-transitive closure of reduction `t →* t'`. -/
inductive RedStar : Term → Term → Prop where
| refl (t : Term) : RedStar t t
| step {t s u : Term} : RedStep t s → RedStar s u → RedStar t u
/-- Exact `k`-step reduction chain `t →^k t'`. -/
inductive RedSteps : Nat → Term → Term → Prop where
| zero (t : Term) : RedSteps 0 t t
| succ {k : Nat} {t s u : Term} :
RedStep t s → RedSteps k s u → RedSteps (k + 1) t u
/-- A term `t` is normal if there is no `t'` such that `t → t'` (Section 3, p. 8). -/
def IsNormal (t : Term) : Prop :=
¬ ∃ t', RedStep t t'
end AehligSchwichtenberg2002V2
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
The types form the freely generated collection with two base types and , binary arrow , tensor and product , and unary list constructor . Arrow chains associate to the right.
The binary list type is .
For a list of types and a result type , the iterated arrow type is , with result for an empty list.
A variable consists of a natural-number identifier and a type . Equality compares both entries, so different types may carry the same identifier.
The constructors are , , a constructor and a constructor for every type , and a constructor for every ordered pair of types .
The constants and have declared type . For every type , the constants and have declared types and . For all types , has declared type .
Raw terms are generated by variable nodes for variables, constant nodes for constructors, abstractions with any variable binder and term body, pairs and applications with two term children, and braces with one term child. The indices and children can be chosen before any typing judgment is given.
For a term and a list of terms , successive application gives , associating to the left, and gives when the list is empty.
A context is a list of variables, with the full identifier and type stored at each entry. The list can be empty or contain repeated variables.
Two contexts are disjoint if every variable belonging to is absent from .
A context is a union of if, for every variable , holds exactly when or . The condition is insensitive to order and multiplicities.
A context is a disjoint union of if and have no common variable and, for every variable , holds exactly when or . Repetitions within either operand or the result are permitted.
The free-variable occurrence list of a term is the singleton list of its variable for a variable node and the empty list for a constant. At it takes the free occurrence list of and deletes all entries equal to . At a pair or application it concatenates the occurrence lists of the left and right children in that order. At a brace it uses the occurrence list of its contents.
For every term , the list removes duplicates from the free-variable occurrence list of , retaining the first occurrence of each distinct variable.
The free-variable cardinality of is the length of , the number of distinct free variables of .
A term is almost closed if every member of has type . In particular, this holds whenever is empty.
A term is closed if is the empty list.
For a term , is the maximum of and every variable identifier in , including the identifiers of abstraction binders.
For variables and a term , renaming free to in replaces each variable node equal to by , leaves constants as they are and recurses into pairs, applications and braces. At an abstraction with binder it returns that abstraction as it is. At other abstractions it keeps the binder and recurses into the body, which permits the new occurrences of to be bound by an existing binder.
The raw syntax size is for a variable or constant, plus the body size for an abstraction or brace, and plus the sum of the two child sizes for a pair or application.
For every term and variables , the raw syntax size of the result of renaming free to in is .
For a natural bound , term , variable and replacement term , the substitution auxiliary function replaces a variable node by exactly when its variable equals , preserves constants, and recurses with bound into both children of pairs and applications and into the contents of braces. At a binder it returns the whole abstraction if . If and occurs free in , it gives the binder a new identifier and keeps its type. It renames free occurrences of in the body to the new variable, and recurses on the renamed body with bound . In the remaining case it preserves the binder and recurses on the body with bound .
Write for substitution of for in , starting the auxiliary function with bound . A binder may be freshened by this operation even when has no free occurrence in its body.
For terms and variables , the two-variable substitution returns if is absent from the free occurrences of . If occurs free in , it chooses of 's type and identifier . It renames free to in , substitutes for in that result, then substitutes for . This function accepts any , including .
The typing relation is generated by the variable rule in any context containing that variable, and the constant rule in any context with the declared constant type. An abstraction has type in if has declared type and has type in a union of and the singleton list . An application has type in a disjoint union of contexts typing at and at . The pair has type if has type and has type in the same context. A term of product type gives applications and of types and in its context. If has Boolean type and both and have type in a shared context disjoint from the context of , then has type in their disjoint union. For distinct variables of types , respectively, has type in a disjoint union of a context typing at and a context disjoint from , provided has type in a union of and . If has type and has type in the empty context, has type in the context of .
The optional list entry count returns on any , returns on if returns a number, and is undefined otherwise. It looks at the rightmost tail argument of each fully applied , permits any parameters on the constructors along that chain, and ignores the contents of the other two arguments.
A term qualifies as a list term if there is a natural number such that returns . Constructors with count qualify.
The direct conversions are , , , and . They also include converting to the two-variable substitution in of for and for , for distinct with respective types . The iteration conversions are and , with the latter requiring to return a number. The term arguments in these patterns range over raw terms.
A single step performs one direct conversion at the root or at a subterm reached by descending through any number of application nodes, on either side of each application.
For any terms , the finite reduction relation holds exactly when a sequence of zero or more single steps goes from to . Its reflexive case is available for every term.
For and terms , the relation of exactly reductions from to holds for precisely when . For it holds exactly when a single step takes to a term and exactly reductions go from to .
A term is normal if it has no outgoing single step. In particular, abstractions, pairs and braces are normal at the root regardless of their contents.