Skip to main content

Class and field constraints

The Solver in solve.rs takes the three kinds of Constraint:

ConstraintMeaningWhen it's solved
Equalτ1≐τ2\tau_1 \doteq \tau_2Right away, by the unifier.
ClassC[τ1,…,τn]C[\tau_1, \dots, \tau_n]When an impl or assumption can be chosen.
Fieldτ.ℓ:τ′\tau.\ell : \tau'When τ\tau is known.

Solving equalities eagerly and deferring the rest makes the checker an instance of HM(X) [Odersky et al. 1999]: Hindley–Milner parameterized by a constraint domain XX, here classes and fields. Deferred constraints that can't be solved in a function's body become part of its type when it's generalized. This is the treatment of predicates in Jones's qualified types [Jones 1994] and in "Typing Haskell in Haskell" [Jones 1999].

Classes​

Bolt classes are type classes [Wadler & Blott 1989], with any number of parameters [Peyton Jones et al. 1997]:

class Show[T] { fn show(x: T) -> String; }
class Convert[A, B] { fn convert(a: A) -> B; }
class Ord[T] where Eq[T] { fn lt(a: T, b: T) -> Bool; }

impl Show[i32] { fn show(x) = "int"; }
impl[T] Show[Option[T]] where Show[T] { fn show(x) = "option"; }

A method of a class has the class's parameters and the class itself as a constraint: show has the scheme ∀T. Show[T]⇒fn(T)→str\forall T.\ \mathsf{Show}[T] \Rightarrow \mathsf{fn}(T) \to \mathsf{str}. Using a method, or a const of a class, adds that constraint.

Assumptions​

Inside a function, some constraints are known to hold. The assumptions query gives them:

  • the bounds and where clauses of the function, and of the impl it's in;
  • for a method in a class, the class itself, like Show[T]\mathsf{Show}[T] inside the default methods of Show.

Solver::assume adds an assumption and its superclasses, transitively: in fn le[T](a: T, b: T) -> Bool where Ord[T], the assumption Ord[T]\mathsf{Ord}[T] gives Eq[T]\mathsf{Eq}[T] as well, because class Ord[T] where Eq[T]. This is the superclass closure of Haskell's entailment relation [Hall et al. 1996].

Instance resolution​

Solver::solve runs until it makes no more progress. It tries every pending class constraint with try_solve, which works like one step of backward chaining in Prolog: find a rule (an impl) whose head matches the goal, and replace the goal by the rule's premises (its where clauses).

  1. If an argument contains the error type, the constraint is solved. An error was already reported about it.

  2. If the constraint is one of the assumptions, it's solved.

  3. Otherwise, each impl visible from the file is matched against the constraint. Matching is one-way: the impl's parameters can stand for any type, but the constraint's inference variables are never bound. Each match has one of three outcomes:

    • Yes: the impl's head matches, with a substitution for its parameters.
    • No: it can't match, whatever the variables become.
    • Maybe: it depends on variables that aren't known yet. For example, impl Show[i32] against Show[β]\mathsf{Show}[\beta].

    Applications are matched like they're unified: impl[E] Functor[Either[E]] matches Functor[Either[str]]\mathsf{Functor}[\mathsf{Either}[\mathsf{str}]] with E:=strE := \mathsf{str} (see Kinds).

    An assumption of the same class also counts as a Maybe when the constraint has variables, since the variables might turn out to be the assumption's types.

  4. With exactly one Yes and no Maybe, that impl is chosen. Its own where clauses, with the substitution applied, become new constraints: choosing impl[T] Show[Option[T]] where Show[T] for Show[Option[i32]]\mathsf{Show}[\mathsf{Option}[\mathsf{i32}]] leaves Show[i32]\mathsf{Show}[\mathsf{i32}].

  5. If there are several Yeses, or a Yes and a Maybe, the solver waits. Something later may decide the variables and rule impls out.

  6. With no candidate at all, it waits if the constraint has variables, and reports "no instance" if it doesn't.

