Just a quick status update. As my 'user' program has become larger, the type solver has begun to slow down horribly. I'm on the wrong end of some horrible O(x) where x is probably n^4 or worse.
So I decided to try an experiment, going back to the classic algorithm W. This only took a couple of days! However. One thing I didn't realize I was getting for 'free' from the constraint-based solver was recursive types. Now I'm forced to actually understand the concept.
I see two potential outcomes: 1) I grok recursive types well enough to fix my unifier, and the compiler gets much much faster; or 2) I rewrite the constraint solver to be more efficient. It's possible that I understand things well enough now to be able to do so.
If anyone out there can explain how to do unification with equirecursive types, I'd love to have the help!
Subscribe to:
Post Comments (Atom)
Posts
What I'm trying today: detect cycles in apply_subst(), and have it return a 'μ' encoding of the resultant type. I'm hoping this will then magically make the problem go away, in the same way that isorecursive types do.
ReplyDeleteOk, that approach seems to work. At least, it compiles a relatively large source file successfully. And interestingly, the types are more detailed than they were with the constraint solver (because I had to actually detect recursion in types).
ReplyDeleteThe new code is about 20X faster than the constraint solver, and less than half the size. Fingers crossed that it's correct.