Full Documentation
All documentation on a single page for easy searching (Ctrl+F), printing to PDF, or pasting into AI assistants.
Getting Started
Formall Documentation
A formal logic programming language for constructing and verifying mathematical proofs
What is Formall?
Formall is a language for writing and verifying formal mathematical proofs. You define your axioms, declare types and symbols, and build proofs step by step — Formall checks every step mechanically.
Unlike most proof assistants, Formall has no hidden automation and no tactics engine. Every step is written in
the text; the one command that writes steps for you (decide) is named in the proof
and expand into ordinary commands. Every run can also write a journal of all steps, which an
independent checker verifies with four rules — hypotheses, axioms, rewriting and applying a theorem (a call
T[…]): contradiction, generalization, calls on quantified facts, implication, equality and
enumerations all come down to calls of theorems and axioms the files write
(Command Reducibility). What you see is exactly what is verified.
Despite this minimalism, Formall is expressive enough for serious mathematics:
- Second-order logic — quantify over predicates and functions, not just values
- Any axiom system — Peano arithmetic, ZFC set theory, or your own foundations
- Type polymorphism — prove a theorem once for a type parameter, instantiate it with any concrete type by a call
T[…] - Parametric theorems — the
lock/axiom/call mechanism lets theorems accept proof arguments, analogous to how higher-order functions accept function arguments - Full reuse — every proved theorem becomes a lemma applicable anywhere by a call
The included library covers propositional logic, quantifiers and equality; Peano arithmetic up to the fundamental theorem of arithmetic; set theory from axioms (the Russell paradox, Kuratowski pairs, and the integers, positive rationals and reals built from sets); ordered fields and completeness, limits and continuity; Hilbert's geometry (incidence and order, synthetically and in coordinates); groups and commutative rings; Cantor's diagonal argument and logic puzzles. Each theory is a module that can be imported or interpreted in another model.
Quick Start
Here's a minimal Formall program that proves a simple logical identity:
Your First Proof
This program defines boolean logic and demonstrates proof by contradiction.
Core Concepts
Types and Atoms
Formall is strongly typed. You declare types with type(...) and atoms (values/functions) with for:
Type declarations
Statements and Proofs
A statement in Formall has the form expression -> expression. The if command introduces assumptions, and a proof <…> derives new statements:
Making statements
Labels for Reuse
Labels let you name and reuse proven statements:
Using labels
Documentation Structure
📚 Basics
Types, atoms, expressions, and fundamental concepts
⚡ Commands
all commands by what they do with scopes — context, proof steps, generators, labels, notation, import
⚙️ Rules
define, bijective — the rules that generate axiom schemes; hint — the theorems a rewrite rests on
🎯 Examples
Peano arithmetic, set theory, logic puzzles
Basics
Types
Declaring and using types in Formall
Overview
Formall is a strongly-typed language. Every expression has a type, and type mismatches are caught at parse time. Types are declared using the type(...) command.
type(typeName1, typeName2, ...)typeName1, …- Names of new primary types; the other forms of
type(enumerations, subtypes, type variables) are on the type page.
Basic examples
Primary Types
Primary types are the basic building blocks. They represent sets of values (like booleans, natural numbers, or sets):
Declaring primary types
Function Types
Functions are typed using the arrow notation [Args -> Result]:
for(f: [A -> B]) // Function from A to Bfor(g: [A, B -> C]) // Function taking A and B, returning Cfor(h: [A, [B -> C] -> D]) // Higher-order function taking A and [B -> C] (function taking B, returning C), returning DDeclarations of functional type atoms
Type Scoping
Types are scoped — they are visible inside the type() scope:
Type scoping
Type Polymorphism
Formall supports type polymorphism in two ways. A type parameter of a theorem: declare type(T) inside the theorem, prove it, and instantiate it with a concrete type by a call (see Calls — Type Parameters). And a type variable: a type whose name starts with an apostrophe, type('α). An atom whose type contains 'α is polymorphic — one atom for all types, its type is inferred at every application (as in HOL and Lean). A statement with 'α in the types of its bound atoms is a schema — true for every type: calls and the search for conditions instantiate 'α by matching.
A polymorphic quantifier and an axiom schema
Atoms in Formall are variables (for means «for any»), so a polymorphic atom does not claim that a type is inhabited: empty types stay sound.
Why Types Matter
Types in Formall serve several purposes:
- Safety — prevent meaningless expressions like applying a boolean function to a natural number
- Clarity — make the domain of discourse explicit
- Verification — enable automatic checking of proof steps
- Quantification —
forand constructors quantify over specific types
Atoms
Values, functions, and named entities
Overview
Atoms are the named entities in Formall — constants, variables, and functions. They are declared using the for command and always have an associated type.
for(atomName: type)for(atomName1, atomName2: type)for(atomName1: type1; atomName2: type2)for(atomName: [argumentTypes -> resultType])atomName- The name of the atom: letters, digits, any non-ASCII symbols (
∀,➕,𝔹) and_ ! $ % & ' = ? @ ` ~ + ^ -(not before>) and*; not spaces or the characters of the syntax( ) [ ] { } < > , : ; | "..is reserved for namespaces. type- A declared type, or a function type
[argumentType1, argumentType2 -> resultType].
Basic examples
Simple Atoms
Simple atoms represent values of a given type:
Declaring simple atoms
More compact declaration
Function Atoms
Functions are atoms with function types. They can take arguments and return values:
Function declarations
Calling Functions
Functions are called with parentheses. Constructors create anonymous functions using {varName: Type | expression}:
Function application and constructors
Atom Naming
Atom names can include letters (including Unicode: Greek, Cyrillic, mathematical symbols like ×, =, ∈, ➕), digits (in any position), and underscores. However, the symbols +, -, *, ^ are reserved for label operations and cannot be used in atom names.
Naming examples
Scoping Rules
Atoms are scoped to their declaration for command. Inner for can shadow outer atoms:
Atom scoping
Atoms vs Labels
Don't confuse atoms with labels:
- Atoms — declared with
for, have types, appear in expressions - Labels — declared with
+, store statements, used in proof commands
Atoms vs Labels
Expressions
Building complex terms from atoms
Overview
Expressions in Formall are built from atoms through function application. Every expression has a type, determined by its structure.
Basic examples
Atomic Expressions
The simplest expressions are just atoms:
Atomic expressions
Function Application
Apply a function to arguments with parentheses:
Function application
Constructors
Create anonymous functions (predicates) with constructor syntax {varName: Type | expression}:
{boundAtomName: type | expression}A function applied to a single constructor needs no parentheses: ∀{x: ℕ | p(x)} is ∀({x: ℕ | p(x)}). Quantifiers are written this way: the braces show where the quantified formula ends, so no precedence rule is needed for it. Nested one-place quantifiers are printed together: ∀{x, y: ℕ | P}. The interpreter prints this form too (with --prefix — the form with parentheses).
This is only a way of writing: ∀ still takes one argument, a function of one variable, and
∀{x, y: ℕ | P} is ∀{x: ℕ | ∀{y: ℕ | P}} — the parser builds the nested form and
L[a, b] removes the quantifiers one at a time. Nothing has to be declared for it: the shorthand
applies to any atom f: [[T -> R] -> R] whose argument is a function into the same type R as its
result (so f{y | P} can be the body of another f): ∀, ∃,
∃!, a sum ∑: [[ℕ -> ℝ] -> ℝ]. It does not apply to sup: [[ℝ -> 𝔹] -> ℝ] or to a
function of two arguments, where {x, y | e} is a function of two variables (define(f := {a, b: T | e})).
Constructor syntax
Lexical Rules
- A name (atom, type, label, command) is a run of letters, digits,
_!$%&'.=?@\`~and any non-ASCII characters:➕,∀𝔹,L➕1,=Colorare single names. In expressions — the terms of commands, calls and proofs — an atom name may also contain+ * ^ -(a-bis one name,a - ban operator):-before>is the arrow->,*right after|is the hint|*. - Reserved in expressions:
( ) , ; { } | [ ] : < >, spaces,"and comment starts//,/*. - Spaces and comments (
// …to the end of the line,/* … */) separate tokens; they cannot occur inside a name. Comments are allowed inside expressions too. - In an expression a space is kept only between two name characters, where it separates names:
a ∘ bis three names,a∘bis one. Elsewhere spaces are insignificant:∀{x: T | p(x)}and∀ { x : T | p ( x ) }are the same. - Unicode spaces (no-break space U+00A0, thin space U+2009, ideographic space U+3000 …) count as ordinary spaces, so text pasted from a word processor reads as it looks. Invisible characters — zero-width space U+200B, joiners, soft hyphen, bidirectional controls U+202A–U+202E, U+2066–U+2069, line separators U+2028/U+2029 — are an error anywhere: otherwise
abandabwould be different names that look the same. - Positions in messages are
line:column, the column counted in Unicode characters.
Proofs
A proof is an expression in angle brackets; the inner brackets mark the places to rewrite:
<expression>Inside <...>, the system searches for matching statements and substitutes their right-hand side:
Prove syntax
Label Hints in Prove
Use <expr | Label> to specify which statement to use for a substitution when there are multiple matching ones:
Label hints
Outer angle brackets are not needed — ➕ is not being substituted.
Expression Equality
Two expressions are considered equal in Formall if they are the same atom, function applications with equal functions and equal arguments, or constructors with alpha-equivalent bodies (same structure up to variable renaming).
Alpha-equivalence of constructors
➕(1, 1) and 2 are different expressions unless you prove they're equal.See Also
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.
Statements
The fundamental unit of proof
Overview
A statement in Formall has the form expression -> expression. It asserts that within the current context, the left expression can be replaced by the right expression.
leftExpression -> rightExpressionleftExpression- What may be replaced.
rightExpression- What replaces it: wherever
leftExpressionoccurs, it can be rewritten torightExpression. A truth is a statement with a true value on the right:P -> ✔.
Basic examples
With if
Introduce statements as assumptions:
if statements
With prove
Derive statements by substitution:
prove statements
Note: outer angle brackets around f are NOT needed since f itself is not being substituted.
Statement Semantics
A statement A -> B means: in the current proof context, A can be replaced with B. This is not logical implication — it's closer to "evaluates to" or "equals". To express logical implication, use a function:
Equality vs Implication
Statement Sources
Statements can come from: if (assumptions), proofs <…> (derived by rewriting), calls T[…] (theorems and quantified facts applied to values; taking their blocks — lifted to universals, flipped assumptions), and axiom (conditional axioms).
Statement Visibility
Statements are visible inside the scope where they were created. When that scope closes, they are no longer accessible:
Statement scope
Chained Substitutions
With nested angle brackets, prove chains substitutions:
Chains
A -> B does not imply B -> A. To express bidirectional equality, you typically prove both directions separately.Scopes
Scope structure, braces, chaining, and bare blocks
Overview
Formall code is organized into nested scopes. Five commands create scopes: type, for, if, lock, and rule. Every declaration and proof result is scoped to the scope where it was delivered.
Braces Are Optional
A scope-creating command always creates a scope, whether or not you use curly braces { }. Braces are just syntax for grouping multiple commands into one scope. Without braces, the scope contains only the next command (and its scope). These two forms are equivalent:
With and without braces
Both forms produce exactly the same scope tree. Braces simply let you put more commands inside a scope.
if(x) if(y) f(); is equivalent to if(x) { if(y) { f(); } }.Chaining
Without braces, scope-creating commands naturally chain — each one wraps around what follows. The chain ends when something that opens no scope — a proof, a call — is done, or when a semicolon ; is encountered:
Chaining
As in C, a semicolon after a statement ends the whole chain: in for(…) if(…) <…>; the ; closes the proof, and with it the if and the for.
Declarations
A chain that consists only of scope commands (type, for, if, lock, rule, import) and ends with ; is a declaration. It lasts until the end of the enclosing block or file, like int x; in C: later semicolons end only their own statements. A chain left open at the end of a file is a declaration as well.
Declarations
A declaration made inside a block ends with the block. This is how a file declares its language once and then states its theorems at the top level — and how import works.
Labels before a chained command apply to that command:
Labels on chained commands
Comma-separated Commands
Non-scope commands can be separated by commas within the same scope. Each command executes independently:
Comma-separated commands
type, for, if, lock, rule) cannot be comma-separated. They must be chained or placed in their own scopes.Bare Blocks
Curly braces can be used without any command, creating an anonymous scope. Anything declared inside is not visible outside:
Bare block
Scope Hierarchy
Scopes form a tree. Each scope may contain child scopes. This tree determines:
- Visibility — atoms, labels, and rules are visible in their declaring scope and all descendants
- Statement access — statements are accessible from the scope where they were delivered and from nested scopes
- Label scope visibility — when reading a label, only statements on the path from the current scope up to the label's declaration are included (see Labels)
- Boundary rules — a call that takes the blocks its proof stands in takes
forandifonly, never atype,lockorrule
Shadowing
The later and the inner hide the earlier and the outer
One rule
When Formall has to choose among several visible things that fit, it takes the nearest: a later one hides an earlier one in the same block, and one in an inner block hides one in an outer block. It is the rule of local variables in programming languages, and it is the same for names, for the facts a proof substitutes, and for the facts a call finds for the conditions of a theorem.
The order of the search is fixed: the current block from its end, then the enclosing block from its end, and so on outward to the top level of the file and the modules it imports. A label given explicitly comes before all of them.
Names
An inner for hides an atom of the same name declared outside (Atoms):
An inner atom hides an outer one
Facts in prove
Without a label, <e> takes the first statement with left side e in the search order. Other statements about e are not an error: in a proof by contradiction the hypothesis X -> false of the inner if stands beside the outer fact X -> true, and the hypothesis is the one meant.
The nearest fact
In the full code the outer if carries the label X1.
Conditions of a call
A theorem's if conditions are patterns; a call matches them against the visible statements to infer the arguments not given (calls). When the conditions can be met in several ways, each way uses one statement per condition, and one way shadows another when each of its statements is the same or nearer, at least one nearer. The ways nobody shadows must give the same result. Two conditions may take the same statement, and the names of the theorem's parameters play no part:
Each condition takes its nearest fact
Unique is an axiom of a lock here only to keep the example short; a uniqueness theorem is applied the same way.
When neither way shadows the other — one is nearer in one condition and farther in another — the call stops and shows both. Here P := A uses the earlier ⇔(A, B) -> ✔ and the later A -> ✔; P := C the other way round:
Neither choice shadows the other
A fact label or an argument such as P := A settles it.
Expected error: Ambiguous arguments of the call
In other systems
Lean's assumption takes the latest matching hypothesis of the local context, and Isabelle's assumption tries the premises in turn; for one condition this is the same rule. Formall extends it to several conditions at once without preferring any of them, so an ambiguity that depends on the order of conditions is reported instead of being decided silently.
Labels
Naming and managing collections of statements
Overview
Labels in Formall serve as named references to collections of statements. They are used to store proof results and pass them on: to calls T[a | L], as hints of proofs <e | L>, to commands like generalize and contradict.
Declaration and Definition
Combined Declaration and Definition
Use +Name: before a command to both declare and define in one step:
Declaration + definition
Module-level declaration: T::
The most common case — a theorem proved deep inside for and if blocks, whose label must live at the top of the file — has its own form. T:: declares the label at the top level of the current file (exactly where +T; would stand before the statement that contains the definition) and defines it here, like theorem in Lean. All for and if between the top level and the definition become the theorem's parameters and conditions. T:: on a label that is already declared is an error (define it with T:), and an undeclared T: is still an error, so a typo never creates a new theorem silently. +T; stays for other levels — for example, a label declared inside a hypothesis block.
Module-level declaration
Forward Declaration
Declare a label with +Name; before defining it later. Use Name: (without +) to add statements to an already declared label. This is useful when the definition happens inside a nested scope but the label must be accessible outside it:
Forward declaration
Delivery Scope
A label placed on a command captures the result at the delivery scope of that command. For most non-scope commands, delivery is the current scope. A call that takes the blocks its proof stands in is special: contradict[| S] delivers above the if it closes, generalize[| S] above the for it takes. Scope commands (if, rule) deliver into themselves.
| Command | Delivery scope | Boundaries |
|---|---|---|
for | N/A (no label allowed) | — |
if | Into itself | — |
type, lock, rule | Into itself (scope marker) | — |
proofs <…>, calls T[…], axiom, +-*^ | Current scope | — |
contradict[| S], a call taking an if | Parent of the if taken | for, type, lock, rule |
generalize[| S], a call taking a for | Parent of the for taken | if, type, lock, rule |
+Label: syntax physically appears. For example, +L: contradict[| …] places the label in the parent of the if the call closes.Since such calls deliver to a different scope, labels on them capture results at those delivery scopes:
Labels at different delivery levels
Since generalize[| …] delivers to the parent of the for it takes, you can pass a proof directly to avoid needing a separate label inside the loop:
generalize delivers above for
Scope Visibility
Labels follow scoping: a label is accessible in the scope where it was declared (and in all nested scopes). When that scope closes, the label is no longer accessible.
Whenever a label's statements are read — by a call, a proof hint, label commands, or any other operation — statements are filtered by scope visibility. Only statements whose definition scope lies on the path from the current scope up to the label's declaration scope are included. Statements from sibling branches of the scope tree are foreign and are excluded (with a warning).
Scope filtering
Collected holds statements from two sibling if branches. Inside the second if, only its own branch's statements are visible.
Using Labels with prove
Inside a proof, you can specify which label to use for a particular substitution using the <expr | Label> syntax:
Labels in prove
Lock Labels
When a label is placed on lock(), it can be used as the first argument of axiom. See lock() and axiom for details. Here is a complete example:
Lock label with axiom
Undeclaration and Undefinition
Two operations for removing label data:
-Name;(undeclaration) — removes the label entirely; any subsequent use causes an error. The label is searched upward through all parent scopes, so you can undeclare a label from inside a nested block.Name-;(undefinition) — clears the label's statements but keeps it declared for later reuse
Undefinition and undeclaration
Since undeclaration searches upward, it can be used to remove visibility of labels declared in outer scopes. A common use case is sealing a lock() after all axioms have been defined:
Sealing a lock via undeclaration
After -𝒜;, no new axioms can be added to this lock, but existing axioms and theorems still work.
Augmentation
By default, redefining a label (L: cmd) clears all its statements in the current scope and replaces them. With an augmentation postfix, you control how new statements combine with existing ones:
L+: cmd— union: adds new, skipping duplicatesL-: cmd— subtract: removes matching statementsL*: cmd— intersect: keeps only statements present in bothL^: cmd— symmetric difference: XOR of the two sets
+L+: cmd is an error). Declare and define first, then augment.All four augmentation operations
Accumulating across scope branches
The L+: postfix is especially useful for collecting results from different scope branches. Plain L: cmd would fail because it tries to clear statements from foreign scopes:
Accumulating with Label+: across scope branches
Duplicate Statements
Statement equality in labels considers both content and scope. Two statements with identical expressions are equal only if they were defined in the same scope. This affects all set operations and augmentation.
Defining a Label with Another Label
A label name is a proof — after | of a call, of a proof hint or of a command — and so it is where a
statement stands: C: H; defines C with the statements of H visible here, as
C: +(H); does. As every reading of a label, it keeps only the statements on the path to here (see
Scope Visibility).
A copy stands where C is declared. That decides which atoms are parameters of its statements — the
atoms of the blocks between a statement and the declaration of its label. A theorem declared at the top of a file
takes the for atoms of its blocks as parameters; its copy declared inside those blocks takes none of
them: it is the statement as a fact of this place.
A copy of a label is a fact of its place
A proof gives its statements to whoever takes it: written as a statement, to the block; as an argument, to the
command that takes it; in a hint, to the hint. A label name alone (H;) is +(H); written as a
statement: it gives the block the statements of H visible here — they are its facts already, so nothing is
added, and the interpreter warns. See Label Commands for +,
-, *, ^.
Proofs <…>
Deriving a statement by rewriting marked places
Overview
A proof is an expression in angle brackets: <and(<P>, <Q>)>. Inner brackets mark the places to rewrite; each is replaced by the right side of a visible statement whose left side it is. The result is a new statement: its left side is the expression as written, without the brackets, its right side — the expression after all rewrites (and(P, Q) -> true).
<expressionWithMarks><expressionWithMarks |> // the top is not rewritten<…<subexpression>…> // a rewrite point: any visible statement whose left side is the subexpression<…<subexpression | hint1, hint2>…> // only these hints<…<subexpression |* hint1, …>…> // rewrite inside repeatedly while a hint applies<term0 -> term1 | hint1 -> term2 | hint2> // a chain: every term writtenexpressionWithMarks- The expression to start from, with the places to rewrite marked by
< >; it becomes the left side of the proved statement, and the result of all rewrites — the right side. Several proofs under one label:+(<a>, <b>). subexpression- The part of the expression to replace; brackets nest, the innermost is rewritten first.
hint1, …- What may justify the rewrite — any proof, as after the bar of a call (below): a label with statements (a fact
a -> b, an equality=(a, b) -> ✔in either direction, a quantified fact — instantiated by matching), a theorem (its parameters inferred from the subexpression:<∈(t, ∪(a, b)) | L∈∪>), a callT[a], a proof<…>, a command:decide()— the value of the place by truth tables. term0 -> term1 …- A chain: each term is written out, the step from the previous term is justified by the hint after it; the interpreter finds where the rewrite happens. The chain proves only the rewrite
term0 -> termN; when the equality of its ends is needed, the lemmaL=ByRewriteoflogic/equality.flstates it:L=ByRewrite[| <term0 -> … -> termN>].
Properties
- Produces
- A statement: the expression as written
->the expression after the rewrites - Delivery & Label
- Into the current scope. A label on the proof (
L: <…>) holds the derived statement at this scope. - Creates scope
- No.
- Mechanism
- Reads the expression, finds for each marked place a statement whose left side it is (the hint labels first, then the current block from its end, then the enclosing blocks — shadowing), and replaces the place with the right side, innermost places first. The brackets are then removed: the expression as written becomes the left side of the new statement, the fully rewritten one its right side. In the journal of the interpreter and in the source map of the certificate the step is named
proof.
Basic examples
Inside <…>, Formall searches for a statement whose left side is the marked expression and puts its right side in place:
A first proof
Details
After a bar come the labels allowed to justify a rewrite: <x | H>. A bar with nothing after it, <t |>, rewrites only the marked places inside t and leaves its top as it is.
A proof is not a command but a form, like a label: it stands wherever a statement may come from — alone (<…>;), under a label (L: <…>), as a fact passed to a call (T[| <…>]), as the proof of a call that takes its blocks (contradict[| <…>]). It never assumes anything: every rewrite is justified by a statement already proved or assumed in this place.
How Substitution Works
- Find a statement
X -> Ywhose left sideXis the expression in<…> - Replace
<X>withY - Process nested
<…>from the inside out - Create a new statement:
original expression -> final result
Substitution steps
Label Hints
Use <expr | Label> to specify which statement to use when multiple match:
Label hints
Outer angle brackets are not needed around ➕ because it is not being substituted.
Without hints, Formall searches all visible statements starting from the innermost scope.
Nested Substitution
Angle brackets can be nested for complex chained substitutions:
Nested substitution
Chained Substitutions
Chained substitution
Several proofs together
Each proof derives one statement. Several proofs are collected by the label command + — under a label, or as one fact passed to a call:
Two proofs at once
The same as two proofs written one after the other; +(…) only lets them stand where one fact is expected.
A proof as an argument
A proof can be stored in a label or written directly where a command expects a statement:
A proof inside contradict
Rewriting with a theorem
A label hint may name a theorem — a label whose statements were proven for arbitrary atoms. A theorem hint is a call of the theorem at this place: the left side of the theorem statement is matched against the expression, and the atoms (and types) found are its arguments; the call does the rest — infers an atom that does not occur in the left side from the conditions (if on its path), over all conditions together, checks that they hold here, and asks for the axioms of a lock on the path to be assumed here. This is rw of Lean: one step instead of a call T[…] followed by a proof. The parameters of a theorem are its for atoms, then the quantifiers of its conclusion (calls), so a theorem whose conclusion is ∀{x: N | =(⊕(x, c), x)} -> ✔ rewrites ⊕(a, z) to a: c := z and x := a are both found in the term, as by T[z, a].
A theorem as a rewriting rule
A hint passes no realizations: a theorem with a lock on its path is used this way only inside that lock, where its axioms are assumed; elsewhere call it, T[… | R], with a realization R.
Hints are proofs
After the bar of a proof stands what stands after the bar of a call: proofs. A label is the simplest one; a call T[a], another proof <…> or a command may stand there too, and the statements it gives justify the rewrite. A hint is a value: it is proved where the bracket stands, and what it gives is not delivered into the block — only the outermost bracket delivers its statement.
A command whose expression is not written takes the place of the hint, as a call T[] infers what is not written: <e | decide()> decides e by the truth tables of its connectives, <e | decide(| H)> from the facts of H first (<e | decide(| H;)> — only them). In a chain the place of a step is found only after the hint, so there the expression is written: <t0 -> t1 | decide(t0 | H)>.
Hints that are proofs
Rewriting with a quantified fact
A hint may also name a fact with a quantifier, ∀{x: nat | P} -> true, when a notation("apply" | …) for the quantifier is visible. The expression is matched against the body P with x as an unknown, and is rewritten to the rule's value: no separate call H[t] is needed before the proof. Nested quantifiers are removed one by one. This is simp [h] in Lean for h : ∀ x, P x; the typical use is reflexivity — <=(t, t) | Reflexive>.
A quantified fact as a hint
Chains of rewritings
A bracket may hold a chain: <t0 -> t1 | H1 -> t2 | H2 -> … -> tn>. Every next term is written out, and the hint after it justifies the step. The interpreter finds the place where t1 differs from t0 and checks that a single rewriting of that subexpression by H1 gives exactly t1; the value of the bracket is the last term. A step without a hint is justified by any visible statement. This is calc in Lean and also … finally in Isabelle: the reader sees every intermediate term, and the writer does not mark the rewritten subterm with its own brackets.
Because the result of each step is written, it also decides what a hint alone could not: the direction of a rule kept in both directions under one label, the place among several occurrences, and parameters that occur only on the right side of a theorem (x -> plus(x, zero) rewrites a with x := a, found from the next term).
A chain of rewritings
In library/algebra/group.fl of the repository every group identity is one chain: <=(<∘(a, ⁻¹(a)) -> ∘(e, ∘(a, ⁻¹(a))) | LeftId -> … -> e | LeftInv>, e) | A=Reflexive>.
e — a fact as it stands, an instance of a quantified fact, an equality either way, a theorem. A single hint <e | H> must rewrite e in one way: statements giving the same result are fine, different results are an error (Ambiguous hint). In a chain the next term is written, so a label with several matching rules is fine there.A step up to associativity and commutativity
Moving terms around a sum — a + b + (c + d) to d + (c + a) + b — is many steps by
associativity and commutativity, each written out. A step with an asterisk, -> t′ |* A, C,
says «t′ is the previous term rearranged by the laws of these labels». The interpreter reads the laws from
the labels — f(f(a, b), c) = f(a, f(b, c)) makes f associative, f(a, b) = f(b, a)
commutative (as facts under ∀ or as theorems) — checks that both terms have the same normal form, and goes
from one to the other by single steps of these laws, each checked like a written step. So nothing new is trusted: the
log shows the single steps, and the kernel checks them. This is abel / ring_nf in Lean and
ac_simps in Isabelle, limited to rearranging.
Rearranging a sum
With an associative but not commutative operation (a group) |* Assoc only moves brackets; with several operations each one obeys only the laws given for it: x × (y + z) -> (z + y) × x |* MulComm, AddComm. In the limits of sequences of the repository (library/analysis/sequences.fl) this replaced 11-step chains by one line each.
Normalizing both terms
The labels of a |* step may also contain other rules. Labels that state no associativity or
commutativity law then rewrite both terms everywhere, left to right, as <e |* L> does (when
several rules apply to a subexpression, the first one in label order is taken). A law f(a, g(a)) = e together
with f(a, e) = a cancels an operand a against g(a′) when a′ equals
a up to the A/C laws, and drops operands e. Finally the two normal forms are compared up to
associativity and commutativity. The path between the terms again consists of single steps by the same labels, so the
kernel sees ordinary rewrites. This proves polynomial identities without copying expanded forms: it is close to
simp only [...]; ac_rfl in Lean, though not a full ring (no numerals, no collecting
a + a into 2 × a). If the normal forms differ, the error shows both.
A difference of squares
In the repository the Binet–Cauchy identity (A × B) • (C × D) = (A • C)(B • D) − (A • D)(B • C) of library/geometry/coordinates/vectors.fl is one such step after unfolding the vector operations into coordinates.
Several labels and rewriting everywhere
A hint may name several labels: <e | A, B> uses the one that rewrites e (different results are an error). With an asterisk, <e |* A, B> rewrites subexpressions of e by the labels again and again while something applies — from the inside out, left to right — like simp only [A, B] in Lean. Rules are used left to right only, and a subexpression is never folded back into one that was already unfolded, so a label may hold both sides of a definition. The typical use is unfolding nested definitions at once.
Unfolding everywhere
The lattice identities of the repository (library/sets/lattice.fl) are each one line: <⇔(<∈(t, ∩(a, ∪(b, c))) |* L∈∩, L∈∪>, <∈(t, ∪(∩(a, b), ∩(a, c))) |* L∈∪, L∈∩>) | decide()> — both sides unfolded, the Boolean identity checked by decide().
Definitions
A definition is a statement that rewrites a new atom into a lambda: if(double -> {x: nat | plus(x, x)}). Marking the atom in front of its arguments, <double>(a), rewrites it and applies the lambda (β-reduction): the result is double(a) -> plus(a, a). Since the atom is new, such a definition adds nothing that could not be written without it — it only names a term.
Unfolding a definition
In the set theory of the repository, operations are defined this way after their unique existence is proven: ∪ -> {a, b: 𝕊 | ι{c: 𝕊 | ∀{t: 𝕊 | ⇔(∈(t, c), ∨(∈(t, a), ∈(t, b)))}}}, where ι is the definite description (∃!(p) implies p(ι(p))).
show() there lists what is visible.Calls T[…]
Applying a theorem or a fact to concrete values
Overview
A call T[a, b | J] applies a proved statement where it is needed. Before the bar come the values of its parameters, after it the proofs it rests on — facts for its conditions and realizations of its lock axioms. T is a label, the result of a command (decide(X)[n]), a proof (<…>[x]) or another call (T[b][a]). The result is the instance of each statement of T, delivered into the current scope.
theoremLabel[]theoremLabel[| factLabel1, factLabel2, …]theoremLabel[argumentExpression1, argumentExpression2, … | factLabel1, …]theoremLabel[parameterName := argumentExpression, … | factLabel1, …]theoremLabel[argumentExpression1, …; | factLabel1, …;]theoremLabel- The theorem: a label whose statements are its conclusions. Everything between a statement and the place where the label is declared is the theorem's contract:
foratoms andtypeparameters to substitute,ifconditions to meet, locks whose axioms need realizations — among them the schemas of the rules the theorem was proved under (below). Also the result of a command, a proof or a call. factLabel1, …- Optional: facts for the theorem's
ifconditions and realizations of its lock axioms — labels, or what gives statements in place: a proofT[| <… |>], a command, a call. Each must be used by some condition or axiom. Conditions not given are met by visible facts;;at the end — only these. argumentExpression1, …- Optional: values of the theorem's parameters in their order — its
foratoms from the first (_skips an atom, which is then inferred), then the quantifiers of its conclusion. Positional values take the parameters not given by name. parameterName := …- Optional, mixed with positional values in any order: values by name — an atom of the theorem's
for(x := S(0)) or a type parameter (D := nat). Every atom not given is inferred from the conditions and facts (an atom that is itself in scope at the call stays itself, implicit);;after the values — all are given, none is inferred.
Properties
- Produces
- Statements (the theorem instantiated with concrete values)
- Delivery & Label
- Into the current scope. A label on the call (
R: T[a]) holds the instantiated statements at this scope. - Creates scope
- No.
- Mechanism
- Walks the path from each theorem statement's definition scope up to the label's declaration scope. Along this path:
•fornodes: collects declared atoms; these are substituted with the given expressions (by name or by position, types must agree). Atoms not given are inferred from the theorem'sifconditions, facts and realizations; an atom that is itself in scope at the call is implicit — it stays itself; another atom of the same name is never taken
•ifnodes: checks that each assumption (with atoms substituted) holds as a statement in the current scope
•type()nodes: collects declared type parameters; they are given by name (D := nat) or inferred from the types of the atom arguments
•rulenodes: a rule is its schemas, axioms of its lock (Apply, Distinct, …); they are realized like the axioms of any lock, by labels passed to the call — the label of the declaration holds its schemas (Rules on the theorem's path)
•lock()nodes: for each axiom registered in the lock, finds a realization among the labels passed to the call by comparing signatures — the lists offor,ifandruleconditions surrounding the axiom in the theorem and the realization, respectively. See Lock axioms: signature matching below.
Every label passed must be used: one of its statements satisfies a condition or realizes an axiom. In the journal of the interpreter and in the source map of the certificate the step is namedcall.
Basic examples
Call a theorem with values for the atoms of its for:
Applying a theorem
Details
The parameters of a statement are what lies between it and the declaration of its label: the atoms of for and the types of type() to substitute, the conditions of if to meet, the locks whose axioms need realizations — then the quantifiers of its conclusion. A theorem proved inside for(x: T) is called on values of x; a quantified fact ∀{x: T | P} -> true has no for of its own and is called on values of its quantifier (calls on facts). It is the one way to use what was proved: from the call of a lemma to the instance of an axiom of a theory at another structure.
Locks make a call more than substitution: a theorem proved under axioms can only be applied where those axioms are honestly supplied. The bulk of this page, from Lock axioms: signature matching onward, explains exactly how realizations are checked.
Arguments inferred from conditions and facts
Most arguments would only repeat formulas already written in the statements the theorem needs, so they are inferred. Each if condition of the theorem becomes a pattern whose unknowns are the atoms not given, and it is matched against the statements visible at the call. Matching is first-order with two higher-order cases: an atom-function applied to bound variables, like p(x) inside {x: nat | …}, receives a lambda (a Miller pattern); an atom-function applied to a term with bound variables, like
P(ι(n)) inside ∀{n: ℕℝ | …}, receives the lambda in which every occurrence of that term is
replaced by its variable — the only solution, since P cannot see n (if n remains
elsewhere, there is none); otherwise p(a, b) against h(c, d) takes p := h. The instantiation is printed in the log (// Arguments: P := A (inferred), Q := B) and then checked as usual.
When the conditions can be satisfied in several ways that give different results, shadowing decides, as in a proof: the later and the inner hide the earlier and the outer. A fact of a label passed to the call comes first, then the statements of the current block from its end, then the enclosing blocks outward. One instantiation shadows another when each of its conditions is met by the same or a nearer statement, and at least one by a nearer one; so closed facts at the top level of an imported module, or of the model in an interpretation, do not disturb inference inside a proof. If the instantiations no one shadows give different results — each is nearer in one condition and farther in another — the call stops with an error showing two of them. The names of the theorem's parameters play no part: with if(P(A)) if(P(B)) at the call, both conditions P(A), P(B) of a uniqueness theorem take the nearer P(B), and the visible A, B are passed as arguments. A label passed to the call is used first — a condition that one of its statements fits is matched only against the label, and every solution must use every label. A condition whose left side is a bare atom (P -> true) fits almost any statement; a fact label or P := … settles it. Inference only chooses the instantiation; soundness does not depend on it, because all conditions, rules and lock axioms are checked afterwards.
Inferred arguments and a fact label
Implicit atoms and type inference
A theorem whose label is declared above a type() and its for atoms is generic: it can be applied to any type. Its outer atoms work like the variables of a Lean section: inside the theory they are the very atoms in scope and stay themselves; elsewhere they are inferred from the conditions, the facts and the realizations given, or written (f := g, or in order), and the types are inferred by matching. An atom of the call site is never taken for a parameter because it has the same name: the names of a lemma's own parameters (P, Q, a) are short and common, and a Q: 𝕊 in scope is not the Q: 𝔹 of the lemma. What the conditions do not determine is written. All conditions of the theorem are checked as usual.
Implicit atoms and inferred type
The full forms Twice[f, zero] and Twice[f := f, x := zero, D := nat] mean the same.
An atom of the same name is not taken
The last call has no condition to infer a and b from, and the atoms a, b of its for are other atoms than the theorem's: they are written, Swap[a, b].
Expected error: Cannot infer argument 'a: nat
Closing a side with ;
Both sides of a call follow one rule: what is written is taken, and whatever the theorem still needs is found by itself — the values of its atoms from its conditions, the facts for its conditions among the visible statements. A ; at the end of a side says «that is all»: nothing on that side is found, and what is missing is an error, not a search.
T[a, b; | …]— everyforatom of the theorem is given, by position or by name; none is inferred or taken by name from the call site. Types still follow from the values. The constants of a definition move with their definition and are not given.T[… | H, G;]— the conditions of the theorem are met only by the facts ofHandG; a visible fact that would meet one is named in the error. Lock axioms are realized only by the proofs written in any case; a lock already in force at the call site, with its axioms unchanged, is the context, not a fact.
Closing never changes what is proved: it only narrows where the call looks. A call that passes closed passes open with the same result. Use it where the visible facts are many or contradict each other, and where a reader should see every premise in the text. The same ; closes decide, and a hint by a theorem closes inside its call: <e | T[| H;]>. Inference and what it chose are printed in the log either way.
Closed sides of a call
The last call is closed by ;: its condition P -> true at P := A is visible, but not given.
Expected error: The proofs of the call are closed by ';', and none of them meets the condition
Strictness for a whole file: --explicit
A project that wants every premise in its text runs the interpreter with --explicit. Then every call is checked as if both its sides ended with ;, every decide takes only the facts written after |, and every rewrite of a proof names its hint (<e | H>, a hint by a theorem as a call with its values and proofs). The errors name the visible fact that was found and the label to write for it. The option only forbids: a text it accepts means the same without it, because a call that gets everything written finds nothing else — the proofs written come first, and the values written are not inferred. So a strict file needs no ; anywhere, and it reads the same in any project. The option checks the text of the file itself, not the text that commands write (the proofs of decide, the schemas of rules) and not its modules.
Theorem with Conditions
When the theorem lies under an if, the call checks that the condition, with the values substituted, holds in the current scope:
Theorem with conditions
A call without arguments
If the theorem has no for atoms of its own, the call has no values: T[]. The theorem's if conditions are still checked in the current scope. (T[] is not T: the bare label stands for its statements as they are, where they were proved.)
This means you can prove something once and reuse it in any scope where the same condition holds — regardless of how you arrived there:
A call without arguments
The theorem AndImpliesOr is proved once. Then AndImpliesOr[] is called in two different scopes — each arrives at and(P, Q) -> true by a different route, but the theorem applies in both without repeating the proof. With for atoms the same call instantiates the theorem at any concrete values too.
A label of several theorems
A label may hold several theorems. A call applies each of them that the arguments and the labels fit here, and skips the others — the log says why each was skipped. At least one must apply; otherwise the error lists the reason for each theorem. The same rule holds for every place that takes a label: a hint tries all statements of its label and takes their result, if they agree.
Only the fitting theorems apply
Arguments for the quantifiers of the conclusion
The parameters of a theorem are its for atoms, then the quantifiers of its conclusion — those the theorem of a visible notation("apply" | …) removes. Values after the for atoms go to the quantifiers, outermost first: T[f, n] for a theorem T over f whose conclusion is ∀{n: ℕ | …} -> true states the instance at n at once (the chain T[f][n] — a call on the result of a call — gives the same: calls are curried), and delivers only that statement. A fact is a statement without for atoms, so H[a] on a quantified fact H is its instance at a (below). A quantifier always takes its value explicitly and by position: the name of a bound variable belongs to the formula, not to the call.
A theorem applied at the quantifiers of its conclusion
Calls on facts
A fact ∀{x: ℕ | P(x)} -> ✔ has no for atoms of its own, so its parameters are the quantifiers of its conclusion: H[c] is its instance P(c) -> ✔. The quantifier is removed by a visible rule("apply", ∀, ✔, ✔) — the rule says which atom is a quantifier and that its value ✔ carries over to the instance. The values go to the bound atoms in their order: as many as the quantifier binds at once, or more for nested quantifiers over one atom each — H[a, b] on ∀{x | ∀{y | P}} removes both. Their types fix the type variables of a polymorphic statement. A quantified fact can also be used without a call, as a hint of a proof.
A call on an axiom
Two quantified atoms
A value may be any expression of the bound atom's type, a lambda among them:
A lambda as the value
A call on a fact removes the quantifier through the theorem named by notation("apply" | A∀Apply) visible at the call: the nearest declaration for the quantifier and value is taken.
Realizations: labels for lock axioms
When a theorem uses lock() with axioms, the caller must supply a realization of each axiom — a proof that the axiom's conclusion holds in the current context. The label holding that proof is passed after the theorem, like a fact.
The realization lives outside the lock, in the calling scope, and is passed after the bar by name.
A realization passed to a call
AxiomAB is the realization: it proves that A -> false leads to B -> true in this specific context. Passing AxiomAB after the bar tells the call to use it as the realization for axiom AxiomPQ inside the lock. The same theorem FastOr can be applied with a different realization label in a different context.
A realization also tells the values of the parameters, as a fact tells them through a condition. The axiom is a pattern: its own for atoms are matched, in order, with the realization's own atoms as bound variables, and its own if conditions with the realization's, so a parameter applied to them is a Miller pattern — an axiom P(S(n)) -> true against a step proved for c gives P the lambda over c. A value is taken only when every match that gives it agrees. A lambda that only applies an atom to its own variables is that atom: {x, y: T | q(x, y)} gives q. The realization is then checked as before.
Values from the realization
A block of proof in an argument
After | a proof may be a block: headers for(…), if(…), type(…) and one statement, T[| for (y: T) S]. It proves what a label declared before the call and defined inside the block would hold — +B; for (y: T) B: S; — a theorem over y, or under the condition of the if. Nothing it proves enters the block of the call. So a lemma whose lock axiom has its own for or if is a command of its own: the block is its argument, and the result stands where the call is, outside the block's headers — as generalize stands outside its for and contradict outside its if.
A command of one's own with blocks as arguments
The values Q := a, P := a ∨ ¬a are inferred from the realizations: the blocks are theorems under a and under a -> ❌.
A call that leaves its blocks
The library names such lemmas by the step they make, in lowercase: contradict, generalize,
deduce, obtain, witness, refute. A command is word(…),
a theorem word[…]; the call reads as the step.
A lock axiom asks for a proof with blocks of its own: generalize asks for p(x) -> ✔ under for (x), deduce for Q -> ✔ under if (P), the library's obtain for a statement under for (x) if (p(x)). A proof written at a point inside such blocks — a label declared where it is defined, or a proof written in the call — is taken with the blocks it stands in, as many as the axiom asks for, and the call then stands above them: its result lies outside the for or if, which the step discharged. This is how the library introduces a quantifier (generalize[| H]), an implication (deduce[| H]) or eliminates an existential (obtain[| H]) — the commands generalize, deduce and obtain are these calls (step 189б). A label declared outside the block it is defined in holds that block (labels): the blocks it holds count too, and the call stands at the label's place.
Quantifier and implication introduced by calls
The reading with the blocks comes first: the call stands as high as it can. When the axiom's obligations cannot be met that way, the call is read as written, in its own block. Without a proof given (contradict[] inside if (Q)), the call takes the blocks it stands in itself and looks for the obligations among the facts there.
Three rules shape the result:
- Where the result stands. At the exit, above the blocks taken — when the call is written inside them. A call written beside them, in a block of its own under the exit (
if (q -> ❌) F: obtain[…, q | G]beside theforthatGleaves), keeps its result at its own place, wherecontradictcan then close thatif. - Which blocks are taken. As many as the axiom's own shape asks for, counted from the proof outwards:
foratoms andifhypotheses, never alock,typeorrule. Several atoms of oneforat once: the library'sgeneralize2 … generalize8(logic/quantifiers.fl), the quantifiers nested in the order of the atoms, each with a type of its own. - Names of the variables. A quantifier variable the theorem applies the predicate to takes the predicate's own name:
generalize2[| S]underfor (a, b)states∀{a, b | …}, not the lemma's∀{x1, x2 | …}; a name already used elsewhere in the statement is not taken, and a variable the inference invented for a term that is no atom gives no name.
Rules on the theorem's path
A theorem proved inside an enumeration type(T = a | b) or rule("bijective", f) rests on their schemas — Distinct, Cases, Injective, Column: the declaration generates them as axioms of a lock (enumerated types, rule("bijective")). Outside, they are realized like any lock axioms: the call is given the labels that realize them. Usually these are the schemas of the same kind of declaration at the call site; any statement of the same form will do — an axiom of the caller's lock, a proved theorem. A call never takes a schema by itself. The same holds for an enumeration replaced by an enumeration of the call site: its schemas of distinct values and of cases are given by a label.
The schemas have no names of their own: the language names nothing. A label on the declaration holds all the schemas it generates — a package, +ColorSchemas: type(Color = red | green) or +ABijective: rule("bijective", color) — and the call takes from a given package the schema each axiom needs. Two schemas of a package that both fit would be an error, as two fitting facts are; the schemas of one declaration never do. The axioms of a quantifier are ordinary axioms of a lock the file writes (A∀Apply, generalize of logic/quantifiers.fl): a theorem proved under them is called under the same lock, or realizes them like any lock axioms.
A rule's schema realized by the call site's rule
R is the call H[x] on a quantified fact, so it rests on the Apply schema of the rule for Q. The call site declares the same rule for G; the label GSchemas on it holds its schemas and is passed to the call like any realization. Without it the call stops with “Axiom realization not found”.
…or by any statement of the same form
No rule at the call site: the axiom GApply of the caller's own lock states the schema for G, for every predicate p, and realizes it. An axiom about one predicate only would not: the schema is about all of them.
Lock axioms: signature matching
The simple case shown above — one axiom realized by one search label — hides what a call actually checks when locks are involved. This section spells out the rule precisely. It matters when realizations contain if, for, nested locks, or when the theorem's lock axioms have their own surrounding conditions.
Which locks require realizations
Only locks that lie on the theorem's path — the parent chain from the theorem statement's definition point up to the scope where the theorem label was declared — oblige the caller. Each axiom of each such lock needs a realization. Locks that merely exist nearby — siblings of the theorem statement, locks in other branches of the tree — do not participate: the theorem was not proved under their axioms, so the call ignores them.
Sibling lock off the path
The lock L sits next to the theorem statement, not above it. The path of T runs from its axiom command through for(a, c) up to the scope where T is declared, inside Scope - it crosses neither L nor Scope, so the call needs no realization at all. A realization label passed here would be an error: every label given to a call must be used.
The signature of a path
Every statement in Formall — a theorem statement, a lock axiom, a realization — sits at some place in the tree, and has a path from that place up to where its label was declared. Along this path, three kinds of blocks add to the local world:
forblocks introduce atoms;ifblocks introduce conditions;typeblocks introduce types;ruleblocks (define,bijective) introduce rules.
The signature of a path is the multiset of these contributions across the path, organized by category. The order in which if and rule commands appear inside a single category does not matter — they are conjunctive — and neither does the relative order of for blocks of different types. What does matter is the order of for-atoms of the same type (used positionally) and the total number of contributions in each category.
What a call compares
For each axiom inside a lock on the theorem's path, the call finds its full path — from where the axiom is declared up to the theorem label's declaration scope. The same is done for the candidate realization — from where its statement is assigned up to where the realization label is declared. The call then matches these two signatures by the following rule of contraction:
The realization's signature must be no wider than the theorem's. Concretely:
for: per type, the realization must have at most as many atoms as the theorem, and atoms are matched positionally (the realization's first atom of a type pairs with the theorem's first atom of that type, etc.). The realization may declare fewer atoms; trailing theorem atoms simply go unused.if: everyif-condition in the realization's signature must appear in the theorem's signature. The realization may use fewer.rule: every rule in the realization must appear in the theorem.typedeclarations are bounded the same way — the realization may not introduce more of them than the theorem's path carries (they are compared by count: type-parameter names are placeholders bound positionally by the call, so the names themselves never matter).
The axiom statement itself is matched after the for-atom mapping is built. Nothing in the realization beyond what the theorem already assumed may appear.
The intent is single and simple: the realization must not give itself more power than the theorem allowed. If it did — by adding an extra if, an extra atom, an extra rule — it could prove things the theorem never could, and the result of the call would be unsound.
Realizations may contain locks
A realization is allowed to cross lock() nodes on its path. Each lock contributes its axioms to the realization's signature, and each such axiom must, in turn, correspond to an axiom of some lock on the theorem's path (the inner match uses equality of signatures, since lock axioms are what the realization provides — they must be exactly as strong as the theorem expects, neither more nor less).
Lock in the realization, matched by signature
The theorem's axiom c -> false is registered in lock L, with a sub-lock Inner contributing a -> true. The realization is the plain label R: its proof sits inside lock RInner, so the realization's signature includes a nested-lock axiom not(y) -> true. After substitution a -> not(y), c -> not(not(y)), the realization's nested axiom matches Inner's axiom exactly. Sound and accepted.
How the realization's locks are nested or grouped does not matter — only the multiset of axioms across all of them does. The realization may split one theorem-lock into several, merge several into one, reorder them, or change the surrounding ifs — as long as the resulting signature stays inside what the theorem allows.
Shared context between the axiom and the theorem
The lock determines which parameters belong to an axiom schema. Values declared above the lock are replaced by the theorem arguments. Parameters declared inside the lock remain universally bound in the axiom, even when the result was proved under the same for block.
Place instance parameters and conditions above the lock when the intended contract depends on those particular values. The following realization supplies the complete schema below L.
Parameters above and below the lock
The parameters a,c and the condition c -> true are above L. The call substitutes them and checks the condition. The parameters m,n and condition a -> true are inside L and remain part of its complete axiom schema.
Permutations and grouping
Because signatures are compared as multisets per category, the textual layout of the proof is free in every way that does not change the multiset:
forof different types may be reordered. A template pathfor(m: bool) for(p: nat)is matched by a realization pathfor(N: nat) for(M: bool)— grouping by type happens before comparison. Only the order of atoms within one type is positional.ifblocks may be reordered and regrouped — two nestedifs, oneifwith two conditions, or any permutation thereof contribute the same set of conditions.- Locks may be split or merged. Two sibling locks with one axiom each, or one lock with two axioms, contribute the same multiset of lock axioms. The realization need not mirror the theorem's lock structure — only its total contract.
- Multi-statement axioms are flattened.
axiom(s1; s2 | L)registers two independent axioms, exactly as two separateaxiom(s1 | L); axiom(s2 | L)commands would. A template written one way is matched by a realization written the other way.
Reordered for-types in a nested lock axiom
The template's nested axiom carries for(m: bool) then for(p: nat); the realization's mirror carries for(N: nat) then for(M: bool). Grouped by type, both are one bool-atom plus one nat-atom — the signatures agree.
Why this is sound
The whole construction rests on a single guarantee: a call delivers a theorem's conclusion only when the realization honestly supplies every premise the theorem was proved under, up to the call's substitution. Nothing weaker is accepted, and nothing the theorem did not assume can sneak in. Three facts together close the loop:
- Requirements may only shrink. An
if-condition, afor-atom, or arulerule on the realization's path is something the realization demands of its context. Demanding less means the realization proved its statement under stricter circumstances — always safe. Demanding more is rejected, because the theorem never sanctioned that extra leverage. - Provided facts match pairwise-exactly, and never exceed the template. A nested lock axiom is something the realization hands back as established. The realization's set of nested axioms must be a subset of the template's — relying on fewer local assumptions is a stronger proof and is accepted (this weakening is what makes derived theorems possible); an extra nested axiom the theorem never sanctioned is rejected. Each nested axiom that is present must match a template one exactly — statement,
for-atoms,if-conditions,rulerules and the count ofruletype parameters on its own chain: handing back a stronger or weaker variant of an expected assumption would silently change what the theorem relied on. - Shared premises are never skipped. The theorem's conditions are checked against the calling scope. Conditions inside an axiom's lock also remain in that axiom's schema. A theorem with an unmet shared
ifis refused outright, even if the realization itself looks fine.
An axiom holds under its own lock. It can supply a realization there because the result stays under that lock. Outside a closed lock, its axiom remains an assumption of the realization's contract and cannot be discarded. A theorem may cross a lock only when its full contract matches the required scheme; an unconditional conclusion requires a proof of every premise.
Type Parameters
Types in Formall form their own small language, separate from expressions. A type is either a declared primary type (like bool, or a parameter introduced by type()) or a function type built from types, like [bool -> bool]. There are no operations on types — they are never computed, compared by value, or produced by expressions; the only things that ever happen to a type are declaration, substitution, and structural equality checking. A type parameter is an atomic placeholder name: it has no content of its own, so a parameter is given by its name among the values (U := bool) or, usually, inferred from the types of the atom arguments. A type argument may be a full type tree, not just primary names — [bool -> bool] is a valid instantiation of U, and the substitution rewrites every occurrence inside atom types structurally, so [U -> bool] becomes [[bool -> bool] -> bool].
When a theorem uses type() to declare a type parameter, the concrete type is inferred from the arguments, or given by name (T := ℕ):
Type parameters
The type parameter T is matched to ℕ. All atoms declared with type T (like =, x, y) are substituted with atoms of the matching concrete type.
Type parameters and lock axioms together
Type substitution composes with signature matching. If a lock axiom's own path declares for-atoms whose types mention a type parameter, those types are substituted by the call's types (inferred or named) before the for-categories are compared. A realization written directly in the concrete type matches a template written in the parameter:
Type parameter in a lock axiom
The template axiom f(u) -> true is parameterized over U both in the function type [U -> bool] and in the atom type of u. The call substitutes U -> bool, f -> not, u -> y; the expected realization becomes not(y) -> true, which the lock-label RL provides. Atom types on the axiom's own path are compared after the same substitution, so a realization declared over the concrete type lines up with a template declared over the parameter.
A theory as a block
A theory is a block whose parameters are its signature and whose assumptions are its axioms: type(M) for(op: [M, M -> M]; e: M) if(…) if(…) { … }. A theorem labelled T:: inside the block is declared outside it, so the type, the atoms and the axioms are its parameters and conditions. Inside the block the theorems serve as hints as usual (the parameters are the atoms in scope); outside, a call applies a theorem to another structure: the axioms of that structure, passed as labels, determine the type and the operations. This is a locale in Isabelle or a structure with an instance in Lean; in the repository, library/algebra/group.fl is the group theory written this way and z2.fl applies it to the integers modulo 2.
A theory and its instance
Commands
Command Groups
All commands of the language, grouped by what they do with scopes and statements
Overview
Every Formall command does one of a few things with the scope tree: it opens a scope (a context the statements inside depend on), passes through without creating a context, adds statements to the current scope, moves a result above an enclosing scope, generates ordinary commands for you, or works with labels. Commands of one group share their boundary and label behaviour, so learning one of them explains the others.
Reading signatures. Each command page starts with its signatures and, under them, what to pass as
each parameter of that command. The names in signatures are placeholders, not names to declare: a name ending in
Label is a label (a command that returns statements can usually stand there too), …Atom /
…AtomName — an atom or its name, …Expression — an expression, …Type — a
type. Arguments come in two sides: first the expressions — terms and statements left -> right,
written as they are, without quotation marks — then, after a bar |, the proofs: labels, proofs <…>,
calls and commands that give statements (axiom(P | L)). Quotation marks are left only for texts that are not
terms: file paths and the kinds of rule("…") and notation("…").
Two forms of the language are not commands at all, though they derive statements as commands do: a
proof <…> and a call T[…].
They are described with the basics and listed below among the inference steps.
| Group | Commands | What they share |
|---|---|---|
| Context | type, for,
if, lock,
axiom, rule |
Open a scope; what is proved inside depends on it. Boundaries for closing commands. |
| Transparent headers | import, notation |
Stand in a header chain or end with ;, but are not a context: commands pass through them. |
| Inference steps | <…>, T[…],
define |
Add new statements to the current scope. |
| Calls that leave their blocks | contradict[| S], generalize[| S], deduce[| S], obtain[| S] |
A call whose lock axiom asks for a proof under for or if takes those blocks and delivers the result above them, removing the assumption or the variable. |
| Generators | decide |
Writes ordinary if / call / <…> text for you; the checker sees only that text. |
| Tools | show |
Print what is visible at the place (scope, facts, labels) or search for text; produce nothing. |
| Labels | + - * ^, expect( ) |
Combine and compare collections of statements; no logical content. |
A second way to look at the same commands is the trusted base: the axioms, the locks, the
enumerations and the two rules — define (from ∃!)
and bijective. The steps of a proof rest on theorems the file writes and names: a call on a quantified
fact removes its quantifier through notation("apply" | A∀Apply), rewriting by equality in proofs through
notation("hint" | …), and the introduction of a quantifier or an implication, the elimination of an
existential, the closing of an assumption are calls of theorems (generalize, deduce,
obtain, contradict of the library). tools/trust.py lists what each theorem relies on.
Context
Context commands are block commands: they open a scope that lasts until } (or until the end of the
enclosing block). A statement proved inside the scope depends on the scope's header, and outside of it the statement
becomes a theorem with that header turned into parameters and conditions, which a call T[…] fills in again:
type(T)andfor(x: T)introduce parameters — types and atoms (⋀ in Isabelle/Pure).type(T = a | b)also declares an enumeration.if(A -> B)introduces assumptions (⟹).lock()is an assumption block whose assumptions are added later, from inside, byaxiom(… | L); a theorem proved with them receives them as parameters that a call realizes.rule("…", …)introduces rules of the logic; a theorem proved under a rule needs that rule wherever it is applied.
All of them are boundaries: closing commands stop at them, and a label on type,
lock or rule names the scope instead of capturing statements.
Transparent headers
import("file.fl") and notation("kind", …) may stand in a header chain
(for(∘, e) notation("infixl", ∘, 70) if(…) { … }) or end with ;, but they are not a
context: closing commands pass through them, and theorems get no parameters or conditions from them.
They are not one command, because they do different things. notation changes only how text is read and
printed: if all operators were written in prefix form and abbreviations expanded by hand, the proof would stay the
same. import brings atoms, axioms, rules and theorems of another file into scope; without it the proof
does not check. It also has its own permissions (--import-root, formall.project).
Inference steps
These forms and commands add statements to the scope they are written in; a label on them captures those statements there.
<…>— rewriting: angle brackets, hints<e | L>, chains<t0 -> t1 | H -> t2>.T[…]— applying a theorem: parameters are instantiated, conditions are discharged by facts, lock axioms are realized; on a quantified fact,L[a], — removing its quantifier (∀-elimination).witness[t | L]— a call of the library's theorem: replacing a term in a fact by a quantified variable (∃-introduction).define(f := …)— a new atom with its defining theorem.
Calls that leave their blocks
A step that takes statements proved inside a scope and delivers the result above it, removing what the scope assumed, is a call of a theorem whose lock axiom asks for a proof of that shape; the library proves the theorems once:
| Call | Takes | Result above the blocks |
|---|---|---|
contradict[| S] | if(A -> B) | The assumption is false: the contradiction flips it (A -> ❌ for A -> ✔) |
deduce[| S] | if(P) | P ⇒ Q for the Q proved inside |
generalize[| S] | for(x) | ∀{x | …} |
obtain[| S] | for(x) if(p(x)) | The statement itself, when it does not mention x (∃-elimination) |
They share all of their mechanics:
- the proof after the bar is a label, a proof or a nested call; a nested call delivers above its own blocks
first, and the outer call stands where that result stands, so the calls compose from the inside out:
generalize[| deduce[| contradict[| …]]]; - a label on such a call captures the result at the delivery scope, not where the call is written;
- context commands a call does not take (
type,lock,rule) are boundaries: the result cannot be carried across them.
contradict and deduce close the same if; which one to use is the author's
decision, so each step names what it does.
Generators
decide(X) computes the value of X from facts by the tables of the functions over
finite types. It produces ordinary if / call / <…> text that is parsed and checked
like hand-written code; it adds nothing to the trusted base. The hints <e | decide()>
and <e |* A, B> inside proofs work the same way. A case split by hand is a
branch if (P -> ❌) S and the same step S after it (decide).
Tools
show() prints the context of its place into the log: the enclosing
for / if (which one a closing command will close), the nearby facts and the labels of the file;
show("text") searches visible facts and labels, imported ones included. It produces no statements — the
proof is the same with or without it.
Labels
Label commands treat a label as a collection of statements: + union, - difference,
* intersection, ^ symmetric difference. expect( ) checks that collections are equal and
reports the difference otherwise; the commonly used check “these statements were proved” is
expect(a -> b; … | L). Declaring, defining and extending labels (+L;, L:,
L::, L+:) is described in Labels.
Context
type
Declaring new types
Overview
The type(...) command declares new primary types. Types are the foundation of Formall's type system.
type(typeName)type(typeName1, typeName2, typeName3)type(enumTypeName = valueAtomName1 | valueAtomName2 | valueAtomName3) // enumerated typetype("'typeVariableName") // a type variable: atoms with it in their type are polymorphictypeName1, …- Names of new types. Inside a theorem (a block whose statements are called elsewhere) a declared type is a parameter: a call substitutes another type for it.
enumTypeName = value1 | …- An enumeration: the type and its values (atoms of that type), every two different, every element one of them. The declaration generates the axiom schemes of distinct values and of cases that
decide,casesand the lemmacontradictof the library rest on; a label on the declaration holds them (+ColorSchemas: type(Color = red | green)), to pass to a call. - "
'typeVariableName" - A type variable (a name starting with
'): an atom whose type contains it is polymorphic, a statement with it is a schema; each use instantiates it.
Command Properties
- Group
- Context
- Produces
- Nothing for a plain type; an enumeration generates the axiom schemes of distinct values and of cases
- Delivery & Label
- A label on
typeholds the schemes of an enumeration (+ColorSchemas: type(Color = red | green)), to pass to a call. - Creates scope
- Yes.
- Mechanism
- Declares the types in its scope; inside a theorem a declared type is a parameter that a call substitutes. An enumeration also declares its values as atoms of the type.
Basic examples
Type names can use mathematical Unicode symbols:
Declaring types
Enumerated types
type(T = c1 | c2 | … | cn) declares the type T and its values: atoms c1 … cn of type T. They are constants, not parameters of theorems. Two rules come with the declaration:
- distinct values — two values of one expression give anything: from
X -> ciandX -> cjfollows everya -> b(Distinct); - exhaustion — the type has no other elements: what follows from each value of
Xfollows (Cases).
For a function between two enumerated types that takes every value once (a grid puzzle), see rule("bijective"). In Lean this is inductive Color | red | yellow | green, in Isabelle datatype.
What the declaration writes
The rules are not built into the interpreter. The declaration writes them as text of the language: a lock under the declaring block, one axiom per rule, and the code after the declaration lies inside that lock. For +Abool: type(bool = false | true) the text is this (names with a dot are internal, '𝓐 is the type of «anything»):
for (𝓨: bool; 𝓪, 𝓫: '𝓐) {
// Distinct: two values of one 𝓨 give anything
+𝓟: lock() { axiom(𝓨 -> false; 𝓨 -> true | 𝓟); bool.Distinct.false.true: axiom(𝓪 -> 𝓫 | bool.Enumeration); }
// Cases: what follows from each value follows
+𝓒: lock() {
if (𝓨 -> false) axiom(𝓪 -> 𝓫 | 𝓒);
if (𝓨 -> true) axiom(𝓪 -> 𝓫 | 𝓒);
bool.Cases: axiom(𝓪 -> 𝓫 | bool.Enumeration);
}
}
// Flip, for two values only: a lemma, not an axiom. If 𝓨 -> true follows from 𝓨 -> false, then 𝓨 -> true.
// Proved by Cases: the case false is the premise, the case true is its own hypothesis.
for (𝓨: bool) +𝓟: lock() { +𝓡0, +𝓡1; if (𝓨 -> false) 𝓡0: axiom(𝓨 -> true | 𝓟); 𝓡1: if (𝓨 -> true) {} bool.Flip.false.true: bool.Cases[𝓨 := 𝓨, 𝓪 := 𝓨, 𝓫 := true | 𝓡0, 𝓡1]; }
for (𝓨: bool) +𝓟: lock() { +𝓡0, +𝓡1; 𝓡0: if (𝓨 -> false) {} if (𝓨 -> true) 𝓡1: axiom(𝓨 -> false | 𝓟); bool.Flip.true.false: bool.Cases[𝓨 := 𝓨, 𝓪 := 𝓨, 𝓫 := false | 𝓡0, 𝓡1]; }
With three values there are three Distinct axioms (one per pair), a Cases axiom with three branches, and no Flip. The label on the declaration (Abool) holds all of them. A call Abool[…] tries each one; the ones whose conditions and lock do not fit are skipped (the log says which), the one that fits is applied. The kernel sees only these axioms: it has no rule for enumerations.
Why contradict works
The library proves the contradiction lemma from these axioms in one line (logic/bool.fl, here with false/true for ❌/✔):
+L: lock() if (P -> true) { +AX: axiom(X -> false; X -> true | L); contradict: Abool[| Abool[_, P, false | AX]]; }
Read it from the inside out:
Abool[_, P, false | AX]— the values are𝓪 := P,𝓫 := false;𝓨is left to the realization.AXholdsX -> falseandX -> true: exactly the two axioms of the lock𝓟of Distinct, so𝓨 := X. Of the four schemas only Distinct fits. Result:P -> false— insideif (P -> true), from the contradiction (ex falso).Abool[| …]— no values written; the proof after the bar isP -> falseunderif (P -> true). Flip.true.false has exactly this lock axiom:if (𝓨 -> true) 𝓨 -> false. The call takes the if block as its realization, with𝓨 := P, and stands above it:P -> falseoutside theif, inside the lockL.- The label
contradictcatches it there. The lemma says: for anyP, X, if underif (P -> true)bothX -> falseandX -> truehold, thenP -> false. The two axioms ofLare what a user must show.
So if (Q -> true) contradict[| works like this: the proof after the bar gives not(Q) -> false, the fact not(Q) -> true is visible, together they realize the lock of contradict with X := not(Q); the call takes the if and delivers Q -> false above it. The second half of the lemma (contradict+, under if (P -> false)) gives P -> true the same way through Flip.false.true.
The schemas by hand, and contradict from them
The same text as the declaration writes, with readable names and without the second Flip. The three lines of contradict are the three steps above. A three-colour version is in Leaving a Block.
Working with the values
The booleans are the case of two values: refuting one value gives the other, so a case split is a branch if (P -> false) and the same step after it (decide). refute of logic/equality.fl turns x = c -> false into a refutation of x -> c the same way. Two values of an expression of any type contradict too, without an enumeration: the fact a = b -> false says they differ, and distinct[_, a, b | A, B] of the same file closes the assumption (A, B hold X -> a and X -> b). Over more values decide finds the value of an expression from the facts and the tables of the functions; its lemma is a call of Cases with a refutation by Distinct in each branch.
Exhaustion by elimination
decide tries the three values: stop(red) -> true and stop(yellow) -> true contradict the fact, so the signal is green.
Subtypes
A subtype makes a new type out of a part of an old one: the type and its embedding are declared as usual, and
subtype states that the embedding is a one-to-one map onto the elements with the property:
type(ℝ⁺) for(ι: [ℝ⁺ -> ℝ]) +Sub: subtype(ι, {x: ℝ | 0 < x}, ∃, ⇒);
The elements of ℝ⁺ are then exactly the positive reals, through ι. This is typedef in Isabelle/HOL and Subtype in Lean. A subtype is how a structure
built inside another one — positive reals inside ℝ, natural numbers inside ℝ, real numbers as sets — becomes a type
to which a theory can be applied with import with substitution.
What «true» means here. subtype(ι, φ, ∃, ⇒) takes an embedding
ι: [S -> T] declared before it, a property φ: [T -> 𝔹] — a name or a set
{x: T | …} — and the existential quantifier and the implication its premises are written with. The property is an expression of the truth type (𝔹), and
the subtype does not evaluate it: «y has the property» is a statement φ[y] -> ✔ to be proved
like any other. The value of truth and the other notions come from the theorems named at the command:
∀ from notation("apply" | A∀Apply), = and ✔ from
notation("hint" | A=Rewrite, …); the quantifiers and the equality must be polymorphic ('α, as in the library), so that
they speak about the new type too. The set may be empty. The command introduces no names; it writes three premises,
and a label on it receives them:
| Statement | Meaning | |
|---|---|---|
| S1 | ∀{u: S | φ[ι(u)]} -> ✔ | the embedding lands in the set |
| S2 | ∀{u, w: S | ι(u) = ι(w) ⇒ u = w} -> ✔ | the embedding is injective |
| S3 | ∀{y: T | φ[y] ⇒ ∃{u: S | ι(u) = y}} -> ✔ | every element of the set is an image |
So a property is proved for an element of the subtype by S1, an element of the subtype is obtained from an element
with the property by S3, and equality in the subtype is decided by its images in T (S2). Applied to a
label with the three statements, a call uses those that fit its arguments: Sub[a]
with a: S gives S1 and S2, Sub[y] with y: T gives S3. Operations on the
subtype are defined with define from unique existence (the value of
a ⊙ b is the element whose image is ι(a) × ι(b)).
Nothing is trusted here. subtype is a generator, like decide:
it writes what could be written by hand. S is a type
parameter of the type block, the embedding a parameter of the for block, and S1–S3 are
the axioms of a lock under the command; the code after it continues inside the lock. The embedding is
an ordinary atom of for: a constant defined under it takes it as an argument, as it takes the other
atoms of the block. A theorem
proved there holds for every type and embedding satisfying S1–S3, so nothing new follows about the old notions. An
interpretation of a theory with a subtype realizes S1–S3 by the subtype of its own copy.
A subtype may be empty
No proof of nonemptiness is needed: any Formall type may be empty. A variable introduced by for is
hypothetical, so a contradiction under it cannot be moved outside its scope (a contradiction closes the assumption it
stands under, not a for), and S1–S3 are hypotheses of the subtype's lock. If no element satisfies φ,
the subtype is an empty type: an element u of it would give φ[ι(u)] and a contradiction,
but only for that u, so nothing new follows about T. Nonemptiness is assumed or proved
exactly where a proof needs an element.
A result about T proved through a subtype leaves the subtype's block with a model of it (a type and an
embedding satisfying S1–S3): Leaving a Block.
The embeddings of nested subtypes compose to give an embedding of the inner type into the original one; they do not automatically supply operations or prove the axioms of a mathematical theory.
A function with a restricted domain does not always need a subtype. A predicate
D: [T -> 𝔹] can restrict statements to arguments satisfying D(x),
including an empty domain. If a separate domain type is useful, declare the subtype. A limit at a point needs a stronger condition for uniqueness:
every punctured neighborhood of that point must contain a domain element.
Even numbers as a type
The subtype declaration supplies an embedding into the original type, membership in the defining set, injectivity of that embedding, and a preimage for every element of the set.
Scoping
Types are scoped to the block of their type command:
Type scoping
for
Declaring variables and universal quantification
Overview
The for command declares atoms (variables and functions) and introduces universal quantification scope. It's one of the most fundamental commands in Formall.
for(atomName: type)for(atomName1, atomName2: type)for(atomName: [argumentType -> resultType])for(atomName: type) { ... }atomName: type- The atoms to declare and their type; several of one type share it (
for(x, y: ℕ)), groups are separated by;(for(x: ℕ; p: [ℕ -> 𝔹])), as in Pascal. A function type is[argumentTypes -> resultType]. Inside the block the atoms are arbitrary: what is proved about them holds for every value (generalize, and a call substitutes them). { … }- The scope of the atoms. Without braces
for(…)is a header of the next command, or with;a declaration to the end of the enclosing block or file.
Command Properties
- Group
- Context
- Produces
- Nothing —
fordeclares atoms but does not produce statements - Delivery & Label
- N/A. Labels are not allowed on
for. - Creates scope
- Yes.
- Mechanism
- Introduces atoms (variables, functions) into scope with specified types.
Basic examples
Simple Values
Declaring values
Functions
Declaring functions
Multi-line Declarations
A single for can declare atoms of different types by separating type groups with commas after their type:
Multi-type declaration
Universal Quantification
A for command introduces a scope where statements proven inside hold "for all" values of the declared variables. Combine with generalize[| …] (a call that takes the for) to lift results out:
Universal proof with generalization
For without Braces
Without braces, for still creates a scope — it just contains only the next command (and its scope). This naturally supports chaining:
Declaration only
Scoping Rules
- Atoms are visible inside the
forscope and cease to exist when it closes - Inner
forcan shadow outer declarations
for doesn't iterate. It introduces a variable that represents "any" value of its type.if
Introducing assumptions and conditional reasoning
Overview
The if command introduces assumptions (hypotheses) that hold within its scope. It's the primary way to work with conditional statements in Formall.
if(expression -> expression) { ... }if(leftExpression1 -> rightExpression1; leftExpression2 -> rightExpression2; ...) { ... }+hypothesisLabel: if(expression -> expression) { ... }if(expression) // with notation("default", ✔): if(expression -> ✔)leftExpression -> rightExpression, …- The assumptions: statements that hold inside the block. Without
->(whennotation("default", …)is declared) the statement gets the default value of its type:if(P)isif(P -> ✔). hypothesisLabel- Optional: a label on
ifholds the assumptions themselves — to name them in hints and as facts of calls. { … }- The block where the assumptions hold. Without braces
if(…)is a header of the next command, or with;a declaration to the end of the enclosing block.
Command Properties
- Group
- Context
- Produces
- Statements (assumptions)
- Delivery & Label
- Into itself — the
ifcommand IS the scope where its statements live. A label onifcaptures its assumptions and is scoped to theifscope. - Creates scope
- Yes.
- Mechanism
- Parses the argument string as a list of statements separated by
;. Each entry follows the formatexpression -> expression. Left-hand sides that share the right-hand side are separated by commas:if(P, Q -> true; R -> false)is equivalent toif(P -> true; Q -> true; R -> false). All resulting statements are introduced as assumptions inside theifscope.
Basic examples
Inside an if scope, the assumed statements are available:
Basic if usage
Details
With notation("default", "true") in scope, a statement without -> means -> true: if(p) is if(p -> true).
Multiple Statements
You can introduce multiple statements at once, separated by ;; a comma joins left-hand sides that share the right-hand side (if(P, Q -> true; R -> false)):
Multiple assumptions
Proof by Contradiction
The most common pattern: assume the opposite, derive a contradiction, and call contradict (the lemma of the library, logic/bool.fl) to flip the assumption:
Proof by contradiction
Case Analysis
Use nested if commands for case analysis (proof by cases):
Case analysis
If without Block
Without braces, if still creates a scope — it just contains only the next command (and its scope):
Chained if
contradict[] only closes the nearest (inner) if. The outer if then simply completes.
Labels and Scope: if Delivers into Itself
Since if delivers its statements into its own scope, a label placed on if captures those assumptions. This label can then be used inside the scope — or passed out to commands that operate at other levels:
Labels on if: scoping and usage
Label A is declared at the if level and captures its assumption. It is accessible inside the block and in nested blocks.
How contradict works with if
contradict[| S] is a call that takes the if it stands in: its lock axiom asks for two values of one expression under the assumption. When it succeeds inside an if scope:
- The assumed statement's value is flipped (by the schemas of the enumeration
type(bool = false | true), from which the lemma is proved) - The flipped statement becomes proven in the outer scope
- The
ifscope typically immediately closes (as continuing within a contradictory scope is pointless — from a contradiction, anything can be proven)
if command must have exactly one statement for contradict to flip it: the axiom of the lemma asks for an if of one condition. Multiple statements in one if cannot be flipped at once.lock
Creating axiom scopes for theorems
Overview
The lock() command creates a scope for axioms. Axioms defined within a lock act as parameters that must be "realized" when the theorem is called (T[… | R]).
+lockLabel: lock() { ... }+lockLabel: lock(); // a declaration to the end of the enclosing blocklockLabel- The label
axiom(| lockLabel, …)adds axioms through. The lock takes no arguments. { … }- Where the axioms hold: everything proved inside is a theorem under them, and a call applies it elsewhere only with a realization of each axiom.
Command Properties
- Group
- Context
- Produces
- Nothing itself — axiom adds statements to it
- Delivery & Label
- A label is required (
+𝒜: lock()):axiom(… | 𝒜)names the lock by it. - Creates scope
- Yes.
- Mechanism
- Opens a scope whose axioms are parameters of everything proved inside: a call of such a theorem from outside the lock needs a realization of each axiom it rests on — a proved statement of the same form — after
|. Inside the lock the axioms are visible facts.
Basic examples
Lock with axioms
Why Lock?
A lock is a scope whose internal rules are defined by its axioms. Each axiom command registers a statement in the lock's axiom list — a record of all conditions that must be satisfied when the theorem is applied. You cannot create statements "from thin air"; every axiom belongs to a specific lock.
When someone calls a theorem, the interpreter inspects each lock's axiom list and requires a realization for every axiom written before the theorem — a proof in the current context that the axiom's statement holds. The realization is checked by signature: it may rely on the same conditions the axiom did, or on fewer (a realization proved under fewer premises is still sound), but never on more. If any axiom cannot be realized this way, the call fails. This is what makes theorems trustworthy: they cannot be applied in contexts that don't satisfy their premises. See signature matching for the precise rule.
Axioms hold within their lock. Closing the lock does not make them facts outside it. A realization used outside a lock keeps that lock's full contract; every premise must match the required scheme. An unconditional result needs a proof of its premises. For assumptions used throughout a file, keep their lock open to the end of the file.
The axiom Command
Inside a lock, use axiom to declare conditional axioms:
axiom(expression -> expression | lockLabel)The lock label must be passed as the first argument. Axiom statements follow the same syntax as if statements.
Axiom requires lock label
Using Theorems with do
When you call a theorem proved in a lock, the interpreter checks that all axioms can be realized from the current proof context. See calls and Peano Arithmetic for full examples.
Nested Locks
A lock can contain another lock. This is a common technique for creating theorems that require axiom realizations containing their own inner axioms:
Nested locks
An inner lock inside an outer lock is a valid pattern for creating theorem templates.
lock() nodes. The interpreter will verify, by comparing signatures, that every axiom of every lock on the realization's path is matched by a corresponding lock axiom on the theorem's side. See Lock axioms: signature matching for details.Sealing a Lock
After all axioms have been defined, you can undeclare the lock label to prevent any further axioms from being added. Existing axioms and theorems built on them remain fully functional — only the ability to call axiom with this label is removed.
Sealing a lock with undeclaration
After -𝒜;, the lock is sealed — no new axioms can reference it.
Boundary Rules
Locks act as boundaries for calls that take the blocks their proof stands in: such a call takes for and if blocks only, never a lock (or a type / rule) — a result proved under a lock leaves it only as a theorem whose axioms a call realizes.
axiom
Declaring conditional axioms in locked scopes
Overview
The axiom command declares statements inside a lock() scope. These axioms act as parameters — when the theorem is called, T[… | R], the axioms must be realized by the current proof context.
axiom(statement1; statement2; … | lockLabel)lockLabel- The label of the
lock()the axioms belong to; theaxiomcommand is inside that lock (possibly underfor,ifand other locks — they become the axiom's own context). statement1; …- The axioms, written as statements
left -> right(or without->withnotation("default", …)). A theorem proved under the lock needs a realization of each of them wherever it is called.
Command Properties
- Group
- Context
- Produces
- Statements (axiom declarations within a lock scope)
- Delivery & Label
- Into the current scope. Additionally registers each axiom in the lock's axiom list (for later matching by calls). A label on
axiomcaptures the declared axiom statements at this scope. - Creates scope
- No.
- Mechanism
- Reads the statements, creates them, delivers them to the current scope, and registers each in the lock label's axiom list. If the
axiomis insideifcommand (between the current scope and the lock), those conditions become part of the axiom's requirements when matched by a call.
Basic examples
Axioms are always declared inside a lock and reference the lock's label:
Basic axioms
Details
Axioms hold within their lock. Closing the lock does not make them facts outside it. A realization used outside a lock keeps that lock's full contract; every premise must match the required scheme. An unconditional result needs a proof of its premises. For assumptions used throughout a file, keep their lock open to the end of the file.
Conditional Axioms
When an axiom is inside an if command, it only takes effect when that condition holds. This is how you create theorems with preconditions:
Conditional axiom
Axiom Label Requirement
The first argument must be a label declared on a lock(). This ensures axioms are properly scoped:
Label requirement
The lock label must be the first argument to axiom
axiom and lock(), all statements would be unconditional.Why Axioms Need a Lock
Every axiom must reference a lock label. This is not a technicality — it reflects a fundamental design principle. A lock is a scope whose internal rules are defined by its axioms. You cannot create a statement "from thin air" with axiom; you must specify which lock this axiom belongs to.
Each axiom is registered in its lock's axiom list. This list is what a call inspects when applying a theorem: for every axiom that stood in the lock when the theorem was proved (an axiom written later is no obligation of it), the call must find a matching realization — a proof in the current context that satisfies the axiom's statement (and its if-conditions). If any axiom cannot be realized, the call fails.
Think of it this way: a lock says "these are the rules of my world", and each axiom adds a rule. When someone calls the theorem, they must prove that every rule holds in their world. This is what makes theorems trustworthy — they cannot be applied in contexts that don't satisfy their axioms.
-𝒜;). This prevents any further axiom calls while keeping existing axioms intact. See Sealing a Lock.See Also
rule
Rules of the logic: definitions by unique existence, bijections
Overview
The rule command declares the two rules of the logic that generate axiom schemes: rule("define", ∃!, ✔) says which atom means «there exists a unique», so that define(f | T) may define an operation from a proved unique existence; rule("bijective", f) says that a function between two enumerated types takes every value once (rule("bijective")). Each is part of what you trust. Everything else that shapes a step is written in the file as theorems and named: an enumeration type(𝔹 = ❌ | ✔) carries the schemas of distinct values and of cases, and the library proves from them the lemma contradict that closes an assumption by a contradiction (logic/bool.fl); the axioms of a quantifier or an implication are ordinary axioms of a lock (A∀Apply, generalize in logic/quantifiers.fl), and the steps are calls of them — generalize[| H], deduce[| H], obtain[| H]; the theorem a call on a quantified fact or a hint uses is named by notation("apply" | A∀Apply) and notation("hint" | …), which generate nothing.
rule("define", quantifierExpression1, …; truthExpression)rule("bijective", functionAtom1, …)quantifierExpression1, …define: the quantifiers «there exists a unique» — atoms of type[[T -> V] -> V](∃!).truthExpression- The value of a true statement of the quantifier's type (
true,✔). functionAtom1, …bijective: functionsf: [D -> C]between enumerated types of one size, each declared a bijection.
Command Properties
- Group
- Context
- Produces
- Nothing —
ruleconfigures the proof system but does not produce statements - Delivery & Label
- Into itself. A label on
ruleholds the schemas the declaration generates (a package to pass to a call); only+Label:syntax is allowed (declaration),Label:(definition without+) is an error. - Creates scope
- Yes.
- Mechanism
- Parses the first string argument as the rule name, checks the types of the atoms given, and generates the axiom schemes of the rule in a lock of its own.
Basic examples
A bijection between enumerations
The rule says that color is a bijection: no two houses have one colour, and every colour is in some house. decide finds the values from the facts by the schemas of the enumerations and of the rule.
Details
Rules are part of what you trust — a false rule is as dangerous as a false axiom, and tools/trust.py lists the rules every theorem relies on. Everything that only changes how text is read (operators, abbreviations, default values, the theorems of steps) is notation, not a rule. Types and locks used to be rules too; they are now separate commands — type() and lock() — and they share the label and boundary behaviour described below.
Available Rules
| Rule | Purpose | Details |
|---|---|---|
define |
Quantifiers «there exists a unique» that allow define(f | T) |
rule("define") |
bijective |
Functions between enumerated types that take every value once | rule("bijective") |
Before step 189в the rules contradict, apply, generalize, deduce, obtain, witness and equality generated the axiom schemes of the steps of a proof. Now these axioms are written in the file, where a reader sees them (Command Reducibility), and the steps are calls; nothing is generated and nothing is hidden.
Labels on rule, type and lock
A label on rule (and likewise on type and lock) does not capture any statements proved under it. A label on a rule or an enumeration holds the schemas the declaration generates — a package, +ABijective: rule("bijective", color), +AColor: type(Color = red | green) — and a call takes from a given package the schema each lock axiom of the theorem needs (Rules on the theorem's path): contradict of the library is proved by A𝔹[| A𝔹[_, P, ❌ | AX]], the schemas of cases and of distinct values of +A𝔹: type(𝔹 = ❌ | ✔).
As a lock label for axiom
When a label is placed on lock(), it can be used as the first argument of axiom to register axioms within that lock. This is the only way to create axioms:
Label on lock for axiom
+Label: (declaration) is allowed on rule, type and lock. Using Label: (definition without +) is an error, because these commands produce nothing to define with.Boundary Role
Any rule, type or lock command acts as a boundary: a call that takes the blocks its proof stands in takes for and if blocks only, never one of these — a result proved under a rule or a lock rests on its schemas or axioms, and leaves it only as a theorem whose axioms a call realizes.
Transparent headers
import
Using another file as a context
Overview
The import command makes the contents of another .fl file a context for the code that follows — exactly like for or if make their atoms or assumptions a context. Types, atoms, assumptions, rules, locks and labels of the imported file are visible inside the import, and nowhere else.
import("filePath");import("filePath") { ... }import("filePath1") import("filePath2");import("theoryFilePath", typeParameterName := argumentType, parameterAtomName := functionExpression, otherParameterAtomName := argumentExpression); // interpretationimport(namespaceName := "theoryFilePath"); // namespace: namespaceName.memberNameimport(namespaceName := "theoryFilePath", typeParameterName := argumentType, …); // interpretation in a namespace- "
filePath" - The file to import, relative to the importing file; by default only inside its directory, the project root (
formall.project) and--import-rootdirectories. Its theorems and declarations become visible here; it is checked once, as a module. typeParameterName := argumentType, …- An interpretation: the theory's type parameters, atoms and axioms are given values here (
G := ℤ, ∘ := +, e := 0); its axioms must then be facts here, and its theorems hold for these values. namespaceName := …- Optional: everything the import brings is visible as
namespaceName.name(an operation asa namespaceName.+ b), so two imports of one theory do not clash. { … }- Optional: the imported content is visible only in the block. Without it, the code after
importis at the top level of the file.
Command Properties
- Group
- Transparent headers
- Produces
- Nothing by itself — the imported file's commands produce their statements as usual
- Delivery & Label
- No label is allowed on
import. - Creates scope
- Yes.
import("f.fl");is a declaration: it lasts until the end of the enclosing block or file.import("f.fl") { ... }limits it to the braces. - Mechanism
- The module's checked result — its block tree with statements, labels and rules — is loaded from its object as children of the
importnode (the file is checked first if needed). Whatever is open at the end of the file — its declarations — stays open: the code afterimportcontinues at the top level of the imported file.
Basic examples
A file is a context
Suppose bool.fl declares a type and two atoms:
bool.fl
Then importing it gives the same context as writing its text in place:
Two equivalent programs
The full code is the second program: the text of bool.fl in place of the import.
Details
An imported file is a module: it is checked on its own, as a main file, and sees only what it imports itself — not the file that imports it. Each module is checked once; its result is kept as a module object and loaded by later runs.
Modules
A module declares what it needs (usually by importing other modules) and then states its theorems at its top level. Everything the module declares at the top level — atoms, assumptions, locks, labels — is visible to the importer. The proofs themselves stay in their blocks; their results are reached through labels, as usual:
theory.fl
The full code inlines bool.fl.
Using the module
The full code inlines theory.fl (and bool.fl through it).
Projects of several files
Each module imports what it needs: a module cannot use a name of the file that imports it. If a file is already imported in an enclosing context (on the same path of the scope tree), a repeated import is skipped with a notice and its names are shared — so "diamond" dependencies work naturally. An import cycle is an error.
main.fl
The repository contains a library built this way (tests/08_corpus/library): common logic, set theory, Peano arithmetic and the Einstein puzzle; the set theory produces exactly the same statements as the single-file version.
Module objects and the cache
There is no separate build step: run formall main.fl. For every imported module the interpreter
finds its object in the cache and checks that it is current: the module's text, the files it read and the objects of
its own imports are unchanged, and so is the interpreter. A module that is not current is checked again — in a child
run, as a main file — and only such modules: after an edit of one file, the files that import it are checked again,
the rest of the project is loaded. The results are the same as without the cache; reports (--log,
--statements, --certificate-journal …) describe the main file, while --trust covers the
theorems of all modules.
- Where. In a project — a directory with a
formall.projectfile — the cache is the directory.formallnext to it. Paths inside are relative to the project, so the project can be moved or copied together with its cache. Without a project the cache is~/.cache/formall($XDG_CACHE_HOME/formall);--cache DIRor$FORMALL_CACHEchoose another directory. The cache can be deleted at any time. Stale modules are compiled in parallel (-j N; by default as many as there are processors). - Errors. An error in a module is reported with its file and position, followed by the place of each import that led to it.
- Interpretations are instances of the theory's object (below): an interpretation of a large theory costs about as much as loading it.
Interpretation: a theory in another model
A theory proved once can be used for every structure that satisfies its axioms. The second argument of
import is a substitution: import("group.fl", G := Z2, ∘ := ⊕, e := 0, ⁻¹ := −) reads the
theory of groups with its parameters replaced by the model — this is interpretation in Isabelle and an
instance in Lean.
- Parameters. A type of the theory named in the substitution becomes the model's type — a named
type or a compound one:
Point := [Axis -> ℝ]makes the points of a theory functions from axes to numbers (library/geometry/real_space.fl); an atom becomes the model's expression of the same type — an atom (⊕), a constant (0) or a λ (⁻¹ := {x: Z2 | x}). The theory's operator notation stays with the theory's text (a⁻¹is read as−(a)), the model keeps its own. - Axioms are obligations. A top-level
ifof the theory's files that speaks about the substituted parameters and about nothing new of the theory must already be a fact of the model, the same statement after the substitution; it is not assumed again, and the theory's label of the axiom points to the model's fact. A missing axiom is an error. The kernel checks the same where the import is written: the file's certificate applies the theory's axiom to the model's values with the model's fact for it, so that the fact is the axiom after the substitution, whether or not a theorem of the instance is used later. An assumption that mentions something the theory itself introduces stays an assumption, as with an ordinary import: the condition of a theorem about its own atoms (for(a, b) if(a + b = 0) T:: …), the definition of a new constant (for(2) if(2 = S(1))), an axiom of a new notion (the order of the indices of sequences). A top-levelifclosed by a call that takes it (contradict,deduce,obtain) is a step of a proof. - The theory is checked once. The theory is a module: its proofs were checked for arbitrary
parameters when its object was built. The interpretation is an instance of that object (as an
instancein Lean): every statement, definition, abbreviation and rule of the theory and of the modules it imports that declare a parameter is copied with the parameters replaced by the model's values — proofs are not checked again, and a new constant of the theory (define) gets a copy of its own. The theory's theorems become available for the model:InvMul[]now gives− b ⊕ − a = −(a ⊕ b). - The names of the parameters (
G,∘,e) are not declared by the instance; they do not hide the model's names. - Axioms of a lock are not obligations. A theory written without
if, with its axioms asaxiom(L, …)in a lock (the style of reducibility), is imported as well, but the import checks nothing against the model: the theorems stay inside the lock, and every call realizes its axioms with the model's facts —RightInv[| ZA, ZI, ZV], as with an ordinary import of such a theory. This is sound, only the check «the model satisfies the axioms» moves from the import to each use.
An optional condition of a theorem can mention only the model parameters, without mentioning that theorem's own arguments. Put such a condition inside the theorem's explicit body. A file-level header chain treats a condition about substituted parameters as an obligation of the interpretation. For example, the convergence library puts nonemptiness of base sets inside its uniqueness proofs; its sum proof and the import itself do not require that extra condition.
type(Z2 = 0 | 1);
for(⊕: [Z2, Z2 -> Z2]; −: [Z2 -> Z2]); …
// the axioms of a group for Z2 — proved by cases: ∀{a, b, c: Z2 | a ⊕ b ⊕ c = a ⊕ (b ⊕ c)}, …
import("algebra/group.fl", G := Z2, ∘ := ⊕, e := 0, ⁻¹ := −);
for(a, b: Z2) InvMul[]; // − b ⊕ − a -> −(a ⊕ b)
The library uses the same mechanism in library/analysis/real_sequences.fl: natural
indices inside ℝ supply the index type and order required by library/analysis/sequences.fl.
The obligations are proved before the theory is imported. To interpret a theory twice in one file,
or next to its ordinary import, give each interpretation a namespace;
otherwise its theorem labels clash.
What a transferred theorem proves
Interpreting theory A in theory B proves the translated theorems of A inside B. The proof must establish the required axioms of A for the chosen type and operations. The resulting theorems retain the assumptions used to establish those facts. Changing names does not remove assumptions.
For example, library/reals/naturals.fl constructs natural numbers inside ℝ,
and library/reals/peano.fl interprets the Peano theory on that type.
It also proves that the imported addition and multiplication agree with the operations
inherited from ℝ. These operation identities let an arithmetic theorem be written in
either representation.
The reverse question has two parts. A proved correspondence between two number representations can translate a statement back to the original representation. To obtain a proof from Peano assumptions alone, the proof must also avoid extra real-number assumptions, or those assumptions must themselves be justified in the target theory. An embedding, even an isomorphism, does not by itself establish this independence.
In practice, write a reusable theorem with the weakest assumptions its proof needs,
then prove those assumptions in each model. Use a proved correspondence to translate
operations and predicates when the models have different representations. A subtype
supplies membership and an injective embedding; it does not supply a general reverse
transfer procedure. tools/trust.py helps inspect the assumptions of a
particular theorem, while show displays its contract.
The Peano module uses induction quantified over predicates of type
[ℕ -> 𝔹]. Its axioms should not be silently identified with the first-order
induction schema of textbook PA when discussing logical strength or independence.
Namespaces
The last argument of import may be a prefix: import(R := "reals/main.fl"). Everything the
import brings — types, atoms, values of enumerations, operators, abbreviations, labels — is visible after it only with
the prefix: R.ℝ, R.sup(X), R.TArchimedes[]. An operator keeps its notation and
is written with the prefix too: n N.+ N.1. Inside the theory's own files the names are plain. Without a
prefix, import works as before.
import("logic/uniqueness.fl"); // shared logic: ∀, =, ∃! — one for both theories
import(N := "peano/main.fl"); // N.ℕ, N.S, N.+, N.T➕Associative, …
import("reals/main.fl"); // ℝ, +, ×, 0, 1 — without a prefix
for(x: ℝ) L0Add[x]; // 0 + x = x
for(m, k: N.ℕ) N.T➕Associative[m, k, m]; // m N.+ (k N.+ m) = m N.+ k N.+ m
- Why. Both Peano arithmetic and the reals declare
+,×,1,<. Without a prefix the later import hides the earlier names: the theorems of Peano stay true (their atoms are different), calls still apply them, but the sum of two natural numbers can no longer be written. With interpretations, a prefix lets one theory be read for two models (import(A := "group.fl", G := Z2, …)and"B"), or for a model next to the ordinary import of the same theory (the reals and their copyC:C.TWeierstrass). - The prefix covers everything the import brings, including the files it imports — unless they
are already imported outside: a shared file (
logic/…) is imported once, before the prefixed imports, and stays shared. A file imported only under a prefix has prefixed names everywhere:N.=, not=. An error on an undeclared name says when it is visible with a prefix. - Inside an interpretation, a file of the theory that is also imported ordinarily outside (it declares the
parameters, like
reals/language.fl) is read again for the model, not shared. - The same import with the same prefix again is skipped; an ordinary import after a prefixed one is a separate copy. A prefixed import without a substitution of a file already imported without a prefix is an error: it would be the same theory under other names.
- Namespaces nest: a theory that imports another one with the prefix
M, imported itself withO, givesO.M.name. .is reserved for namespaces: it cannot appear in declared names of atoms, types, values and labels, nor in the prefix itself.
Rules
- Paths are relative to the importing file (absolute paths are allowed too); spaces in paths are not supported. Only
.flfiles can be imported. - An imported file must be complete: balanced braces, closed comments, no unfinished command, label definition or trailing comma, and no trailing statement chain without
;. A trailing chain of scope commands is a declaration. - Files are walls in both directions:
;and}inside an imported file never close the importer's chain, and the importer's;never closes the declarations of the imported file — they end together with theimport. import("f.fl") <…>;— an import followed by a statement in the same chain ends with that statement.importcannot be an argument of another command and cannot carry a label.- Messages and statements from imported files show their position as
file.fl:line:column.
Security
By default the interpreter imports only files inside the directory of the main file and inside the project root — the nearest parent directory containing a formall.project file (paths are compared after resolving .. and symbolic links). Command-line flags widen this: --import-root DIR adds an allowed directory, --allow-any-import lifts the restriction for trusted local use.
Running a project
The interpreter always gets one file; its imports are resolved and checked recursively. Any module of a project can also be checked on its own — it imports its dependencies itself, and the end of a file closes its declarations. The same file imported twice on one path of the scope tree (also via .., an absolute path or a symbolic link) is used once.
notation
How text is read and printed: operators, abbreviations, default values, steps read through theorems
Overview
notation("kind", …) collects everything that changes only how the text is read: writing atoms as operators, names for formulas, the default right-hand side of a statement, and which theorems a step of a proof — a call that removes a quantifier, generalize, deduce, witness, obtain, a hint by a fact of a relation — is read as calling. A notation never makes anything true.
notation("infixl" | "infixr" | "infix" | "prefix" | "postfix", operatorAtomNames, precedenceInteger)notation("abbreviation", abbreviationName := expression)notation("default", defaultExpressions)notation("alias", shortName := Namespace.Prefix)notation("apply" | applyTheorem) notation("generalize" | generalizeTheorem)notation("deduce" | deduceTheorem) notation("witness" | witnessTheorem) notation("obtain" | obtainTheorem1, …)notation("hint" | rewriteTheorem, rewriteBackTheorem, reflexiveTheorem)kind- What the notation is: an operator (
infixl,infixr,infix,prefix,postfix), a name for a formula (abbreviation), the default right side of statements (default), a short name for a namespace (alias). operatorAtomNames- Atoms (comma-separated) to write as operators — two-argument for infix kinds, one-argument for prefix and postfix. Infix operators need spaces around them:
a ∘ b. precedenceInteger- The binding strength, as in Lean: a higher number binds tighter (
+65,×70,=50,¬40, postfix 1024). abbreviationName, expression- The name and the formula it stands for; a function is written as a constructor
{x: T | e}. See below. defaultExpressions- Values, at most one per type: a statement without
->inif/axiomgets the value of its type. See below. shortName, Namespace.Prefix- Write
shortName.xforNamespace.Prefix.x. See below. | theorems- For a step: the labels of the theorems the step calls. The quantifier, implication or relation and its values are read from their forms. See below.
Command Properties
- Group
- Transparent headers
- Produces
- Nothing; no label can be put on it
- Creates scope
- Operators — wherever the atom is visible, from this point on; abbreviations and default values — in the enclosing block after the command
- Mechanism
- A transparent header: it can stand in a chain (
for(∘: [G, G -> G]) notation("infixl", ∘, 70) if(…) { … }) or end with;
Basic examples
Any visible atom of two arguments can be written between its arguments, and an atom of one argument before or after it. notation("infixl", ∘, 70) makes a ∘ b ∘ c mean ∘(∘(a, b), c); statements are then also printed this way, with parentheses only where they are needed. The notation is pure syntax: the parser turns a ∘ b into ∘(a, b), so proofs, the journal and the independent checker do not change. The prefix form ∘(a, b) stays valid, and an operator can still be passed as an argument: f(=, x).
notation("infixl", ∘, 70) // left-associative: a ∘ b ∘ c = (a ∘ b) ∘ cnotation("infixr", ⇒, 25) // right-associative: a ⇒ b ⇒ c = a ⇒ (b ⇒ c)notation("infix", =, 50) // non-associative: a = b = c is an errornotation("prefix", ¬, 40) // ¬ anotation("postfix", ⁻¹, 1024) // a⁻¹notation("infixl", ∪, ➕, 65) // several operatorAtomNames with the same fixityCommand Properties
- Group
- Transparent headers
- Produces
- Nothing; the atoms are written as operators wherever they are visible, from this point on
- Mechanism
- The expression parser reads operators by precedence (Pratt parsing) and passes the prefix form to the core parser.
Spaces
An operator is separated by spaces, as in Agda: a ∘ b is three names, a∘b is a single name. This keeps names like L➕1 or ∀𝔹 intact and lets an editor split the text into tokens without knowing the declarations. Parentheses need no spaces: (a ∘ b) ∘ c, ¬(a ∧ b).
Prefix and postfix operators may be glued to their operand: a⁻¹, ¬¬p, −a!, f(x)⁻¹⁻¹. A name that is not a visible atom is split into prefixes, a core and postfixes; the core is a visible atom without notation or a bound variable, and the result is parsed by precedence as if spaces were there. The split happens only where the name would otherwise be unknown: a declared atom a⁻¹ stays one name. If a name splits in more than one way (postfixes ! and !!, text a!!!) it is an error, and spaces decide. Infix operators are never split. The interpreter prints a prefix or postfix glued — a⁻¹, −ε, n!, (a ∘ b)⁻¹, ¬¬p — when the glued text reads back the same: the operand has no spaces outside parentheses (otherwise ¬ ι(p) ≤ x would look like (¬ι(p)) ≤ x), the glued piece is not a visible atom, it splits in exactly one way, and the junction does not spell another operator of the same kind (with an atom c! and postfixes !, !! the term c! ! is not printed c!!). Otherwise it keeps the space: a !!. Infix operators are always printed with spaces.
Precedence
The precedence is an integer 0–1024; the greater binds tighter. The scale is the one of Lean 4 and Isabelle, so that the same numbers can be used: ⇔ 20, ⇒ 25, ∨ 30, ∧ 35, ¬ 40, = ∈ ⊂ 50, ∪ + 65, ∩ * 70, ^ 75, ⁻¹ 1024. Application f(x) binds tighter than any operator. A prefix operator takes as its operand everything that binds at least as tight as itself: with ¬ 40, ¬ a ∧ b is (¬ a) ∧ b and ¬ a = b is ¬ (a = b), as in Lean.
Example
A group in operator notation
The library of the repository (tests/08_corpus/library) is written this way: in its expressions there are 2.5 times fewer parentheses than in the prefix form, and the proved statements are exactly the same.
Details
None of it is logic — the core, the journal and the independent checker never see it. That is why notation is transparent: it may stand in a chain of headers or end with ;, but unlike rule, type, lock, for and if it is not a context — calls pass through it, and theorems get no parameters or conditions from it. Rules of logic, which generate axiom schemes and are part of what you trust, are declared separately with rule.
Steps read through theorems: notation("apply" | …), notation("hint" | …)
A call on a fact H[a] removes a quantifier, a fact a = b rewrites a to b. Neither step is built into the language: each is a call of a theorem, and the file says which. notation("apply" | A∀Apply) reads «a call removes ∀ through A∀Apply»; the quantifier ∀ and the values come from the form of the theorem, not from arguments. The declaration states nothing, so it is a notation, not a rule: a theorem of another form is an error that names it. The other steps name their theorem themselves: the introduction of a quantifier or an implication, the elimination of an existential and the closing of an assumption are calls that take the blocks their proof stands in — generalize[| H], deduce[| H], obtain[| H], witness[t | L], contradict[| H] (logic/quantifiers.fl, logic/propositional.fl, logic/bool.fl); nothing is generated (Command Reducibility).
| Notation | The theorem | The step it reads |
|---|---|---|
notation("apply" | Apply) | p(x…) -> c under if(Q(p) -> d), over p, x… | H[a] on a fact Q(p) -> d: p(a) -> c; a hint <e | H> by such a fact |
notation("hint" | Rewrite, RewriteBack, Reflexive) | a -> b and b -> a under if(R(a, b) -> v); R(x, x) -> v | a fact R(l, r) -> v as a hint (notation("hint")) |
The steps of a theory named by its own theorems
The library (logic/quantifiers.fl, logic/propositional.fl, logic/equality.fl) is written this way: notation("apply" | A∀Apply), notation("hint" | A=Rewrite, L=RewriteBack, A=Reflexive), and the calls generalize[| H], deduce[| H], obtain[| H], witness[t | L]. Its only rules are rule("define", ∃!, ✔) and rule("bijective", …).
A theorem of the wrong form
Without the condition ∀(p) -> true the axiom would say p(x) -> true for every p, much more than Apply, so the notation refuses it.
Expected error: notation("apply"): the theorem 'Wrong' must lie under one if(Q(p) -> d), Q a quantifier
Abbreviations: notation("abbreviation")
Long formulas often repeat: "t is empty" is ∀{z: set | not(in(z, t))}, written a hundred times in a proof. notation("abbreviation", empty := {t: set | ∀{z: set | not(in(z, t))}}) gives it a name. Wherever empty(x) is written afterwards, the parser puts the expression in its place (the lambda is applied to the arguments, with fresh bound variables). No atom and no axiom appear: statements are exactly the same as with the formula written out, so nothing has to be unfolded in proofs. This is abbreviation in Isabelle and notation in Lean. Unlike define, which introduces a new atom with a defining theorem, an abbreviation is pure syntax.
notation("abbreviation", abbreviationName := {boundAtomName: type | expression});notation("abbreviation", abbreviationName := expression);abbreviationName- The new name:
name(a)(or justnamefor a term) is replaced by the formula while the text is read. {boundAtomName: type | expression}- A formula with arguments: the bound atoms are its parameters, the expression its body. A formula without arguments is written as an expression.
Command Properties
- Group
- Transparent headers
- Produces
- Nothing; the name is visible in the enclosing block after the command, like an atom declared by
for - Mechanism
- Expanded by the expression parser:
name(a)becomes the lambda applied toaand is β-reduced. Statements are printed expanded.
Example
Naming a formula
In library/sets/pairs.fl of the repository two abbreviations replaced 169 occurrences of these formulas: the file became a quarter shorter, and its statements did not change.
Printing folds abbreviations back. The checker sees only the expanded formula, but statements, messages and show print it with the name: an expression that matches the body of a visible abbreviation is printed as name(arguments), as Isabelle prints abbreviations. A parameter-function applied to bound variables is matched as a Miller pattern: with notation("abbreviation", everywhere := {f: [T -> T] | ∀{i: T | p(f(i))}}) the formula ∀{i: T | p(g(i))} prints as everywhere(g) and ∀{i: T | p(g(s(i)))} as everywhere{i: T | g(s(i))}. An abbreviation declared in a block folds only inside that block. The interpreter flag --no-fold prints everything expanded.
An abbreviation written as an operator
An abbreviation of one or two arguments can be given an operator notation like an atom. Strict order defined
through ≤ is the typical case: a < b is then literally ¬ b ≤ a, so
decide and the rules see through it, and no lemmas «from < to
¬ ≤ and back» are needed. With define instead, a < b would be a new atom and
every passage between the two forms a rewriting by the definition.
Strict order as an abbreviation
Statements are printed with the abbreviation expanded: ¬ z ≤ x -> true. In the real numbers and limits of the repository (library/reals/, library/analysis/) this replaced two lemmas and 25 of their uses.
Default values: notation("default")
Most assumptions and axioms say that something is true: if(x ∘ y = e -> true). notation("default", true) lets you write just if(x ∘ y = e): in if and axiom a statement without -> gets the default value of its own type as the right-hand side.
notation("default", defaultExpression1, defaultExpression2, …)defaultExpression1, …- One value per type (
✔;true, ∅): the right side given to a statement of that type written without->.
- Each value is the default of its type, at most one per type in one block:
notation("default", true, ∅)makesif(p)meanp -> trueforp: boolandif(a ∪ b)meana ∪ b -> ∅for sets. - It acts in the enclosing block after the command; the nearest declaration with a value of the type wins.
- It is notation only: the statement is
P -> true, and it is printed that way. - The arrow is searched up to the end of its group, so lists keep their meaning:
if(p, q -> r)is stillp -> randq -> r, whileif(p -> r; q)isp -> randq -> true. - Without a default value of the type a statement without
->is an error.
In the repository library the rule stands next to the booleans, in logic/bool.fl: notation("default", ✔).
Example
Assumptions without -> true
Commands that check statements, such as expect(), are not affected: there a string without an arrow already means «the statement with this left-hand side».
Short names for namespaces: notation("alias")
Nested namespaces make long names: a construction imported as
Reals that itself imports pairs as PairClasses and classes as Classes gives the type
Reals.PairClasses.Classes.Class. notation("alias", R := Reals.PairClasses.Classes) lets the
file write R.Class, R.classEmbed, R.SomeTheorem instead — for types, atoms and labels,
in code and inside strings — like import … as R in Python.
notation("alias", shortName := Namespace.Prefix)shortName- The short prefix to write (
R). Namespace.Prefix- The long prefix it stands for — a namespace of an import, possibly nested (
Reals.PairClasses.Classes).
- The alias is expanded while the text is read:
R.xis the nameReals.PairClasses.Classes.x. Statements, the journal and the output show the full names. - It belongs to this file: imported files and files importing this one do not see it. Inside the file it acts in the enclosing block after the command, like an abbreviation.
- The prefix must have visible names, and the short name must not already be a visible namespace.
- The first argument of
import, the file path, is left as written; the substitution string of an interpretation may use the alias.
import("real_numbers.fl");
notation("alias", R := Reals.PairClasses.Classes);
import(RealSpace := "../../geometry/coordinates/space.fl", Number := R.Class, + := Reals.⊕, …);
for(a: R.Class) { … }
In the repository library: sets/numbers/real_numbers.fl, sets/constructions/*.fl
(C for PairClasses.Classes). A block that opens a namespace, so that its names need no prefix
at all, is not part of the language.
See Also
Inference steps
define
Naming a term, or an operation whose result is unique
Overview
define introduces a new atom together with what defines it. There are two forms, and both are conservative: nothing new can be proven about the old atoms, so a definition can never make a theory inconsistent.
+definitionLabel: define(atomName := expression)+definitionLabel: define(atomName | theoremLabel)atomName- The name of the new constant.
expression- Its definition: a term (
S(S(0))) or a function written as a constructor ({a, b: ℕ | e}). The defining statements say the constant equals it — in both directions. theoremLabel- A proved unique existence
∃!{c: R | φ(c)} -> ✔(withrule("define", ∃!, ✔)); the constant is that unique element, and the definition isφof it. Underforatoms the theorem gives a function of them. definitionLabel- Receives the defining statements, to use as hints and facts.
Command Properties
- Group
- Inference steps
- Produces
- The defining statements (a theorem over the atoms of the definition)
- Delivery & Label
- The new atom is declared in the current scope (until the end of the block or file). The label receives the defining statements.
- Creates scope
- No.
- Mechanism
- Explicit form: the atom gets the type of the expression; for a function
{a, b: T | e}the label holds the theoremname(a, b) -> eande -> name(a, b)overa, b— call it or use it as a hint of a proof to unfold or fold. Unique-existence form: see below.
Basic examples
Explicit definition
An atom equal to a term can always be eliminated by substituting the term, which is why this is conservative.
Unfold and fold a definition
Definition by unique existence
An operation like the union of two sets is defined after it is proven that for any arguments the result exists and is unique. The language does not know which atom means «there exists a unique» — the theory declares it, as it declares the rules of its quantifiers:
Union of two sets
In the repository the set theory is built this way: define(∪ | T∪), define(∩ | T∩), define({} | T{}) for unordered pairs, and the Kuratowski pair as an explicit definition define(⟨⟩ := {a, b: 𝕊 | {}({}(a, a), {}(a, b))}).
The theorem must have the form Q{c: R | φ} -> v for a quantifier Q and value v declared by rule("define", …). Its for atoms become the arguments of the new operation, and its conditions stay: the defining statement can be used only where unique existence was proven. This is the theorem on functional extensions (J. Shoenfield, Mathematical Logic, § 4.6), the same principle as func … means … existence uniqueness in Mizar.
What the kernel sees
For the steps of a proof, define(f := …) is a for(f) block with a lock under
it whose axioms are the definition: f(a) -> e and
e -> f(a) for an explicit definition, φ(a, f(a)) -> ✔ (under the conditions
of the theorem) for unique existence. Both blocks are declarations: the code after the command continues inside the
lock until the end of the enclosing block. Inside the lock, a call finds the lock already assumed. Outside it,
or when a call substitutes an atom that the definition mentions, an explicit definition is replaced by its body
and its axioms become e -> e, given as statements proved there; an interpretation realizes them by the
definition in its own copy. So a constant can never be detached from its definition: a definition made under
for(x) does not survive a call with another value of x, and a call taking the blocks
around a proof that mentions the constant cannot cross the lock.
The certificate kernel knows an explicit definition as a definition level: the constant with its value,
and the defining statements as facts it checks to be true by unfolding the value. A result leaves the definition by the
level's own rule, stated of the value. This is how Lean, Coq, Isabelle and HOL Light treat definitions; why it is
conservative and how it compares is on Definitions in the Kernel. A definition by
unique existence has no value: for the kernel it stays a for block with a lock, and how to leave it — with a
function that satisfies it — is shown on Leaving a Block. The
research behind the design is in docs/design/constants.md of the repository; subtypes work the same way
(type).
Definitions and their requirements
A mathematical definition and a theorem can have different requirements.
Include the requirements of a public notion in its defining predicate. For example,
library/analysis/domains.fl defines functionLimitOnDomain(f,D,a,L)
as both an accumulation-point condition on a and the epsilon-delta
condition. The weaker helper satisfiesEpsilonDeltaConditionOnDomain
names only the latter condition, which can hold vacuously. A fact about the public
limit already supplies the accumulation-point requirement; its uniqueness theorem
does not ask the caller to supply it again.
Extra assumptions needed by a particular theorem belong in that theorem's conditions. Requirements for an operation defined from unique existence remain on its defining equation: being able to write a well-typed expression does not establish those requirements. Check the exported contract with show, and document these distinctions beside the mathematical definition.
Generators
decide
Evaluation over finite types
Overview
Many steps of a proof are pure propositional logic: from iff(P, Q) -> true and P -> true follows Q -> true; from P -> true follows or(P, Q) -> true. Each such step can be a lemma applied by a call, but then every pattern needs its own lemma and its own name. decide(X) finds the value of X from the facts by the tables of its functions and writes the proof as ordinary commands. The same works over any enumerated type: a value of Color = red | green | blue left when the others are refuted, a law of a group of two elements checked for every value of its variables, the house left for a value in a puzzle.
decide(expression);decide(expression, otherExpression, …); // the same as decide(expression); decide(otherExpression); …decide(expression | factLabel1, factLabel2, …);decide(expression | factLabel1, factLabel2, …;); // only these factscontradict[| decide(expression)] theoremLabel[| decide(expression)] // as a proof in an argument<functionAtom(<expression | decide()>) |> // as a hint: decides its place<functionAtom(<expression | decide(| factLabel1, …)>) |> // its place, from these facts firstexpression- The expression whose value to compute — of an enumerated type: 𝔹, or any
type(T = c1 | … | cn)(X, notX -> ✔). Several, comma-separated, are decided in order; each sees the previous results. factLabel1, …- Optional: the facts to use first — labels or commands that return statements. What they leave undetermined is found among the visible facts sharing atoms with the expression, as a call finds the conditions its proofs do not meet;
;at the end — only these. Each must be needed. Facts about the expression itself are never used.
Command Properties
- Group
- Generators
- Produces
X -> v, wherevis the valueXtakes under every assignment of its atoms consistent with the facts- Delivery & Label
- Like a proof: into the current block, a label before
decidecatches the result, and as a proof in an argument of a call its statement is that proof. Facts aboutXitself are not used, socontradict[| decide(X)]refutes an assumption aboutX. - Mechanism
- Functions with tables are atoms of type
[T1, …, Tk -> T]over enumerated types whose rows are visible as statements (or(false, true) -> true,next(red) -> green);=of a hint on two values of an enumeration is a table too (c = cis true,c = dfalse). Atoms of the problem are maximal subexpressions that are no such function —P,p(x),∀{x | …},k: Color; each has an enumerated type. A cellf(h)of a bijection is an atom bound to the other cells: two cells take no value together, every value stands in a cell. Facts are statementsF -> cwith a value on the right: from the labels if given, otherwise the visible ones that share atoms withX(transitively, up to 10 atoms; the cells of one bijection share). The interpreter checks all assignments and then writes the proof as ordinary commands, parsed inside thedecidenode (asimportparses a file inside its node): a case analysis by the schemas of the enumeration, every branch closed by a fact refuted or by the value computed (below). The result is checked like a hand-written proof by cases, and the kernel does not grow.
Basic examples
Values from facts
The atoms may be any expressions of the type: decide(or(not(p(x)), p(x))), decide(∀{x: nat | q(x)}) from iff(∀{x: nat | q(x)}, R) -> true and R -> true.
Several expressions
A list of expressions is decided in order, exactly as separate commands decide(P); decide(Q);: each expression sees the results of the previous ones, and a label before decide catches all of them. This is how the parts of an assumption are taken out: for(p) if(prime(p) ∧ p ∣ d) decide(prime(p), p ∣ d). Nothing appears by itself: every result is written in the command.
Over an enumeration
The atoms, the functions and X itself may be of any enumerated type. A function over enumerated types with visible rows is evaluated by them, like a connective by its truth table; an atom of three values is split three ways. The cells of a bijection color: [House -> Color] (rule("bijective", color)) are evaluated together: the value left for a house, the house left for a value.
Three colours and three houses
The library proves the group laws of Z2 so: for(a, b, c: Z2) decide(a ⊕ b ⊕ c = a ⊕ (b ⊕ c)) with the table of ⊕ (algebra/z2.fl), and solves the Einstein puzzle from the refutations of values (puzzles/einstein_enum.fl).
Equality of values
An equality is the relation of a hint (notation("hint" | Rewrite, Reflexive); the library declares = so in logic/equality.fl): c = c is true by its Reflexive, c = d of two values false by their distinctness. A refuted value is such a fact: k = red -> false above an assumption if(k -> red) that led to a contradiction is what refute of the library delivers (contradict).
What decide is — and what it is not
decide is not a rule of the logic. It is a proof generator: it searches, writes
text with if, calls of the schemas of the enumeration and proofs, and that text is checked by
the kernel like any hand-written proof. So a mistake in decide can only make it refuse — it can never make a false
statement pass. For the same reason a generator may in principle be as clever as one likes (up to a neural network
that finds proofs by itself): only its output is trusted, after checking.
Today decide is a small and weak piece of automation. It is a brute-force search over
the assignments of a finite abstraction of the formula: every maximal subexpression that is not a function
with a table — P, p(x), a = b over an infinite type, ∀{x | …} — is
an opaque atom with no meaning but its enumerated type. It is complete only in this narrow sense: if the selected
facts determine X when the atoms are treated as independent variables over their types,
decide finds the value. It is far from a general prover: Lean's decide and tauto
cover the same ground, Isabelle's blast and auto go far beyond it.
Limits
- Enumerated types only:
Xand every atom are of atype(T = c1 | … | cn)(𝔹 among them). At most 16 atoms, and at most 216 assignments of their values in the search. - Functions with tables are atoms of type
[T1, …, Tk -> T]over enumerated types, with at most 8 arguments and at least one row visible as a statement (and(false, true) -> false). An application is evaluated by a row when one applies; when the rows are incomplete and none applies, the application is an opaque atom. An atom with no visible row is an ordinary function, and its applications are atoms.=is a table on two values of an enumeration only when a hint with a Reflexive theorem is declared for it. - Atoms are opaque and compared syntactically (up to renaming bound variables). No equality
reasoning between atoms:
p(c)andp(d)are unrelated even ifc = dis a fact. No quantifiers:∀{x | p(x)}andp(c)are unrelated. No arithmetic. - Facts are statements
F -> cwith a valuecofF's type on the right: those of the labels if labels are given and, if they do not determineXand the list is not closed by;, the visible ones that share atoms withX, transitively, while the total stays within 10 atoms — a needed fact beyond that is not taken, and the answer is «not determined». Rewritingsa -> bwhose right side is not a value are not facts. Facts aboutXitself are skipped on purpose (so thatcontradict[| decide(X)]refutes an assumption aboutX). - Closed formulas (only values and known functions) are evaluated with one empty assignment, using the same checked proof generator.
- On failure it reports what it saw: assignments with different values of
X, or the list of contradictory facts. Closing the labels with;makes the search exact; when the closed facts do not determine X but the visible ones would, the error names those visible facts. - Every label passed must be needed: the proof keeps only the facts
Xneeds, preferring the labelled ones, and a label none of whose facts is kept is an error, as in a call.
A case split by hand
A case split needs no command. Under P -> false write the step; after the
branch closes, P -> true holds and the same step is written once more:
if (P -> false) contradict[| <…>]; // the branch P -> false: closed, so P -> true above it
contradict[| <…>]; // now with P -> true
With a block, the block stands in the branch and again after it. For two atoms, the branch holds the split on
the second one. When the branches only check the tables, one line does the same: contradict[| decide(G)]
proves G by the tables and the split on its atoms, and the value found against the assumption on
G closes it (logic/propositional.fl, puzzles/knights.fl). decide builds
the tree itself: it chooses the atoms and their order, closes a branch as soon as a fact is determined by the
atoms already split — P ∧ Q is false once P is false — and makes the determined parts facts
from the bottom up, each by one row of its function's table, so taking one conjunct out of a conjunction of twelve
needs a few branches, not 211. A branch that needs more than the tables (a call, a rewriting by a fact)
is written by hand.
The tree is written once for the shape of the step, not for its atoms. The atoms become variables, the
facts the step needs become conditions, and the tree proves a lemma: P(u) from P(u) ∧ Q(u)
is the lemma «𝓅1 from 𝓅1 ∧ 𝓅2», proved where the enumerations, the functions and their tables are visible
and applied by a call with 𝓅1 := P(u), 𝓅2 := Q(u). Another decide of the same shape —
Q(w) from Q(w) ∧ P(v) in another theorem — applies the same lemma; so does one in a file that
imports it. One row of a table with an unknown argument («𝓆1 -> false gives
𝓆1 ∧ 𝓆2 -> false») is a lemma of its own, shared the same way, and so is c = d -> false of
two values. The cells of a bijection stay themselves in the lemma. The log says for each step whether its
lemma is new or applied again. These lemmas have internal names: a program does not see them.
How automation is added to Formall
- The machine reasons only in a generator command that you write for a goal you name (
decide(X)). Other commands and calls never reason silently: no facts appear by themselves, no condition is accepted without a fact. - A generator's scope is a whole theory that can be stated in one phrase («tables over finite types»), not a list of cases that happened to be needed. Inside the scope it searches exhaustively or refuses with a clear message.
- Stronger automation — equality reasoning (congruence closure), linear arithmetic, rings, propositional logic
modulo such a theory — will come as separate commands with their theories stated,
not as one more special case inside
decide.
What decide writes
decide is not a new rule of the logic. It finds the value by trying all assignments, and then writes a
proof by cases with the commands you already know; that text is parsed inside the decide node and checked
like any other code. The proof always has the same shape:
- Split an atom by the values of its enumeration: a branch
if(A -> c) B1: …per value, each proving the goalX -> vunder its hypothesis, and the cases schema of the enumeration (type generates it) combines the branches:Bool[A, X, v | B1, B2]through the label of the type. A value of a bijection is split by the cells it may stand in, with the column schema of the bijection. Atoms that have a fact of their own (P -> true) have their value from the start and are never split. - Close every branch as soon as the values chosen so far make a fact or
Xitself computable:<F(<A>, <B>)>rewrites each atom to its value in the branch and the functions by their tables. A fact refuted so gives the goal by ex falso — the distinctness schema of two values (Bool[F(A, B), X, v | <F(<A>, <B>)>], the factF(A, B) -> wfound at the point), or the injectivity schema of two cells with one value;Xcomputed is the goal itself; a branch whose hypothesis is the goal is that hypothesis (B2: if(X -> v) {}). - The branch labels and the lemma's own label are internal names (
𝓑1,decide.…); below they are written as a program could, through the labelBoolof the type.
For the first example above, if(iff(P, Q) -> true; P -> true) decide(Q) writes:
What decide(Q) writes
The same text as if(iff(P, Q) -> true, P -> true) decide(Q) generates, the schemas of the enumeration named through the label Bool of the type; the full code declares the connectives by their truth tables. P has a fact of its own, so only Q is split.
Modus tollens, if(imp(P, Q) -> true) if(Q -> false) decide(P):
What decide(P) writes for modus tollens
The text if(imp(P, Q) -> true) if(Q -> false) decide(P) generates.
A tautology with three atoms has no facts, so every branch is closed by X itself: eight branches, each
<imp(<and(<imp(<P>, <Q>)>, …)>, …)> computing
true, combined by the cases of the three atoms. The log shows the size of the generated proof:
[ decide ] … // 0 facts, 3 atoms, 8 branches.
Because the result goes through if, the schemas of the enumeration and proofs, the kernel does not grow:
the certificate of such a proof uses only the kernel's ordinary rules.
Labels first, then the visible facts; ; — only these
After | come the facts decide takes first. What they leave open is found among the visible facts, like the conditions of a call that its proofs do not meet: one rule for every |. A ; at the end of the list says «only these». It is needed where the visible facts must not be used — in a block whose assumptions contradict each other on purpose, or where a reader should see everything the result rests on.
Labels first, then the visible facts
The second decide is closed by ;: the error names the visible fact Q -> true that would decide it.
Expected error: with these visible facts it would be true (pass their labels or remove ';')
decide as a hint
In a proof, <e | decide()> rewrites e to its value decided from the visible facts — the propositional counterpart of a theorem hint. A hint is a proof, and a command whose expression is not written takes the place of the hint, as a call T[] infers what is not written; <e | decide(| H)> decides the place from the facts of H first, <e | decide(| H;)> from them alone (Hints are proofs). Standing alone, decide() has no place and is an error.
A hint and an argument
Labels
Label Commands (+, -, *, ^, expect)
Set operations on label collections and the check expect
Overview
Labels in Formall hold collections (packages) of statements. The standalone label commands +, -, *, ^ perform set-like operations on these collections. They take one or more arguments and produce a new collection of statements that can be captured by a label.
+(statementSource1, statementSource2, ...)-(statementSource1, statementSource2, ...)*(statementSource1, statementSource2, ...)^(statementSource1, statementSource2, ...)expect(left -> right; … | statementSource1, ...)expect(left -> right; …)statementSource- A statement label or a nested command returning statements.
left -> right, …expectonly, at most one: the expected set, read as the statements of if (without->— the value ofnotation("default")). Alone, it names visible statements: an error if one is not visible here, otherwise they are returned as a label.+ − * ^ expect- Union, difference, intersection, symmetric difference of the sets of statements;
expectchecks that all sources are equal sets (an error shows the difference) and returns that set. Inclusion is written by composition:expect(| *(A, B), A).
Command Properties
- Group
- Labels
- Produces
- Statements (result of set operations on statement collections)
- Delivery & Label
- Into the current scope. A label on a label command captures the resulting statement collection at this scope.
- Creates scope
- No.
- Mechanism
- Processes arguments left to right. The first argument initializes the result (copied in full). Each remaining argument is combined using the set operation (
+union,-subtract,*intersect,^symmetric difference). Arguments are labels or commands returning statements.
Basic examples
Union: +(first, second, ...)
Initializes the result with the first argument, then for each remaining argument adds its statements to the result, skipping those already present:
Union of two labels
Subtract: -(first, second, ...)
Initializes the result with the first argument, then for each remaining argument removes from the result any statements that match:
Subtraction of labels
Intersect: *(first, second, ...)
Initializes the result with the first argument, then for each remaining argument keeps in the result only those statements that also appear in that argument:
Intersection of labels
Symmetric Difference: ^(first, second, ...)
Initializes the result with the first argument, then for each remaining argument performs a symmetric difference (XOR) with the accumulated result. For each statement in the current argument:
- If the statement exists in the result (as it was before processing this argument), it is removed.
- If the statement did not exist in the result, it is added.
After processing an argument, the result contains only statements that were in exactly one of the two sets. When there are more than two arguments, this process repeats — the next argument is XORed with the accumulated result, and so on.
Symmetric difference of labels
How It Works
Label commands process arguments left to right. The first argument initializes the result collection (copied in full, unaffected by the command symbol). Then each remaining argument is combined with the accumulated result using the set operation indicated by the command symbol.
With a single argument, all four commands produce the same result — a copy of that argument's statements. With multiple arguments, each one is folded into the result in order.
+L: +(A, B) declares L and fills it with the union of A and B.Arguments
Each argument is a source of statements:
- Label — a label name; uses the statements accessible from that label (filtered by scope visibility, so only statements reachable from the current scope are included)
- Anything that gives statements in place — a proof
<…>, a callT[…], a command (decide(X),expect(…), another label command) - The statements of
expect— before the barexpecttakes one set of statements, read as inif:expect(P -> true; Q -> false | L)checks thatLholds exactly these; alone,expect(P -> true)checks that each is visible here
At least one argument is required. If no arguments are provided, the interpreter reports an error.
Statements Named in Place
Label commands work on proofs: labels and commands. To use a visible statement that no label holds, name it whole
with expect: it checks that the statement is visible here and returns it as a label.
Statements named in place
Multiple Arguments
When more than two arguments are provided, the operation is applied sequentially — each argument is combined with the accumulated result from all previous steps:
Multiple arguments
Nested Label Commands
Label commands can be nested. The result of one command can serve as an argument to another, allowing complex set expressions in a single statement:
Nested label commands
Checking: expect
expect(A, B, ...) checks that all its arguments contain the same set of statements (brought to the current scope, ignoring order and duplicates). If they differ, it is an error that lists what is only in one side and only in the other. If they are equal, it returns that set, so it can be labeled and passed on like any label command.
Use it to state important facts explicitly instead of writing them in comments: a comment can silently become wrong, a check cannot.
What expect states, the independent kernel checks too: a statement of another file it names here (a fact of
an imported module, a theorem of an interpretation at the model) is
proved at this place in the file's certificate, by that statement's own proof applied here.
Explicit checks
A statements string in expect is the expected set — with labels beside it, it does not have to exist in the scope; there is one such string at most. Inclusion is expressed by combining expect with intersection: expect(*(A, B), A) means A ⊆ B.
Inclusion through intersection
Statement Equality
All set operations rely on statement equality to determine matches. Two label statements are considered equal when both conditions hold:
- Their expression content is identical (same left-hand and right-hand sides)
- They were defined in the same scope
This means two statements with identical text but originating from different scopes are treated as distinct entries. Union will not deduplicate them, subtract will not match them, and so on. This scope-awareness ensures that statements retain their provenance through set operations.
+, -, *, ^ are reserved in Formall and cannot be used in atom names.Scope Visibility Filtering
When a label is passed as an argument to a label command, its statements are filtered by scope visibility. A statement visible here is a fact of this scope. A statement standing in a closed block inside the label's declaration scope is a theorem of that label (see Theorems keep their place) and is kept with its place. The receiving label holds it only when declared in a scope that encloses that place; otherwise the statement is considered foreign to it and is excluded (with a warning).
Scope filtering in action
Statements from sibling scopes are invisible. +(Collected) inside the second if can only see statements defined in its own scope branch.
This is why L:OtherLabel; (defining a label directly with another label) is not allowed — the filtering would happen implicitly, and the user might expect all of OtherLabel's statements to be copied. Using a label command makes the filtering explicit:
resultLabel: +(sourceLabel); // explicit: copy accessible statements from sourceLabel into resultLabelTheorems keep their place
A statement proved inside for and if blocks and delivered to a label declared outside them is a theorem: its contract — parameters, conditions, lock axioms — is the path from its place to the label's declaration (as with T::). Label commands keep that place: +(T, S) holds both theorems with their own contracts, and a call applies each with its own conditions. Two theorems that look the same but rest on different conditions stay different statements, so -, *, ^ tell them apart. String arguments still find visible facts only: a theorem is given by its label.
Label commands with theorems
Both theorems have the same form, but different conditions: OnlyT needs not(y) -> false, the symmetric difference — y -> true.
A label on type or rule holds what the declaration generates — its schemas, each with its place (a package to pass to a call).
Augmentation vs. Label Commands
Label commands (+(A, B)) and augmentation postfixes (L+: cmd) use the same underlying set operations, but differ in how they are applied:
- Label commands create a new collection from existing labels and statements. They are standalone commands that produce a result to be captured.
- Augmentation postfixes modify an existing label in place by combining its current contents with the result of a command. They are part of the label definition syntax.
See Labels for details on augmentation postfixes.
See Also
Tools
show
What is visible here: the scope, nearby facts, labels — and a search
Overview
show() prints into the log what one needs to know at this place: the enclosing for and if, the facts already there and what the labels hold. show("text") searches the visible facts and labels for a piece of text. Nothing is produced.
show()show("searchText")show(| theoremLabel)show("check", leftExpression -> rightExpression; …)show("facts", expression1, expression2, …)show("type", expression1, expression2, …)()- The context here: visible atoms, types, assumptions, labels, rules.
- "
searchText" - Visible facts and labels whose text contains it.
theoremLabel- The contract of each conclusion of the theorem — what a call would require — without applying it.
"check", statements- For each statement: is it already a visible fact?
"facts", expressions- The visible facts with this left side.
"type", expressions- The types of the expressions.
Command Properties
- Group
- Tools
- Produces
- Nothing: no statements, no label (a label on
showis an error). The command is a tool; the journal and the checker do not see it. - Delivery & Label
- —
- Mechanism
show(): the enclosing scopes of this file, inner first — the nearestifis marked «a call taking this if closes it» (contradict[| …],deduce[| …]), the nearestfor«a call taking this for delivers above it» (generalize[| …],obtain[| …]); then the facts of this file, nearest first (at most 40), and the labels declared in this file. A label statement is printed as a theorem: theforandifbetween the place it was delivered to and the label declaration are its parameters and conditions.show("text"): every visible fact and label whose printed form (or name) contains the text, from all files. The search is literal: bound variables keep the names they were printed with (1 + x, not1 + y).
Basic examples
Context and search
Contract and exact queries
Details
A Formall proof goes forward, so there is no «goal» as in tactic provers. What one needs to know before the next
command is the place itself: which for and if enclose it (what a
call that takes its blocks — contradict, deduce,
generalize, obtain — will close or lift over), which facts are already there and which labels hold what.
show() prints exactly this into the log, like the infoview of Lean. show("text") searches the
visible facts and labels, including those of imported files — a quick way to find the name of a lemma.
Exact queries
show("check", P -> true) reports FOUND with the source statement or NOT FOUND.
It uses the visible-statement lookup used by calls, including type-polymorphic statements. It does not rewrite,
apply a theorem or infer a value: NOT FOUND means that the requested fact is not already available, not that
it cannot be proved. The same statement-list syntax and default right-hand values as in if are accepted.
show("facts", P) lists visible statements whose left side is exactly P (up to bound-variable
renaming and type-scheme matching), nearest first, with a count and at most 40 entries per expression. Unlike text search,
it does not find occurrences of P inside other expressions. show("type", P, f) prints the type
of each expression; neither query evaluates it.
show(theoremLabel) prints every conclusion and its own contract: atom and type parameters, assumptions,
rules and lock obligations. Assumptions are checked as written against the current facts. This is a template
inspection, without argument substitution, inference or checking lock realizations; it is not a verdict that
theoremLabel[] will succeed or fail. Different conclusions may have different contracts.
See Also
Rules
Quantifiers
rule("define")
Declaring unique existence: definitions of operations
Overview
define has two forms. An explicit definition
define(f := {a: T | e}) needs no rule: the new atom is just a name for a term. A definition from a
theorem define(f | T) introduces an operation whose value is described by a property, and this is
allowed only for the quantifier «there exists a unique» declared by rule("define").
rule("define", quantifierExpression1, quantifierExpression2, …; truthExpression)quantifierExpression1, …- The quantifier of unique existence
∃!: an atom of type[[T -> V] -> V], possibly polymorphic. truthExpression- The value
vof a true statement. Thendefine(c | T)withT: ∃!{x | φ(x)} -> vintroducescwithφ(c).
Basic examples
An operation from unique existence
In the library the rule stands in logic/uniqueness.fl next to the general ∃!, so the set
theory (∪, ∩, {}, 𝒫, A × B) and the reals
(sup) define their operations the same way.
What the rule states
If for all ā under conditions H(ā) a theorem gives ∃!{c | φ(ā, c)} -> v,
then a new operation f may be added with the theorem φ(ā, f(ā)) -> v under the same
conditions. This is the theorem on functional extensions (Shoenfield, Mathematical Logic, § 4.6) and
func … means … existence uniqueness in Mizar: the extension is conservative, so the rule is safe
exactly when the declared atom really means unique existence.
Equality & functions
notation("hint")
Facts of a relation as hints, through named theorems
Overview
notation("hint" | Rewrite, RewriteBack, Reflexive) lets a fact R(a, b) -> v of a relation R be a hint: a proof rewrites a to b by it, as if it called Rewrite[| F]. The relation and its value are read from the theorems themselves. Like every notation it states nothing: every step it allows is a call of one of the theorems it names, and the certificate says so. The other steps of a proof are named the same way — notation("apply" | A∀Apply), notation("generalize" | generalize), notation("deduce" | deduce), notation("witness" | witness), notation("obtain" | obtain, …) — see steps read through theorems.
notation("hint" | rewriteLabel)notation("hint" | rewriteLabel, rewriteBackLabel, reflexiveLabel)rewriteLabel- Required:
a -> bunder oneif(R(a, b) -> v), over the atomsa,bonly. A factR(l, r) -> vthen rewritesltor. rewriteBackLabel- Optional:
b -> aunder the same condition. Without it a fact rewrites one way only. reflexiveLabel- Optional:
R(x, x) -> vover one atom. With itR(t, t)reduces tovby itself.
Basic examples
A relation of its own
Details
The three theorems are the axioms Reflexive, Rewrite and the lemma RewriteBack a file writes for its equality (Command Reducibility); here they are named: a fact, a quantified fact and a theorem whose conclusion is R(l, r) -> v rewrite by Rewrite and RewriteBack, a bracket without a hint uses the visible facts of the relation, R(t, t) is Reflexive. The library declares its equality this way: notation("hint" | A=Rewrite, L=RewriteBack, A=Reflexive) in logic/equality.fl, and equivalence the same way: notation("hint" | L⇔Rewrite, L⇔Back, L⇔Reflexive) in logic/propositional.fl, so a fact P ⇔ Q -> ✔ rewrites P to Q and back. Nothing about = or ⇔ is built into the language beyond what the theorems say.
Each theorem must hold one statement and be proved without locks or rules of its own, over atoms of one type; the theorems must be about one relation and one value. A theorem of another form is an error that names it.
One way only
Without RewriteBack the fact rewrites left to right only.
Expected error: No matching statement found for expression substitution
rule("bijective")
Functions between enumerated types that take every value once
Overview
In grid puzzles every house has one colour and every colour is in one house. With enumerated types the first half is already there: color(2) -> red and color(2) -> blue contradict each other, and refuting all colours but one of house 2 gives the last one. rule("bijective", f) adds the second half for a function f: [D -> C] between enumerated types of the same size.
rule("bijective", functionAtom1, functionAtom2, …)functionAtom1, …- Functions
f: [D -> C]between enumerated types of the same size, each declared a bijection.
Basic examples
Row and column
The Einstein puzzle in the repository (library/puzzles/einstein_enum.fl) is solved this way in about a hundred lines of code: properties are functions color: [House -> Color], clues are conditional axioms, and the solution is a sequence of refutations.
Details
- Injectivity.
f(a) -> candf(b) -> cwith different valuesa,bofDcontradict each other. - Exhaustion by column. When
f(h) -> cis refuted (orhalready has another value) for everyhbut one,f(k) -> cfollows. By row, the values already taken by other houses are excluded too.
Both are schemas of the declaration — Injective and Column, axioms of a lock of its own — and decide works with them: the value of a cell is found from the facts about the other cells of its row and column, by the tables of the functions applied to it. A label on the declaration holds the schemas, to pass to a call of a theorem proved under another bijection. Like every rule, the declaration is an axiom of the theory: the function is a bijection.
Examples
Boolean Logic
Propositional logic fundamentals
Overview
This example shows how to set up boolean logic in Formall and prove basic theorems like the law of excluded middle, De Morgan's laws, and double negation.
Basic Setup
Boolean setup
Complete boolean logic foundation
Law of Excluded Middle
For any proposition P, either P is true or not(P) is true:
Excluded middle
Proof that P ∨ ¬P is always true
Double Negation
not(not(P)) = P for any proposition:
Double negation
Proof that ¬¬P ↔ P
De Morgan's Laws
not(and(P, Q)) = or(not(P), not(Q)):
De Morgan
Proof of ¬(P ∧ Q) ↔ (¬P ∨ ¬Q) by case analysis
Tips for Boolean Proofs
- Case analysis — use nested
ifto cover all combinations - Contradiction — assume the opposite and derive
falseandtruefor the same expression - Substitution — proofs with nested angle brackets chain substitutions
Peano Arithmetic
Formalizing natural numbers and proving 2+2=4
Overview
This example shows how to formalize Peano arithmetic in Formall — defining natural numbers, equality, addition, and proving 2+2=4.
Complete Proof
Full 2+2=4 Proof
Complete working proof that can be executed in the interpreter.
Step-by-Step Explanation
1. Equality Setup
We establish reflexivity (x = x), substitution (if x = y, we can replace x with y), and symmetry (if x = y then y = x) — all inside a lock scope so they work as reusable axioms.
2. Number Definitions
Each number is defined as the successor of the previous: 2 = S(1), 3 = S(2), 4 = S(3).
3. Addition Axioms
A➕1: adding 1 is successor (x + 1 = S(x)). A➕2: recursive step (x + S(y) = S(x + y)).
4. The Calculation
2 + 2 = 2 + S(1) // by definition of 2 = S(2 + 1) // by A➕2 = S(S(2)) // by A➕1 = S(3) // by definition of 3 = 4 // by definition of 4
Key Techniques Used
T=S[a, b]— Apply symmetry: if=(a,b)proven, get=(b,a)A=I[a, b]— Apply substitution: if=(a,b)proven, enablea -> breplacementA➕1[2]— Instantiate addition axiom with specific value<...>— Chain substitutions together
Steps as Theorems
Contradiction, generalization, calls on facts and if, written as axioms and theorems of a file
Overview
Formall's core is four commands — type, for, lock, axiom — and two forms: proofs <…> and calls T[…]. The steps of a proof — contradiction, generalization, calls on quantified facts, and even if — are theorems about these primitives, not commands. This page shows each step twice: first with the theorem of the library, then with axiom-based theorems written in the file itself (and, in the final example, without if either).
The page was written when these steps were commands of the interpreter (contradict, generalize, apply) and showed that each is reducible to the core. Since step 189в the language is exactly this. There are no commands contradict, generalize, deduce, obtain, witness and no rules generating their schemes: an enumeration type(bool = false | true) writes the schemas of distinct values and of cases as axioms of a lock, the library proves contradict from them (logic/bool.fl), the axioms of the quantifiers and of the implication are written in logic/quantifiers.fl and logic/propositional.fl, and every step is a call — contradict[| H], generalize[| H], deduce[| H], obtain[| H]; a call on a quantified fact removes its quantifier through the theorem named by notation("apply" | A∀Apply). The independent kernel checks proofs with three rules — axioms, rewriting and applying a theorem (a call). The examples below keep the shape of the reductions as they were found: the «built-in» step is the library's theorem, written in the file.
Contradiction: contradict
Let's start with the most interesting case. We'll prove that if an implication is false, its consequent must be false: implies(P, Q) -> false implies Q -> false.
Using contradict
Contradiction with the library theorem
Using axiom-based contradiction theorems
To replace contradict, we define four theorem variants — one for each combination of assumption direction and contradiction direction. Each theorem encodes the logical conclusion directly as an axiom:
Axiom-based contradict — same proof without contradict
Each contradict is replaced by a call of the appropriate theorem. The realization label after the bar (e.g. A) provides the axiom realization: a label whose statements prove the contradictory statement under the given assumption.
Generalization: generalize
Let's prove that equivalent(x, x) -> true for all x, and lift it to forall_b{x | equivalent(x, x)} -> true.
Using the axiom of the quantifier
Built-in generalize
Using an axiom-based generalization
The axiom-based version declares two axioms inside a lock: one per-element (p(x) -> true) and one quantified (forall_b(...) -> true):
Axiom-based generalize
The realization label ReflProof provides the per-element proof. The call verifies that equivalent(x, x) -> true holds for each x and produces the quantified statement.
Calls on facts: notation("apply")
Continuing from the previous example, we now instantiate the universal statement for a concrete value.
Using notation("apply")
Built-in apply
Using an axiom-based instantiation
Axiom-based apply
G[true] becomes AppTheorem[predicate, true]. The if-condition forall_b(p) -> true is satisfied by the generalized statement.
if as a lock
So far we've reduced contradiction, generalization and calls on facts down to axiom-based theorems with if-conditions. But if itself can be reduced too: an if-block is essentially a lock with a single axiom — a hypothesis under which the body is proved. Lifting an assumption out of if and into a lock-axiom is a routine restructuring.
The example below is a direct restatement of FlipTrueIfTrue from the contradict reduction above, but written without using if for the hypothesis: each if-condition becomes a lock-axiom, and the realization mirrors that structure.
if reduced to lock
Each if becomes an axiom of its own lock, and the theorem is registered inside the innermost lock so that every supporting lock lies on its path. The axiom c -> false (carried by proof) gets a realization; the deeper axiom a -> true (in L2) becomes a nested lock axiom that the realization must match exactly. The caller mirrors the structure: ExL1 realizes c -> true, and Exproof realizes c -> false while crossing ExL2, whose axiom not(y) -> true matches L2's a -> true after substitution. Remove either realizer and the call fails — both axioms are genuinely on the path. This is the general pattern: any if-block rewrites to a single-axiom lock, and any proof using that if rewrites to a realization crossing the equivalent lock.
This is what unifies the language: if, for, type, lock, and rule are not separate features each requiring its own treatment in calls — they are all elements of the same signature. When a call walks the path from a theorem statement back to its label declaration, it sees the conditions imposed by these constructs and checks them against the realization's path uniformly. Whether an assumption was written as if(P -> false) or as axiom(P -> false | L) inside a lock, a call compares it the same way.
Everything at once: the full reduction
Each section above removed one step. The natural stress-test is to remove all four at once: a complete file that proves the same chain — hypothetical reasoning, contradiction, generalization, application — using only axiom, calls, lock(), proofs and for. The full code below contains not a single if, contradict, generalize or call on a quantified fact.
It goes one step further. Of the six Flip schemas, only four remain postulates: the two unary ones (FlipIfFalse, FlipIfTrue — Clavius laws, the only mechanisms that carry a result out of a hypothesis lock) and two binary ones (FlipTrueIfFalse, FlipTrueIfTrue — ex falso engines, one per conclusion polarity). The other two binary schemas are derived, not postulated — their labels are defined by the result of a call carrying the very same lock contract:
The four commands, fully eliminated
The derivation pattern, twice: inside a hypothesis lock the two axioms c -> true and c -> false contradict; a binary Flip of the needed polarity turns the contradiction into ex falso (its realization uses fewer nested assumptions than the template — weakening, allowed by the subset rule); the matching Clavius law then carries the result out of the hypothesis. The label FlipFalseIfFalse is defined by the result of a call, yet exposes exactly the same lock contract as the removed postulate — every later FlipFalseIfFalse[| HIPQ, A, ...] works unchanged. Mutation-checked: breaking the ex-falso polarity, the Clavius step, or any realizer fails the file.
Two things are worth noting. First, the derived theorems demonstrate that a theorem in Formall need not be an axiom registration: a label marked on the result of a call, positioned inside the right locks, carries a full lock contract and is applied like any other theorem. Second, the four remaining postulates are genuinely minimal for a language without a negation function: deriving a binary schema with a -> false conclusion requires an ex-falso schema of that same polarity, which is circular.
The other mechanisms
The other mechanisms of the language — notations, generated text, search, declarations — enlarge the core no further: the minimal set is still type, for, lock, axiom, proofs and calls. The table below groups these mechanisms by how they reduce. To check a reduction, compare the statements proved with and without the mechanism using expect( ).
| Mechanism | Kind | Without it |
|---|---|---|
notation("default", true) | notation | if(P -> true) written out |
abbreviation, multi-place ∀{x, y | …} | notation | the formula written out; nested one-place quantifiers |
decide | generates text | a lemma over the schemas of cases of the enumeration with the tables of the functions as conditions, applied by a call at the place |
hints <e | L>, <e |* L>, chains, implicit arguments of calls | search | explicit calls with all arguments, then plain <…<e>… |> steps |
obtain[| S], witness[t | L] | lemmas of the library | the same calls with p, q written out — or of an axiom scheme in a lock (below) |
type(T = a | b) | declaration (axiom schemes) | type(T) for(a, b: T) and the schemas Distinct and Cases as axioms of a lock (an enumeration, written out) |
notation("hint" | Rewrite, RewriteBack, Reflexive) | two axioms and a lemma written in the file (no kernel rule since step 96) | =(x, x) -> true and, under if(=(a, b) -> true), the rewriting a -> b; a rewrite by an equality is a call of the second one (below) |
define(f := {a | e}), define(f | T∃!) | definitional extension (no kernel rule since step 93) | for(f) and a lock under it with the defining axioms (f(a) -> e, e -> f(a); or φ(a, f(a)) under the theorem's conditions); the code goes on inside the lock, and a call realizes the axioms outside it — an explicit definition by its body |
subtype(ι, φ, ∃, ⇒) | subtype premises about a declared ι: [S -> T] (no kernel rule since step 93) | a lock with S1–S3 as axioms; no nonemptiness is needed by the kernel |
rule("bijective", f) | axiom | axioms of injectivity and exhaustion for f |
contradict[| S], generalize[| S], H[a] on a quantified fact, deduce[| S] | theorems and axioms written in the files (step 189в; no kernel rule since steps 95–97) | Distinct: Y -> c1 and Y -> c2 give anything, Cases: what follows from each value follows — the lemma contradict; Generalize: p(x) -> c for an arbitrary x gives Q(p) -> d; Apply: under Q(p) -> d, p(x) -> c; ⇒(P, Q) -> true from Q -> true under if(P) in a lock |
So the independent kernel checks every proof of the corpus with three rules — axioms, rewriting and
applying a theorem — plus two shortcuts for modules (import, instance) that its strict mode does
without.
How a result proved inside each of these blocks — a definition, a subtype, an enumeration — is carried out of it, and under which condition, is the subject of Leaving a Block.
equality as two axiom schemes
A statement a -> b already says that b may replace a anywhere. An equality fact =(a, b) -> true is only a fact until something turns it into such a rewriting. A file does it with two axioms of a lock, named by notation("hint" | Rewrite, RewriteBack, Reflexive): Reflexive =(x, x) -> true and Rewrite: under if(=(a, b) -> true), the rewriting a -> b. Rewriting right to left, the equality of a chain's ends and symmetry are proved from them. In the journal every step by an equality is a call of Rewrite (or of the proved RewriteBack), with the equality fact as its condition, and --trust lists the two schemes as axioms. Here they are written out without the rule:
Equality as two axioms
Under a binder the interpreter writes the same call of Rewrite at the bound variable: the condition is then met by the quantified fact instantiated right in the step (a premise written inline), since a statement about a bound variable cannot stand on its own.
obtain as an axiom scheme
Like FlipTrueIfTrue above, ∃-elimination is a theorem whose premise is a lock: «if ∃(p), and from p(x) for an arbitrary x follows q, then q». obtain[| S] is this call, with p and q found from the proof and the blocks it stands in:
obtain and the ∃-elimination scheme
In the library the scheme is not an axiom but a lemma (obtain), proved from the definition of ∃ through ∀; the call obtain[| S] takes the for and the if its proof stands in.
Summary
Once the axiom-based theorems are defined, using them takes roughly the same number of lines as the library's theorems. The real difference is that a call taking the blocks its proof stands in needs no extra labels: it expresses «flip the assumption» or «generalize over x» as one call, and the theorem it calls says exactly what the step is.
Leaving a Block
How a result proved inside a block is carried out of it, and under which conditions
Overview
Every block of Formall is an assumption: for introduces arbitrary atoms, if assumes
statements, lock assumes axioms, type introduces a type parameter. A result proved inside
is a result under these assumptions. A block is useful only if such results can be carried out of it — and
only under conditions that keep them true. This page lists, for every block, how a result leaves it and what the
kernel checks. The sugar of the language (definitions, subtypes, enumerations) is a combination of these blocks,
so the same table says how to leave a definition or a subtype.
| Block | A result leaves by | Condition |
|---|---|---|
{ … }, import | nothing to do | no assumption: its statements hold in the enclosing block |
for(x) | generalize[| S] (∀-introduction) | the axiom of the quantifier; no assumption between the result and the for |
for(x) if(p(x)) | obtain[| S] (∃-elimination) | the result does not mention x; the fact ∃(p) is visible above |
if(H) | deduce[| S] (⇒-introduction), contradict[| S] | the theorem of the implication; a contradiction under H |
| any path of blocks | a call of the result as a theorem | every atom and type of the path substituted, every if met by a visible fact, every lock axiom realized |
define(f := {a | e}) | automatically, by a call that takes the blocks around it | none: a definition level of the kernel; a result with f is stated of the body (Definitions in the Kernel) |
define(f | T∃!) | a call with f := g, then ∃-elimination over g | a function g satisfying the definition exists: ∃{g | ∀a. φ(a, g(a))} is visible |
type(S) for(ι: [S -> T]) subtype(ι, φ, ∃, ⇒) | a call with a model S := M, ι := e | the model satisfies S1–S3 |
type(T = c1 | … | cn) of a theory | a call with an enumeration of the call site | the type and the values replaced together, value for value; its schemas of distinct values and of cases realized by the label (the package) of the call site's |
An explicit definition is a level of the kernel: the constant with its value (Definitions
in the Kernel). The last three rows are not rules of the kernel. A definition by unique existence is a for
block of the constant with a lock under it whose axiom is the definition; a subtype is a type parameter, a
for block of the embedding and a lock with S1–S3. Leaving them is an ordinary call: the constant is
substituted by something that satisfies its axioms. The condition is always the same — a witness: the
body of an explicit definition, a selector function for define!, a model type for a subtype. Without a witness the
assumptions of the block could be contradictory (no such function, no such type), so nothing may leave it, not even a
statement that does not mention the constant.
An explicit definition
The body is the witness, so the interpreter discharges the definition by itself. A result without the constant
leaves the definition's lock with the call that takes the blocks around it
(generalize[| R], deduce[| R]); in the
certificate it leaves the definition level as it is, by the kernel's own rule (Definitions
in the Kernel). A result that mentions the constant stays inside: outside the definition it would speak of
a constant without a meaning.
Leaving an explicit definition
The full code declares a polymorphic = with reflexivity and the quantifier ∀; in the library they come from logic/equality.fl and logic/quantifiers.fl.
Repository test: tests/13_boundaries/44_generalize_leaves_explicit_definition.fl (and 45 for
deduce).
A definition by unique existence
define(f | T) with T: ∃!{c | φ(a, c)} assumes that f picks the value for
every a. To leave the block, show that such a function exists — by a construction or by the principle of
unique choice, written as an explicit axiom (it is not part of the trusted kernel):
Leaving a definition by unique existence
In the full code: the quantifiers ∀, ∃, ∃! with their rules (the library's logic/uniqueness.fl), unique choice as an explicit axiom AUniqueChoice, and R with unique values (H).
Repository test: tests/08_corpus/experiments/reduction/define_unique_exit.fl.
A subtype
A result about T proved through the subtype S leaves with a model: a type M
and an embedding e for which S1–S3 hold. The subtype may be empty; then the model is an empty type as
well. Formall does not assume that every predicate has a model type (the typedef principle of HOL).
Leaving a subtype with a model
The full code proves Inside through the subtype S of {x: T | p(x)} and then leaves it with the model M, e; ⇒, =, ∀, ∃ are declared at the top (in the library — logic/).
Repository test: tests/08_corpus/experiments/reduction/subtype_exit.fl.
An enumeration, written out
An enumeration is a type, its values as atoms, and two kinds of axiom schemas: distinctness —
two different values of one expression give anything — and exhaustion — what follows from each
value of an expression follows. The refutations of an enumeration (if(X -> red) refute[| …], the lemma of
logic/equality.fl) and the value decide finds are calls of these schemas.
Three colors without the enumeration rules
Only type, for, lock, axiom, if, proofs and calls: the kernel needs no rule of its own for enumerations. The repository test experiments/reduction/enumeration_as_axioms.fl derives the same X -> blue with the built-in enumeration as well.
Why this matters
The kernel is trusted, so it must be small. The richer commands are trusted only through such reductions: each one is shown to be a combination of the core blocks, and each block is shown to be left only with a witness. Every example on this page is a test of the repository, checked by the interpreter and by the independent kernel.
See Also
Definitions in the Kernel
What an explicit definition is for the certificate kernel, why it is conservative, and how other systems do it
Overview
An explicit definition define(g := {x: T | e}) introduces a constant together with its value. In the
language it means a new atom and two defining statements, g(x) -> e and
e -> g(x). The certificate kernel (the small independent checker of proofs, see
Steps as Theorems) knows definitions as one of its kinds of context: a
definition level that declares the constant with its value. This page shows the same definition
written with ordinary blocks, what the kernel checks, why nothing false can come from a definition, and how other
proof assistants treat definitions.
The same definition, written with blocks
Here is a definition and a step that uses it:
A definition
In the full code T, f and a are declared above.
For the steps of a proof the definition is the same as a new atom g with a lock whose axioms are the
two defining statements. The following code proves the same statement in the same way:
The same with a for block and a lock
The difference is what the axioms are. In the second program they are assumptions: any statement could
be written there, g(x) -> a as well, and every theorem below is proved only
for a g that satisfies them. In the first program they are true: g is
{x: T | f(x, a)}, and g(x) -> f(x, a) holds as
f(x, a) -> f(x, a). The definition level lets the kernel see this.
What the kernel checks
In the certificate the definition is a level {"define": [g, type, value]}, and each defining statement
is a level {"fact": [name, statement]}:
{"open": {"define": ["g", [[], ["fn", ["T"], "T"]],
[[], ["lam", ["T"], ["app", ["v", "f", []], [["b", 0], ["v", "a", []]]]]]]}}
{"open": {"fact": ["gDef", ["all", "x", [[], "T"],
["red", ["app", ["v", "g", []], [["v", "x", []]]],
["app", ["v", "f", []], [["v", "x", []], ["v", "a", []]]]]]]}}
- The value is checked where the definition stands, before the constant exists: its type must be the type of the constant, and it cannot mention the constant itself (a definition is not recursive).
- A fact must become true when the definition is unfolded: replace
gby its value, reduce, and both sides must be one term.g(x) -> f(x, a)becomesf(x, a) -> f(x, a);g(x) -> ais rejected. So the defining statements are not assumptions; a proof uses them like any hypothesis. - Closing the level. A result that mentions
gis closed as "g := {x | f(x, a)}in the result", and this means the result with the value in place ofg. A result withoutgleaves as it is. So the theorem above saysf(a, a) -> f(a, a)once the definition is closed. - References. A later step that refers to a theorem under the same definition (in the same block,
or in another file that imports the module where it is defined) keeps the constant:
g(a)staysg(a). Anywhere else the kernel unfolds it.
A result therefore leaves a definition by the rule of the definition itself; earlier the certificate builder had to write a call of the result with the body for the constant (Leaving a Block).
Why a definition is conservative
An extension is conservative if everything it proves about the old notions could be proved
without it. A definition is: take any proof that uses g and replace g by its value everywhere.
The facts of the definition turn into steps e -> e, which hold by
reflexivity. Every other step stays valid, because no rule of the kernel looks at what an atom is, only at the
shape of the terms (substituting a term for an atom keeps a proof a proof). What remains is a proof of the same
statement without the definition. This is the classical theorem on definitional extensions (J. Shoenfield,
Mathematical Logic, § 4.6), and it is exactly what the kernel does when it closes the level.
For the same reason a constant cannot be detached from its value. A definition made under for(x)
is about this x; outside the for block a theorem about it says something about the value:
A constant goes with its value
Applied to a, the theorem c -> x gives
a -> a, never c -> a for the old
constant. The language asks the call for the defining statement at the new value,
a -> a, as a statement proved here (Same: a call proves nothing
by itself); the kernel does not even need it, because it unfolds the definition. An early kernel rule for definitions
(of the first proof journal) treated the constant as a fresh atom with global axioms and could be tricked exactly here;
the regression tests tests/13_boundaries/36–41 keep this case closed.
define(f | T∃!), is not of this kind: it has no value, only a property that holds of exactly one thing. It stays a for block with a lock, and a result leaves it only with a function that satisfies the property (Leaving a Block). Leaving it without one would need a principle of description, like THE in Isabelle; that principle is not in the trusted base.How other systems do it
Almost every proof checker has definitions in its kernel. Definitions are the most common extension of a theory, and the kernel has to know that they cannot make a theory inconsistent; otherwise each definition would be one more axiom to trust.
| System | Definitions in the kernel |
|---|---|
| Lean 4 | def adds a constant with its value to the environment; the kernel unfolds it (δ-reduction) when it compares terms, so g f a a = f a a is proved by rfl. |
| Coq (Rocq) | Definition is a global constant unfolded by δ-reduction; a Let inside a Section is substituted when the section closes (ζ). This is the closest relative of our definition level. |
| Isabelle/HOL | definition adds the axiom g ≡ λx. f x a; the kernel accepts it only as a definition (a new constant, no cyclic dependencies) and gives the theorem g_def. |
| HOL Light | new_basic_definition is one of the few primitive rules of the kernel: from a closed term t it makes a constant c and the theorem ⊢ c = t. |
| Mizar | A definition comes with its correctness conditions (existence, uniqueness, coherence), which the checker verifies. |
| Metamath | The exception: definitions in set.mm are ordinary axioms (df-…); that they are conservative is checked by separate tools, not by the verifier. |
The Coq program below closes a section with a Let; the theorem it leaves is stated of the value, just as
a Formall theorem is when its definition closes:
Section Definitions. Variable T : Type. Variables (f : T -> T -> T) (a : T). Let g := fun x : T => f x a. Lemma L : g a = f a a. Proof. reflexivity. Qed. End Definitions. Check L. (* L : forall (T : Type) (f : T -> T -> T) (a : T), f a a = f a a *)
Why Formall builds it in
Formall's kernel is kept small: logic rules, equality, enumerations are schemas and lock axioms, not rules of the
kernel (Steps as Theorems). Definitions were treated the same way, as a
for block with a lock, and this was sound. But it had a price:
- the defining statements were assumptions of the certificate, and the kernel accepts an assumption of any formula; a separate tool had to check, against the source, that each one really was the definition;
- leaving a definition needed a step written by the certificate builder (a call with the body and reflexive realizations) instead of a rule of the block;
- every theorem stated after a definition carried its axioms as premises.
The definition level costs each of the two kernels (Python and C++) about a hundred and thirty lines with their comments: a context entry with a value, a check that a fact is true by unfolding, the binder that closing writes and the rule that keeps or unfolds it in a reference. In return the defining statements are proved, not assumed, and leaving a definition is the kernel's own rule. This is the choice made by Lean, Coq, Isabelle and HOL Light.
Locks and Realizations
How do compares signatures, and what locks in realizations mean
Overview
When a call applies a theorem proved in a lock(), you supply realizations — search labels whose statements implement the lock's axioms in the calling context. The interpreter does not require these realizations to be plain unconditional proofs: each may itself sit inside if, for, or rule blocks, and may even cross other locks. What is required is that the realization's surrounding context — its signature — is no wider than the signature of the axiom it implements.
This page is an extended worked discussion of that rule. It builds up gradually, from the simplest case to nested locks and shared paths. The compact specification is on the do page.
The basic match: realization beside the call
The simplest case: the theorem uses one lock with one axiom; the caller proves the axiom's conclusion in plain scope, labels the result, and passes the label to the call. The realization's path is just ifs — no for, no lock.
Plain realization
The theorem's axiom AxiomPQ is registered inside L under if(P -> false). The realization AxiomAB sits under if(A -> false) in the caller. The substitution P -> A, Q -> B makes the two signatures match: same if, no extra for, no extra rules.
Realization may use less than the theorem allows
The realization's signature may be narrower than what the theorem assumed — fewer ifs, fewer for-atoms, fewer rules. This means the realization proved its conclusion under stricter conditions than necessary, which is always sound.
Realization narrower than theorem
The theorem assumed the axiom under if(P -> false), but the caller proves B -> true outright. This is fine: the realization is strictly stronger than the theorem required.
Realization may not exceed the theorem
What is not allowed is the realization adding anything to its signature that the theorem did not have. An extra if, an extra for-atom of some type, or an extra rule — any of these would let the realization invoke assumptions the theorem never sanctioned. The call rejects such cases.
Realization with an extra if - rejected
The call reports that the realization's extra if-condition B -> false is not in the theorem's signature for this axiom. The realization could be reading any kind of falsehood out of that assumption - that is not something the theorem ever agreed to.
Expected error: Axiom realization not found
Locks in the realization
A realization's path may cross lock() nodes. Each such lock contributes its own axioms to the realization's signature, and each of those axioms must be matched by an axiom of some lock on the theorem's path. The match for nested lock axioms is by equality of signature, not by containment — a lock axiom is what the realization provides, so it must be exactly as strong as the theorem expects, neither weaker nor stronger.
The grouping of locks does not matter. The realization may split one theorem lock into several locks of its own, or merge several into one — as long as the resulting multiset of nested lock axioms is contained in the theorem's.
Nested locks: signatures match
The theorem's two locks together carry two supporting axioms. The realization carries both in a single outer lock. Because a call matches by multiset of nested-lock axioms (not by lock-by-lock isomorphism), the regrouping is accepted.
Parameters above and below the lock
An axiom keeps the entire schema declared inside its lock. Its own parameters are universally bound; a theorem argument cannot specialize them. Parameters declared above the lock are instance parameters and receive the theorem substitution.
Parameters above and below the lock
The realization supplies the full schema inside L. The parameters a,c and condition c -> true are above L and are handled by the theorem application.
The position of the lock determines the contract; the common ancestor of the axiom and the proof result does not remove schema parameters.
Multiple axioms in one lock
If a lock has several axioms, a call requires a realization for each one written before the theorem — whether or not the theorem actually uses it. The lock is a contract: every axiom standing in the lock when the theorem was proved is a hypothesis under which it was proved, and every one must be discharged. Realizations may be supplied in any order; the call matches them by signature, not by position.
All axioms must be realized
A lock is a contract: every axiom standing in it when the theorem was proved must be discharged. Order does not matter.
An axiom written after the theorem
The text is read in order, and a theorem is proved under the conditions that stand when it is written. An axiom added to the lock after the theorem could not take part in its proof, so it is no obligation of the theorem: a call asks for no realization of it. Here T1 is proved before Ax is added to A, and is applied outside A without one.
An axiom written after the theorem is not required
T1 rests only on what stood in A when it was proved. Written before T1, Ax would have to be realized (it cannot be here).
do inside a realization
A realization may freely call other theorems. The result of a call is a plain statement delivered into the current scope; whatever locks lived inside the theorem applied by that nested call stay there, never appearing on the outer realization's path.
A call inside a realization
A call gives a regular statement; the theorem applied by the inner call does not affect the outer realization's signature.
Summary
A call checks realizations by comparing signatures. A signature is a structured account of everything between a statement's definition and where its label was declared: the multiset of for-atoms (per type), the multiset of if-conditions, the multiset of rule rules.
For each axiom the theorem requires:
- The realization's signature must be contained in the axiom's signature — fewer or equal
for-atoms per type (positional, prefix-matched), fewer or equalifs, fewer or equal rules. - Parameters above the axiom's lock receive the theorem substitution. Its own parameters inside the lock remain part of the complete schema.
- Nested locks on either side contribute their axioms; these are matched by equality of signature, in any grouping.
The single underlying principle: the realization must not be allowed to use anything the theorem did not. Everything else — order, grouping, narrowing — is just freedom to write the proof naturally.
Formall vs. Other Proof Assistants
A structured comparison with Lean 4, Coq, Agda, Isabelle/HOL, and Metamath
Overview
Formall sits at a different point in the proof assistant design space than Lean 4, Coq, Agda, Isabelle/HOL, and Metamath. This page puts them side by side on the same concrete theorems, then summarises the conceptual differences. The goal is not a ranking but a clear picture of what each system optimises for.
- Lean 4 — dependent types, tactic and term mode, Mathlib standard library. Proofs and programs unified via Curry–Howard.
- Coq / Rocq — dependent types, tactic-based, constructive by default. Classical axioms are an explicit import.
- Agda — dependent types, no tactics, proof terms written directly. Constructive (intuitionistic) only.
- Isabelle/HOL — higher-order logic, structured Isar proof language, classical by default. Powerful automation via sledgehammer.
- Metamath — no built-in logic: axioms are declared as
$astatements, proofs are chains of substitutions written in reverse Polish notation. Its main databaseset.mmbuilds ZFC set theory from scratch (about 48,000 theorems); there are many small independent verifiers. The closest relative of Formall — see below. - Formall — typed atoms with HOL-style type variables (not dependent types, see below), scope-tree proofs, a small core of commands. No built-in logic — you define it from axioms.
Example 1: double negation elimination — ¬¬x → x
Prove: if ¬¬x holds, then x holds. Constructive systems (Agda, base Coq, base Lean) cannot prove this without a classical axiom.
Lean 4 — term mode with Classical
-- Classical is a built-in namespace; no external file needed
open Classical
-- em p : p ∨ ¬p (excluded middle, from Classical)
-- Or.elim splits the disjunction into two cases:
-- · left branch (hp : p) → return hp directly
-- · right branch (hnp : ¬p) → absurd : ¬p → ¬¬p → False → p
-- Result type: p
theorem dne {p : Prop} (h : ¬¬p) : p :=
Or.elim (em p)
(fun hp : p => hp) -- case p holds: done
(fun hnp : ¬p => absurd hnp h) -- case ¬p: contradicts h : ¬¬p
Coq (tactic mode) — with full manual classical setup
(* Coq is constructive by default.
We can either import Classical or declare the axiom ourselves. *)
(* Rule A: import the library *)
Require Import Classical.
(* This gives us: NNPP : forall P : Prop, ~~P -> P *)
Theorem dne_library : forall P : Prop, ~~P -> P.
Proof.
intros P H. (* H : ~~P, goal : P *)
apply NNPP. (* NNPP reduces ~~P → P to showing ~~P *)
exact H. (* H : ~~P. QED, result: P *)
Qed.
(* Rule B: declare classical axiom manually, no imports *)
Axiom excluded_middle : forall P : Prop, P \/ ~P.
Theorem dne_manual : forall P : Prop, ~~P -> P.
Proof.
intros P H.
destruct (excluded_middle P) as [hp | hnp].
- exact hp. (* case P holds: done, result P *)
- exfalso. (* goal becomes False *)
apply H. exact hnp. (* H : ~~P, hnp : ~P, so H hnp : False *)
Qed.
Agda — constructive only; DNE requires a postulate
-- Agda's logic is intuitionistic: ¬¬A → A is not provable.
-- We can postulate excluded middle as an axiom:
open import Data.Empty using (⊥; ⊥-elim) -- ⊥ = False
open import Data.Sum using (_⊎_; inj₁; inj₂)
-- ¬ A is defined as A → ⊥
¬_ : Set → Set
¬ A = A → ⊥
-- Postulate excluded middle (not provable constructively)
postulate
em : (A : Set) → A ⊎ ¬ A
-- Double negation elimination using the postulate
dne : {A : Set} → ¬ ¬ A → A
dne {A} h with em A
... | inj₁ a = a -- case A holds: return a directly
... | inj₂ ¬a = ⊥-elim (h ¬a)
-- case ¬A: h : ¬¬A, ¬a : ¬A, so h ¬a : ⊥, ⊥-elim gives A
Isabelle/HOL — classical by default, Isar proof language
(* Isabelle/HOL is classical; no imports needed. *) (* 'classical' is a built-in rule: (¬P ⟹ P) ⟹ P *) theory DNE imports Main begin theorem dne: "¬¬P ⟹ P" proof (rule classical) (* apply classical: assume ¬P, prove P *) assume "¬P" "¬¬P" (* both assumptions now in context *) then show P by contradiction (* ¬P and ¬¬P directly contradict *) qed (* Result: ¬¬P ⟹ P *) end
Metamath (set.mm)
$( Metamath has no built-in logic either: set.mm declares its axioms
(ax-mp, ax-1, ax-2, ax-3, ...) as $a statements, and a proof is a
list of labels in reverse Polish notation. The verifier only checks
that every step is a correct substitution instance. $)
$[ set.mm $]
$( Double negation elimination from Clavius' law
pm2.18 : |- ( ( -. ph -> ph ) -> ph )
jarli turns |- ( ( ph -> ps ) -> ch ) into |- ( -. ph -> ch ). $)
dne $p |- ( -. -. ph -> ph ) $=
wph wn wph wph wph pm2.18 jarli $.
$( wph wn : build the wff -. ph (substituted for ph in jarli)
wph wph : ps := ph, ch := ph
wph pm2.18 : jarli's hypothesis, an instance of Clavius' law
Result: |- ( -. -. ph -> ph ) $)
Formall: double negation elimination
No imports. The logic rules — which truth values contradict each other, how not behaves — are declared explicitly at the top. The proof assumes x -> false, derives not(not(x)) -> false by a proof, then contradict closes the assumption. Result: x -> true inside the outer if block.
Example 2: reusing a theorem — ¬¬¬x → ¬x
Apply the double negation theorem to ¬x instead of x.
Lean 4
open Classical
-- Lean's type system unfolds ¬¬¬p as ¬¬(¬p) automatically.
-- dne is applied with implicit argument ¬p inferred from context.
theorem triple_neg {p : Prop} (h : ¬¬¬p) : ¬p :=
dne h
-- Result: ¬p (Lean infers the substitution from the type)
Coq (tactic mode)
Axiom excluded_middle : forall P : Prop, P \/ ~P. Theorem dne_manual : forall P : Prop, ~~P -> P. Proof. intros P H. destruct (excluded_middle P) as [hp | hnp]. - exact hp. - exfalso. apply H. exact hnp. Qed. Theorem triple_neg : forall P : Prop, ~~~P -> ~P. Proof. intros P H. (* H : ~~~P, goal : ~P i.e. P → False *) apply dne_manual. (* reduce goal to ~~(~P) = ~~~P *) exact H. (* H : ~~~P matches. Result: ¬P *) Qed.
Agda
-- Using dne from Example 1 (with em postulate)
triple-neg : {A : Set} → ¬ ¬ ¬ A → ¬ A
triple-neg h = dne h
-- Agda unifies ¬¬¬A with ¬¬(¬A); dne applied with A := ¬A.
-- Result: ¬A
Isabelle/HOL
theory TripleNeg imports DNE begin (* Use dne lemma from Example 1 *) theorem triple_neg: "¬¬¬P ⟹ ¬P" using dne by blast (* blast: automated reasoner closes the goal instantly. *) (* Result: ¬P *) end
Metamath (set.mm)
$( Reuse dne from Example 1. The verifier computes the substitution ph := -. ph itself; the proof only builds the wff -. ph (wph wn). $) triple-neg $p |- ( -. -. -. ph -> -. ph ) $= wph wn dne $. $( Result: |- ( -. -. -. ph -> -. ph ) $)
Formall: reuse by a call
MyDNE[not(y)] substitutes not(y) for x in the theorem. The substitution is explicit — passed as a string. Lean and Agda infer it from types; Coq infers it from the goal. Result: not(y) -> true inside not(not(not(y))) -> true.
Example 3: symmetry of equality — x = y → y = x
Lean 4
-- Equality (=) is built into Lean's type theory (reflexivity, congruence).
-- h ▸ rfl: rewrite the goal "b = a" using h : a = b, giving "a = a",
-- then close with rfl (reflexivity). Result: b = a
theorem eq_symm {α : Type} {a b : α} (h : a = b) : b = a :=
h ▸ rfl
Coq (tactic mode)
Theorem eq_symm : forall (A : Type) (a b : A), a = b -> b = a. Proof. intros A a b H. (* H : a = b, goal : b = a *) rewrite H. (* rewrite a → b in goal via H, goal becomes b = b *) reflexivity. (* close b = b. Result: b = a *) Qed.
Agda
-- Equality is defined inductively (refl : a ≡ a)
-- Pattern matching on refl forces a = b, unifying a and b.
open import Relation.Binary.PropositionalEquality using (_≡_; refl)
sym : {A : Set} {a b : A} → a ≡ b → b ≡ a
sym refl = refl
-- When h : a ≡ b is matched as refl, a and b become equal by definition.
-- refl then proves b ≡ a trivially. Result: b ≡ a
Isabelle/HOL
theory EqSym imports Main begin (* sym is already in Main; shown here for comparison *) theorem eq_sym_manual: "a = b ⟹ b = a" proof - assume h: "a = b" (* h : a = b in context *) from h show "b = a" by (rule sym) (* sym : a = b ⟹ b = a *) qed (* Result: b = a *) end
Metamath (set.mm)
$( Class equality is defined in set.mm (df-cleq), and eqcom is a theorem:
eqcom : |- ( A = B <-> B = A )
mpbi : from |- ph and |- ( ph <-> ps ) conclude |- ps
A ${ ... $} block scopes the hypothesis eqsym.1 to this theorem. $)
${
eqsym.1 $e |- A = B $.
eqsym $p |- B = A $=
cA cB wceq cB cA wceq eqsym.1 cA cB eqcom mpbi $.
$}
$( Result: from |- A = B infer |- B = A $)
Formall: symmetry of equality
Formall has no built-in equality. Reflexivity is an explicit axiom; rewriting is the substitution syntax <=(y, <x>)>; indiscernibility is a lock axiom. More code than other systems — but every rule that equality follows is visible and auditable. Result: L=Sym — =(y, x) -> ✔ whenever =(x, y) -> ✔.
Conceptual differences
Metamath: the closest relative
Of all the systems on this page, Metamath shares Formall's core philosophy most closely: the verifier knows no logic. In Metamath, ax-mp, the propositional axioms and ZFC are ordinary $a declarations in a text file; the verifier checks only that every proof step is a correct substitution instance of an earlier statement. The whole language is a handful of keywords ($c $v $f $e $d $a $p), and set.mm — about 48,000 theorems of ZFC — is verified by the reference program in roughly four seconds. Even the route to double negation is the same: set.mm derives it from Clavius' law ((¬φ → φ) → φ), which is exactly what Formall's contradict does when it flips an assumption.
The differences are in what the core takes care of:
- Binders and variables. Metamath is pure string substitution; bound variables are managed by explicit distinct-variable conditions (
$d) and substitution lemmas. Formall has typed terms and constructors{x: T | …}with α-equivalence built in, so bound variables need no bookkeeping. - Contexts. Metamath is Hilbert-style: there are no local assumptions, so set.mm writes most theorems in deduction form
ph -> …and carries the context by hand. Formall's scope tree (if,for,rule) gives natural-deduction-style contexts directly. - Proof text. A Metamath proof is a list of labels in reverse Polish notation (including the steps that merely build formulas); it is compact and machine-checkable but unreadable without a tool that displays it. A Formall proof is a sequence of commands, each producing a visible statement.
- Instantiation. Metamath's verifier computes substitutions by unification —
wph wn dneis enough to usedneat¬φ. A Formall callT[a]takes the substitution as written values, or infers them from the conditions of the theorem. - Hypothetical theorems. Metamath's essential hypotheses (
$e) turn a theorem into an inference rule whose premises must be proved before use. Formall'slock()/axiom/ call plays the same role, but a realization may itself be proved under localfor/ifassumptions and is matched by signature. - Ecosystem. Metamath has a large library, a detailed specification and several independent verifiers written in different languages. Formall has one interpreter and a growing corpus.
In short: Metamath minimises the trusted kernel; Formall trades a somewhat larger kernel (types, binders, scopes, contradiction) for proofs that read as structured text.
Logic system: axiom-defined vs. built-in
Lean, Coq, and Agda have a fixed constructive core — intuitionistic type theory. Classical axioms exist but must be added deliberately. Isabelle/HOL is classical but still has a fixed higher-order logic built in.
Formall, like Metamath, has no built-in logic at all. type(bool = false | true) declares the truth values, every two different; if axioms declare how connectives behave; lock() introduces any further axioms. You can define classical boolean logic (as above), a three-valued logic, or a custom axiom system — Formall treats them identically. There is no constructive/classical split to manage, because the distinction is itself defined by your axioms.
Types: three designs
A frequent question: how do you state one equality = that works for numbers, sets and functions alike? The three families of systems answer it differently.
Metamath: one universe, no types
set.mm has no types of mathematical objects. Everything — the number 2, a real number, a function, ℝ itself — is a set (a class). So there is a single = between classes, and no =ℕ, =ℝ copies; ℕ ⊆ ℝ is ordinary inclusion. "x is a real number" is a hypothesis A ∈ ℝ, not a type. Metamath has only syntactic sorts (wff, setvar, class) that keep formulas well-formed. A theorem is a scheme over metavariables, and applying it is textual substitution.
HOL (Isabelle/HOL, HOL Light) and Formall: type variables outside the statement
Formall follows this design. A type variable 'α makes an atom polymorphic and every statement about it a scheme; a call substitutes a concrete type. This is how library/logic/equality.fl declares equality once for every type:
Formall (actual library code)
type("'α");
for("=: ['α, 'α -> 𝔹]"); notation("infix", "=", "50");
for ("x: 'α") A=Reflexive: axiom(𝒜, "x = x");
for ("a, b: 'α") if ("a = b") A=Rewrite: axiom(𝒜, "a -> b");
'α stays outside the statement: one cannot write a single statement that says "for every type". Structures such as groups are theory blocks type(G) for(∘, e) if(axioms) { … } applied by calls — the same idea as Isabelle's locales. The kernel needs no computation, and equality of types is plain syntactic equality.
Inside a block a premise over 'α can be used at another type: a proof about ℕ rewrites with A=Rewrite at ℕ. The certificate kernel (Reducibility) states such a premise as the schema it is, "for every type A, A=Rewrite at A", and each use is the schema taken at a type, which the kernel checks like any other step. The certificate has a quantifier over types for this; the language does not need one, because 'α already says it. Other systems differ here. HOL instantiates a whole theorem at a type together with its hypotheses (INST_TYPE), so the hypothesis at the other type becomes one more hypothesis of the theorem. Isabelle keeps 'a fixed inside a locale, and the locale's assumptions cannot be used at another type there. In Lean and Coq a hypothesis "for every type" is an ordinary formula ∀ α, P α.
Lean, Coq, Agda: types are values (dependent types)
The code below is hypothetical — Formall does not support it. It shows what Formall would look like on the dependent-type route.
1. A type of types 𝕋 (Lean's Type) lets a statement quantify over types inside the formula:
Hypothetical Formall
for("=: ∀{T: 𝕋 | [T, T -> 𝔹]}") // one constant with a type argument
axiom(𝒜, "∀{T: 𝕋 | ∀{x: T | =(T, x, x)}} -> ✔")
if("∀{T: 𝕋 | ∃{x: T | ✔}} -> ✔") // "every type is inhabited" as a hypothesis
2. A structure is a value, and its carrier is a type computed from that value:
Hypothetical Formall
define("Group", "{ G: 𝕋, ∘: [G, G -> G], e: G, assoc: …, … }")
for("H: Group")
for("a, b: H.G") // the type depends on the value H
"∀{H: Group | ∀{a: H.G | a H.∘ H.e = a}}" // an ordinary statement about all groups
This allows lists of groups, a function "group ↦ its centre (a group)", the type of elements of a subgroup.
3. A type depending on a number — and the price:
Hypothetical Formall
for("Vec: [ℕ -> 𝕋]")
for("append: ∀{n, m: ℕ | [Vec(n), Vec(m) -> Vec(n + m)]}")
for("n: ℕ") for("v: Vec(n), w: Vec(0)")
"=(append(v, w), v)" // TYPE ERROR unless the kernel computes Vec(n + 0) to Vec(n)
- The kernel must compute. To see that
Vec(n + 0)andVec(n)are the same type it has to reducen + 0— a small evaluator inside the trusted kernel. - Theorems do not help type checking. If addition recurses on the second argument,
0 + ndoes not reduce ton;0 + n = nis only a theorem, so one needs an explicit cast ("transport"). Fighting such casts is a known cost in Mathlib. - Equality depends on typing.
x = yis well-formed only when the types coincide, and that coincidence is a computation, not a statement.
On the HOL route one writes v: 𝕊 with a hypothesis length(v) = n instead: coarser, but the kernel needs no evaluator.
Which is better?
There is no consensus; it is a trade-off. Dependent types are more expressive, and Lean has the largest library of formal mathematics (Mathlib). HOL has a much smaller logic and kernel (HOL Light's is a few hundred lines), strong automation (Sledgehammer) and large verification projects (seL4, CakeML); it is argued (e.g. by Paulson) that HOL with locales suffices for most ordinary mathematics. Formall takes the HOL route: its goal is a small, reliable, checkable kernel — rank-one polymorphic constants plus schematic theorems, with "for every structure" expressed by theory blocks and calls.
Proof structure: tactics vs. scope tree
Coq and Lean build proofs interactively by transforming goals. You see the current goal state, apply a tactic, and get subgoals. Lean 4 has simp, omega, decide, and grind — tactics that solve whole classes of goals in one step. Isabelle's sledgehammer calls external theorem provers automatically.
Formall builds proofs as a static nested-block tree. There are no goals, no subgoal queue, no tactic state. Each if block introduces an assumption; each for introduces variables; each lock introduces local axioms. The structure of the code is the structure of the proof. Every step is an explicit command with a precisely defined effect. Formall proofs are longer, but fully readable as text without a running proof assistant.
Standard library vs. blank slate
Lean's Mathlib, Coq's standard library, and Isabelle's Archive of Formal Proofs each contain tens of thousands of theorems. Agda's standard library is similarly substantial. Working in these systems, you build on a large existing body of mathematics.
Formall starts from axioms. The library modules (library/logic/uniqueness.fl, library/sets/main.fl, library/peano/main.fl) build logic, arithmetic, and set operations from explicit axioms — including the Russell paradox, ordered pairs by Kuratowski, and existence of unions. This is slower to use but makes the foundations completely explicit and auditable.
A small core
Lean, Coq, and Isabelle have large trusted kernels and many derived rules. The kernel correctness is what you ultimately trust. Metamath sits at the other extreme: its whole verification rule is "check the substitution", and independent verifiers fit in a few hundred lines.
Formall's trusted core is a handful of commands — type, for, if, lock, rule, axiom — and two forms: proofs <…> and calls T[…]. The steps of a proof — contradiction, generalization, calls on quantified facts — and even if are expressed through lock, axiom and calls, as shown on the Command Reducibility page. If you understand what the core commands do, you understand everything the interpreter can verify.
induction tactic with Formall's Peano axiom approach; a set theory example; and the Curry–Howard correspondence — how proofs-as-programs applies (or does not) to Formall.API
API
Submit Formall source code and receive interpreted output files.
Upload & Run
Upload a .fl file or paste source code directly to interpret:
Endpoints
POST /api/run
Submit source code for interpretation. Accepts either a file upload or raw source text.
POST /api/runRequest (file upload)
Content-Type: multipart/form-data
| Parameter | Type | Description |
|---|---|---|
file | file | Formall source file (.fl). Max 2 MB. |
Request (source text)
Content-Type: multipart/form-data or application/x-www-form-urlencoded
| Parameter | Type | Description |
|---|---|---|
source | string | Formall source code as plain text. Max 2 MB. |
Response
{
"success": true,
"token": "aBcDeFgHiJkLmNoPqRsTuVxYz012345",
"status_url": "/api/status?token=aBcDeFgHiJkLmNoPqRsTuVxYz012345",
"files": {
"source": "/files/TOKEN/source.fl",
"output": "/files/TOKEN/output.txt",
"result": "/files/TOKEN/result.txt",
"statements": "/files/TOKEN/statements.txt",
"log": "/files/TOKEN/log.txt",
"messages": "/files/TOKEN/messages.txt",
"tree": "/files/TOKEN/tree.txt",
"links": "/files/TOKEN/links.txt",
"labels": "/files/TOKEN/labels.txt"
}
}
status_url to poll for results.GET /api/status
Check whether the interpretation has finished. Once ready is true, download result files via the URLs returned by /api/run.
GET /api/status?token=TOKEN| Parameter | Type | Description |
|---|---|---|
token | string | 32-character alphanumeric session token returned by /api/run. |
Response (processing)
{ "ready": false }
Response (ready)
{ "ready": true, "ok": true, "exit_code": 0 }
ok is true when the code is checked without errors
(exit code 0); exit code 1 means an error in the code, other codes a failure of the interpreter.
GET /files/{token}/{filename}
Download individual result files directly once interpretation is complete.
Available files (the interpreter runs as formall source.fl -o DIR, see
the command line):
source.fl— the sourceoutput.txt— what the interpreter printed: the error, warnings and notices about the source, and the result lineOK <seconds>orERROR <seconds>result.txt— the result line alone, written laststatements.txt— every statement with its positionlog.txt— every command with the statements it gives and all messagesmessages.txt— all errors, warnings, notices and remarks, also about imported fileslabels.txt— labels and their statementslinks.txt— the premises of every statementtree.txt— the block tree (for debugging the interpreter)
Runs made before 2026-10-11 keep their old file names (out.fl,
log.fl, log.messages.fl, …).
Command line
The same interpreter runs locally:
formall FILE.fl [options] -o, --out DIR all reports with standard names in DIR (created if missing); result.txt last --log FILE every command with the statements it gives and all messages --statements FILE every statement with its position --messages FILE all errors, warnings, notices and remarks, also about imported files --links FILE, --labels FILE, --tree FILE, --result FILE --certificate-journal FILE a certificate of every statement (JSON lines), checked by the independent kernel --trust FILE the axioms, definitions, rules and conditions of every theorem T:: --profile FILE where the time went --cache DIR where module objects are kept (default: .formall next to formall.project, else ~/.cache/formall) -j, --jobs N modules compiled in parallel --import-root DIR also allow import() from DIR; --allow-any-import --explicit every value and fact is written (calls) --prefix, --no-fold printing; -q, --quiet only the error on stderr; -h, --help
Imported files are modules: each is checked once and kept as an object in the cache; only what changed is checked again (import).
The last line on stdout is OK <seconds> or
ERROR <seconds>; the exit code is 0 (OK), 1 (an error in the file) or 2 (a wrong
command line, a file that cannot be read or written). The error, and the warnings and notices about the file itself
(not about imported files, not about text generated by decide), go to stderr.
Errors
Error responses use standard HTTP status codes:
| Code | Meaning |
|---|---|
400 | No input provided |
405 | Method not allowed (use POST for /api/run) |
413 | File or source too large |
500 | Internal server error |
Examples
cURL — file upload
curl -X POST -F "file=@example.fl" https://formall.mooo.com/api/run
cURL — source text
curl -X POST -d "source=for x (do)" https://formall.mooo.com/api/run
cURL — check status
curl https://formall.mooo.com/api/status?token=YOUR_TOKEN
JavaScript (fetch)
// Create file input element
const fileInput = document.createElement('input');
fileInput.type = 'file';
document.body.appendChild(fileInput);
// Handle file selection
fileInput.onchange = async () => {
try {
// Prepare form data with selected file
const form = new FormData();
form.append('file', fileInput.files[0]);
// Upload file
const res = await fetch('https://formall.mooo.com/api/run', {
method: 'POST',
body: form
});
const data = await res.json();
// Poll for completion
const poll = async (token) => {
const r = await fetch(`https://formall.mooo.com/api/status?token=${token}`);
const s = await r.json();
if (s.ready) return s;
await new Promise(r => setTimeout(r, 1000));
return poll(token);
};
await poll(data.token);
// Download output file
const output = await fetch(`https://formall.mooo.com${data.files.output}`)
.then(r => r.text());
console.log(output);
} catch (error) {
console.error('Error:', error);
}
};
// Open file picker
fileInput.click();
Python (requests)
import requests, time
# Upload file
r = requests.post('https://formall.mooo.com/api/run',
files={'file': open('example.fl', 'rb')})
data = r.json()
token = data['token']
# Poll for results
while True:
s = requests.get(f'https://formall.mooo.com/api/status?token={token}').json()
if s['ready']:
break
time.sleep(1)
# Download output
output = requests.get(f'https://formall.mooo.com{data["files"]["output"]}').text
print(output)