The solver never backtracks and never guesses. It only commits to an impl when no other impl or assumption could still apply. Every solution is then the only one, which keeps the meaning of a program independent of the order constraints are solved in. It's the rule GHC uses for overlapping instances: an instance is chosen only if it matches the constraint and no other instance unifies with it [GHC User's Guide].

visible_impls decides which impls a file can use: those of the file itself, of its prelude, and of every file they import, directly or not.

Two impls of a class overlap when some types fit both instances, like impl[T] Size[[T]] and impl Size[[i32]]. A constraint on those types would wait forever at step 5, so the later impl is an error where it's defined (E0235, overlap.rs): each impl is compared with those before it in its file and those of the files it uses. The two instances overlap if they unify once each impl's parameters, hidden mutabilities included, are fresh variables. As in GHC, where clauses aren't looked at, so that an impl added somewhere else can't make two impls overlap. Two impls in files that don't use each other aren't compared, even when a third file uses both; there, a use that both fit says that more than one impl fits.

What's left​

When a body is done, Solver::finish solves what it can, defaults the numeric variables, and solves again, since defaulting can decide constraints like Show[βInt]\mathsf{Show}[\beta_{\mathsf{Int}}]. A class constraint that's still pending after that is ambiguous: the types were never known well enough to choose an impl.

For an inferred function, generalization first turns the pending constraints that are about the function's own type variables into part of its scheme. Only the rest are ambiguous.

Fields​

A field access e.x emits τ.x:β\tau.x : \beta, where τ\tau is the type of e. solve_field looks at τ\tau:

  • A variable: wait.
  • A struct S[τˉ]S[\bar\tau]: look up the field x in struct_field_types, substitute the struct's arguments, and emit an equality with β\beta. If there's no such field, report "no field" and make β\beta the error type.
  • A tuple, for a field like 0: the element type, if the index is in range.
  • ! or the error type: the field is the error type too, without an error.

Field constraints are tried as soon as they're added, unlike class constraints, because the field's type often decides what follows. In p.x + 1, knowing the field is i32 makes the 1 an i32.

A field constraint whose type is never decided becomes part of the scheme of the function it's in:

struct Line { start: Point }
fn start_x(l) = l.start.x;
start_x: forall a b c. a.start: c => c.x: b => fn(a) -> b

When start_x is called with a Line, instantiation adds Line.start:γ\mathsf{Line}.\mathsf{start} : \gamma and γ.x:β\gamma.x : \beta. The first decides γ\gamma, and then the second can be solved.

These constraints work like the kinded types of Ohori's polymorphic record calculus [Ohori 1995], where a type variable's kind lists the fields its values must have. Row polymorphism [Rémy 1989, Gaster & Jones 1996] solves the same problem with row variables instead. Bolt's structs are nominal, so a field constraint is solved by looking up a declaration, much like GHC's HasField class.

A field constraint whose type is never decided in a body that isn't generalized, like the top level of a file, is reported as "type needed".

Associated types​

An associated type applied to types, like C.Item, is a Ty::Assoc. Before the solver sees a type, flatten_assoc replaces each one with a new variable β\beta and an Assoc constraint Item[τc]=β\mathsf{Item}[\tau_c] = \beta, which solve_assoc solves as soon as it can:

  • An assumption says what it is: β\beta is that type.
  • An impl of the class matches τc\tau_c: β\beta is the impl's type for it, with the impl's parameters substituted.
  • τc\tau_c is a type parameter with a bound or where clause of the class: β\beta is the projection itself, which only equals itself.
  • Otherwise it waits. One left when an inferred function is generalized stays in its type, like a.Item = Bool.

An impl that doesn't give an associated type gets the class's default, like the i32 of type Item = i32;, with the class's parameters and its other associated types replaced by the impl's (impl_assoc_ty): the default type Item = Iter.Item; is the Item of the impl's Iter. Inside the class, an associated type is always its projection, like C.Item, even with a default, since an impl can give another type.

