Cubist

LANGUAGE REFERENCE · CHAPTER 3

Functions, pairs and sums

Each basic type in full: how to build its values and how to use them, expected types, and precedence.

Types at a glance

Propositions are types, and a proof of a proposition is an element of it. There is no separate sort of propositions. A -> B is implication, A and B is conjunction, A or B is a disjunction that records which side holds, and A -> Void is negation.

SourceMeaningBuild an elementUse an element
A -> BFunctions, and implicationfun (a : A) => b, or intro a;Application f(a)
forall x : A. B(x)Dependent functions, Πx:A B(x)The same as for ->Application f(a) : B(a)
A and BPairs, A × B(a, b)Projections p.1, p.2; obtain, unpack
exists x : A. B(x)Dependent pairs, Σx:A B(x)(witness, evidence)Projections p.1 : A, p.2 : B(p.1); obtain, unpack, pair_induction
A or BDisjoint sums, A + Bleft(a), right(b)match
UnitThe one-element typettunit_induction
VoidThe empty type, falsehoodNoneabsurd
UNatNatural numbers0, succ(n), numeralsmatch, induction
x = yEquality: paths from x to yrefl(x)See equality and paths
U0, U1, …Universes of typesTypes themselvesSee universes

exists is a pair with an actual witness. It is not truncated. Likewise, or keeps the side a value is on. For mere existence, use propositional truncation.

Functions

fun (x : A) => body is the function sending x to body. Its type is A -> B when body : B does not mention x, and forall x : A. B(x) when it does. Binders can be grouped like parameters:

SourceMeans
fun (x, y : A) => bodyfun (x : A) => fun (y : A) => body
fun (a : A, b : B) => bodyBinders with different types, separated by commas, exactly as in a parameter list
fun x => bodyOne binder whose type is taken from the expected function type
def constant(A, B : U0) := fun (a : A, b : B) => a;

def second(A : U0) := fun (x, y : A) => y;

def twice(A : U0, f : A -> A) := fun (x : A) => f(f(x));

A binder without a type needs an expected function type, from a stated result type, an exact goal or typed. In compose_, each untyped binder reads its type from the goal: g : B -> C, then f : A -> B, then x : A.

import unat;

def compose_(A, B, C : U0) : (B -> C) -> (A -> B) -> A -> C {
  exact fun g => fun f => fun x => g(f(x));
}

def successor_function := typed(UNat -> UNat, fun n => succ(n));
def no_expected_type := fun x => x;  // Error: Untyped lambda requires an expected function type.

All typed binders go in one parenthesized list, separated by commas, as in parameters. An untyped binder stands alone: fun x => fun y => ….

Currying

A function of several parameters takes them one at a time. Its type is a chain of arrows, A -> B -> C, which reads A -> (B -> C): given an A, it returns a function that waits for a B. This is called currying. So f(a, b) means f(a)(b), and f(a) alone is a function waiting for the rest. Arguments can be supplied all at once, one at a time, or a few at a time; every argument is written, or is a hole that the others determine.

import unat;
use unat;

def apply_twice(A : U0, f : A -> A, a : A) := f(f(a));

// All at once, one at a time, or a few at a time.
def five := apply_twice(UNat, fun (n : UNat) => succ(n), 3);
def five_again := apply_twice(UNat)(fun (n : UNat) => succ(n))(3);
def add_two := apply_twice(UNat, fun (n : UNat) => succ(n));
def twice_on_nat := apply_twice(UNat);

evaluate add_two(3) expecting five;
evaluate twice_on_nat(fun (n : UNat) => n + n, 3) expecting 12;

Each argument turns the function into one that waits for the remaining ones:

> typeof apply_twice;
forall A : U0. (A -> A) -> A -> A
> typeof apply_twice(UNat);
(UNat -> UNat) -> UNat -> UNat
> typeof add_two;
UNat -> UNat
> evaluate !!add_two;
fun (m : UNat) => succ(succ(m))

apply_twice(UNat) is a function of the other two parameters, and add_two, with a function supplied too, waits only for the number. Evaluating it shows the function it is: it applies succ twice.

Only a function can be applied:

import unat;
use unat;

def not_a_function := 0(1);  // Error: Source application is not a function.

Dependent functions

In forall x : A. B(x), the result type depends on the argument. Applying f : forall n : UNat. P(n) to 0 gives an element of P(0). forall x, y : A. B abbreviates two nested quantifiers over the same type.

