3 ms·
I had thought about that, but I am pretty sure the reason Hindley-Milner is exponential has to do with the generalization for let-polymorphism. I'm not familia
by trurl 10y ago
I had thought about that, but I am pretty sure the reason Hindley-Milner is exponential has to do with the generalization for let-polymorphism. I'm not familiar with all the details of Swift, but I do not recall seeing that it will infer polymorphic types for you.
That doesn't mean there isn't a good reason that Swift's inference is exponential – I just think HM's exponential time behavior is a red herring.
- gilgoomesh 10y agoThe article focusses on function overloads, which are not a part of Hindley-Milner (so yes, a red herring in this case) and not necessarily exponential. The fact that Swift is exponential here is an implementation shortcoming and little more. Swift's type checker does also have an exponential path for protocol constrained generic parameters which is functionally equivalent to the exponential path for classical Hindley-Milner. However, there are "pseudo" linear optimizations for this too that Swift should also consider.