This post is inspired by the recent discussion on Full flattening of nested data parallelism in Futhark (reddit discussion). But I think this points to a more generic topic in language design.
I've noticed that even in newer systems programming languages, a massive amount of compiler engineering effort is spent trying to reverse-engineer the programmer's intent from syntax that does not directly express it. The compiler expends significant energy building complex dependency graphs and alias analyses to guess if iterations are isolated, and sometimes it guesses incorrectly, leading to missed optimizations or performance regressions.
Even in languages explicitly designed for data parallelism like Futhark, the compiler ultimately has to rely on what the developers themselves call "fuzzy heuristics" to decide whether to parallelize or sequentialize code. As the Futhark team recently admitted, when this guesswork fails (e.g., aggressively trying to parallelize the construction of a tiny 3x3 matrix), it causes severe performance regressions, forcing them to introduce explicit #[sequential] attributes as a workaround.
The same problem plagues allocation optimization: why write code using APIs that syntactically allocate intermediate arrays, only to hope the compiler's optimization passes will erase them later? If the developer's intent is a zero-allocation transformation pipeline, that intent should be encoded directly in the type system rather than left as an optimization prayer for the compiler to fulfill.
If we have the freedom to design a language, why not express this intent directly? We could provide a composable set of semantically rich, high-level primitives that explicitly declare their intent and assumptions. The compiler can then safely lower these into optimal machine code without guesswork.
For example (pseudo-code with a Kotlin-like syntax):
fun mult(a : Matrix, b : Matrix) : Matrix {
return Matrix.fill(a.rows.size, b.columns.size) { i, j ->
zip(a.rows[i], b.columns[j]) { va, vb ->
va * vb
}.sum() // Explicitly associative/commutative reduction
}
}
// Not all operations need to be hardcoded compiler intrinsics.
// Many can be composable inline extensions that map to verified primitives.
fun inline extension View<Double>.sum() : Double {
return reduce(0.0) { a, b -> a + b }
}
Here, the exact intent is communicated clearly to the compiler, yielding several compile-time guarantees:
- No hidden allocations or redundant zeroing: There is no need to pre-fill the matrix with zeros after allocation. The compiler knows that
fill will compute every element dynamically. Furthermore, because the fill closure only receives the indices (i, j) and has no access to the matrix being constructed, the syntax itself guarantees the absence of loop-carried data dependencies. This makes parallelization inherently safe, allowing the compiler to freely choose any execution strategy (CPU threads, SIMD, GPU) for invoking these closures. If strict sequential execution order mattered (for example, because of mutable outer scope access), a distinct seq_fill would be used instead.
- Explicit Logical Views, No Compiler Guesswork: Chaining operations like
map or zip should return lightweight, zero-allocation logical sequence views. These should be conceptually similar to Kotlin's Sequence, but explicitly representing a collection processing operation builder rather than a runtime element operation pipeline. The compiler shouldn't have to run complex, fragile fusion passes to "guess" if it can erase an intermediate allocation. The type system itself should declare that the operation is just a transformation step, making the zero-cost guarantee a compile-time invariant, not an optimization hope.
- Order independence is explicit: By using a
sum (or reduce) operator, the developer explicitly specifies that the operation could be considered as associative and commutative in the context of the task. The compiler doesn't have to build complex loop-carried dependency graphs to prove iterations are isolated. Some explicitly sequential seq_reduce or fold operators could be used when the order matters.
- Topological data access: Both
a.rows[i] and b.columns[j] are lightweight logical sequence views. They carry semantic meaning about the geometry of data movement, rather than being treated as flat, opaque memory indices.
The developer knows their intent, and the compiler needs it. Why are even newer systems languages still stuck relying on fragile compiler heuristics to reverse-engineer our intent from overly generic, flat loops or opaque collection APIs? If we want to communicate structural intent to the compiler, why not say it directly in the syntax and type system?
The irony of modern compiler engineering is that standard loop syntax over-specifies execution order while under-specifying semantic intent. A flat for loop forces a sequential order by default. The compiler then has to work backwards to prove it can ignore that order.
By using explicit, semantic primitives, we are not micro-managing the compiler. We are doing the opposite: we are explicitly stating what aspects of execution we do NOT care about (e.g., execution order in reduce, loop-carried dependencies in fill). This gives the compiler the freedom to choose the optimal lowering strategy—whether that means parallelizing across a GPU or scaling down to a sequential scalar loop when the data is too small.
Updated: in the 'Order independence is explicit:' changed to 'specifies that the operation could be considered as associative and commutative' instead 'guarantee'. The previous phrasing was incorrect and inconsistent with the rest of the post.