import unat;
use unat;

def apply_at_zero(P : UNat -> U0, f : forall n : UNat. P(n)) : P(0) {
  exact f(0);
}

def swap_arguments(A : U0, P : A -> A -> U0, f : forall x, y : A. P(x, y)) : forall y, x : A. P(x, y) {
  intro y, x;
  exact f(x, y);
}

The argument decides the result type, so f(0) does not prove P(1):

import unat;
use unat;

def wrong_index(P : UNat -> U0, f : forall n : UNat. P(n)) : P(1) {
  exact f(0);  // Error: Type mismatch: found P(0), expected P(1).
}

Functions defined by cases, on sums below or on inductive types, use match. A function that calls itself on smaller values uses structural recursion.

Holes and named arguments

An argument that the call's other arguments determine can be left as a hole, _. The elaborator reads it off the types of the other arguments and the type the call is expected to have, and the kernel checks the call as though the argument had been written. In joined, the carrier and the three endpoints come from the two paths:

import unat;

def concat(U < UU0, A : U, x, y, z : A, p : x = y, q : y = z) : x = z := trans(p, q);

def joined(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat(U0, _, _, _, _, p, q);

A named argument, x := e, gives the parameter x of a definition. Each parameter before the last one given that no argument gives is a hole, and the arguments without names fill the other parameters in order. The parameters after the last one given are left for a later application, as in f(a):

import unat;

def apply(U < UU0, A, B : U, f : A -> B, a : A) : B := f(a);

def by_name(n : UNat) : UNat := apply(U0, a := n, f := fun x => succ(x));
def successor : UNat -> UNat := apply(U0, f := fun (x : UNat) => succ(x));

In by_name, A and B are holes: n gives A and the expected type gives B. The untyped fun x => succ(x) waits for both, then is checked against UNat -> UNat. Click a hole in the workspace to see what it became.

A hole is filled only by what determines it. Nothing is searched for, so a hole whose type has an inhabitant, such as a proof of n = n, is still refused. The arguments of a built-in form, such as refl, and of a constructor are written out:

import unat;

def same(U < UU0, A : U, a : A) : A := a;

def no_search(n : UNat) : n = n := same(U0, n = n, _);  // Error: Nothing determines the parameter a of same, of type n = n: not the other arguments' types, nor the type expected of the call. Give it explicitly.

Cumulativity can leave a type open: UNat is in U0, and in every larger universe too. Where a larger universe would do as well, the hole is refused rather than guessed:

import unat;

def same(U < UU0, A : U, a : A) : A := a;

def universe_open := same(U2, _, UNat);  // Error: The parameter A of same is not determined: U0 fits, and so would a larger universe. Give it explicitly.

Bounds on both sides settle it: in pinned, T : U1 needs A to hold T, and the expected type needs A to be at most U1, so A is U1.

def same(U < UU0, A : U, a : A) : A := a;

def pinned(T : U1) : U1 := same(U2, _, T);

Universe arguments

A universe argument can be a hole too. It is the least universe the call needs: the largest of the universes the other arguments' types say it must contain, or the one an equality of types fixes. In same(_, UNat, n), A := UNat is in U0, so U is U0. Where nothing bounds it and the call's type does not mention it, any universe would do, and it is U0; where the call's type does mention it, it is refused:

import unat;

def same(U < UU0, A : U, a : A) : A := a;

def at_nat(n : UNat) : UNat := same(_, UNat, n);
def at_types(T : U1) : U1 := same(_, U1, T);
import unat;

def the_universe(U < UU0, n : UNat) : next(U) := U;

def which(n : UNat) := the_universe(_, n);  // Error: Nothing determines the universe U of the_universe: no argument's type bounds it, and the call's type depends on it. Give it explicitly.

Implicit parameters

Parameters in double braces, {{ … }}, before a definition's parameter list are implicit: a call reads them off its other arguments and the type expected of it, universes included, and gives only the others, in parentheses. Each implicit parameter before the last argument given is a hole. So append reads its universe and element type off its lists:

import lists;
use unat;

def three := length(append(cons(1, typed(List(U0, UNat), nil)), cons(2, cons(3, nil))));
evaluate three expecting 3;

def concat{{U < UU0, A : U, x, y, z : A}}(p : x = y, q : y = z) : x = z := trans(p, q);

def joined(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat(p, q);

To give implicit arguments yourself, write them in double braces after the name, in order: concat{{U0, UNat}}(p, q) gives U and A, and the endpoints after them are still inferred. _ leaves one to infer. Inside them, a named argument gives an implicit parameter by its name, as concat{{A := UNat}}(p, q), and the others fill the rest in order; an implicit parameter is not named in parentheses, nor an explicit one in double braces:

import unat;

def concat{{U < UU0, A : U, x, y, z : A}}(p : x = y, q : y = z) : x = z := trans(p, q);

def all_given(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat{{U0, UNat, a, b, c}}(p, q);
def middle(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat{{_, _, _, b}}(p, q);
def named(a, b, c : UNat, p : a = b, q : b = c) : a = c := concat{{A := UNat}}(p, q);

Double braces settle what the call leaves open. Here T : U0 and the expected type U1 both fit A := U0 and A := U1:

def same{{U < UU0, A : U}}(a : A) : A := a;

def open_type(T : U0) : U1 := same(T);  // Error: The parameter A of same is not determined: U0 fits, and so would a larger universe. Give it explicitly.
def settled(T : U0) : U1 := same{{_, U0}}(T);

An argument whose type applies a definition, as Tagged(U0, Unit), and a parameter's type that applies the same definition, as Tagged(U, A), are compared unfolded first. Where that leaves a parameter open, the other arguments and the expected type settle it if they can; only then are the two matched argument by argument. So the arguments are read off even where the definition's value forgets them: Tagged(U, A) is UNat whatever A is, and untag(t) still finds A := Unit. But an argument that does determine the parameter comes first: Family(n) is UNat too, and pick(a, refl(1)) finds n := 1 from refl(1), not 0 from a's type. When the arguments do not all match, nothing they solved is kept. A theory's homomorphisms rely on this: f.map reads f's models off f : Monoid.Hom(A, B) (homomorphisms).

import unat;
use unat;

def Tagged(U < UU0, A : U) : U0 := UNat;

def untag{{U < UU0, A : U}}(t : Tagged(U, A)) : UNat := t;

def tag_of(t : Tagged(U0, Unit)) : UNat := untag(t);

def Family(n : UNat) : U0 := UNat;

def pick{{n : UNat}}(a : Family(n), h : n = 1) : UNat := n;

def picked(a : Family(0)) : UNat := pick(a, refl(1));

The library's lists declares append{{U < UU0, A : U}}(xs, ys : List(U, A)). A definition that calls itself passes its implicit parameters unchanged: length(tail) in its own clause, never length{{U, A}}(tail). Double braces without parentheses give the function of the other parameters, so same{{U0, UNat}} is the identity on UNat; the name of a definition alone is the function of all its parameters. Goals and messages show a definition's implicit arguments in double braces too: append{{U, A}}(xs, nil) = xs.

A definition names its parameters apart, implicit or not, since a call can give each one by its name. So does a declared type, and each constructor its arguments:

def twice{{x : UNat}}(x : UNat) : UNat := x;  // Error: twice has two parameters named x: give each its own name.

Pairs and dependent pairs

(a, b) builds an element of A and B, or of exists x : A. B(x) when b : B(a). For an existential, the first component is the witness and the second is the evidence about it.

import unat;
use unat;

def two_units := typed(Unit and Unit, (tt, tt));

def two_exists : exists n : UNat. n = 2 {
  exact (2, refl(2));
}

A pair needs an expected type. (1, 2) could belong to UNat and UNat or to many exists types, and the elaborator does not guess. The expected type comes from a stated result type, a let's stated type, a function argument’s type or typed.

def unannotated := (1, 2);  // Error: Pair requires an expected type.

Tuples

The kernel has only binary pairs. Tuple notation (a, b, c) means (a, (b, c)), and the same notation works for types: A and B and C means A and (B and C). Explicit left nesting ((a, b), c) is a different shape.

import unat;
use unat;

def flat_triple : UNat and Unit and UNat {
  exact (1, tt, 2);
}

def nested_triple : (UNat and Unit) and UNat {
  exact ((1, tt), 2);
}

def first_of_three(t : UNat and UNat and UNat) : UNat {
  obtain (a, b, c) := t;
  exact a;
}

def one := first_of_three((1, 2, 3));

To pass a tuple as one argument, keep its parentheses: f((1, 2, 3)). f(1, 2, 3) passes three arguments. A tuple must match the nesting of its type:

import unat;
use unat;

def wrong_nesting : (UNat and Unit) and UNat {
  exact (1, tt, 2);  // Error: Expected a Sigma type for pair.
}

The formatter, npm run format:cubist, writes right-nested pairs as flat tuples and checks that the expanded syntax is unchanged. npm run linearize:cubist -- --check lists such pairs without changing any file.

Using a pair

p.1 and p.2 are the components of a pair p. For p : exists x : A. B(x), p.1 : A is the witness and p.2 : B(p.1) is the evidence about it. The dot is tight, with no space on either side. Projections apply to any term of a pair type, such as f(x).2, and they chain: the components of t : A and B and C are t.1, t.2.1 and t.2.2.

import unat;

def witness_(P : UNat -> U0, e : exists n : UNat. P(n)) : UNat := e.1;

def evidence(P : UNat -> U0, e : exists n : UNat. P(n)) : P(e.1) := e.2;

def swap_pair(A, B : U0, p : A and B) : B and A := (p.2, p.1);

def last_of_three(t : UNat and Unit and UNat) : UNat := t.2.2;

Projections compute. A projection of a pair is its component, and every pair is the pair of its projections, so p = (p.1, p.2) holds by refl:

import unat;
use unat;

def pair_of_projections(A, B : U0, p : A and B) : p = (p.1, p.2) := refl(p);

evaluate typed(UNat and UNat, (2, 5)).2 expecting 5;

Only a pair has projections, and it has two. A projection of anything else is reported at the projection:

import unat;

def not_a_pair(n : UNat) : UNat := n.1;  // Error: Projection .1 requires a dependent pair; found a value of type UNat.
def third(t : UNat and UNat and UNat) : UNat := t.3;  // Error: A pair has only the projections .1 and .2.

In a proof block, obtain names the components instead. In a term, unpack pair as (a, b) return T { body; } does the same, where the result type T does not mention a or b:

import unat;

def first_number(pair : UNat and UNat) :=
  unpack pair as (a, b) return UNat { a; };

def swap(pair : UNat and Unit) :=
  unpack pair as (n, u) return Unit and UNat { typed(Unit and UNat, (u, n)); };
import unat;

// Error: unpack requires a dependent pair.
def not_a_pair(n : UNat) := unpack n as (a, b) return UNat { a; };

When the result type depends on the pair itself, use pair_induction(motive, branch, pair). For pair : exists x : A. B(x), the branch takes x : A and y : B(x) and proves motive((x, y)). The result proves motive(pair).

def pair_is_itself(A : U0, B : A -> U0, p : exists x : A. B(x)) : p = p {
  exact pair_induction(fun (q : exists x : A. B(x)) => q = q,
    fun (x : A, y : B(x)) => refl(typed(exists x : A. B(x), (x, y))), p);
}

Sums

left(a) and right(b) build elements of A or B. Like pairs, they need an expected type, because the other side is not determined:

import unat;
use unat;

def unit_on_the_left := typed(Unit or UNat, left(tt));

def three_on_the_right : Unit or UNat {
  exact right(3);
}
def unannotated := left(tt);  // Error: Sum injection requires an expected type.

Case analysis: match

match works on sums and on declared inductive types, such as UNat and your own types. This section shows the sum cases.

match value return T { left x => …; right y => …; } computes a result of type T from each side. Each branch is an expression and ends with ;.

import unat;
use unat;

def to_number(value : Unit or UNat) := match value return UNat {
  left u => 0;
  right n => n;
};

def swap_sides(A, B : U0, value : A or B) := match value return B or A {
  left a => right(a);
  right b => left(b);
};

When the result type depends on the value, name it with as: match value as z return C(z) { … }. The left branch must produce C(left(x)) and the right branch C(right(y)).

import unat;
use unat;

def Shape(value : Unit or Unit) := match value return U0 {
  left a => UNat;
  right b => Unit;
};

def default(value : Unit or Unit) := match value as z return Shape(z) {
  left a => 0;
  right b => tt;
};

Shape needs no as: its result type, U0, is the same for both sides. An as name that the result type does not mention is accepted, with a warning:

import unat;
use unat;

def to_number(value : Unit or UNat) := match value as z return UNat {  // Warning: z is unused: the return type does not mention it.
  left u => 0;
  right n => n;
};
import unat;

def not_a_sum(n : UNat) := match n return UNat {  // Error: UNat has no constructor left: its constructors are zero, succ.
  left a => 0;
  right b => 1;
};

The result type is the expected type of each branch, so right(a) needs no annotation. In a proof block, the match statement takes a sum apart with a block for each side, each proving the goal at its side.

Unit, Void and negation

tt is the element of Unit. Void has no elements: absurd(impossible) turns impossible : Void into an element of any expected type. Negation is A -> Void; there is no not keyword.

Every language keyword, built-in form and generated interface name is reserved: declarations, parameters, binders, pattern variables, fields, constructors, labels and modules cannot use it as a name. This includes words whose syntax appears only in one place, such as def, law, set, prop, compose and print, and the deriving vocabulary deriving, morphisms, free and initial. Some derivations are planned; their names are reserved now.

Generated members remain callable: T.Hom.make(map := f, …), T.Hom.compose(g, f) and a generated T.squash(…) @ i refer to the interface the language supplies. Naming an existing generated field in a call introduces no binding. Use another name for your own declarations, such as model_ or inverse_.

Reserved names

FunExt, Glue, Hom, Interval, IsColimit, IsInitial, IsLimit, IsTerminal, Iso, PathP, Unit, UnivalenceBeta, Void, abelian, absurd, additive, and, apd, apd_path, as, at, axiom, based_induction, by, calc, cat, comp, compose, computable, cong, decidable_equality, def, deriving, empty, equality, evaluate, exact, exists, expecting, ext, extends, face, face_when, fill, flip, fold, fold_map, fold_unique, forall, free, from, from_to, fun, gen, glue, hlevel, hlevel_rule, id, import, in, ind_prop, induction, inductive, initial, inspect, intro, inverse, irrelevance, isomorphisms, join, law, left, let, lift, limits, literal, make, map, match, max, meet, model, morphisms, next, nonempty, notation, numeral, obligations, obtain, occurrence, on, only, open, or, pair_induction, path, path_from_transport, path_induction, path_to_transport, paths, preabelian, preadditive, print, priority, prop, rec, refl, return, rfl, right, rw, section, set, simp, simp_rule, simp_set, simpa, sort, squash, sym, theory, to, to_from, trans, transport, trunc, tt, type, typed, typeof, ua, unfolding, unglue, unit_induction, universal, unpack, use, using, with, without, witness.

def Unit : U0 := UNat;  // Error: Unit is reserved, as a keyword or a built-in type of the language; pick another name.
def anything_from_void(A : U0, impossible : Void) : A {
  exact absurd(impossible);
}

def double_negation_intro(A : U0, a : A) : (A -> Void) -> Void {
  intro not_a;
  exact not_a(a);
}

def unit_is_tt(u : Unit) : u = tt {
  exact unit_induction(fun (v : Unit) => v = tt, refl(tt), u);
}

unit_induction(motive, base, value) proves motive(value) from base : motive(tt). absurd needs to know the type to produce:

// Error: absurd requires an expected type.
def unannotated(impossible : Void) := absurd(impossible);

Numbers and arithmetic

UNat is built from 0 and succ. A numeral is notation for repeated succ: 3 is succ(succ(succ(0))), not a machine integer. The unary numeral reader goes up to 256; the default binary nat reader accepts larger decimal magnitudes directly. A numeral means what the selected notation reads it as: import unat; loads the arithmetic library, and use unat; selects its notation for the rest of the file.

import unat;
use unat;

def three := succ(succ(succ(0)));

def three_is_three : three = 3 {
  exact refl(3);
}
import unat;

def too_big := unat.(257);  // Error: Unary numerals are limited to 256. Import nat and use nat for binary naturals.

The operators +, *, < and <= are unat's notation for add, mul, isLt and le, which the arithmetic library defines; x > y and x >= y are y < x and y <= x. use unat; selects them for the rest of a file, and unat.(2 * 3) for one expression. An operator means only what the selected notation binds: it is not overloaded by the types of its operands, and a function named add in scope gives + no meaning. A use of a model binds them to its operations instead.

import unat;
use unat;

def two_times_three : 2 * 3 = 6 {
  exact refl(6);
}

def two_below_three : 2 < 3 {
  exact tt;
}

Closed arithmetic computes, so refl(6) proves 2 * 3 = 6. The order is defined by computation too: 2 < 3 computes to Unit, proved by tt, and 3 < 2 computes to Void. Where no notation is selected, neither the operators nor the numerals mean anything:

import unat;

def four := 2 + 2;  // Error: x + y means what a selected notation binds + to: for natural numbers, use nat; or write nat.(x + y).

Addition recurses on its first argument. 0 + n computes to n, but n + 0 is stuck on the variable n, so it needs a proof by induction. The library proves it as unat_add_zero(n).

import unat;
use unat;

def zero_plus(n : UNat) : 0 + n = n {
  exact refl(n);
}

def plus_zero(n : UNat) : n + 0 = n {
  exact unat_add_zero(n);
}
import unat;
use unat;

def plus_zero_by_computation(n : UNat) : n + 0 = n {
  exact refl(n);  // Error: Type mismatch: found n = n, expected n + 0 = n.
}

unat proves the laws of its arithmetic, each by induction or from the others:

LawsStatements
Additionunat_zero_add, unat_add_zero, unat_add_succ, unat_add_assoc, unat_add_comm, and the regroupings unat_add_left_comm, a + (b + c) = b + (a + c), and unat_add_interchange, (a + b) + (c + d) = (a + c) + (b + d)
Multiplicationunat_mul_zero, unat_mul_succ, unat_one_mul, unat_mul_one, unat_mul_comm, unat_mul_assoc, and distributivity, unat_add_mul, (x + y) * z = x * z + y * z, and unat_mul_add, x * (y + z) = x * y + x * z
Cancellationunat_add_cancel, from k + x = k + y to x = y, and unat_mul_cancel, from x * succ(k) = y * succ(k) to x = y
Successorspred, unat_succ_injective, and unat_zero_ne_succ: 0 = succ(n) is impossible
Orderunat_le_refl, and unat_trichotomy(a, b): a exceeds b by a successor, they are equal, or b exceeds a, each with its evidence
import unat;
use unat;

def distributes(a, b : UNat) : 2 * (a + b) = 2 * a + 2 * b {
  exact unat_mul_add(2, a, b);
}

// 2 when a exceeds b, 1 when they are equal, 0 when b exceeds a.
def compare(a, b : UNat) : UNat := match unat_trichotomy(a, b) return UNat {
  left above => 2;
  right rest => match rest return UNat {
    left same => 1;
    right below => 0;
  };
};

evaluate compare(4, 3) expecting 2;
evaluate compare(3, 3) expecting 1;

The library builds the integers and the rationals from the naturals, as quotients, and the algebraic structures they carry. Induction on UNat and binary numerals are described in natural numbers and inductive types.

Expected types and typed

Several forms need an expected type: pairs, left and right, absurd, and untyped fun x =>. The expected type comes from:

  • the stated result type of a block declaration, through exact;
  • the type in let name : T;
  • the parameter type, when the term is an argument of a function;
  • the result type of a match branch;
  • typed(T, term), which checks term against T.
import unat;
use unat;

def number := typed(UNat, 3);

def successor := typed(UNat -> UNat, fun n => succ(n));

def unit_on_the_right := typed(UNat or Unit, right(tt));
import unat;

def not_a_number := typed(UNat, tt);  // Error: Type mismatch: found Unit, expected UNat.

Precedence

From tightest to loosest:

  1. application f(a) and projection p.1, from left to right, so f(a).2(b) applies the second component of f(a) to b;
  2. reversal ~p, so ~p @ i is (~p) @ i;
  3. the meet of coordinates i & j;
  4. their join i | j;
  5. interval application p @ i, for cubical paths;
  6. ^, grouping to the right;
  7. negation -x, so -x ^ 2 is -(x ^ 2) and -x * y is (-x) * y;
  8. * and /;
  9. + and -;
  10. path composition p ++ q;
  11. =, <, <=, >, >=;
  12. and;
  13. or;
  14. ->.

->, and, or and ^ group to the right. The other operators group to the left, so 2 * 3 ^ 2 is 2 * (3 ^ 2) and a - b - c is (a - b) - c. A qualified operator, x G.(^) y, has its operator's place in this list. The body of fun, forall and exists extends as far as possible. So A -> B -> C means A -> (B -> C), and forall x : A. P(x) -> Q(x) means forall x : A. (P(x) -> Q(x)).

def arrows_group_right(A, B, C : U0, f : A -> B -> C) : A -> (B -> C) {
  exact f;
}

def and_before_or(A, B, C : U0, x : A and B or C) : (A and B) or C {
  exact x;
}

Comparisons do not chain. 1 < 2 < 3 means (1 < 2) < 3, which compares a type with a number. Write (1 < 2) and (2 < 3).

import unat;
use unat;

def chained : 1 < 2 < 3 {
  exact tt;  // Error: Type mismatch: found U0, expected UNat.
}