https://www.reddit.com/r/haskell/comments/16x9v54/is_class_dictionary_passing_the_result_of_a/
1 Like
The contents of the linked post (for anyone else who would prefer not to visit Reddit):
As far as I understand function with class constraints are transformed into a function with an extra parameter being the typeclass dictionary. This allows the function to not have to be specialized and only decide at runtime what to do exactly (sorry for the bad explanation). In short
Show a => a -> Stringis transform internally toDict a -> a -> String.I have a discussion on discourse where people consider this extra parameter as part of the function:
Show a -> a -> Stringhas TWO parameters.My intuition is that this extra parameter is only the result of an implementtaion choice. An hypotetical compiler could work back from the main an instantiate all functions with required types. Therefore passing a class dictionaly might be needed for practical reason but not in theory.
Am I right or is dictionary passin the only way to implement typeclass in Haskell ?
Good luck to your hypothetical compiler at specializing all possibly-necessary versions of bitsToInt in the following program, without using dictionary parameters:
import Data.Word (Word64)
import GHC.Clock (getMonotonicTimeNSec)
newtype Zero a = Zero a
newtype One a = One a
data Nil = Nil
class BitClass a where
bitsToInt :: a -> Word64
instance BitClass a => BitClass (Zero a) where
bitsToInt (Zero a) = bitsToInt a * 2
instance BitClass a => BitClass (One a) where
bitsToInt (One a) = bitsToInt a * 2 + 1
instance BitClass Nil where
bitsToInt _ = 0
data SomeBits = forall a. BitClass a => SomeBits a
instance BitClass SomeBits where
bitsToInt (SomeBits a) = bitsToInt a
intToBits :: Word64 -> SomeBits
intToBits 0 = SomeBits Nil
intToBits i = case i `divMod` 2 of
(i', 0) | SomeBits a <- intToBits i' -> SomeBits (Zero a)
(i', 1) | SomeBits a <- intToBits i' -> SomeBits (One a)
main :: IO ()
main = do
someInt <- getMonotonicTimeNSec
print (bitsToInt (intToBits someInt))
(Ask me to explain if it isn’t clear how this example demonstrates that universally replacing dictionary parameters with specialization is a practical, if not theoretical, impossibility.)
I think it’s even theoretically impossible with polymorphic recursion.
On the other hand Rust does monomorphization instead of dictionary passing so it’s not an invalid strategy. It doesn’t support polymorphic recursion, of course.
3 Likes
Thanks! (I don’t mind viewing Reddit, but I’m not going to try posting there.)
Yes when Wadler came up with the idea it was an implementation choice, not the way to define the semantics. So another compiler might support constraints in a different way.
And then there was an interesting to-and-fro ~1999 between Wadler and SPJ re DatatypeContexts that are now deprecated. [‘Contexts on datatype declarations’, starting at SPJ’s opener.]
data Floating a => Cart a = Cart{ x, y :: a}
samePoint (Cart{ x1, y1 }) (Cart{ x2, y2 }) = x1 == x2 && y1 == y2
displacement (Cart{ x, y }) = sqrt $ x^2 + y^2
The rules are (were) that anything that wants to consume a Cart must supply a Floating dictionary – even though it’s only going to throw it away (samePoint needs only Eq). Contrariwise for anything that wants to build a Cart, it’s reasonable that it asks for sight of a Floating – but again it’s probably going to throw it away. SPJ said that passing around all the dictionaries was both awkward and useless. But Wadler insisted (he seemed not to get the implications of dictionary-passing – like that was an implementation choice which didn’t always apply).
What we have today in GADTs is that dictionaries are built inside the data constructor, so are revealed upon pattern matching. That’s a fine design for some purposes; but also wasteful/almost-useless for say a vector of Cart describing a polygon.
1 Like
Oleg Kiselyov has written extensively about type classes and their implementation:
https://okmij.org/ftp/Computation/typeclass.html
…and provides small working examples in Haskell and OCaml to illustrate the concepts.
1 Like
I’m not convinced that whole program monomorphisation counts as “a different implementation” of type classes; rather it is an optimisation (staged/partial evaluation) of the usual dictionary passing implementation.
Due to polymorphic recursion, there are also Haskell programs which can’t be completely monomorphised.
Let us take this example (taken from wikipedia, for a lack of creativity):
data Nested a = a :<: (Nested [a]) | Epsilon
infixr 5 :<:
nested = 1 :<: [2::Int,3,4] :<: [[5,6],[7],[8,9]] :<: Epsilon
Let’s write an Eq instance:
instance Eq a => Eq (Nested a) where
Epsilon == Epsilon = True
x :<: xs == y :<: ys = x == y && xs == ys
_ == _ = False
What’s curious about this instance is that you really need the full generality of Eq a in order to define Eq (Nested Int); if you “monomorphise” the instance to Eq (Nested Int) you’ll get a type error in xs == ys, which needs an instance for Eq (Nested [Int]).
Since the nesting depth of Nested has no static bound, and because Haskell allows user input, there is no way to statically compute the number of necessary monomorphisations of the form Eq (Nested Int), Eq (Nested [Int]), Eq (Nested [[Int]]), …,Eq (Nested [^n Int]]). You really need explicit dictionary passing here.
As a result, GHC is only able to specialise the outer Eq (Nested Int) instance of this program (even though in this particular example, it could perhaps see that it only needs 3 instances):
-- RHS size: {terms: 28, types: 35, coercions: 0, joins: 0/0}
Main.$fEqNested_$s$c==1 [Occ=LoopBreaker]
:: Nested [Integer] -> Nested [Integer] -> Bool
[GblId, Arity=2, Str=<1L><1L>, Unf=OtherCon []]
Main.$fEqNested_$s$c==1
= \ (ds_d133 :: Nested [Integer]) (ds1_d134 :: Nested [Integer]) ->
case ds_d133 of {
:<: x_aGo xs_aGp ->
case ds1_d134 of {
:<: y_aGq ys_aGr ->
case GHC.Classes.$fEq[]_$c==
@Integer GHC.Num.Integer.$fEqInteger x_aGo y_aGq
of {
False -> GHC.Types.False;
True -> lvl_r1UL xs_aGp ys_aGr
};
Epsilon -> GHC.Types.False
};
Epsilon ->
case ds1_d134 of {
:<: ipv_s13F ipv1_s13G -> GHC.Types.False;
Epsilon -> GHC.Types.True
}
}
...
lvl1_r1UM :: String -- <------------- THE MAIN THING
[GblId]
lvl1_r1UM
= case Main.$fEqNested_$s$c==1 Main.main2 Main.main2 of {
False -> GHC.Show.$fShowBool4;
True -> GHC.Show.$fShowBool2
}
Are there other implementation strategies besides dictionary passing, aside from variations like passing instance methods individually? I doubt it, but I also don’t care much. You can define dictionary passing style in terms of type classes, which is good proof that you can’t implement it using anything less expressive. As far as type classes is concerned, I don’t care much about distinguishing the abstract concept from the only reasonable implementation I know of.
2 Likes
We could instead not erase types and get at runtime the class dictionary from the argument type. Would that be unreasonable ?
You might say this equivalent but in the case of Eq a => a -> a -> Bool, it would be equivalent to (a, Type) -> (a, Type) -> Bool so depending on how you are seeing it, either a function with 2 or 4 parameters (but not 3). I am just wondering how much of this “only reasonable implementation” is leaking and if this leaking is reasonable.
Try doing that with Monoid's empty :: Monoid a => a:
myEmpty :: Monoid a => a
myEmpty = empty
You need to pass something in the position of Monoid a; otherwise you have no chance to “inject” your Type in an argument position.
Even if it were possible, I’d consider not erasing types as another special case where we partially evaluate less: What you are describing sounds a bit like doing instance resolution at runtime instead of compile-time.
1 Like
It might be possible to inject at the caller site. Not saying this is practical, just checking the theory.
It might be possible to inject at the caller site
Exactly! The class dictionary is a parameter 
Call me crazy, but I feel like in this discussion, dictionary passing is r -> and runtime lookup is Reader r.
In core, not in Haskell.
Here is another more theoretical problem which shows that typeclasses cannot always be compiled via dictionary passing. The setting requires subtyping, so it isn’t directly applicable to Haskell, but it would be applicable to a language based on algebraic subtyping (e.g. https://dl.acm.org/doi/10.1145/3093333.3009882 or https://dl.acm.org/doi/10.1145/3409006).
In that setting, an if-then else expression like the following:
if b then (5 :: Int) else "hello"
has the inferred type Int \/ String. And if we read typeclasses as predicates on types, as in the original articles by Blott, Wadler and Mark P Jones, then this type should satisfy the covariant predicate Show. So we should be able to write:
show (if b then (5 :: Int) else "hello")
But I do not immediately see how we would compile this using dictionary passing, since the information which typeclass instance to use is only available at runtime.
2 Likes