Rewriting the Futhark Type Checker
5 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.