3 ms·
Swift is highly inspired by Standard ML. If you look at https://en.wikipedia.org/wiki/Standard_ML https://en.wikipedia.org/wiki/Standard_ML, you can see the sim
by Someone 10y ago
Swift is highly inspired by Standard ML. If you look at https://en.wikipedia.org/wiki/Standard_ML https://en.wikipedia.org/wiki/Standard_ML, you can see the similarities:
fun dist ((x0, y0), (x1, y1)) = let
val dx = x1 - x0
val dy = y1 - y0
in
Math.sqrt (dx * dx + dy * dy)
end
Because of that, it also has its exponential time complexity (see for example http://spacemanaki.com/blog/2014/08/04/Just-LOOK-at-the-humongous-type/ http://spacemanaki.com/blog/2014/08/04/Just-LOOK-at-the-humo...)
What makes things especially bad for Swift seems to be that it has function overloading and uses lots of it in its standard library, as that increases the constants in the exponentiation (for example, with 6 choices to make and 10 vs 2 possible overloads per decision point you get 10^6 = a million versus 2^6 = 64 options to consider)
- eastWestMath 10y agoI'm confused, shouldn't people be supplying type signatures to make the compilers job easier? I use plenty of lambdas in Haskell, but my top level functions are always typed.
- trurl 10y agoI 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.