> There are multiple valid ways to compile a source with the same semantics, but a decent compiler should absolutely be deterministic. Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%:

That's not the only kind of non-determinism, you know?

Lots of algorithms benefits from access to random bits, too.

The context is

> for each input, there is one and only output

A randomized algorithm which uses non-determinism but produces the same output is OK.

Also, psuedo-randomness is OK as long as the same program compiled in the same version of the compiler always gets the same seed.

But if the algorithm can produce different output causing the same program to compile to different assembly, that's a problem. Unless you can formally prove that every possible variation will have the same behavior, but formal methods + non-determinism is hard, so it usually isn't worth it.

Even random hash order in hashmaps can create problems: see https://github.com/rust-lang/rust/issues/84447 and https://github.com/rust-lang/rust/pull/82272#issuecomment-82..., though this is a very small issue in the diagnostic reporter and not a case of 2 valid programs with different semantics.

If you are using something like a SAT solver to produce code, non determinism might be unavoidable. Like, say the solver is heavily multi threaded for perf reasons (these things are slow right?). Or I guess, any FPGA compiler would fit that mold also.

Or anything that compiles a corpus into a model, though we typically call that training rather than compilation :).

Parallel computing can still produce deterministic outcomes, if you are careful.

Having said that, most people are not careful, and most languages make it very hard to be careful.

The keyword is 'deterministic parallelism', if you want to look into the research. See eg https://www.well-typed.com/blog/2012/12/deterministic-parall...

Deterministic parallelism has a non-trivial cost that can negate the perf you were hoping to gain by using multiple cores (or even GPU cores) in parallel.

> Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%

Nondeterministic doesn’t mean random. Consider how NFAs relate to DFAs and then realize the same applies to nondeterministic TMs.