Playground Documentation Challenges Full Docs

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.

NameWhat it saysIn Formall
α{x | p(x)} is {y | p(y)}: bound names do not matteralways, in every comparison
β{x | e}(a) is e with a in place of xalways, when a term is built
η{x | f(x)} is fno; a fact or the extensionality axiom gives it
δa defined name is its definitionon request: define gives a statement, a hint unfolds it
curryingf(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

▶ Run

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

▶ Run

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 β

▶ Run

η: 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

▶ Run

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

▶ Run

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

▶ Run

No partial application: this fails

▶ Run

Expected error: Too few arguments

Write the one-argument function as a λ instead:

A λ in place of f(a)

▶ Run

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) where f(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 piece f(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 pattern p(x, y) of inference would have to be matched one argument at a time.
  • Operations and tables stay whole. a + b is one application of + to two arguments; the truth tables of decide (∧(✔, ❌) -> ❌) 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]

▶ Run

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 λ

▶ Run

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

▶ Run

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.