News for hackers. Stuff that matters.
Re:The Easiest Way to Build a Type Checker by octachron on Sunday November 30, 2025 @03:35PM (#46100146)
For a bounded size of types of sub-expressions, HM inference is quasi-linear in the size of the program, because the constraints appearing in the HM algorithm are only equality between meta-variables.A NP-complete SAT solver is not really a good fit for this kind of simple constraints. Even more so when typechecking often represents a significant part of compilation time.

(Of course the tricky part of the definition above is that the size of types can theoretically be exponential in the size of a program, but that doesn't happen for programs with human-understandable types)

There are no comments on this comment yet.