Class and field constraints
The Solver in solve.rs takes the three kinds of Constraint:
| Constraint | Meaning | When it's solved |
|---|---|---|
Equal | Right away, by the unifier. | |
Class | When an impl or assumption can be chosen. | |
Field | When 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 , 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
.
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
whereclauses of the function, and of the impl it's in; - for a method in a class, the class itself, like 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
gives 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).
-
If an argument contains the error type, the constraint is solved. An error was already reported about it.
-
If the constraint is one of the assumptions, it's solved.
-
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 .
Applications are matched like they're unified:
impl[E] Functor[Either[E]]matches with (see Kinds).An assumption of the same class also counts as a
Maybewhen the constraint has variables, since the variables might turn out to be the assumption's types. -
With exactly one
Yesand noMaybe, that impl is chosen. Its ownwhereclauses, with the substitution applied, become new constraints: choosingimpl[T] Show[Option[T]] where Show[T]for leaves . -
If there are several
Yeses, or aYesand aMaybe, the solver waits. Something later may decide the variables and rule impls out. -
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 . 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 , where is the type of e.
solve_field looks at :
- A variable: wait.
- A struct : look up the field
xinstruct_field_types, substitute the struct's arguments, and emit an equality with . If there's no such field, report "no field" and make 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
and . The first
decides , 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 and an Assoc constraint ,
which solve_assoc solves as soon as it can:
- An assumption says what it is: is that type.
- An impl of the class matches : is the impl's type for it, with the impl's parameters substituted.
- is a type parameter with a bound or
whereclause of the class: 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 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 , 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 (
solve_overloadsininfer.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, 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.