Use TrieMaps to speed up type class instance lookup
Currently, type class instance resolution is performed by doing a map lookup by type class, and then linearly matching against every instance. This is not great, and for a while, simonpj has been keen on using the TrieMap data structure in GHC, which has been previously used to implement a map from CoreExprs to various things (e.g. for CSE). What makes this a little tricky is that instance lookup isn't intended to be an exact match: we should unify so-called template variables and provide a substitution; furthermore, there may be multiple matches.
After some prototyping, I think we should be able to make this work. The primary refactoring we have to do is *maintain the key associated with an entry in a TrieMap*. Unlike the current uses of TrieMaps, where it's acceptable to lose the underlying key associated with an entry in the TrieMap, we need to know the key when doing unification, because it may be reported in the substitution. There are a few knock-on effects of this:
- We should add a method
foldWithKeyTM :: (Key m -> a -> b -> b) -> m a -> b -> b
to theTrieMap
type class. - We need a variant of
UniqFM
which tracks the original key that was used. I propose we name itUniqKM
(unique key map). A number of implementations ofTrieMap
need to be adjusted to use this instead ofUniqFM
. - Why can't we just represent keyed TrieMaps as
TypeMap (Type, a)
? It might be possible. An insurmountable difficulty would be if we need to know the partial key PRIOR to having finished traversing the TrieMap; however, for the parts of the unification algorithm I've implemented, this does not seem to be the case. The primary actual difficulty is thatType
uses a named representation, whereasTypeMap
keys are on-the-fly deBruijn numbered. There would at least be some annoying fiddliness. - Reversing the deBruijn numbered key into a
Type
is a bit goofy. Essentially, you need the reverse of the currentCmEnv
: a mapping from de Bruijn levels to theVar
you've decided to allocate. (I've called thisCfEnv
in my prototype) - When we represent a TrieMap binder, we have to put the binder map on the OUTSIDE, as opposed to the inside as it is currently. Otherwise, we can't update the
CfEnv
with the new mapping before making the recursive call to fold-with-key.
I'll attach the standalone Haskell file I used to prototype this, wherein I copy-pasted a lot of Haskell from GHC's source and implemented fuzzy map on a simplified version of Type
.
Trac metadata
Trac field | Value |
---|---|
Version | 7.9 |
Type | Task |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler (Type checker) |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | simonpj |
Operating system | |
Architecture |