News for hackers. Stuff that matters.
Re:How the OCaml type checker works (2022) by incognito124 on Sunday August 18, 2024 @09:58AM (#41282415)
Before opening the article, my first thought was "wdym, it's HM and Algorithm W"

The very first sentence was: > There is more to Hindley-Milner type inference than the Algorithm W.

I guess congratulations to the author for knowing the audience well enough

Re:How the OCaml type checker works (2022) by Drup on Sunday August 18, 2024 @10:25AM (#41282576)
That remark is actually more interesting than you think. As groundbreaking as it was, algorithm W iss far too slow for non-toy languages. All modern HM languages (that I know of) use some form of union-find trickeries, as pioneered by the one presented in the blog post (but also present in resolution-by-constraints approaches employed by Haskell and Scala).

So, in fact, it's actually never algorithm W in non-toy languages. ;)

Side note: this article is originally from 2013 and is considered a must-read by any would-be hackers trying to modify the OCaml typechecker (it's cited in the documentation).

Re:How the OCaml type checker works (2022) by lupire on Sunday August 18, 2024 @10:51AM (#41282715)
The Wikipedia articles claims that W is efficient, but only for a core language without highly desirable features like recursion, polymorphism, and subtyping.

https://en.m.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_...

Re:How the OCaml type checker works (2022) by carlmr on Tuesday August 20, 2024 @04:40AM (#41298073)
OCaml without recursion would not be the same.
Re:How the OCaml type checker works (2022) by Rusky on Sunday August 18, 2024 @01:13PM (#41283633)
In fact, those union-find trickeries come from the same paper that presented algorithm W, where they were named algorithm J. W was known from the start to be more useful for proofs than implementation:

> As it stands, W is hardly an efficient algorithm; substitutions are applied too often. It was formulated to aid the proof of soundness. We now present a simpler algorithm J which simulates W in a precise sense.

https://doi.org/10.1016/0022-0000(78)90014-4

Re:How the OCaml type checker works (2022) by derdi on Monday August 19, 2024 @11:13AM (#41291736)
Isn't the union-find trickery "just" standard almost-linear unification as discovered by Paterson-Wegman and Martelli-Montanari around 1976? Or is there more to it in the setting of Algorithm J?

I'm actually a bit surprised that it took so long to discover these formulations of unification. I wonder what Prolog systems were doing at the time, given the importance of efficient unification.

Re:How the OCaml type checker works (2022) by Rusky on Monday August 19, 2024 @02:48PM (#41293635)
Paterson-Wegman and Martelli-Montanari are worst-case linear, but Algorithm J just uses the earlier almost-linear union-find approach: unification variables are represented as mutable pointers to either a) nothing, or b) another type (which may itself be the "parent" unification variable in the union-find structure). Unification is then just a recursive function over a pair of types that updates these pointers as appropriate- and often doesn't even bother with e.g. path compression.
Re:How the OCaml type checker works (2022) by 082349872349872 on Sunday August 18, 2024 @10:12AM (#41282500)
The subtitle, "or what polymorphism and garbage collection have in common", is another hint there may be more to TFA than its HN submission title indicates.