Skip to main content

Types and schemes

Types​

The checker's types are the Ty enum in ty.rs. Unlike the TypeRefs of hir-def, which are types as written, a Ty points at definitions: a struct is its StructId, not its name.

τ::=αinference variable (Var)∣T[τ1,…,τn]struct or enum, maybe partially applied (Adt)∣F[τ1,…,τn]parameter or variable applied to types (App)∣i32∣bool∣str∣…primitive (Builtin)∣(τ1,…,τn)tuple; () is unit∣[τ]array∣fn(τ1,…,τn)→τfunction∣Pdeclared type parameter (Param)∣aibound variable of a scheme (Bound)∣!never∣⊥error\begin{array}{rcll} \tau & ::= & \alpha & \text{inference variable (\texttt{Var})} \\ & \mid & T[\tau_1, \dots, \tau_n] & \text{struct or enum, maybe partially applied (\texttt{Adt})} \\ & \mid & F[\tau_1, \dots, \tau_n] & \text{parameter or variable applied to types (\texttt{App})} \\ & \mid & \mathsf{i32} \mid \mathsf{bool} \mid \mathsf{str} \mid \dots & \text{primitive (\texttt{Builtin})} \\ & \mid & (\tau_1, \dots, \tau_n) & \text{tuple; } () \text{ is unit} \\ & \mid & [\tau] & \text{array} \\ & \mid & \mathsf{fn}(\tau_1, \dots, \tau_n) \to \tau & \text{function} \\ & \mid & P & \text{declared type parameter (\texttt{Param})} \\ & \mid & a_i & \text{bound variable of a scheme (\texttt{Bound})} \\ & \mid & ! & \text{never} \\ & \mid & \bot & \text{error} \end{array}

A few of these need explaining.

Inference variables are TyVar(u32), indices into the unifier's table (see Unification). Each also has a VarKind:

  • General variables can become any type.
  • Int and Float variables come from number literals without a suffix, like 1 or 2.5. They can only become integer or float types, and they default to i32 and f64 when nothing else decides them.

VarKinds have nothing to do with the kinds of types.

This replaces Haskell's Num and Fractional classes and their defaulting rules with something much simpler. There's no class for numbers, so arithmetic operators only require both sides to have the same type.

Type parameters and bound variables are both "type variables" in the literature, but the checker keeps them apart:

  • Param is a parameter someone declared, like the T of fn id[T](x: T) -> T. Inside the item that declares it, it's rigid: it stands for an unknown type and only equals itself. In the literature this is a skolem constant. When the item is used, its parameters are replaced by fresh inference variables.
  • Bound(i) is a variable that generalization introduced in the scheme of a function without a complete signature. These are the a, b, ... in forall a. fn(a) -> a.

Never, written !, is the type of return, break, continue, a loop that's never left, and a match without arms. It fits wherever any type is expected. Bolt has no subtyping, so the checker handles this in unification: ! unifies with every type without binding anything. See Unification.

The error type ⊥\bot is what a type becomes once an error has been reported about it, like an unresolved name. It also unifies with everything, so that one error doesn't cause more. See Errors.

There's also Number, which only appears in diagnostics. It shows a literal that got its type from defaulting as {integer} or {float}.

Lowering written types​

lower.rs turns TypeRefs into Tys with a TyLoweringContext, which resolves paths with hir-def's Resolver. Signatures are lowered by their own queries, so they're computed once and shared:

QueryResult
fn_sigThe parameter and return types of a function. Each is None where no type is written.
struct_field_types, enum_field_typesField types in terms of the type's own parameters.
generic_predicatesThe class constraints of [T: Show] bounds and where clauses. For a class, these are its superclasses.
impl_headerThe instance an impl provides, like Show[Option[T]].
type_alias_tyThe type an alias stands for. A cycle is caught with Salsa's cycle recovery and reported as a recursive alias.
const_tyThe declared type of a const.

Type aliases are expanded during lowering by substituting their arguments, so later stages never see them. Lowering also checks the kind of every type, which includes that type constructors get the right number of arguments.

Type schemes​

A function has a type scheme (Scheme in scheme.rs). It's a type with quantified variables and the constraints that must hold wherever the function is used:

σ::=∀Pˉ aˉ. Q1⇒⋯⇒Qn⇒τQ::=C[τ1,…,τk]∣τ.ℓ:τ′\sigma ::= \forall \bar{P}\, \bar{a}.\ Q_1 \Rightarrow \dots \Rightarrow Q_n \Rightarrow \tau \qquad Q ::= C[\tau_1, \dots, \tau_k] \mid \tau.\ell : \tau'

A constraint QQ is one of:

  • A class constraint C[τˉ]C[\bar\tau] (a ClassConstraint): the types have an instance of class CC, like Show[a]\mathsf{Show}[a]. These are the predicates of Jones's qualified types [Jones 1994].

  • A field constraint τ.ℓ:τ′\tau.\ell : \tau' (a FieldConstraint): values of type τ\tau have a field ℓ\ell of type τ′\tau'. A function that uses a field of a value whose type it doesn't decide keeps the constraint:

    fn norm(p) = p.x * p.x;
    norm: forall a b. a.x: b => fn(a) -> b

    norm then works on any struct with a field x. This is close to the kinded record types of Ohori's polymorphic record calculus [Ohori 1995]. In GHC's terms, it's a HasField "x" a b constraint.

