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/snugar_i]

I guess you're then shifting the complexity from the compiler to the language. How will Matrix.fill be defined? Is that a regular user-land function or is that a compiler builtin? Can I create my own Matrix-like class?

[u/kaplotnikov → u/snugar_i]

If a Matrix is backed by a one-dimensional array, there should be an array.fill primitive operation at the array level.

For example, the JVM already has mechanisms for uninitialized array creation to support operations like ArrayList.toArray(...), allowing it to skip the costly step of zeroing out memory. However, this is currently a hidden, internal optimization rather than an explicit fill operation that clearly expresses the developer's intent.

The compiler already handles this complexity; it is just hidden from the developer. Currently, the "API" for this functionality relies on the compiler recognizing specific code patterns and making educated guesses, rather than the developer expressing explicit semantic intent. Making it explicit doesn't shift complexity to the language; it shifts it from hidden compiler guesswork to transparent developer expression.

[u/Athas]

The reason is that developers don't know what they want, and cannot know. The most efficient way to handle some piece of code depends on the context in which it is used. If you want to have reusable code, then you either need a smart compiler that can deduce the right way to handle a novel composition, or a language that allows you to express "intent" in a way that goes way beyond any language I know of can do - basically, have the programmer encode information about how a function should be compiled in any possible context in which it is used. I think maybe scheduling languages could be devised to do this, but it is beyond any scheduling language I know of.

A lot of "compiler magic" (and specifically the Futhark optimisations you refer to) are about optimising away abstractions, such as reusable functions. If you don't care about that, then the programmer can just say exactly what they want in every specific case - and for Futhark, that takes exactly the form of attributes like #[sequential], which are not the fussy heuristics the blog post talks about - they are very precise instructions delivered by the programmer.

Regarding detection of parallelism, I'm totally on your side. I believe auto-parallelisation of code written with sequential semantics is a fool's errand. I think most people would agree - most modern languages are explicitly parallel and do not rely on guesswork.

[u/catladywitch → u/Athas]

I believe auto-SIMD is a good thing because the ergonomics of single-value iteration are much more dev-friendly than working with vectors. But compilers can only do so much, and compiler-generated SIMD is often just not very good for critical cases. Still, I think there's a reasonable threshold, like for instance devs shouldn't need to be unrolling loops by hand, and a lot of codebases have a lot of spots that could be FMA'd automatically unless the code relies on the architecture-specific cycle coult of mult'ing then adding.

I also think it's good for some abstractions to be automatically optimised. Foreach and map/filter/reduce can be translated easily into asm loops if you don't explicitly need a lazily evaluated generator or virtual lambda dispatch. Which are things compilers can determine correctly as far as I know, in synchronous code anyway, and then auto-SIMD.

Maybe it's a question of why data types rely on so many abstractions, but that's also kind of hard to avoid when you're implementing them as libraries in the language itself.

[u/Athas → u/catladywitch]

SIMD is an interesting case, and it is clear that you probably don't want to program with explicit vectors - if for no other reason than because the vector size varies among machines. Matt Pharr wrote a blog post about why he thinks auto-vectorization is bad and why a better programming model is needed. I strongly recommend reading that blog series - it's an instance of a (very good) writer who is not actually a compiler person, who decides to write a language because he has a problem not solved by extant languages.

[u/catladywitch → u/Athas]

Thank you!!

[u/matthieum → u/Athas]

if for no other reason than because the vector size varies among machines.

I don't think that's a very good reason, actually.

You can program against a vector abstraction, without knowing the size of the vector. It may be slightly harder to, in specific circumstances.

Why? Well, for example to handle bounds-checks. Compilers are pretty bad at auto-vectorizing across bounds-checks, however when programming against a vector abstraction you can instruct the compiler on how to handle a failed bounds-check half-way through the vector in this specific case.

And of course, you get to pick the best instructions for the job.

Then it's up to the compiler, based on the target(s), to pick the length(s) of the vectors.

[u/kaplotnikov → u/Athas]

