The biggest semantic mess in Futhark
7 hours ago
- #Parallel Programming
- #Type Systems
- #Futhark
- Futhark was designed to simplify parallel programming, maintaining semantic simplicity similar to first-year university functional languages.
- Size types in Futhark, which allow functions to impose constraints on parameter sizes, have introduced complexity and numerous edge cases.
- Size parameters can be used as term-level variables, leading to challenges in determining their values, especially with empty arrays or multidimensional arrays without elements.
- The solution involves arrays carrying shapes with them, but this complicates the creation of arrays without example elements.
- The Futhark evaluation model allows polymorphic functions to inquire about concrete types and extract shapes, but this requires intricate machinery and has led to many bugs.
- Type definitions in modules that reference local bindings and size parameters add another layer of complexity, requiring closures for type constructors.
- Despite formalizing part of the size-based type system, its interaction with the module system remains unformalized, and the current environment-based implementation is believed to be fundamentally correct but may still contain bugs.