Scheme stores the declared parameters Pˉ\bar P and the number of bound variables aˉ\bar a separately. Its display prints both after one forall.

Instantiation​

Using a function instantiates its scheme (Scheme::instantiate). Every parameter and bound variable is replaced by a fresh inference variable, and the constraints are added to the solver with those variables:

x:∀vˉ. Qˉ⇒τβˉ freshtype τ[vˉ↦βˉ], constraints Qˉ[vˉ↦βˉ]\frac{x : \forall \bar{v}.\ \bar{Q} \Rightarrow \tau \qquad \bar\beta \text{ fresh}} {\text{type } \tau[\bar v \mapsto \bar\beta], \text{ constraints } \bar Q[\bar v \mapsto \bar\beta]}

This is the only way polymorphism enters a body. Each use of id gets its own copy of its type, so id(1) and id(True) don't interfere.

Tuples with names and packs​

A tuple has positional fields, like (i32, Bool), or named ones, like (x: i32, y: Bool), not both. The first is a Ty::Tuple, the second a Ty::Record, with the named fields in the order of their names, so that (x: 1, y: 2) and (y: 2, x: 1) have one type. () has no fields of either kind, so it's both: the unit type. In an expression, *e spreads the fields of a tuple with positional ones, and **e those of a tuple with named ones.

A function can take any number of fields with a pack parameter: [*Ts] stands for positional fields and [**R] for named ones, of the kinds *Pack and **Pack. In a tuple type, a pack is a Ty::Spread, like the *Ts of (T, *Ts) or the **R of (name: String, **R). At a use, a pack parameter becomes a pack variable, which becomes a Ty::Tuple of the types it stands for, or a Ty::Record of the named fields: a tuple whose spread is solved has them spliced in when it's rebuilt.

Unifying two tuples with spreads (Unifier::unify_tuples):

  • Positional fields are matched from the start and from the end, until a spread. What's left on one side is what a single pack variable on the other stands for: (T, *Ts) with (i32, Bool, u8) makes Ts the (Bool, u8). Two spreads in the same places, like (*As, *Bs) on both sides, are matched pairwise. Anything else, like (*As, *Bs) with (i32, Bool), could be split in more than one way, and is a mismatch, so a pack must be alone where it's solved.
  • Named fields are matched by name. A named pack variable on one side takes the fields only the other side has. When both sides have one, each gets the other side's fields and a new variable for the rest, as in row rewriting (Rémy, Leijen).

A tuple with named fields and a named pack, like (id: i32, **R), needs R not to give an id: instantiating a scheme adds a Lacks constraint for that, which is checked once R is known.

What a body can do with a value whose type has a pack: pass it on, read a positional field before the first spread or a named field, and match it with ... Monomorphization knows each pack, so MIR reads a field after a spread from the end (Ctor::TupleEnd) and a named one by its name (Ctor::TupleNamed), which the code generator turns into indices. Spreading such a value, like (**p, y: 1) in a generic body, type-checks but isn't lowered yet (#405).

Parameters of functions​

A function's parameters are positional, keyword-only, or rests:

fn push(xs: [T], /, x: T) // `xs` only by position
fn split(s: String, *, at: Char) // `at` only by name
fn print[*Ts](*args: *Ts, sep: String) // the other positional arguments
fn call[*Ts, **Ks](f: F, *args: *Ts, **opts: **Ks)

Before a /, parameters can only be passed by position, after a * or *args only by name, and **opts comes last, so a positional pack is never followed by positional parameters. In the body, args is the tuple (*Ts) and opts the tuple (**Ks).

Ty::Fn holds a Params: the positional parameters, a positional pack, the keyword-only ones in the order of their names, and a named pack, shown as fn(String, *, at: Char) or fn(*Ts, sep: String, **Ks). A pack that's solved is spliced in, so a function type has one form. Two functions with only positional parameters unify parameter by parameter. Otherwise the parameters unify as tuples (Params::as_tuple), so positions, names and packs work as they do for tuples.

A call f(1, *xs, sep: ",", **opts) is checked the same way: its arguments make a tuple, through the spread constraint when there are spreads, which must be the parameters as a tuple. A name given twice is E0259. Neither tuple is a value, so neither has a mutability (Ty::Unwritten), and what's spread in the arguments isn't required to be at most anything.

Monomorphization lays the parameters out flat (MonoTy::Fn): the positional ones, then those of the positional pack, then the keyword ones together with those of the named pack, in the order of their names, whose names it keeps. MIR passes a call's arguments in that order, after evaluating them into temporaries in the order they're written. A function with keyword parameters or rests binds its parameters from the flat ones (bind_params in the code generator), building args and opts.

Names of positional parameters​

