Geek Answers Handbook

Why is "Random.nextInt" not considered to be "composite, modular, easily parallelized",

From the book "Functional Programming in Scala" there is a section on how to functionally write a random number generator.

Here is an example of scala.util.Random :

Even if we did not know anything about what was happening inside scala.util.Random, we can assume that the rng object has some internal state, which is updated after each call, since wed otherwise gets the same value every time we called nextInt or nextDouble. Because state updates are performed as a side effect, these methods are referenced. And, as we know, this implies that they can be testable, composite, modular, and easily parallelized as they could be.

The last sentence says that it is not:

  • verifiable
  • composable
  • modular
  • easy to parallelize

In later content, he explained the testable part, but how to understand the other 3 aspects?

+7
scala random functional-programming
source share
1 answer

1. Tested

You cannot easily isolate your state, especially when tests are executed in parallel. This makes it impossible to reproduce a sequence of random numbers in a predictable way in parallel testing.

2. Typed

You cannot create a sequence of operations that first sow a random number with a known value, and then get a sequence with respect to this seed (especially when running in parallel).

While this may intersect with “testable,” it may also be required for security reasons, so you do not accidentally leak from one session to another session.

3. Modular

It is not possible to swap different randomization algorithms. All modules must use the same algorithm. This overlaps with “compositional” in the sense that instead of seed you also cannot provide a generator as a (possibly implicit) parameter.

4. Parallelized

For all threads, there is only one state. In a very parallel situation, this can be a serious bottleneck.

Sample code example

Please do not use this code in the manufacturing process. This is pretty awkward and scalaz or cats you can easily build something better. Usually the random number generator is comonad, this state is executed in the monad.

First, make the code modular by providing different pseudo-random generators and different seeds

 // This is a commonly used pseudo-random generator // https://en.wikipedia.org/wiki/Linear_congruential_generator // This implementation is awful slow! def lcg(multiplier : BigInt, increment : BigInt, dividend : BigInt)(seed : BigInt) = (seed * multiplier + increment) mod dividend // Some commonly used pseudo random number generators def glibRand = lcg(multiplier = 1103515245, increment = 12345, dividend = 2^31) _ def vb6Rand = lcg(multiplier = 214013, increment = 2531011, dividend = 2^31) _ def javaRand = lcg(multiplier = 25214903917L, increment = 11, dividend = 2L^48) _ // This is really insecure, don't use it for anything serious! def seedFromTime() = BigInt(System.nanoTime()) // I used a dice to determine this value, so it random! def randomSeed = 5

Then create an implementation that can create functions:

 case class Random[T,U](val generator : T => T, val seed : T)(val currentValue : U){ def apply[V](f : (T,U) => V) : Random[T,V] = { val nextRandom = generator(seed) Random(generator, nextRandom)(f(nextRandom, currentValue)) } def unsafeGetValue = currentValue }

A few examples where we use these building blocks to create a list of random numbers and summarize some random numbers:

 val randomNumbers = Stream.iterate(Random(glibRand, seedFromTime())(List.empty[BigInt])){r : Random[BigInt, List[BigInt]] => r.apply{(rnd : BigInt, numbers : List[BigInt]) => rnd :: numbers } } randomNumbers.take(10).last.unsafeGetValue val randomSum = Stream.iterate(Random(glibRand, seedFromTime())(BigInt(0))) { r: Random[BigInt, BigInt] => r.apply(_ + _) } randomSum.take(100).last.unsafeGetValue

As usual, when we want to compose something in a functional language, we will compose functions to achieve different goals. If we provided a monadic implementation, we could also combine functions with side effects.

In this case, parallelization and verifiability are automatically performed (as usual).

+7
source share

More articles:


All Articles