Functions and λ
Lambda terms, α, β, η, currying, binder notation and Miller patterns — what Formall does and does not do
Overview
Formall terms are the terms of the simply typed λ-calculus: atoms, applications f(a, b) and
anonymous functions {x: T | e} (written λx. e elsewhere). The theory of λ-calculus names several ways in which two
terms can be «the same»; each is called a reduction or an equivalence and has a Greek letter. This page explains each
one on the smallest examples and says whether Formall does it automatically, does it on request, or not at all.
| Name | What it says | In Formall |
|---|---|---|
| α | {x | p(x)} is {y | p(y)}: bound names do not matter | always, in every comparison |
| β | {x | e}(a) is e with a in place of x | always, when a term is built |
| η | {x | f(x)} is f | no; a fact or the extensionality axiom gives it |
| δ | a defined name is its definition | on request: define gives a statement, a hint unfolds it |
| currying | f(a, b) is f(a)(b) | no: [A, B -> C] and [A -> [B -> C]] are different types |
α: names of bound variables
In all{x: T | p(x)} the name x is only a place holder. Renaming it gives the same expression,
so a fact written with x is found for a formula written with y.
α-equivalence
When a substitution would put a free name under a binder with the same name, the bound name is changed in print
(n′, 𝓋1), so that the meaning stays the same. This is called capture-avoiding substitution.
β: applying a function
A λ applied to an argument is replaced by its body with the argument substituted. Formall does it at once, every
time a term is built (after parsing, substitution in a call, a hint): you never see a term like
{x | e}(a) in statements.
β-reduction when a term is built
The same happens when a definition is unfolded: the hint <double> replaces the atom by its λ, and the
application is reduced.
Unfolding a definition (δ) followed by β
η: a function is the λ of its values
η says that {x: T | q(x)} and q are the same function. Lean, Coq and Agda build this into
comparison; Isabelle keeps terms η-short. Formall does not: the two are different expressions, and a fact about one
is not found for the other.
No η: this fails
Expected error: No matching statement found for expression substitution
Two ways around it. Write the same form that the facts use (most library code does so). Or obtain the η statement as a
fact: it follows from function extensionality (logic/extensionality.fl, «functions with equal values are
equal»), and then it rewrites like any statement:
η from a fact
Formall never identifies the two forms by itself: a call infers a predicate η-reduced (∀(p) from
generalize[| S] under for(x) with p(x) -> ✔), and where
∀{x | p(x)} is wanted, the predicate is written: generalize[{x: T | p(x)} | S].
Currying
A function of two arguments can be a function of a pair ([A, B -> C]) or a function returning a function
([A -> [B -> C]], «curried»). Formall has both types and keeps them apart: there is no partial
application f(a) of a two-place f.
Two kinds of two-argument functions
No partial application: this fails
Expected error: Too few arguments
Write the one-argument function as a λ instead:
A λ in place of f(a)
Why functions are not curried
HOL, Lean and Coq identify the two types: there every function takes one argument, and f(a) of a
two-place f is simply a function. Nothing in the logic forbids that. Formall keeps the number of arguments
in the type on purpose:
- A forgotten argument is an error where it is forgotten. With currying,
f(a)wheref(a, b)was meant is not wrong — it is a function. The mistake surfaces later and elsewhere, as a type mismatch far from the place, or not at all: in the failing example above,h(f(a))would be accepted and mean something the author did not write. - Every subterm is a term someone wrote. In a curried
f(a, b)the piecef(a)is a subterm too. A hint, a chain step or argument inference that rewrites functions would also find these partial applications: more places to rewrite, more ambiguous hints, and the patternp(x, y)of inference would have to be matched one argument at a time. - Operations and tables stay whole.
a + bis one application of+to two arguments; the truth tables ofdecide(∧(✔, ❌) -> ❌) list whole applications. Curried, each would be a chain of one-argument applications that printing has to fold back. - Nothing is lost. A partial application is one λ:
{y: T | f(a, y)}says exactly which argument is left open, and it is also the only way to leave open the first argument ({x: T | f(x, b)}), which currying does not give either.
Calls of proofs, on the other hand, are curried: there a partial call is useful and cannot be confused with anything. The parameters of a theorem are a list — its for atoms, then
the quantifiers of its conclusion — and a call may give them all at once or a few at a time: T[b][a] is a call
on the result of T[b], and states the same as T[b, a]. Nothing makes it so on purpose: the result of a
call is again a statement that can be called. Partial application of a proof is how a theorem becomes a fact of the place:
T[b] can be named once and its quantifiers given later (see Calls).
Curried calls: T[a][b] is T[a, b]
Binder notation f{x, y | P}
A function applied to one λ needs no parentheses: ∀{x: T | p(x)} is ∀({x: T | p(x)}).
Several variables are a shorthand for nested binders: ∀{x: A; y: B | r(x, y)} is
∀{x: A | ∀{y: B | r(x, y)}}. It applies to any atom f: [[T -> R] -> R] whose argument returns
the same type R as f itself (so that f{y | P} can be the body of another f): ∀, ∃, ∃!, a sum
∑. With a polymorphic quantifier (∀: [['α -> 𝔹] -> 𝔹]) the variables may have different types; each nested ∀
gets its own. It does not apply to sup: [[ℝ -> 𝔹] -> ℝ], and for a function of two arguments
{x, y | e} is one λ of two variables. See Expressions.
Higher-order matching and Miller patterns
To infer the arguments of a theorem, a call matches its conditions with visible facts. When the unknown is a
function, matching is «higher-order», and in general it has many solutions. A Miller pattern is the good
case: an unknown function applied to distinct bound variables, like P(x) under {x | …}. Then there is
exactly one solution: P is the λ over those variables of whatever stands in their place.
A Miller pattern: P is inferred as a λ
An unknown applied to an ordinary term, like P(a), is not a pattern: against p(c) both
P := p, a := c and P := {y | p(c)} fit. Formall then matches first-order, by the head:
Not a pattern: matched by the head
A third case is an unknown applied to a term built from bound variables, like P(ι(n)) under
∀{n | …}: every occurrence of that term becomes the variable, again the only solution. When inference is not
unique, the call asks for the argument (P := …) or a fact label. Inference only chooses; the conditions are
checked afterwards as usual (calls). Hints of proofs (<e | T>) match first-order
only, without Miller patterns.