This is something I have been wondering for a while. Is there a place for nondeterministic functions in a purely functional language?
I'm talking about nondeterminism as in nondeterministic algorithms, not NTMs or nondeterministic programming. A function that may return different outputs for the same input.
Traditionally, one would achieve nondeterminism with a pseudorandom function, using a seed for an RNG. The seed needs to be incremented for every call to the function ergo you have a side-effect.
But let's pretend our CPU has a quantum random number generator: it can quantum entangle and collapse 2 qbits to generate a true random number. To the best of my knowledge, this would be truly side effect free. Alternatively, we simply don't give a shit about the underlying implementation of the random function and pretend It Just Works™.
The use of nondeterministic functions obviously breaks referential transparency. Should we care?
It does make memoization impossible for some functions, but if nondeterminism can be statically identified, this would not affect any functions that can theoretically be memoized anyway.
It shouldn't matter for lazy evaluation. Random 'choice' is random, regardless of order, a true random function wouldn't care when it is called.
It shouldn't affect the Curry-Howard correspondence, as it doesn't change the type system.
It shouldn't really affect the isomorphism with category theory, as while we may no longer have equality of values for many cases, we still have equivalence. Two random numbers are equivalent in that they are both random numbers.
However, I cannot help but feel I am missing something important here. I haven't been able to find any academic literature about the subject, but then again I suck at finding academic literature.
Top comments (13)
For your example of a function that gets a random number from an outside source of random data, it seems analogous to me to a function that gets a user’s input.
In, for e.g. Haskell, we’d presumably wrap that code in an IO monad to keep the function nominally pure.
User input is inherently statefull; user and machine interact by sharing a state. Therefore a monadic representation seems necessary (although you may be able to successfully fuck around with linear types, input getter functions and interleaving, probably not a good idea though).
Randomness is not inherently statefull. A true random function, unlike a pseudorandom, will not give two shits about when, in what order or by whom it is called. It will produce an 'equally random' result in every case.
Haskell may use IO monads, but that does not mean it is necessary or even good. I don't think quantum random number generators were in the back of everybody's mind in the late 80's when Haskell was first created after all ;-)
Purity is not about state, it's about referencial transparency. A function is pure iff (if and only if) given same arguments it returns the same output.
A random generator takes no argument and returns a different result every time, so it is inherently impure.
That's an excellent point.
Would you know of any practical arguments (besides memoization) in favor of referential transparency, insofar as it is lost by introducing non-determinism?
Reverseability for example. Haskell has STM (software transactional memory) which is like a global shared variable between threads, but instead of race conditions of two threads try to write at the same time, the actions get rolled back and then redone one after another. The type system guarantees that you cannot do monadic actions when writing to STM, just pure stuff. If you would have randomness in there, rollback and redoing would not be the same thing.
That's true, but sort-of isn't. The new computation "may as well" have been the old one: it is still equally correct because true randomness has no hidden state that was affected by the rollback and redo.
This is all still ignoring the de-facto pseudorandom / deterministic nature of most of our machines.
To me the situation seems fairly simple in that the world is still different afterward than it was before. In terms of consistency also, if a language guarantees purity (like elm or haskell), it seems a bit silly to equivocate about that.
That's only true if you use seeds, which as I mentioned is theoretically unecessary and could be abstracted away in practice.
There is a formal definition of purity in What is a Purely Functional Language by Amr Saby:
Non-determinism conflicts with this definition, specifically the definition of "weakly equivalent":
A naive inclusion of a nondeterministic variable breaks this equivalence.
EDIT: fix typo V => B
I had conceded this point to Jan van Brugge in another comment.
Seeing this particular definition, though, I hesitate (assuming Amr Saby is an authoritative figure).
If we assume B is a superposition of all outcomes of the non-deterministic operation, one that only collapses to a single value once we observe it, which would have been an IO operation anyway, weak equivalence holds. I'm hardly familiar with quantum computing so maybe I'm abusing some terminology.
Even if this idea holds, though, I guess sharing a non-deterministic redex by value would give faulty results.
This would be the same strategy used to make all effects including IO pure, described in the section 5.1 Effects as values of the paper. Notice nondeterministic algorithms like quick sort needs the value of the random number, making a sequence of collapses, mandating an order therefore a monadic implementation. Actual quantum algorithms like quantum annealing of Shor's factorization algorithm may be fully lifted into the Applicative, but don't take my word for it.
Btw, you do not need to create qubits for randomness. A piece of hardware sampling electrical noise usually has enough entropy. In Haskell, true random number can be obtained from hardware via operating system with
getHardwareEntropy.Interesting points.
I would argue there is at least some difference between "regular" effects-as-values and non-determinism since the latter does not set order requirements or dependencies on "the outside". Classifying non-determinism as an effect seems therefore incorrect.
Quicksort is an interesting case since it's only non-deterministic in evaluation, not in result; weak equivalence holds.
Although I am more skeptical of what I wrote after a good sleep, no that's not what I meant. I agree with you that they are different, it just so happens that we can wrap it in a monad to deal with it. (Monad is everything) (Not really but pretty much).
Being Haskell, there is a paper for it: Purely Functional Lazy Non-deterministic Programming. We can use Monad to represent deterministic computation. To add non-determinism, we instead use
MonadPlus, which is monoid under monad constraints, because the monoid law requires the binary operation to be commutative.