Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm a bit surprised by a sentence found in the book "Clojure Programming" (1st [and only as I write this!?] edition), page 78:

It should be obvious that it's impossible to deterministically test a function that depends upon a random number generator

Well, to me it's not obvious at all.

First in the context the book definitely talks about a PRNG (that sentence just follows a mention of java.util.Random, which is a PRNG), not a real random source.

Seen that functional languages that do support higher-order function can be, well, passed functions... Why not simply pass the random generator function itself to the function you want to be able to deterministically test?

If I've got something like the following function (it's just an example) and the PRNG itself is deterministic, why would it be impossible to deterministically test the following function:

(defn shuffle-deck [deck  last-generated-number   prngf]
      ...)

I realize that instead of keeping a (global?) reference to your random generator, you need to keep a reference to the last generated number (and update it accordingly) but that's basically it.

You can then test/reproduce the behaviour of any function using a PRNG as long as you pass the PRNG and 'the random number you're currently at'.

It's not unlike deterministic game engines (like Blizzard's Warcraft III) where the replays only contains the player inputs, the time at which they happened and the overall seed to the PRNG.

Basically I'm a bit confused: I've always seen PRNG as something that is not "real randomness" and I've got the impression that functional languages accepting higher-order function make it particularly easy to reproduce behavior of functions depending on PRNG.

So, is that sentence of the book (which I found a great book btw) complete rubbish? I sure do not find it "obvious" at all...

share|improve this question
1  
I don't know much about Clojure, but at least in Haskell the random numbers package is designed so that you can give it any generator you want. You can use a global one that gets a seed from the system, but you can just as easily use one with a constant seed. So this is certainly possible--and, in fact, really easy--in Haskell, which is a language even more functional than Clojure. –  Tikhon Jelvis Jan 5 '13 at 17:40
add comment

2 Answers

up vote 4 down vote accepted

It depends on what the author had in mind when they made the statement. You're certainly correct that by using a deterministic PRNG, you can then test functions which are deterministic other than the PRNG they use.

On the other hand, if what you're testing depends on the PRNG having some behavior common to them (like having at least a certain period or a particular distribution) and your test PRNG does not provide those behaviors, you'll break your tests (or at least neuter them).

In general though, I would consider the sentence to be incorrect. It's commonplace to use deterministic PRNG's to deterministically test functions that use them as input.

share|improve this answer
add comment

The quote comes from a paragraph that goes like this:

It should be obvious that it’s impossible to deterministically test a function that depends upon a random number generator. For all intents and purposes however, the same is true of any function that depends upon or produces external state, since it is often very difficult to enumerate (...) all the potential edge cases and failure conditions related to that state. This is what mocks are for in testing, to dummy up an external data source or sink so that it will reliably behave in ways we know ahead of time so as to provoke particular results from a function under test. (...)

The paragraph comes from a section on pure functions that focuses on how pure functions differ from non-pure functions, namely the determinism that comes with the fact that output is a function of the input and input alone - no dependency on an external state. RNG is used as an example of such an external state, but so are things like number of twitter followers or bank account balance.

What author wanted to say is that you can't deterministically test a function like this:

(defn addRandom [x]  
  (+ x (rand-int 10)))

since there is an external state involved and calling (addRandom 5) twice could return two different results.

Now, you could refactor this function to break the dependency on the rand call. But then you won't have a function that depends upon a RNG. You would have a higher order function that takes a function that provides a number that might or might not be random, or you would have a function that takes a pair of numbers, and so on. You would have a pure function that you could reason about reliably, since you pushed external state out of the equation. But it would be a different function than the one you started with - one that the sentence you quoted no longer applies to.

share|improve this answer
    
oowww gotcha, it's good that I gave the exact page. I didn't really understand it like that, hence my question. So I guess that, in a way, it's maybe not the greatest choice of them all to have picked a PRNG used internally as an example of a function that cannot be idempotent (and hence certainly not pure). –  Cedric Martin Jan 5 '13 at 22:22
    
@CedricMartin: I suppose so. If the author used something more blatantly external, like a function that contains a call returning current date or current stock price, there would be no place for doubts. That said, he did make certain disclaimers why he had chosen RNG as an example of external state earlier in the same section. Also, why the downvote? –  scrwtp Jan 6 '13 at 10:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.