Short answer
• Inside an ordinary λ-term that is represented as a tree you cannot have all three of
Take a closed λ-term t = λx. b and try to build two copies of it “little by little’’ inside a pure tree language that insists on the usual scope rule:
copy (λx. b) ↦¹ (λx₀. ?) & (λx₁. ?) (1 step)
The moment you create the two outer lambdas you have to decide what to do with the occurrences of x that live arbitrarily deep in b.
• If you do nothing, both bodies still contain the same variable x,
but that variable is now free – its binder (the original λx)
has disappeared from the tree that contains the bodies.
Scope is broken.
• To keep scope you would have to rename every occurrence of x that
belongs to the left copy to, say, x₀ and every occurrence that belongs
to the right copy to x₁.
That renaming requires you to traverse the whole body b,
so one step can no longer be O (1).
Hence, within tree syntax you must choose: either allow the temporary scope violation that your calculus exhibits, or perform a complete, linear-time traversal before the first observable copy is delivered. There is no third option.
Let the term be a graph.
A variable occurrence is not a name in the text but a pointer to its
binder node. Duplication is performed by adding a fan-out node that
forwards the same pointer twice:
f
/ \
n n (f is a fan-out node)
No renaming is necessary and no variable ever loses its binder – the pointer still reaches it, even if the binder no longer lies “above’’ the occurrence in the drawn picture. Because graph nodes are manipulated by updating a constant number of pointers, each reduction step costs O (1). This is the principle behind
• Lamping’s abstract algorithm for optimal reduction,
• Lafont’s interaction-net version,
• the Gonthier–Abadi–Levy sharing-graph calculus,
• call-by-need semantics with let / heaps (Launchbury),
• calculi with explicit substitutions (λσ, λse, the suspension
calculus, …),
all of which enjoy ordinary lexical binding and incremental (often optimal) copying.
If by “closed scopes’’ you mean the precise tree property “every variable occurrence is syntactically contained in its binder’’, then incremental O (1) copying forces you to relax that property in the intermediate terms, exactly as your Abstract Calculus does.
If, on the other hand, you are willing to represent terms with sharing (graphs, lets, explicit substitutions, environments, …) then you can have both:
• lexical binding that never breaks, and
• an explicit copy/contraction operation whose implementation really is
constant-time and incremental.
Was this answer helpful?
version: o3-pro-2025-06-10
Status: UQ Validated
Validated: 8 months ago
Status: Failed Human Verification
Verified: 7 months ago
Loading model reviews...
Loading reviews...