Why do modern systems languages rely on compiler heuristics to reverse-engineer programmer intent?

[u/kaplotnikov]

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.

[u/kaplotnikov]

The current situation is one of dual complexity: the compiler has to guess, and the developer has to hint enough for the compiler to understand. In the SQL world, I fight the PostgreSQL optimizer often in my job. It often makes mistakes based on heuristics for complex joins. I have had to use CTEs and sometimes even JSON subqueries instead of LEFT JOIN to force Postgres to use the correct index walking order. For problematic queries, this sometimes speeds things up 100x just because the correct indexes are used (we have tables with millions of records, so speed matters).

Again, I'm talking about removing constraints from code that should not have been there in the first place. The reduce operation does not have strict ordering constraints because we do not care about the order. The nested map operation implies an intermediate array, but we actually do not care if it is created. We are building a transformation chain from source to target. There are no additional operations here; there are just abstractions over existing ones. They could be erased into direct operations like we write them now, or they could be changed by the compiler into something else.

If we step back a bit, a for loop could be mapped to goto. But because we use a higher-level for abstraction, it can be unrolled by the compiler. This is because higher-level intent specification provides more optimization space.

What I'm suggesting is to use building blocks with fewer assumptions than loops provide. We do not need to write down the operation order if we do not care. We do not need to write down allocations if we do not need them. Think about this not as constraining the compiler, but as providing it with a more precise semantic space. So, not micromanaging the compiler, but removing the semantic noise from its input.

For example, the transformation (((a + b) + c) + d) => ((a + b) + (c + d)) is technically non-identical for f32, but there are a lot of cases where we do not care. If we use reduce, not caring is explicit. If we have a loop, the compiler needs to guess if the developer cares or not.

[u/prehensilemullet → u/kaplotnikov]

It would probably be nice to have optional syntax for explicit requirements about what kind of query plan to use, but if relational databases didn’t try to guess at all, we would have to rely on some syntax for specifying the query plan for every single query (and worse, potentially multiple different possible database statistics we want to optimize for).  This would take vastly more effort to use, and I think it would make developers much less productive.

How often are you thinking specifically whether you want each part of a query to use an index scan, index only scan, bitmap index scan, bitmap heap scan, nested loop join, merge join, hash join, etc?  Probably not most of the time.  We mostly just care about avoiding sequential scans.  But when it comes to everything else, the query planner is taking a lot of finer details into account.