Playground Documentation Challenges Full Docs

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

▶ Run

Function Application

Apply a function to arguments with parentheses:

Function application

▶ Run

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})).

⚠
Nesting is what the shorthand means for every such atom, including ∃!: ∃!{x, y: T | P} is ∃!{x: T | ∃!{y: T | P}} («exactly one x for which there is exactly one y»), which is not the same as «exactly one pair (x, y)».

Constructor syntax

▶ Run

Lexical Rules

  • A name (atom, type, label, command) is a run of letters, digits, _!$%&'.=?@\`~ and any non-ASCII characters: ➕, ∀𝔹, L➕1, =Color are single names. In expressions — the terms of commands, calls and proofs — an atom name may also contain + * ^ - (a-b is one name, a - b an 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 ∘ b is three names, a∘b is 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 a​b and ab would 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

▶ Run

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.

▶ Run

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

▶ Run
❗
Formall expressions are purely syntactic — there's no evaluation or simplification. ➕(1, 1) and 2 are different expressions unless you prove they're equal.