A bound or where clause can say what an associated type is, like the Item = T of I: Iterator[Item = T]. Lowering keeps those as Predicates::equalities, next to the class constraints. Inside the function, they're assumptions (Solver::assume_assoc), so I.Item is T there. In its scheme, they're among Scheme::assoc, which a use instantiates as Assoc constraints, so that the impl chosen for the arguments must give T. An impl's where clause works the same way: when the impl is chosen, its equalities are added like its class predicates. They're only allowed on functions and impls, where they can be assumed, and in the bounds of associated types.

A bound of an associated type can say what another associated type is, like the Item = Item of type Iter: Iterator[Item = Item]; in class Iterable[C]: for every C, C.Iter.Item is C.Item. Wherever Iterable[X] is assumed, X.Iter.Item = X.Item is assumed too (implied_equalities), as Iterator[X.Iter] is from the bound itself. So a function with C: Iterable gets C.Item from next(iter(c)). Each impl of the class must meet it (unmet_assoc_equalities): its Iter's Item, found through the impls of Iterator, must be its Item (E0241).

Overloads​

Functions can share a name. Name resolution keeps all the functions with a name, from the file, its imports and the prelude, as one set, and a path that names several is a ValueNs::Overloaded. Its use gets a new variable α\alpha for its type, and an OverloadConstraint with the candidates, each with a probe: its type with new variables for its parameters and associated types (Scheme::probe), without its predicates.

Solver::narrow_overloads crosses out a candidate when its probe no longer unifies with α\alpha, which it tries on a copy of the unifier, so that nothing is decided. It never guesses and never backtracks:

  • One left: it's instantiated for real, adding its predicates, and unified with α\alpha (solve_overloads in infer.rs, since that needs the types of the functions being inferred). A call is checked against it argument by argument, so that a mismatch is at the argument.
  • None left: the candidate with as many parameters as the call has arguments that fits the most of them, then the most if mutabilities don't count, is checked as if it had been chosen, for precise errors. Without a single such one, the error lists the candidates (E0236).
  • More left when the body is done: the use is ambiguous (E0237). It doesn't become part of the function's type: generic code uses classes.

For a call, α\alpha is unified with fn(β₁, …, βₙ) -> β first, and candidates are crossed out before each argument is checked. When the arguments before a closure leave one candidate, the closure is checked against its parameter types. So the number of arguments and the first argument usually decide early, as with methods in other languages, without making the first argument special.

A choice is kept by expression in InferenceResult::overloads, which MIR building uses instead of resolving the name again.

Two functions with a name overlap when a call could fit both: they take as many arguments, and their parameter types unify once their parameters are new variables (functions_overlap in overlap.rs). That's an error at the later one (E0238), as for impls, so that adding a function can't change what an existing call chooses. A class method's parameter is a type parameter, so it overlaps every function with its name that takes as many arguments.

This is close to System O [Odersky et al. 1995], where an overloaded name's instances are given by their types, except that in Bolt a name's functions don't share a declared type, and a use that the types don't decide isn't generalized.

References​

  • M. Odersky, M. Sulzmann and M. Wehr. Type Inference with Constrained Types. Theory and Practice of Object Systems 5(1), 1999.
  • M. P. Jones. Qualified Types: Theory and Practice. Cambridge University Press, 1994.
  • M. P. Jones. Typing Haskell in Haskell. Haskell Workshop, 1999.
  • P. Wadler and S. Blott. How to make ad-hoc polymorphism less ad hoc. POPL 1989.
  • S. Peyton Jones, M. Jones and E. Meijer. Type classes: an exploration of the design space. Haskell Workshop, 1997.
  • The GHC Team. GHC User's Guide, section "Overlapping instances".
  • C. Hall, K. Hammond, S. Peyton Jones and P. Wadler. Type Classes in Haskell. TOPLAS 18(2), 1996.
  • A. Ohori. A Polymorphic Record Calculus and Its Compilation. TOPLAS 17(6), 1995.
  • D. Rémy. Type checking records and variants in a natural extension of ML. POPL 1989.
  • B. R. Gaster and M. P. Jones. A Polymorphic Type System for Extensible Records and Variants. Technical report NOTTCS-TR-96-3, University of Nottingham, 1996.
  • M. Odersky, P. Wadler and M. Wehr. A Second Look at Overloading. FPCA 1995.