Comment by lalaithion
2 days ago
A deterministic program follows a single path of execution, always producing the same result.
A nondeterministic_1 program follows a single path of execution, but at certain points, it randomly chooses how to proceed, therefore producing different results for different runs.
A nondeterministic_2 program follows multiple paths of execution, at certain points _splitting_ its execution to follow two (or more) paths instead of one, producing a set of results at the end.
A nondeterministic_1 program follows a randomly sampled path from a nondeterministic_2 program, and produces a randomly sampled result from a nondeterministic_2 program.
> A deterministic program follows a single path of execution, always producing the same result.
Looking at a whole program as D/ND isn't too useful for me since it's too big to analyse and constantly being patched by multiple contributors.
Does this definition of deterministic work for smaller things, like a method?
You can transform a function `f: (Rng, args...) -> A` into a function `f: (args...) -> Set<A>` with very little machinery. Some programming languages allow writing functions that are _generic_ over whether they're random or nondeterministic, such as in this Haskell package: https://hackage.haskell.org/package/nondeterminism-1.5/docs/...