A positional parameter can be passed by name too: f(y: 2, x: 1) for fn f(x: i32, y: i32). The names are in the function's type, as fn(x: i32, y: i32), and a function type can be written with them. Each positional parameter in Params has a name slot in Params::names: a Ty::ParamName, which is None for one without a name, like a pattern that isn't a name, or a variable of kind VarKind::Name while it's inferred. At runtime nothing changes: a name only decides a position, which the checker and MIR find the same way (place_args), and monomorphization drops the names.

Only a call by name checks a name (the reasons are in Arguments and parameter names). A name in a function type says how whoever holds a value of that type can call it by name, so names never make unification fail, and instance matching ignores them. A written function type renames the parameters of what it's given: apply(f) for fn apply(k: fn(item: i32) -> i32) checks whatever f calls its parameter, and inside apply, k(item: 1) uses apply's names.

A slot stands for the set of names its parameter can be called by: one name, none, or any, for a variable that nothing decided yet. When a type variable is bound to a function type (Unifier::bind_freshened), its slots become new variables. On the side that's expected, the given function's slots flow into them (NameEdge), and when the unifier meets two function types, the actual one's slots flow into the expected one's too, the other way around inside parameters. A written slot doesn't receive anything, which is the renaming. A variable's set is the intersection of what flowed into it (Unifier::name_set), so the type of if c { f } else { g } has the names that f and g share: with f(x, y) and g(x, z), it's fn(x: i32, i32). A variable on the other side, like k in apply(k) for a k without an annotation, gets open slots.

A call with a named argument looks at what the callee's slots are now (Unifier::slots_now). A name that no slot has takes the first open one after the positional arguments, in the order the call writes them, and the call claims the slot (Unifier::claim), along with the open slots that flowed into it, so that what's given there can be called by that name. So fn pick(c, f, g) = { let k = if c { f } else { g }; k(x: 1) } names the parameters of both f and g x. A call by name of a function that isn't known yet makes its arguments positional parameters, with open slots that the call claims: fn r(k) = k(item: 2) has type fn(k: fn(item: i32) -> a) -> a. A slot that's claimed has one name, so k(x: 1); k(y: 1) is an error. A function that flows into a claimed slot after the call must have its name, or unifying it fails.

Names normally flow from what's read into what reads it: a pattern takes the names of what it matches (Solver::equal_into). A place shares its slots with what it denotes (Solver::equal_shared): a field access with the field, and an associated type, like the Index.Item of xs[i], with what the impl gives. What's in a mut array, struct or tuple shares its slots on both sides when the two are unified (Unifier::share_if_mut), since either side can write to it: after put(ks, |y: i32| y) for fn put[T](xs: mut [T], x: T), the elements of ks can't be called x anymore.

Before generalizing, the solver settles the names (Solver::settle_names): a claimed slot has its claim, one whose set is a single name has that name, and every other slot has none.

Since a written type renames, copy(|dst, src| ...) for fn copy(f: fn(src: Path, dst: Path)) checks, and passes src to the lambda's dst. So the unifier records each function type that it finds given for another (Unifier::given_fns), in the case of two function types and when a variable takes a function's shape, and the solver keeps where (Solver::unify_at). Once the names are settled, it warns where a name of the given function is the name of another position in the type it was given for (TypeError::SwappedNames, W0005).

A parameter before a / has no name (ParamData::name is None), so its type is the same as if the name were left out: fn f(x: i32, /, y: i32) has type fn(i32, y: i32). A function type has no / for that reason, since leaving the names out says the same.

A lambda's parameters have the names of its patterns, whatever it's checked against. A method of a class impl can name its parameters otherwise than the class: calls through the class use the class's names.

Default values​

A parameter can have a default, like fn f(a: i32, b: i32 = a * 2, *, c: i32 = 0). The defaults are part of the function's body (Body::defaults), each in a scope that has the parameters before it, and they're checked with the body, against their parameters' types, so fn g(x = 1) takes an i32. A default is evaluated where the function is called, so what it does, the function does: its effects are the function's. A positional parameter without a default after one with a default is E0260, and a default on a method of a class impl is E0261, since calls through the class use the class's defaults, as they use its names.

Function types have no defaults (#408), so only a call that the checker knows the function of can leave parameters out: a call by its name, a method call, or one of a class method. ParamDefaults says which parameters have one, and place_args passes over the positional ones that no argument is for. The arguments are then checked against the parameters that are left, and InferenceResult::defaults has, for the call, the function and the declared parameters that get their defaults.

In MIR, each default is a body of its own (BodyOwner::Default), a function of the parameters before it, after the lambdas in MirBodies. A call evaluates its arguments into temporaries in the order they're written, then calls the default of each parameter it leaves out, in the order of the parameters, with the values of those before it, through an ItemRef::Default. Its of is the type the call uses the function at, which decides the instance of the default: InstanceDef::Default is generic over what its function is, with the default's own type. A class method's defaults work the same way, since its declaration has a scheme. A default with a lambda or a handler in it isn't lowered yet.

What's left: lambdas with keyword parameters, and passing a pack on, like f(*args) in a generic body.

References​

  • M. P. Jones. Qualified Types: Theory and Practice. Cambridge University Press, 1994.
  • A. Ohori. A Polymorphic Record Calculus and Its Compilation. TOPLAS 17(6), 1995.