Tuesday, July 2, 2013

Immutability and randomness

In my last post, I proposed a working definition for mutability: in short, an object mutable if code can directly affect its state. I mentioned one odd implication of this rule: certain OS calls like getCurrentTime are considered immutable even though their results are different each time. An even trickier problem is that of randomness and pseudo-randomness.

Let's take a random number generator first. There are various ways to produce truly random (or very close to it) number sequences: using the weather, relying on hardware inputs, or even leaning on quantum mechanics. A language can't affect any of these, so random number generators that use them fall within the realm of immutable objects by my definition.

On the other hand, a pseudo-random number generator's sequence is completely based on code, once its initial state is set. The PRNG has some seed, and when asked it does some math to determine a new seed and a result for the random. This means that PRNGs are "normal" objects that have to participate in a language's mutability rules.

For languages that have immutable objects, this makes PRNGs awkward to work with; rather than just asking for the next random number, you have to ask for a pair (randomNumber, nextPrng). If you forget to do this, your pseudo-random sequence will be boringly predictable. Here's an example from Haskell (using ghci):

> prng <- getStdGen > next prng (750537749,750578441 40692) > next prng (750537749,750578441 40692) > next prng (750537749,750578441 40692)

As you can see, this is quite boring; the reason is that the second element of the returned pair (shown here as "750578441 40692") is the crucial next-immutable-PRNG, which we're not using. Here's that code done right:

> prng0 <- getStdGen > let (r1, prng1) = next prng0 :: (Int, StdGen) > let (r2, prng2) = next prng1 :: (Int, StdGen) > let (r3, prng3) = next prng2 :: (Int, StdGen) > r1 750537749 > r2 1579754317 > r3 1580611703

This is the behavior we want, but look how much more code it took! Even ignoring the ":: (Int, StdGen)" bits (that's Haskell needing some help with its type inference), it took twice the lines of code and required littering the block with one-time-use prngN variables.

This is a case where I think Effes' semi-mutability really shines. Once you get the PRNG object, you can use it all you want, and it'll mutate its internal state to update its seed as it goes. If you pass it to a function, that invalidates (at compile time) your copy; you have to get a different one if you want to continue generating random numbers. This is a tad more cumbersome, but not much (there are ways to alleviate it, such as "forking" the PRNG before passing it to the function).

No comments:

Post a Comment