Home / Docs / Specification
20. Constraints on generics
Status: Normative, v0.2 (ADR 0066).
A type parameter of a function may carry one of three built-in constraints: Eq, Ord or Integer. A constraint allows operators on values of the parameter, which keep their built-in meaning, and restricts the types that can instantiate it. There are no user traits and no implementations: a type satisfies a constraint by what it is.
Editions. The constructs of this chapter exist only in packages of edition 0.2 and later (spec/13 §7).
- In edition
0.1, type parameters stay unconstrained, equality on them keeps the inferred bound of spec/10 §12 rule 9, and the prelude keeps its v0.1 signatures (spec/14 §1). - A single file has the default settings, and so edition
0.1. - The benchmark baseline stays on edition
0.1.
1. The constraints
| Constraint | Allows on values of T |
Satisfied by |
|---|---|---|
Eq |
==, !=, and interpolation (ADR 0068) |
every type whose values hold no functions |
Ord |
what Eq allows, and <, <=, >, >= |
Int, I8 to U64, Text, and sum kinds whose variants have no payload |
Integer |
what Ord allows, and x.to_int() |
Int, I8 to U64 |
- Order.
OrdincludesEq, andIntegerincludesOrd: a type that satisfies a constraint satisfies the ones it includes. The order is fixed. A program declares no constraint of its own. - Type parameters. A type parameter written with a constraint satisfies that constraint and the ones it includes. An unconstrained type parameter satisfies none.
- Kinds. A record or a sum satisfies
Eqwhen its values hold no functions, whatever its type arguments are. It satisfiesOrdonly when it is a sum whose variants have no payload. Lists, options and results satisfyEqwhen their element types do, and neverOrd. (v0.2, ADR 0069.) AMap[K, V]satisfiesEqwhenVdoes, and neverOrd(spec/21 §1). (v0.5, ADR 0119 rule 2.)Stack[T],Queue[T]andSet[T]satisfyEqwhenTdoes, andBitSetdoes;HashMap,HashSetandPriorityQueuenever satisfyEq, nor does a type that holds one at any position; none of them satisfiesOrd(spec/28 §3). - Labels do not take part in satisfaction:
secret IntsatisfiesInteger. - Operators keep their meaning.
==is structural equality and<the built-in order of spec/03 §1, on every type that satisfies the constraint. Nothing redefines them (charter §6). - No arithmetic on
T.+,-,*,/and%stay undefined on a type parameter, constrained or not, so theoverflowobligations of spec/18 §5 stay on concrete types.x.to_int()on aT: Integergives anInt, on which arithmetic is defined.
2. Syntax
These productions change spec/02 §2 and §3:
signature = lower_ident [ constrained_params ] "(" [ params ] ")" "->" type ;
constrained_params = "[" constrained_param { "," constrained_param } "]" ;
constrained_param = upper_ident [ ":" upper_ident ] ;pub sort[T: Ord](xs: List[T]) -> List[T]
pub largest[T: Ord](xs: List[T], floor: T) -> T = xs.fold(initial: floor, step: fn(best, x) -> max(best, b: x))
pub total[T: Integer](xs: List[T]) -> Int = xs.map(each: fn(x) -> x.to_int()).sum()- A constraint is written on the type parameters of functions only. The type parameters of kinds keep
type_paramsof spec/02 §2, andKind[T: Eq]is a syntax error (U0101). - Each type parameter takes at most one constraint.
Eq,OrdandIntegerare names of the prelude in the upper namespace. A constraint name that is none of them is U2027. A user kind, variant or capability namedEq,OrdorIntegeris U1002, as forI8(spec/18 §1).traitandimplstay reserved, with the message of §9.
3. Static semantics
- Operators on
T. An operator of §1 on values of a type parameter is allowed when the parameter's constraint allows it, directly or through the constraints it includes. Otherwise it is U2026 at the operator, with a repair that writes the constraint that allows it on the parameter. This holds for==and!=too: equality on an unconstrained type parameter is U2026. to_int(). On a value of a type parameterT: Integer,x.to_int()is a built-in method with typeInt. On any other type parameter it is U2026.- Instantiation. At a call, and wherever a function is used as a value, each type argument MUST satisfy the constraint of its parameter (U2025 at the call, naming the type and the constraint). Refined and second-class types stay excluded as type arguments (U2002, U3016). A type argument that is a type parameter of the caller satisfies the constraints of its own declaration (§1 rule 2).
- Inference for private functions. A private function whose type parameter has no written constraint gets the least constraint that its body needs: the one that allows every operator of §1 its body applies to values of the parameter, joined with those of the callees its type parameter instantiates. Public functions write their constraints (U2026 at the first operator, or U2025 at the call that needs more). This follows ADR 0007 for
usesand ADR 0062 foruses of. - Equality and functions. The bound of spec/10 §12 rule 9 is, in edition
0.2, the constraintEq: a type whose values hold functions does not satisfyEq(§1), so instantiating a parameterT: Eqwith it is U2025.
4. Information flow
- Operators. A comparison, an equality or
to_int()on values ofTis labeled with the join of every label of its operands, the symbolic labelℓ_Tincluded (spec/07 §7 rules 3 and 8). Branching on it raises the program counter, symbolically when the label containsℓ_T. - The prelude. The functions of §6 read values, so their results are labeled with the join of every label of their arguments, element types included (ADR 0051). For
sort, every position of the result, and the result list, carries the join of the labels of the list and of all its elements, since where an element ends up depends on the others.
5. Verification
- Generic bodies. In the body of a generic function,
<,<=,>and>=on aT: Ordare uninterpreted relations over the sort ofT,u!Param_<name>(spec/12 §4), with no axioms.x.to_int()on aT: Integeris an uninterpreted function from that sort toInt. Equality stays SMT equality. - Calls. A callee's contract is instantiated with the type arguments, as today (spec/12 §3). When the type argument is
Intor a fixed-width type, its comparisons are those of the integers, andto_int()is the identity, with the bounds of the type. ForTextthey are the uninterpreted order ofText, and for a sum without payloads the order of its tags. - No laws. No axiom states that an order is total, reflexive or transitive. Laws of constraints wait for laws with quantifiers (
plan/backlog.md, v0.3).
6. The prelude of edition 0.2
These signatures replace those of spec/14 §1 in edition 0.2:
| Signature | Contract |
|---|---|
min[T: Ord](a: T, b: T) -> T |
ensures result <= a and result <= b and (result == a or result == b) |
max[T: Ord](a: T, b: T) -> T |
ensures result >= a and result >= b and (result == a or result == b) |
contains[T: Eq](xs: List[T], item: T) -> Bool |
none |
sum[T: Integer](xs: List[T]) -> Int |
none |
sort[T: Ord](xs: List[T]) -> List[T] |
ensures result.len == xs.len |
sumadds the values of the elements asInt, so it never overflows.sortreturns the elements in ascending order, and keeps the order of the list for equal elements (stable).absstaysabs(x: Int) -> Int, sinceabsof a fixed-width value can overflow.- Calls with
Intarguments keep their meaning and contracts.
7. Dynamic semantics
- The interpreter evaluates
==,<andto_int()on values ofTby the form of the value, as on concrete types (spec/11). - The native backend (spec/16 §4) compiles each function once. A function with constrained type parameters takes, for each of them, a hidden type descriptor after its parameters: a word that says how to compare and convert values of the type that instantiates it (a tagged
Int, a fixed-width type with its width and signedness,Text, a sum without payloads compared by tag, or structural equality). A call with a known type passes a constant descriptor. A call that instantiates a parameter with a type parameter of the caller passes the caller's descriptor on. Unconstrained parameters take no descriptor.
8. The report and the contract
- The header of
una contractshows the constraints as written, and inferred ones as written by the canonical form, with the comment-- inferred(spec/13 §5). una.contract/1gains the keyconstraints, afterheader: one entry per constrained type parameter,{"param": "T", "constraint": "Ord", "inferred": false}, in parameter order, and[]when there are none.
9. Reserved words
In edition 0.2, the table of spec/01 §5, as changed by spec/17 §9 and spec/19 §9, changes as follows:
| Keywords | Message |
|---|---|
trait, impl |
reserved for a later version (user traits) |
10. Diagnostic codes
These codes join the registry of spec/13 §4 with their implementation: