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.