3 ms·

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, psu

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 https://github.com/rust-lang/rust/issues/84447 and https://github.com/rust-lang/rust/pull/82272#issuecomment-825124318 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.

seanmcdirmid 3y ago
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 :).
- eru 3y ago
  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-parallel-programming-with-haskell/ https://www.well-typed.com/blog/2012/12/deterministic-parall...
  - seanmcdirmid 3y ago
    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.

seanmcdirmid 3y ago

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 :).

eru 3y ago
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-parallel-programming-with-haskell/ https://www.well-typed.com/blog/2012/12/deterministic-parall...
- seanmcdirmid 3y ago
  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.