Dictionary passing

Dictionary passing is the translation that implements type classes by ordinary function application^[1]^[2]. A class declaration becomes a record type with one field per method, called a dictionary. An instance declaration becomes a value of that type, or, if the instance has a context such as Eq a => Eq [a], a function from the dictionaries in the context to a new dictionary. A function whose type has a constraint, such as elem :: Eq a => a -> [a] -> Bool, gets an extra parameter for each constraint, and the type checker, which knows at each call site the types involved, inserts the argument by assembling the right dictionary from the instances in scope. After the translation no overloading remains, only records and functions. Wadler and Blott proposed type classes together with this translation in 1989^[1], and it is how Haskell compilers implement them. In languages without type classes, such as OCaml, the translated form is written directly.

§ 01

Translation

The translation is driven by type inference. Wherever an overloaded method is used at a type, the inferred constraint must be discharged: either by an instance, which supplies a dictionary, or by a constraint of the enclosing function, which receives the dictionary as a parameter and passes it on^[2]. Each part of the source language has a counterpart:

A class class Eq a where (==) :: a -> a -> Bool becomes a record type 'a eq with a field equal. A superclass, as in class Eq a => Ord a, becomes a field of the subclass's record that holds the superclass dictionary, so a function that has an Ord a dictionary also has Eq a. An instance without a context, Eq Int, becomes a value eq_int. An instance with a context, Eq a => Eq [a], becomes a function eq_list from an 'a eq to an 'a list eq. A constrained function takes one dictionary parameter per constraint, and a call elem [2] xss at type [[Int]] becomes elem (eq_list eq_int) [2] xss.

Eq, Ord and Show with instances for integers, strings, lists and pairs, translated by hand.

(* Each class becomes a record type of its methods. A superclass is a
   field holding the superclass's dictionary. *)
type 'a eq = { equal : 'a -> 'a -> bool }
type 'a ord = { eq : 'a eq; compare : 'a -> 'a -> int }
type 'a show = { show : 'a -> string }
 
(* Instances for base types are values. *)
let eq_int = { equal = Int.equal }
let ord_int = { eq = eq_int; compare = Int.compare }
let show_int = { show = string_of_int }
let show_string = { show = Printf.sprintf "%S" }
 
(* An instance with a context, such as Eq a => Eq [a], is a function
   from the dictionaries it needs to the dictionary it provides. *)
