Rewriting the Futhark Type Checker

6 hours ago

The Futhark type checker originally had a simple design with scalars, arrays, tuples, first-order monomorphic functions, and no type inference, but already included uniqueness types for in-place updates.
As features like records, modules, higher-order functions, Hindley-Milner inference, and size types were added, the single-pass type checker became increasingly complex and hard to maintain.
The type checker was eventually split into multiple phases: name resolution, alias checking (post-type-checking), and a core term type checker.
A new constraint-based unsized type checker was introduced to handle complex features like AUTOMAP, generating constraints solved offline rather than on the fly.
The current new type checker performs four stages per function: name resolution, unsized type checking (ground types), size inference, and in-place update violation checking.
This layered design improves error messages by providing full information from previous stages and allows moving many checks into separate passes after main type checking.
Despite potential inefficiency from multiple passes, optimizations have resulted in a slight speedup (~4%) compared to the old single-pass checker.
The type checker also now supports recursion via an environment variable, though that is a separate topic.

Hasty Briefsbeta