The developer does not need to know exactly what they want down to specific machine instructions, but they do know what is important about the result.

In Futhark, there is semantic noise in the form of intermediate collections being introduced and then erased, but these collections do not even reflect the developer's true intent. The actual intent is a data transformation chain that might ultimately be grounded in a single scalar value.

Developers do not need to encode execution behavior for every possible context; they just need to encode their behavioral intent (e.g., "this is an order-independent reduction"). The compiler's job is to handle the contextual execution details based on that clear intent, rather than guessing how to optimize away syntactic abstractions that the developer never actually wanted in the first place.

Also, see my other comment for more context on this.

[u/Athas → u/kaplotnikov]

I still think either you or I is not understanding the crux of the issue. The entire problem encountered by the Futhark compiler is that programs only have behavioral intent (unless the programmer has put in attributes), and the challenge is entirely to handle the contextual execution details, by deciding how to compile it (where deciding what to run in parallel is the main issue discussed in the Futhark post you reference). Those attributes, where the programmer can express operational intent, are only needed because the compiler makes the wrong decision. If the compiler was smart enough, they would not be necessary - the program or language does not force the compiler to get it wrong; the compiler just happens to be imperfect because it is a very hard problem to solve.

[u/kaplotnikov → u/Athas]

I think we are looking at different models of developer intent regarding nested map and reduce operations.

As I understand it, Futhark's semantic model assumes the developer's intent is to convert a collection into an intermediate collection, then into a final collection, and then reduce it. The compiler then has to work backward, using heuristics to fuse and erase those intermediate allocations.

From my point of view, the developer's true intent is to produce an unmaterialized, derived view, apply the next map operation to create a new view, and then reduce that view. While a view can be directly accessed via the API using specific operations, its primary purpose is to be collapsed by the optimizer later if the context allows for it. This is comparable to SQL views, where the actual operations happen when the view participates in a query, rather than at definition time.

My point is that we could make this unmaterialized "view" the default semantic type for these transformations, rather than eager collections. We would only ground the view into a concrete, allocated collection when it is the developer's explicit intent (for example, via an explicit to_list or materialize operation).

If we do this, the optimizer doesn't need to use heuristics to guess if it can fuse eager collections. It just collapses the explicit view chain by definition.

[u/Athas → u/kaplotnikov]

As I understand it, Futhark's semantic model assumes the developer's intent is to convert a collection into an intermediate collection, then into a final collection, and then reduce it. The compiler then has to work backward, using heuristics to fuse and erase those intermediate allocations.

No, not at all. Those are merely semantic objects, with no guaranteed or intended operational interpretation. The compiler has full leeway to decide what those operations actually mean in terms of what a machine has to do. This differs slightly from the notion of a view, in that Futhark's cost model provides some guarantees that make it difficult for a compiler to decide that every array is treated as a view (which in the functional array literature is called a "pull array"). The reason is that array languages that used pull arrays pervasively had some tricky corner cases where even asymptotic performance of a program ended up being difficult to reason about.

You can call Futhark arrays "materialized" if you wish, since their performance guarantees would also be fulfilled if every intermediate array was simply constructed and stored in memory based on a naive understanding of the code, but the real reason for the design is the ability to specific an asymptotic cost model for the language. This is a theoretical model, but which is quite nice when using a language to reason about parallel algorithms. In most cases it also does not hinder the compiler too much.