let eq_list (d : 'a eq) : 'a list eq =
  { equal = (fun xs ys -> List.equal d.equal xs ys) }
let ord_list (d : 'a ord) : 'a list ord =
  { eq = eq_list d.eq; compare = List.compare d.compare }
let show_list (d : 'a show) : 'a list show =
  { show = (fun xs -> "[" ^ String.concat "; " (List.map d.show xs) ^ "]") }
let show_pair (a : 'a show) (b : 'b show) : ('a * 'b) show =
  { show = (fun (x, y) -> "(" ^ a.show x ^ ", " ^ b.show y ^ ")") }
 
(* A constrained function, such as elem :: Eq a => a -> [a] -> Bool,
   takes its dictionaries as ordinary arguments. *)
let elem (d : 'a eq) x xs = List.exists (d.equal x) xs
let nub (d : 'a eq) xs =
  List.fold_left (fun acc x -> if elem d x acc then acc else acc @ [x]) [] xs
(* Ord a gives access to Eq a through the superclass field. *)
let sort_uniq (d : 'a ord) xs = nub d.eq (List.sort d.compare xs)

Running it.

[[]; [2]; [3; 1]]
[("a", 1); ("b", 2)]
elem [2] xss = true

The dictionary for Ord (int list) built by ord_list ord_int. Its eq field is the superclass dictionary Eq (int list); its methods are closures over the element dictionaries.

The instance functions make dictionaries compositional: from finitely many instance declarations, the type checker can build a dictionary for any of the infinitely many types those instances cover, such as Show [(String, Int)] in the example. Instance resolution is a proof search, and the dictionary is the proof term; this is why dictionaries are also called evidence^[2].

§ 02

Dictionaries at run time

Most dictionaries are known at compile time, since in most programs the type at each call site is fixed. This is not always so. With polymorphic recursion, a function calls itself at a different type, and the dictionaries it needs depend on how deep the recursion goes. Nested datatypes, in which a type is defined in terms of itself applied to a larger type, force this^[11].

Showing a nested datatype needs a new dictionary at every level.

open Classes
 
(* A nested datatype: each level holds pairs of the previous level's
   elements, so a value of depth d holds 2^d - 1 elements. *)
type 'a nested = Flat | Nest of 'a * ('a * 'a) nested
 
let built = ref 0
let show_pair_counted a b = incr built; show_pair a b
 
(* Showing an 'a nested needs Show a at the top, Show (a * a) one level
   down, and so on: polymorphic recursion. The dictionaries are built at
   run time, as deep as the value is. *)
let rec show_nested : 'a. 'a show -> 'a nested show = fun d ->
  { show = function
      | Flat -> "Flat"
      | Nest (x, rest) ->
        d.show x ^ " :: " ^ (show_nested (show_pair_counted d d)).show rest }

Running it.

1 :: (2, 3) :: ((4, 5), (6, 7)) :: Flat
dictionaries built: 3
for a value of depth 16: 16

The dictionary for the 16th level, for 16-fold nested pairs, is constructed while the program runs, and a compiler cannot build every dictionary a program might need in advance. This is a genuine difference between dictionary passing and implementations that generate a separate copy of each polymorphic function for every type at which it is used.

§ 03

Costs and optimizations

A method call through a dictionary is an indirect call to an unknown function, which prevents inlining; an arithmetic operation in code overloaded on Num is a call to a closure instead of a machine instruction. Compilers remove most of this cost by specialization: when a constrained function is called at a known type, the compiler makes a copy of it with the dictionary as a constant and simplifies the copy, and GHC does this automatically within a module and on request across modules^[12]. Jones showed that in a Haskell-like language without polymorphic recursion, partial evaluation at compile time can remove dictionaries altogether^[5].

Dictionary parameters also change sharing. A definition such as n = genericLength xs that is overloaded on the numeric type is, after the translation, a function of a dictionary, and it is recomputed at every use instead of being evaluated once. The Haskell monomorphism restriction exists to prevent this: a binding without function arguments and without a type signature is not generalized over constrained type variables^[6]. Augustsson described these and other implementation issues in 1993^[4].

§ 04

In ML

OCaml has no type classes, and the translated form is written directly: the programmer passes a record or a module where a Haskell compiler would insert a dictionary. A record works for classes over types, such as Eq or Show. For classes over type constructors, such as Functor or Monad, a record type cannot be written, since OCaml types cannot abstract over a type constructor (see higher-kinded type); the dictionary is then a module and the constrained function a functor. The standard library's Set.Make is an instance of this pattern: it takes an ordering as a module and produces the operations on sets that depend on it.

Dictionaries as first-class modules and functors, and a dictionary packed with a value.

(* The same idea one level up: a module is a dictionary, a module type
   is a class, and a functor is an instance with a context. *)
module type ORD = sig type t val compare : t -> t -> int end
 
(* A first-class module can be passed like a record... *)
let maximum (type a) (module O : ORD with type t = a) (xs : a list) =
  List.fold_left (fun m x -> if O.compare x m > 0 then x else m) (List.hd xs) xs
 
(* ...but a class over a type constructor, such as Monad, has to be a
   functor parameter, because OCaml types cannot abstract over 'a t. *)
module type MONAD = sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end
 
module Traverse (M : MONAD) = struct
  let rec map_m f = function
    | [] -> M.return []
    | x :: xs -> M.bind (f x) (fun y -> M.bind (map_m f xs) (fun ys -> M.return (y :: ys)))
end
 
module Option_monad = struct
  type 'a t = 'a option
  let return x = Some x
  let bind = Option.bind
end
 
module List_monad = struct
  type 'a t = 'a list
  let return x = [x]
  let bind xs f = List.concat_map f xs
end
 
(* A dictionary packed together with a value of an unknown type is an
   object: the dictionary is its method table. *)
type showable = Showable : ('a -> string) * 'a -> showable
let show_all = List.map (fun (Showable (show, x)) -> show x)

Running it.

maximum: quince
map_m half [2; 4; 6] = Some [1; 2; 3]
map_m half [2; 3; 6] = None
choices: 8
42, text, 2.5

The last example packs a dictionary, here a single function, together with a value whose type is hidden by an existential GADT constructor. That is the representation of an object: the dictionary plays the role of a method table. Rust's trait objects and Swift's existential types are represented in the same way. Swift also compiles generic functions by dictionary passing, calling its dictionaries witness tables, while Rust compiles each generic function separately for every type at which it is used.

Dreyer, Harper, Chakravarty and Keller showed that type classes can be explained as ML modules with a mechanism for inferring module arguments^[9], and the modular implicits proposal for OCaml would add such a mechanism: a function could declare an implicit module parameter, and the compiler would find a module of the right signature in scope and pass it^[8].

§ 05

Coherence

Dictionary passing makes the choice of instance part of the program's meaning. If two different dictionaries for the same class and type could be chosen at different call sites, two parts of a program could disagree, for example about the ordering used to build a balanced tree and the ordering used to search it. Haskell prevents this by requiring instances to be globally unique, which is what makes orphan instances a problem^[2]. Scala's implicits, which pass dictionaries as implicit parameters and permit local instances, give up global uniqueness in exchange for flexibility^[7]; ML's explicit functor application avoids the question, since the programmer names the dictionary, and a set built with one ordering has a different type from a set built with another.

§ 06

Alternatives

A compiler can instead generate a separate copy of every polymorphic function for every type at which it is used. This is called monomorphization, and it is how C++ templates, Rust generics and whole-program ML compilers such as MLton work^[13]; it produces fast code, cannot handle polymorphic recursion without bounds on its depth, and increases code size. Another approach passes representations of types instead of dictionaries and dispatches on them at run time, called intensional type analysis^[10]. A dictionary can be seen as the part of such a type representation that a particular function actually uses.

§ 07

History

Wadler and Blott introduced type classes in 1989 as a way to make overloading of arithmetic and equality fit the Hindley–Milner type system, and presented the dictionary translation as their semantics^[1]. Kaes had described a similar system of parametric overloading in 1988^[3]. Type classes were adopted in the first Haskell report in 1990, and Hall, Hammond, Peyton Jones and Wadler gave the full typing and translation for Haskell in 1996^[2]. Augustsson and Jones studied the performance of dictionary passing and its elimination^[4]^[5]. In 2007 Dreyer and co-authors related type classes to ML modules^[9], in 2010 Oliveira, Moors and Odersky described Scala's encoding of type classes with implicit dictionaries^[7], and in 2014 White, Bour and Yallop proposed modular implicits for OCaml^[8].