Inference rules, pattern footprints, and resource boundedness
DefinitionMoserSchneckenreither_TypingThe footprint judgement has application, composition, sharing, and variable rules; the full judgement additionally has all four source weakening rules. Contexts are finite partial maps represented up to permutation. Freshness, disjoint context domains, and linearity in composition are explicit. A substitution is consistent with a context when its domain covers the context and each substituted ground value has the assigned annotation, with its typing cost existentially quantified. The potential freed by a pattern is specified by an explicit linearisation, footprint derivations for its arguments, and summation of annotations for copies of each original variable. A rule is resource bounded when the right-hand side is derivable within the root cost plus freed potential, less its charge. The budget is expressed by an equality with a nonnegative residual cost, avoiding truncated subtraction. Strict rules cost one and weak rules zero; the optional cost-free mode charges neither. Resource boundedness is syntactic and contains no assumption about operational potential decrease.
import Definitions.Def_MoserSchneckenreither_Annotations
/-!
Figure 2 and Definitions 4–6 of Moser–Schneckenreither, arXiv:1811.09071v1, pp. 9–11.
The footprint uses app, comp, share and var; full typing also admits the four weakenings.
Contexts are finite partial maps represented up to permutation. Freshness, disjointness,
and the linearity condition on comp are explicit.
-/
namespace MoserSchneckenreither
inductive Mode where
| footprint
| full
variable {sig : Signature} {P : Problem sig}
def flatContext {n : ℕ} (xs : Fin n → ℕ) (ps : Fin n → Annotation) : Context :=
List.ofFn fun i ↦ (xs i, ps i)
/-- The source inference rules. No operational cost inequality is a constructor of this relation. -/
inductive Typing (F : AnnotatedSignature P) :
Mode → Context → ℚ≥0 → Term sig → Annotation → Prop
| app (mode : Mode) (f : Symbol sig) (a : Declaration (sig.arity f))
(ha : F.declarations f a) (xs : Fin (sig.arity f) → ℕ)
(hx : Function.Injective xs) :
Typing F mode (flatContext xs a.inputs) a.cost (.app f fun i ↦ .var (xs i)) a.output
| var (mode : Mode) (x : ℕ) (q : Annotation) :
Typing F mode [(x, q)] 0 (.var x) q
| comp {mode : Mode} (f : Symbol sig) (ts : Fin (sig.arity f) → Term sig)
(xs : Fin (sig.arity f) → ℕ) (ps : Fin (sig.arity f) → Annotation)
(Γs : Fin (sig.arity f) → Context) (ks : Fin (sig.arity f) → ℚ≥0)
(k₀ : ℚ≥0) (q : Annotation) (hx : Function.Injective xs)
(hfresh : ∀ i j, xs i ∉ (Γs j).keys)
(hdisjoint : ∀ i j, i ≠ j → ∀ x ∈ (Γs i).keys, x ∉ (Γs j).keys)
(hlinear : (Term.app f ts).Linear)
(hhead : Typing F mode (flatContext xs ps) k₀ (.app f fun i ↦ .var (xs i)) q)
(hargs : ∀ i, Typing F mode (Γs i) (ks i) (ts i) (ps i)) :
Typing F mode (List.ofFn Γs).flatten (k₀ + (List.ofFn ks).sum) (.app f ts) q
| share {mode : Mode} (Γ : Context) (x y z : ℕ) (p₁ p₂ p q : Annotation)
(t : Term sig) (k : ℚ≥0) (hshare : Shares p p₁ p₂)
(hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z)
(hx : x ∉ Γ.keys) (hy : y ∉ Γ.keys) (hz : z ∉ Γ.keys)
(h : Typing F mode (Γ ++ [(x, p₁), (y, p₂)]) k t q) :
Typing F mode (Γ ++ [(z, p)]) k
(t.rename fun w ↦ if w = x ∨ w = y then z else w) q
| perm {mode : Mode} {Γ Δ : Context} {k : ℚ≥0} {t : Term sig} {q : Annotation}
(hperm : Γ.Perm Δ) (h : Typing F mode Γ k t q) : Typing F mode Δ k t q
| w1 {Γ : Context} {k k' : ℚ≥0} {t : Term sig} {q : Annotation}
(h : Typing F .full Γ k t q) (hk : k ≤ k') : Typing F .full Γ k' t q
| w2 (Γ : Context) (x : ℕ) (p r q : Annotation) (k : ℚ≥0) (t : Term sig)
(h : Typing F .full (Γ ++ [(x, r)]) k t q) (hr : r ≤ p) :
Typing F .full (Γ ++ [(x, p)]) k t q
| w3 {Γ : Context} {k : ℚ≥0} {t : Term sig} {q s : Annotation}
(h : Typing F .full Γ k t s) (hq : q ≤ s) : Typing F .full Γ k t q
| w4 (Γ : Context) (x : ℕ) (p q : Annotation) (k : ℚ≥0) (t : Term sig)
(hx : x ∉ Γ.keys) (h : Typing F .full Γ k t q) :
Typing F .full (Γ ++ [(x, p)]) k t q
/-- Compatibility of a normalised substitution with each context annotation, ignoring its cost. -/
def Consistent (F : AnnotatedSignature P) (σ : Substitution sig) (Γ : Context) : Prop :=
Γ.Valid ∧ ∀ x q, (x, q) ∈ Γ → x ∈ σ.domain ∧
∃ k, Typing F .full [] k (σ.apply x) q
/-- Definition 5: linearise the argument patterns, derive their footprints, then merge renamings. -/
def Frees (F : AnnotatedSignature P) {n : ℕ} (ts : Fin n → Term sig)
(ps : Fin n → Annotation) (Γ : Context) (ℓ : ℚ≥0) : Prop :=
∃ (us : Fin n → Term sig) (ρ : ℕ → ℕ) (Γs : Fin n → Context) (ks : Fin n → ℚ≥0),
((List.ofFn fun i ↦ (us i).vars).flatten).Nodup ∧
(∀ i, (us i).rename ρ = ts i) ∧
(∀ i, (Γs i).keys.Perm (us i).vars ∧ Typing F .footprint (Γs i) (ks i) (us i) (ps i)) ∧
Γ = Context.renameMerge (List.ofFn Γs).flatten ρ ∧ ℓ = (List.ofFn ks).sum
/-- The syntactic budget condition for one rule and one annotation of its root. -/
def RuleBounded (F : AnnotatedSignature P) (r : Rule sig) (charge : ℚ≥0) : Prop :=
∀ a, F.declarations r.head a → ∃ Γ ℓ k,
Frees F r.args a.inputs Γ ℓ ∧ a.cost + ℓ = charge + k ∧
Typing F .full Γ k r.rhs a.output
/-- Definition 6, with cost-free boundedness selected by `countStrict = false`. -/
def ResourceBounded (F : AnnotatedSignature P) (countStrict : Bool := true) : Prop :=
(∀ r ∈ P.strict, RuleBounded F r (if countStrict then 1 else 0)) ∧
(∀ r ∈ P.weak, RuleBounded F r 0)
end MoserSchneckenreither
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
Signature. The underlying signature consists of a natural number , symbols , an arity for each symbol , and a nonempty designated set of constructor symbols. At least one symbol has arity zero; that symbol is not required to belong to . In particular the symbol set is nonempty, and individual symbols may have arity zero.
Terms, variables, and renaming. Terms are finite expressions formed from variables indexed by and applications . The list of variable occurrences is for the variable and the concatenation, in argument order, of the lists for an application; repetitions are retained. A term is ground when this list is empty and linear when this list has no repeated entry. For a total map , replaces every variable in by , recursively through applications; this does not recursively apply inside its replacement terms. A renaming by a total map is the substitution sending to the variable . The symbols occurring in a term are all its application labels, including those below its root.
Rules and problems. A rule consists of a head symbol , exactly argument terms , and a right-hand term , with the requirement that each variable occurring in occurs somewhere in . Its left-hand term is this application. The arguments are not required to be constructor terms or to contain distinct variables. A problem consists of finite lists and of such rules, called strict and weak respectively, and its combined rule list is followed by . Either list may be empty, may repeat rules, and may overlap the other list. Let be the set of symbols that either belong to or occur anywhere inside an argument of a rule in either list.
Annotations and declarations. An annotation is a finitely supported function ; addition, multiplication by a nonnegative rational scalar, and comparison are pointwise. The zero annotation is permitted. An arity- declaration is a triple consisting of input annotations, a cost , and an output annotation ; is permitted.
Annotated signature. For the given signature and problem, supplies, for each symbol , a nonempty collection of arity- declarations, and, for every output annotation , input annotations for and a cost . For every and every annotation , the declaration belongs to ; every declaration for such an has for all and . For every and annotations , one has and, for every , . For every , scalar , and annotation , one has and, for every , . The cost equations apply also to nullary symbols. No corresponding uniqueness, addition, or scaling condition is imposed on symbols outside , although their declaration collections must still be nonempty and their functions are still supplied.
Contexts. A context is a finite ordered list of pairs with and an annotation. Its key list is the list of first components, retaining order and repetitions; it is valid exactly when this list has no repeated entry. The empty context is permitted, and arbitrary contexts are not presumed valid. Concatenation of contexts is list concatenation, and a permutation of a context preserves its entries with their multiplicities. All sums over empty lists or empty argument families are zero.
Finite-domain substitutions. A substitution consists of a finite domain and a total assignment . Its effective action is when and the variable otherwise. Write for . No requirement is imposed on the assignment outside , and the domain may be empty.
Mode. There are exactly two modes, called footprint and full.
Flat context. For every natural number , every family of variable names , and every family of annotations , the flat context is the ordered list . This definition places no distinctness requirement on the names. For it is the empty list.
Typing. For the given , write for the least family of relations with mode equal to footprint or full, context , cost , term , and annotation , generated by the following rules. All cost variables in these rules are nonnegative rationals, all annotation variables are finitely supported nonnegative-rational sequences, and all variable names are natural numbers. In either mode, for every symbol , declaration , and pairwise distinct names indexed by , the ordered context types at cost with output ; also for every . For composition, choose a symbol , terms , names , annotations , contexts , and costs for , and a cost and output annotation . If the are pairwise distinct and each is absent from every key list of every , contexts at distinct indices have disjoint sets of keys, the concatenation of the variable-occurrence lists of the has no repetitions, , and for every , then the concatenation types in the same mode at cost with output . For sharing, for every context , pairwise distinct names all absent from its keys, annotations with , term , and cost , a judgment gives , where replaces every variable named or by and leaves all other names unchanged. In either mode, any permutation of the context preserves a judgment with the same cost, term, and output. In full mode there are four additional rules: from and obtain ; from and obtain , with no extra freshness premise in this rule; from and obtain ; and from and a name absent from 's keys obtain for any annotation . The five shared rules keep the same mode in all their premises and conclusion. Nullary symbols, zero costs, and zero annotations are included; argument-index conditions for a nullary symbol are vacuous, its ordered argument context is empty, and its argument-cost sum is zero.
Consistency. For every , substitution , and context , consistency means the conjunction of the following requirements: the keys of have no repetitions, and for every variable name and annotation such that is an entry of , one has and there exists a cost with . The witness may depend on the entry. This definition alone does not require the substitution to be normalised. The empty context is consistent with every substitution.
Freeing arguments. For every , natural number , term family , annotation family , context , and cost , the freeing condition means that there exist a term family , a total renaming , contexts , and costs in such that: the concatenation of all lists in index order has no repetitions; renaming every variable of by gives exactly for every ; for every , the key list of is a permutation of and ; ; and is the context obtained by first concatenating the in index order, then replacing each key by , and finally keeping each resulting key once, in its first-occurrence order, with annotation equal to the sum of all original annotations whose renamed keys equal it. The renaming need not be injective, so it can identify different names and add their annotations. When , this condition holds exactly when and .
Boundedness of one rule. For every , rule , and charge , boundedness of at charge means that for every declaration there exist a context and costs such that the family of left-hand arguments with input annotations satisfies the freeing condition with context and cost , the exact equality holds, and . The witnesses may depend on the declaration, and the condition quantifies over all declarations for the head, not merely one selected declaration.
Resource boundedness. For every and Boolean parameter , resource boundedness means that every rule in is bounded at charge if is true and at charge if is false, and every rule in is bounded at charge . The parameter defaults to true when omitted. A rule appearing in both lists must satisfy both applicable conditions; a condition on an empty list is vacuous.