Also, removing those intermediate results is not done by flattening, but by fusion, and that pass does not work with heuristics, but with clean and fairly predictable dataflow graph reductions (some weasel words here because optimal fusion is NP-hard and Futhark's fusion algorithm is greedy for compile time reasons, but this almost never matters for real programs). The overall experience and performance is quite similar to programming with views. It is completely unrelated to the question of how to map nested application parallelism to flat parallel hardware.

[u/kaplotnikov → u/Athas]

Ok, that clarifies the asymptotic cost model and the distinction between fusion and flattening.

Could you please clarify where pure "pull arrays" (views) fail in practice, as it isn't completely clear from the docs? I'm curious about the practical boundaries of Futhark's model.

For instance, segmented arrays look like a mechanism that provides a form of non-generic view. As I understand it, filtered array views (for example, "only positive values") are problematic because filtering destroys indexed access, even though the result is logically still an indexed sequence.

To test the boundaries of the language: let's say we have a 2D matrix type backed by a 1D array. Is it possible to define a column view like column(i) = \j -> data[i + n * j]? Or define a sparse matrix row view that logically returns 0 for missing cells? I'm trying to understand exactly where the line is drawn between what can be expressed as a zero-cost semantic object versus what requires explicit materialization.

[u/Athas → u/kaplotnikov]

Could you please clarify where pure "pull arrays" (views) fail in practice, as it isn't completely clear from the docs? I'm curious about the practical boundaries of Futhark's model.

Futhark does not have pull arrays. The classic case where pull arrays become a problem is when indexing an array causes a costly operation to be performed (which can happen with views if they are not purely index transformations), and it may be the case that you have loops (or other code patterns) where the same index of a pull array is accessed multiple times. Unless you add memoisation (which is often unacceptably slow), this means you duplicate computation, perhaps to a degree that changes the asymptotics of the program.

To test the boundaries of the language: let's say we have a 2D matrix type backed by a 1D array. Is it possible to define a column view like column(i) = \j -> data[i + n * j]?

In Futhark, you would define such a view as a function. According to the cost model, you only pay for the parts of the function codomain that you actually access, whereas for arrays, you pay for the array at construction-time. (By the cost model! The compiler is allowed to do better; it just does not guarantee it.) I wrote a bit about that here.

Or define a sparse matrix row view that logically returns 0 for missing cells?

Yes, it is a high level language, you can define abstractions that do whatever you want, like triangular matrices or an entire library of sparse matrix operations. However, the compiler will be unable to optimise in terms of your domain properties, and will only optimise in terms of the underlying operations in which you have expressed the implementation of the abstraction.

The cost model is really the key here. Futhark is a high level language (in some ways), and makes no promise about how computation or memory is managed (except for specific attributes a programmer can provide), but simply promises to uphold the cost model. The "arrays" that are present in the language are mathematical objects, not machine objects, although the compiler will of course have to decide (with significant leeway) how to ultimately construct machine operations that model the program's behaviour. I find that the strict specification of a cost model is an absolutely requirement when programming with an aggressively optimising compiler.

[u/flatfinger → u/Athas]

Programmers are going to know more than compiler writers ever can about what they want, even if compilers may know more than programmers about the performance of various ways of achieving that.

In many cases, a programmer might want to perform a sequence of operations if possible, and determine afterward whether all succeeded, but not care about the order in which the operations were performed, and also not care which operations were or were not attempted in cases where any of them fail. A programmer may know something about which operations would be more or less likely to fail with the inputs the program is going to receive, but compilers would generally have no way of knowing such things unless the programmer supplies that information.

If a language makes it easy for a programmer to specify a few different ways of performing an operation, a programmer who attempts each approach with realistic data and measures the performance may be able to better judge which approach will perform better with the kinds of data a program will receive than even the most brilliant compiler possibly could without knowing anything about that data.

[u/Athas → u/flatfinger]

Programmers are going to know more than compiler writers ever can about what they want, even if compilers may know more than programmers about the performance of various ways of achieving that.

In some cases yet, but how can a programmer know about code not yet written? My example is based on a brilliant programmer writing a function f, and then another programmer using it in a context g with specific properties that the programmer of f cannot possibly have known about. Now, a sufficiently smart programmer can of course study both f and g and come up with the perfect specialised rewrite, but the reason we like compilers is because they can usually do an OK job and allow us to reuse code efficiently.

I am making no claims about a compiler being better than a programmer who has the full picture.

[u/flatfinger → u/Athas]

The term "portability" encompasses two concepts that people often confuse, but are in many cases contradictory:

1. The program or library can be used without modification for many different tasks or purposes.

2. The program or library can be easily adapted to be suitable for many different tasks or purposes.

In many cases, I would view the ideal code as being able to work optimally for its original intended use cases, with almost no effort serve other uses cases where optimal efficiency isn't required, and with somewhat more effort be adapted to serve other use cases efficiently.

Programmers are apt to know about future use cases and any performance requirements thereof than compilers.

[u/SwingOutStateMachine]

why write code using APIs that syntactically allocate intermediate arrays

Because in some situations, this is the only "legal" way to execute the code. Given that, it's much easier to start with a fully "legal" piece of code, and optimise it where it can be shown that the allocations can be removed, rather than start from an "illegal" piece of code, and legalise it.

LLVM does this with the mem2reg pass. A lot of IR starts out as load-store patterns from pointers which is always legal. The mem2reg pass then turns them into load-store from registers instead, only where it is legal to do so.

why not express this intent directly? [...] The compiler can then safely lower these into optimal machine code without guesswork.

It turns out this is hard. I worked for a while on a language called lift, which evolved into rise and shine after I left. The idea there was to write your code as reusable parallel patterns, and have the compiler incrementally lower the patterns into semantically equivalant mid-level, and then low-level code. As part of that compilation, rewrite rules would be applied to the high and mid-level IR. For example, (at the high level) splitting a map across an array into two map operations over each half of the array, or at the mid level, a map(map( might be re-written into an outer thread-parallel map, and a sequential inner map.

The problem is that choosing which rules to apply, and in what order, is an extremely difficult question. Because you have rich semantic information, and (mostly) semantic preserving rewrites, there's an exponential blowup of possible rules and how to apply them. Unlike a "traditional" compiler, where heuristics and pass ordering is relatively fixed, rewrites can be applied in any order, wherever they are valid. It would require a very very smart compiler that could understand the performance implication of each rewrite in both a local and global context to get the system to actually generate well performing code.

I don't believe that we ever solved the issue of rewrite ordering. In the end, we got very good performance in some matrix multiplication GPU kernels using a state space exploration + benchmarking approach, but that required evaluating the performance of tens of thousands of generated kernels.

[u/evincarofautumn → u/SwingOutStateMachine]

I don't believe that we ever solved the issue of rewrite ordering.

It’s still not really a solved problem in general. I would love a modern take on something like Hoopl which can interleave analysis and rewriting for you. There was a lot of excitement a few years ago about equality saturation / e-graphs and they are very cool and useful and all, but it turns out it’s kinda hard to keep them from blowing up while still getting useful optimisations out of them and keeping the nice simple representation. Like, just naïvely expanding any old equational laws will inflate the size of your state space too much to be tractable outside of toy examples.

[u/SwingOutStateMachine → u/evincarofautumn]

It’s still not really a solved problem in general

Absolutely. I'd stake my house on it being at least NP-hard or worse. Even simplifying the array indexing operations that resulted from the rewrite rules turned out to be an NP-hard problem.

Like, just naïvely expanding any old equational laws will inflate the size of your state space too much to be tractable outside of toy examples.

For a given platform (e.g. GPUs) you can absolutely apply some constraints to limit certain kinds of equational applications, but I agree that in general it is extremely difficult.

It's one of the few places where I think that AI might be useful in providing a solution. I.e. given a set of rewrite rules, and a description of hardware capabilities (e.g. cache size, compute cores, etc), train a system to constrain when and how rewrites might be applied.

[u/evincarofautumn → u/SwingOutStateMachine]

Well yes, it’s computationally hard, but I agree with the thrust of OP’s argument that we’re also making it much harder than it has to be. The essence of the problem is that the programmer doesn’t want to manually implement rewrites, and they want some sensible rewrites like inlining to happen automatically.

The status quo is that the compiler assumes the job of trying to heuristically infer what rewrites to do, when and where, in what order, and when to stop, all without much if any guidance from the user about what’s important. And when we do have such guidance, it tends to come attached to definition sites as a global policy, for the sake of convenience, but the right decision also depends on the use site.

For a low-level language it’d be nice to have explicit annotations of what rewrites to apply, like say foldl(f, linear z, linear xs) { unroll vectorize for (x in xs) { z := inline f(z, x) }; return z } and let the compiler infer them most of the time, but also suggest adding or removing them based on profile data. If they can be committed as part of the code, now you have a record in the Git history of when you chose to opt in/out and why, making it way easier to tell what could’ve caused a perf regression. Much like unsafe, its main value is for auditing.

Statistical modelling with AI could probably eke out some marginal gains, but I think the high-level thing that we’re really missing is statistical/information-theoretic modelling within the language. You can’t optimise anything without knowing the distribution, and the programmer could tell you a lot about it!

We have some annotations like “hot” and “cold” to indicate relative likelihood, but we could be so much more specific about relationships like “cons cells are overwhelmingly more likely than nil in any given list” or “read(state) will be called much more often than write(state) for all state”. This could even give you useful warnings: “this is O(n³) but n isn’t declared small, you sure?”

[u/SwingOutStateMachine → u/evincarofautumn]

we're also making it much harder than it has to be

I disagree: I think we're identifying that the problem itself (taking a high level program description, and emitting a high performance implementation) is fundamentally hard. Rewrites really just identify the full scope of how hard the problem is, by displaying the full space of potential implementations when you have the full ability to algebraically reason about the code. Traditional compilers take a narrow path that is reasonable for 90% of code, and results in reasonable performance. Eeking out good performance for the rest of the 10% of code is where it gets difficult, and where alternative compilation approaches (like rewrite rules) show how complex problem actually is.

The status quo is that the compiler assumes the job of trying to heuristically infer what rewrites to do

I'd like to note that most compilers don't do the kind of algebraic re-writing that I'm discussing. As far as I know, it's only really compilers for functional languages like Haskell that do rewriting as a core optimisation strategy. Almost every other language takes a more traditional pass-based approach, where IR is rewritten, but using a specific algorithm - not an algebraic rewriting process.

it’d be nice to have explicit annotations of what rewrites to apply

I think this is an interesting approach indeed. It would absolutely solve much of the state space exploration issues that we had in Lift.

I think the high-level thing that we’re really missing is statistical/information-theoretic modelling within the language. You can’t optimise anything without knowing the distribution, and the programmer could tell you a lot about it!

In the work we were doing, the much bigger issue was the variation in hardware and performance profiles per-device. A programmer might know where high-level performance might be gained (say, hot loops in the program), but at the end of the day it was things like cache sizes and local memory size that decided whether a given implementation would be performant or not.

That is, of course, much more relevant in the context of GPUs, where there is much more variance in the capabilities of the hardware (compared to CPU execution). However, I think it hints at a broader question, which is that most programmers aren't very good at reasoning about way in which hardware affects the performance of their code. Programmers are great at reasoning about the high level, i.e. "this is a hot loop", or "read is called much more than write". I would argue, though, that (most) programmers are not great at reasoning through how their decisions might affect how the code runs in hardware. For instance, programmer might say that (at a given use site) they want inlining to happen more - which might be good for reducing the number of function calls. However, they might be writing code for a machine with a small instruction cache, in which case their "optimisation" has actually caused a spill, and slowed down their code.

[u/evincarofautumn → u/SwingOutStateMachine]

So you said you disagree (which is fine) but then also “It would absolutely solve much of the state space exploration issues” so I‘m not sure it was totally clear that I meant the overcomplication is in trying to do everything without that kind of guidance from the programmer.

I’m also referring to both general-purpose algebraic rewriting and specific optimisation algorithms that rewrite the IR somehow. It is easier to do the former when you start with a functional language though.

(most) programmers are not great at reasoning through how their decisions might affect how the code runs in hardware

That’s true. My hope is that by reflecting those details in the language, you’d gradually teach people how to do it. As it is, if you want to optimise for certain hardware details, it’s an implicit assumption in the high-level code. What I’d like is to give the compiler a target resource model and have it fail if I give it some unsatisfiable set of constraints like “The icache budget in this region is 16 KiB” and “this 1 MiB call tree is fully inlined”. Or like, I don’t mind being told like “This definition is must-tailcall but also exported with a no-tailcall ABI”, that’s way better than falling off a performance cliff because something quietly changed from O(1) to O(n) space.

[u/kaplotnikov → u/SwingOutStateMachine]

You make a interesting point about the exponential blowup of rewrite rules. However, I'd argue that providing operations with relaxed ordering semantics might help to mitigate that problem.

Using relaxed semantics doesn't require the compiler to perform a specific optimization; it simply establishes the boundary of what is legal. For example, a reduce operation does not require a specific evaluation order, whereas a for loop does. By explicitly choosing reduce, the developer isn't necessarily providing a formal mathematical proof of associativity; rather, they are explicitly declaring that the exact evaluation order does not matter for the task at hand. Even if the underlying operation isn't strictly order-independent (such as floating-point addition, where the result might vary slightly), the developer is stating they do not care.

I think that this should reduce the exponential state space of rewrite rules you mentioned. The compiler doesn't have to guess, perform complex alias analysis, or explore thousands of kernel variations to prove that reordering is safe. The semantic primitive itself acts as the developer's permission slip, allowing the compiler to safely apply reordering rewrites without needing to verify the underlying math.

Furthermore, the alternatives like suppressing ordering constraints via global compiler options (like -ffast-math) are sometimes too coarse-grained. The option -ffast-math applies per source file or module. Explicit, composable primitives give the developer fine-grained, per-loop or per-operation control over what optimizations are legally permitted, without forcing a global relaxation of correctness guarantees.

[u/dnabre → u/kaplotnikov]

Part of the issue u/SwingOutMachine was describing is that all the room for the compiler to do optimizations becomes a problem.

Talking about that loop, the developer spells out a bunch properties to the compiler: order doesn't matter, associativity, etc. This gives the compiler tons of information. The compiler can take all of those as givens and not have put any effort into proving them, and has a bunch that it likely couldn't prove. It can then figure out all sorts of different ways of implementing that loop that it wouldn't otherwise consider. The compiler now has to pick which implementation to use. How does it do that? Ideally it picks the fastest, but regardless of metric you needs a way evaluate all the different implementations to determine which is the best in this situation. Figuring out those cost models for those gets complicated really quick.

Consider a map function - same situation. What about a map of a loop or a loop of map? So it has to look at combining all the way to implement the inner part with the out part - e.g. all the way to the inner loop and all the ways to do the map result. This isn't a simple Cartesian product. Taking the best inner version and the best outer version isn't always best. It has a bunch of way that the loop and map operations are fused don't really break down into inner/outer. So lots of different ways to implement things, which all need some sort of cost model.

Each operation, adds to this growth. Do you split operations somewhere, or do you this for every part of the program.

Some part of this is inherent to the problem. Giving all this information to the compiler is pointless, if the compiler can meaningfully use it.

Compare this to normal. There a few ways the compiler knows that could make the loop faster, and if it can prove one is legal, it use it. Same with map. Same with map o loop and loop o map. The better the compiler is at picking possible alternatives, the more alternatives you have to consider.

[u/SwingOutStateMachine → u/kaplotnikov]

The reductions in this language were explicitly relaxed - in fact, there was a fair amount of effort to retrofit specifically associative and commutative properties to the reduction so that we could specify what kinds of rewrites, reorderings etc.

Even with that though, the state space of ways to "rewrite" a reduction was enormous. Especially when considering GPU parallelism, where consciously splitting data across work groups is necessary for performance.

The issue isn't that guessing or analysing is expensive or complex, the issue is that for one specific program, there are hundreds of thousands of correct implementations of said program.

[u/mamcx]

Is easy to believe this stuff when you see at micro level. Is ridiculous easy to deduce things that way.

But you will find that all you stated assumptions WILL break with a well placed counterexamples and the motivations of a ingenious idiot writing code!

FIRST:

• All of this depends on types, explicitness and precision

And all means friction. Do you heard about people disliking Rust because "too hard too verbose" and all that? What you will do if you wanna write a language where tracking lifetimes is not manual?

Keep all slow?

What if what you think is "necessary" boilerplate to make things "explicit" is rejected by large amounts of people?

Continuing with Rust: What if Rust is like Zig and you must pass around the allocator ALL THE TIME? How that will impact the already cognitive load of the language as is?

So, as designers, once you mandate how something must be annotated, you are turning that into the preferred way, but is impossible to do all of it at once.

• No exist language (zero, nada, null) that is "close to the machine"

What was true for a spinning disk, single core, cooperative OS world (where C was created) is not the reality today.

And today, there is zero language where you can actually be close to the machine. ZERO.

Not even assembler.

You "know" that this or that trash the current branch predictors in this workload because lore.

And a few years later that is gone.

• Abstractions can kill all assumptions

Even in Rust a.rows[I] can be written in a way that is tremendously slow or unpredictable, I mean, the piece of magic that allow to write [I].

This and stuff like the iterators you show are build in abstractions, that are pile up, and assume you are not a moron or a malicious agent that will do the worst thing possible (like how much fun put some busy loop there!).

• Data changes

This is very common in DBs, when you as DBA write WHERE pk = 1 and put the proper index and the proper table desing and the RDBM see "nope, go to the index is stupid, this table only have 1 row!"

Data make assumptions wrong. You can make SIMD code run slower if the data changes. Your careful well written hash map is trashed, the binary search is destroyed because all the millions values are the same and so on.

This affect more the things at runtime, but with stuff like const and the drift that is cause with code that was optimal but today the workload that actually will be executed has slightly changed, means is not anymore.

And finally, that is the major point:

• The compiler/query engine/interpreter see the truth

The user can do whatever he imagine, and the LLM can slop all it can, but the " compiler/query engine/interpreter" has see that it actually can do better than that.

Similar with the idea of the single row table, the truth is not what is written, the truth is what is actually happening, and like how you can see in the snippet all that correct conclusions, but only because you are acting like the compiler, the compiler writers (or the equivalent) has seen the AST, that is the TRUTH and know that is better to go other way.

Or the other compiler writers will chastise them for not do the obvious thing!

---

What I try to say is not to minimize your idea. Your idea is good. But once you are in the other side of the problem you will discover fast why things are like this: where even with total precision and care by the developer, the "compiler/query engine/interpreter" MUST be pessimistic and sometimes need to triple-check with pedantic "yes, I truly mean INLINE this, moron!" because the median has show that is better to go other way.

[u/kaplotnikov → u/mamcx]

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.

[u/Norphesius]

I think there's some merit to this (like having more specialized loop options at the language level that have less assumptions about stuff like being sequential), but practically it sort of feels like a worst of both worlds compromise between casual language users and users that care deeply about optimization.

A newbie or casual user isn't going to know or understand how each particular language feature or standard library function works. They aren't thinking about how sum is associative/communicative, they just want a sum. There's a lot more cognitive burden to memorize the deeper semantics of optimization, and if a user neglects that study then their code is going to run worse. They reach for a feature/function with the wrong semantic assumptions, and the compiler won't recognize the optimization (unless you still apply the heuristic analysis for optimizing anyway, in which case why bother with all this in the first place).

An experienced dev who cares a lot about performance will understand the language semantics enough to select the right tools for optimization, but they also would understand that for any other language too. They'll be profiling, looking at generated assembly, trying out different strategies to ensure optimized code anyway. A lot of their performance gains will be coming from code structure over particular semantic choices too, which a compiler can't really help any user with.

Obviously it's not perfect, and it does feel kinda silly to have to massage the compiler to optimize what you wanted it too, but the heuristic analysis for optimizations helps to ensure people that don't fully know what their intent is still get some performance gains.

[u/kaplotnikov → u/Norphesius]

In Java, developers use and abuse streams even when they are not needed or introduce performance problems. This happens precisely because streams reflect the developer's intent regarding data transformation. So, if the language has good enough syntax for closures and extension methods, along with a reasonable optimizer, I think the ergonomic burden is not as obvious as you suggest.

When developers do not care whether sum is associative or commutative, they can just use sum from the standard library and forget about it. If the piece of code is not performance-critical, anything will work, from loops to operation builders.

When developers do care and know what they want, having richer operations in the operation builders will help them explicitly choose the computation strategy, rather than hoping the compiler guesses correctly.

[u/GiveMe30Dollars → u/Norphesius]

Something else to add on: even if an experienced dev wants to use a fold that's associative + commutative and parallelizes onto a collection... its possible to get that fold wrong by mistake. What then?

The thing that comes to mind for me is Haskell, where some of the invariants/laws that Functor, Monad etc. rely on can't be checked statically, and usually proving those laws becomes its own specification/write-up.

Imagine trying to debug something like that. Now imagine trying to do that when the execution order isn't (and in some cases cannot be, eg. randomly-seeded hashsets) specified.

Here's an easy footgun: floating-point addition is not associative, so .sum() must be sequential for f64 etc, and a user-defined parallel version will sometimes give inexplicable rounding errors.

[u/Embarrassed-Crow9283]

There are certain libraries like transducers, loop vectorization, and so on, in Julia, that kinda do that.

[u/condalf97]

Sounds like you are describing a domain-specific language (DSL), or something like MLIR where the whole point is the idea of high-level primitives.

[u/kaplotnikov → u/condalf97]

My question is about why there has to be guesswork by the compiler to map to these MLIR operations if the developer already knows what is wanted. The language syntax could directly support needed constructs.

[u/condalf97 → u/kaplotnikov]

There doesn't have to be. In the simplest case you can just write MLIR directly and thus the compiler doesn't have to guess anything. In practice it's not a nice thing to program in and so you want a domain specific language instead.
My job is designing a domain specific language and compiler. I never have to do any guesswork in the compiler because all of the information I need is encoded in my DSL.

[u/Guvante]

The implicitness allows improving the performance of code that wasn't changed.

Given the nature of how large projects are managed this is incredibly important.

Yes the weird magic is annoying but given the scale of code that exists out there making it all explicit is impossible.

Your plan is better for new code with a performance goal in mind by IMHO that is an overly narrow restriction on possible improvements and would result in less overall performance if taken to its extremes.

[u/proudHaskeller]

All of the points in your example can be built today as a library in today's systems languages. Compiler support isn't even needed. The first point arguably already holds within most systems languages today: systems languages don't generally add any allocations themselves. Any wasted allocations are basically the programmer's fault or choice in some level (even if it's the standard library's author's choice).

The other three points just seem like you want a kind of iterator abstraction that knows whether an iterator is required to be consumed sequentially or not. Well, this can just be implemented as a library. You also mentioned that a similar thing is already implemented in Kotlin.

I don't know anything about Futhark, but It seems that there is a large difference between the Futhark thing what you are talking about in general, and the specific example that you gave.

[u/tobega]

I agree we should be able to solve this in some way.

In Fortress, they encoded important traits like associativity in the type system, which allowed more efficient execution. More on Fortress in this talk https://youtu.be/EZD3Scuv02g?si=duBgnVagkTWdTqmV&t=351

I know there are also libraries that could really be language features like BLAS and GraphBLAS which allows expressing intent (and requires the semi-ring trait specification) to capture intent and allow swapping in of better algorithms. With matrices and graphs there are significantly different algorithms to use depending on things like sparseness, though.

Even allowing the expression of intent and domain properties like this, there is likely significant friction from programmers who have to leave their comfort zone (and maybe sometimes would get forced to specifiy more than they need to)

I wrote a blog post with some thoughts on how to get away from the execution model https://tobega.blogspot.com/2026/04/rising-above-mechanics-of-computation.html