Explicit vs implicit state passing

[Boarders]

I'm unsure about the specifics of the current random proposal but I am interested in getting a discussion going on the plans for explicit vs implicit state (given that there is talk of pure vs impure RNG I presume this encompasses some of the same issues?). Currently if we wish to generate 1000000 dice rolls (to choose an inconsequential example) we have two options:

diceRollsIO :: IO [Int]
diceRollsIO = do
  replicateM  1000000 (randomRIO (1,6))

diceRollsState :: IO [Int]
diceRollsState = do
  let
    roll :: StdGen -> (Int, StdGen)
    roll = randomR (1,6)
  gen <- getStdGen
  pure $ evalState (replicateM 1000000 (state roll)) gen

In the second we generate state and then explicitly pass it around. I haven't benchmarked these particular functions but upon doing so one will quickly learn that the second is significantly faster than the first! Beyond GHC dealing better with pure code storing two Int32 pieces of state in an IORef and then reading and writing is a terrible idea!

This is a shame because I feel like the second piece of code is not necessarily as accessible to beginners as possible and it may not appear obvious without knowing the internals of the library that the second should always be preferred (I should also note that the version with explicit recursion typically performs worse than replicateM when used in real code though I am unsure of what fusion related details make that the case). I think the library should expose common combinators for things like this or come up with some better plan for not having a state monad interface. On top of this if the library is going to offer implicit state in the form of an IORef then an unboxed variant like this should probably be used because chasing pointers to something that should never be a thunk anyway is a bad idea!

I should also say that implicit state is not thread-safe and is quite error prone in such contexts so we might want to take that into account in any such discussion.

Note: I use here the culprit random functions which should probably face some sort of chop in a newer version of the library but it is irrelevant to this particular issue.

[Boarders]

I should note that this problem is dealt with to some extent by mcw-probability. Given that there is talk of such an interface already being useful for generation of floating point numbers I think adopting other ideas here would a good idea. I should say this doesn't answer all the questions about this aspect of an interface. For example I would like to be able to write something like:

-- Generate an increasing sequence of numbers bounded above
-- by 100 and starting from the initial argument.
generate l acc | l >= 100  = acc
               | otherwise =  do
                                d1 <- uniformR (l , 100)
                                generate (d1 : acc) d1

In other words if I am in a monadic state context I would like the state threading to be done for me! This is one of the purposes of the state monad and do notation after all.

[idontgetoutmuch]

The current proposal should cover #3 (comment) - there will no longer be a randomIO function (at least that is my understanding).

[idontgetoutmuch]

For #3 (comment) the proposal is that the "base" package does not generate floating point numbers (from a uniform distribution). For that you should use another package e.g. random-fu.

[Boarders]

Edit: The comment below is preserved but in fact I think that you can just directly have a state monad interface:

class Random a where
  random :: (RandomGen g) => State g a
  randomR :: (RandomGen g) => (a, a) -> State g a
-- etc.

I am glad we are moving away from randomIO but I think if that is the case someone needs to come up with a high level API for how to use the library because manually passing the generator around is no good at all and I have seen zero discussion so far about the top-level api which is a huge problem for a pure-pnrg. The problem is essentially that we would like a monadic interface but with constrained types and so you would need some sort of bind like:

(>>=) 
  :: (RandomGen g, Random a, Random b) 
  => RandomState g a -> (a -> RandomState g b) -> RandomState b

-- RandomState is just a newtype wrapper around a state monad:
newtype RandomState g a = RandomState {runRandomState :: g -> (g, a)}

Does anyone have any ideas for a good design here?

[lehins]

I think I might have a decent solution in for an API that solves both spectrums, stateful and pure (optionally married with state monad) RNGs. The changes I will describe below are already in #1

I haven't run any tests or benchmarks on it. I'll try to do at least the latter tonight.

The gist of this is. We introduce MonadRandom (similar to what @Shimuuar suggested in #5 but more general):

class Monad m => MonadRandom g m where
  type Seed g :: *
  restore :: Seed g -> m g
  save :: g -> m (Seed g)
  -- | Generate `Word32` up to and including the supplied max value
  uniformWord32R :: Word32 -> g -> m Word32
  -- | Generate `Word64` up to and including the supplied max value
  uniformWord64R :: Word64 -> g -> m Word64

  uniformWord8 :: g -> m Word8
  uniformWord8 = fmap fromIntegral . uniformWord32R (fromIntegral (maxBound :: Word8))
  uniformWord16 :: g -> m Word16
  uniformWord16 = fmap fromIntegral . uniformWord32R (fromIntegral (maxBound :: Word16))
  uniformWord32 :: g -> m Word32
  uniformWord32 = uniformWord32R maxBound
  uniformWord64 :: g -> m Word64
  uniformWord64 = uniformWord64R maxBound

Note that we can also provide default implementations for uniformWord32R and uniformWord64R by using uniformWord32 and uniformWord64 respectfully.

Cool part about this monad is that it can probably be used for something like a system random generator (eg. /dev/urandom):

data SysRandom
instance MonadIO m => MonadRandom SysRandom m where
...

We can create instances for stateful generators like mwc-random:

instance (s ~ PrimState m, PrimMonad m) => MonadRandom (MWC.Gen s) m where
  type Seed (MWC.Gen s) = MWC.Seed
  restore = MWC.restore
  save = MWC.save
  uniformWord32R u = MWC.uniformR (0, u)
  uniformWord64R u = MWC.uniformR (0, u)
  uniformWord8 = MWC.uniform
  uniformWord16 = MWC.uniform
  uniformWord32 = MWC.uniform
  uniformWord64 = MWC.uniform

But most importantly, I think it can not only solve @Boarders concerns as well as reduce duplication drastically, but it also allows us to use functions that work for both stateful and pure generators by the means of MonadState, while keeping a lot of things backwards compatible. Here is an example:

We can write a general function like randomListM and use it with StdGen and MWC.Gen:

randomListM :: (Random a, MonadRandom g m, Num a) => g -> Int -> m [a]
randomListM gen n = replicateM n (randomRM (1, 6) gen)

rlist :: Int -> ([Word64], [Word64])
rlist n = (xs, ys)
  where
    xs = runStateGen_ (mkGen 217 :: StdGen) (randomListM GenState n)
    ys = runST $ MWC.create >>= (`randomListM` n)

-- Potential helper functions that can be added to the API:
runStateGen :: RandomGen g => g -> State g a -> (a, g)
runStateGen g = flip runState g

runStateGen_ :: RandomGen g => g -> State g a -> a
runStateGen_ g = fst . flip runState g

runStateTGen :: RandomGen g => g -> StateT g m a -> m (a, g)
runStateTGen g = flip runStateT g

runStateTGen_ :: (RandomGen g, Functor f) => g -> StateT g f a -> f a
runStateTGen_ g = fmap fst . flip runStateT g

Here is a sample:

λ> rlist 5
([1,2,3,5,5],[3,4,3,1,4])

The fun part about MonadRandom is its instance for all pure generators:

data GenState g = GenState

instance (MonadState g m, RandomGen g) => MonadRandom (GenState g) m where
  type Seed (GenState g) = GenSeed g
  restore s = GenState <$ put (mkGen s)
  save _ = saveGen <$> get
  uniformWord32R r _ = state (genWord32R r)
  uniformWord64R r _ = state (genWord64R r)
  uniformWord8 _ = state genWord8
  uniformWord16 _ = state genWord16
  uniformWord32 _ = state genWord32
  uniformWord64 _ = state genWord64

Where the RandomGen gets a few extra things that will result in compile time warning for all that don't have 'em implemented yet:

class RandomGen g where
  type GenSeed g :: *
  type GenSeed g = Word64
  mkGen :: GenSeed g -> g
  saveGen :: g -> GenSeed g
  next     :: g -> (Int, g) -- `next` can be deprecated over time
  genWord8 :: g -> (Word8, g)
  genWord8 = first fromIntegral . genWord32R (fromIntegral (maxBound :: Word8))
  ...

What this means for RNG package maintainers:

• Pure generators create an instance of RandomGen and automatically get the monadic interface
• Stateful generators create instances for MonadRandom

Random instances only need to define the monadic functions, because we can use functions below:

genRandom :: (RandomGen g, Random a, MonadState g m) => m a
genRandom = randomM GenState

genRandomR :: (RandomGen g, Random a, MonadState g m) => (a, a) -> m a
genRandomR r = randomRM r GenState

to define default implementation:

class Random a where
  randomM :: MonadRandom g m => g -> m a
  randomRM :: MonadRandom g m => (a, a) -> g -> m a

  randomR :: RandomGen g => (a, a) -> g -> (a, g)
  randomR r g = runStateGen g (genRandomR r)
  random  :: RandomGen g => g -> (a, g)
  random g = runStateGen g genRandom

All is left is checking the performance (which I suspect should be pretty good with strict StateT wrapper) of such interface and if it's all good and everyone is onboard then we left with implementing the rest of the functionality.

Sorry for the long comment, but I feel pretty excited about it, hopefully there won't be too much pushback ;)

@idontgetoutmuch @curiousleo @Shimuuar @Boarders @cartazio Please, guys, let me know what you think?

PS. I explicitly omitted other issues that can be handled separately (splittable vs non-splittable, bounded vs unbounded numbers etc.)

[cartazio]

This is along the lines of what I’ve been planning or suggesting. I’ll share my flavor / sibling of this in a span. But along this line yess.

[Shimuuar]

It suddenly occurred to me that pure and stateful generators are not that different. They have same state monad underneath. If we look at MonadPrimitive definition and strip all newtypes we get:

For stateful PRNG

nextX :: PRNG (State# s) -> State# s -> (# State# s, X #)

For pure (Proxy is added just to make shape of type similar):

nextX :: Proxy PRNG -> PRNG -> (# PRNG, X #)

We have to thread something along which is state token for stateful PRNGs and full state for pure ones. Stateful ones also need some stateful value. I need to think some more about this. Also is there something in between?

P.S. @lehins I didn't look at your proposal in details yet

[cartazio]

I feel like the class should just have m Word64

We can have a child class that has stuff like ‘m (vec 64 Bool)’ or whatever for optimal bit complexity. Step zero is a way to write portable rng parametric algorithms

[cartazio]

These are just monads. :)

[cartazio]

The commonality is they are monads. It’s exactly the name for that interface. We can’t write that one normally in Haskell because it conflicts with the reader instance for function types. Plus unboxed tuple trickiness.

But write a mock fucntion type or newtype of fucntions and you could make bare state monad code pattern an instance.

I’m sure there’s a fun bit of historical context for why we don’t have that instance. And perhaps ghc and base should have it. / me wearing clc hat.

[lehins]

@cartazio I think there was already some agreement on set of primitives in #5

I feel like the class should just have m Word64

@Shimuuar That's right IO and ST is just a way to pass an opaque state token around. The difference with state monad + pure RNG is that we pass the actual generator (two Word64s in case of splitmix) as the state, while for stateful generators we are mutating a vector (generator), instead of passing it around.

Another way to simulate the stateful interface for pure RNGs would be to stick the generator values into a small MutableByteArray and mutate it instead of passing it around, but I suspect it will affect the performance. Although would be an interesting experiment to see by how much.

[Shimuuar]

@cartazio whether interface should be monadic or not is question that's completely orthogonal to the question which primitives we should use

@lehins Yes they're different but they share similarity. Question is whether this could be exploited. After all semantics on high level is same: threading of state.

[Boarders]

@lehins : I think your suggestions here are seriously good and would definitely move us in all the directions we want API-wise:

• unification of pure and non-pure rng interfaces
• modular/polymorphic in the RNG algorithm
• nice user interface

Thank you for thinking about it, I think this direction of travel will really improve the library and moreover make it modular enough to be a good basis for all RNG libraries.

[lehins]

I just checked the performance of generating Word64 values with mwc-random and splitmix directly and through this suggested interface. There was no overhead whatsoever.

GHC is able to optimize the StateT and the proxy GenState away successfully, so they have no negative affect on performance of pure generator.

[Shimuuar]

@lehins I finally read your proposal. First thoughts:

GenSeed type family and mkGen & saveGen could be removed. Seed is just a snapshot of generator's state but for pure generator snapshot of state and state are one and same. It should help type inference is well, since it's not possible to infer g from GenSeed

With this change your proposal could be written as:

class Monad m => MonadRandom g m where
  type Seed g :: *
  restore :: Seed g -> m g
  save    :: g -> m (Seed g)
  uniformWhatever :: g -> m Whatever

class RandomGen g where
  genWhatever :: g -> (Whatever, g)


data GenState g = GenState

instance (MonadState g m, RandomGen g) => MonadRandom (GenState g) m where
  type Seed (GenState g) = g
  restore s = GenState <$ put s
  save    _ = get
  uniformWhatever = state genWhatever

I added magic Whatever primitive to avoid writing 8 lines of nearly identical functions

This API does provide unified API for both stateful and pure generators. Which is absolutely great! We need that sort of thing

Now things I don't like:

• Carrying generator around explicitly is very annoying (esp. for pure PRNG where it does nothing). Maybe we should hide it behind Reader? N.B. (→) r is MonadReader, lens makes active use of this.
• We likely will run into problems with type inference if we create generator state generically, say using function like createGenerator :: Random g => IO g. We don't have anything like that yet but I think we'll add some generic initialization at some point. It's not unsolvable problem but it's something that needs attention.

[lehins]

That's a good observation. I concur. Removed.

GenSeed type family and mkGen & saveGen could be removed.

I don't think we should care about it in MonadRandom, since uniform* functions are not gonna be really used directly, it's the randomM and randomRM that will be:

Maybe we should hide it behind Reader?

I thought about a bit, except Random g is not a possibility, because g depends on a PrimState, something like that: createGenerator :: Random (Seed g) => IO g is also a bad idea, because it implies that the seed or the actual generator can draw randomness from any other RNG

We don't have anything like that yet but I think we'll add some generic initialization at some point.

Question on the latter point is that where do we get initial randomness, do we add ability to use /dev/random to random package? What about portability across operating systems? So I think we should postpone solving this problem. But I do agree that it would be nice to have createGenerator be a part of MonadRandom.

I was pretty stoked about it too 🤘

This API does provide unified API for both stateful and pure generators. Which is absolutely great! We need that sort of thing

[Shimuuar]

I don't think we should care about it in MonadRandom, since uniform* functions are not gonna be really used directly

But randomM :: MonadRandom g m => g -> m a has exactly same type. With this sort of one have to pass g around. You can't materialize it from somewhere.

Also I'm not sure that it impossible to use MonadReader. But I need to experiment before I can say anything

Question on the latter point is that where do we get initial randomness, do we add ability to use /dev/random to random package? What about portability across operating systems?

Portability is actually one of the reasons I think such API should be added. mwc-random has way to initialize generator using /dev/random on *nixes and windows' crypto API on windows. It took several contribution in order to gent working right.

It's not reasonable to expect that PRNG implementors will jump through flaming hoops in order to get good platform independent initialization. It's complicated thing and thus should be centralized. random seems to be a good place for that

[lehins]

Portability is actually one of the reasons I think such API should be added. mwc-random has way to initialize generator using /dev/random on *nixes and windows' crypto API on windows. It took several contribution in order to gent working right.

That's great that there is already a decent solution. I am not that fond of falling back onto time and printing various warnings to the terminal, a better solution would be to return Either String Seed, but that is orthogonal.

      hPutStrLn stderr $ "Warning: Couldn't use randomness source " ++ randomSourceName
      hPutStrLn stderr ("Warning: using system clock for seed instead " ++
                        "(quality will be lower)")

It's not reasonable to expect that PRNG implementors will jump through flaming hoops in order to get good platform independent initialization. It's complicated thing and thus should be centralized. random seems to be a good place for that

If we can agree on reliable solution for this (I haven't looked at the one in mwc-random too closely yet), I agree that random package would be a really good home for it.

[Shimuuar]

Fallback on time remains from the time when it was used on Windows instead of proper cryptographic API. It was contributed only much later

a better solution would be to return Either String Seed, but that is orthogonal.

I think it would be better to just throw exception. After all there isn't many way to handle failure expect falling down and cry. But yes, that's not very important now

[Shimuuar]

It come to me that MonadState instance comes with a problem.

instance (MonadState g m, RandomGen g) => MonadRandom (GenState g) m where
  uniformWord64 = state genWord64

It could be that programmer wants to use MonadState instance to work with some value (with lens etc) and at the same time wants to use pure RNG. This would impossible to use this instance since we could have only one MonadState s.

I'm not arguing against such instance. It is quite useful. But probably we should add another variant of MonadState, say MonadRandState which is exactly like MonadState except it isb't MonadState?

[lehins]

This is a pretty vague description of a problem. Could you provide a concrete example?

This would impossible to use this instance since we could have only one MonadState s.

If I understand the problem you describing correctly, which I probably don't, then you could solve it by stacking up multiple StateT with generators and just use lift in order to get to another generator

[Shimuuar]

Say I want to work with some complex state like Foo { _bar :: Bar, _notBar :: NotBar, ... } and use lens since doing anything with nested records is total pain without lens. Lens operators for working in monadic style require MonadState Foo m, at the same time using MonadRandom with pure gen requires MonadState PurePRNG m. Obviously both couldn't be satisfied at the same time.

On other hand this problem could be solved by adding single instance without incurring any breakage. Something along the lines (names are pretty much arbitrary):

data RandGenState g = RandGenState

instance (MonadRandState g m, RandomGen g) => MonadRandom (RandState g) m where
  ...
  uniformWord64 _ = randState genWord64

[lehins]

I think I understand your concern. What I am saying the solution for this problem is for the user to not stick the generator into the complex state like Foo but instead have it as a separate state, eg.

data Foo ...
runComplexState :: StdGen -> Foo -> StateT StdGen (StateT Foo IO) a -> IO (a, Foo)
runComplexState g foo action = runStateT (runGenStateT_ g action) foo

or if you wish other the way around:

runComplexState' :: StdGen -> Foo -> StateT Foo (StateT StdGen IO) a -> IO (a, Foo)
runComplexState' g foo action = runGenStateT_ g (runStateT action foo)

I personally don't want to complicate the API much more than needed just to accommodate lens users. For example what this MonadRandState g m would be? If it is imitation of a MonadState, then who creates all the instances for all of the transformers out there? There are quite a few questions I have, probably because there is no concrete code that depicts the issue and suggested solution. If you feel like it is a real problem and you have a good solution in mind I think the best approach would be for you to submit a PR, cause I am at a loss here.

[Shimuuar]

To be clear at the moment I'm running around with sharp stick and try to poke hole in proposed API.
This particular problem is well defined and has solutions which doesn't break anything. So it could and should be left alone until (if) users start complain. We'll see.

[curiousleo]

I believe that this ticket has been addressed through changes made by @lehins.

@Boarders, I've made a preview of the current Haddocks here: https://htmlpreview.github.io/?https://raw.githubusercontent.com/idontgetoutmuch/random/haddock-preview/docs/index.html. We're actually using your "rolling a die" example a lot!

I'm interested in your thoughts on the explicit / implicit ("pure / monadic" in the docs) APIs and their documentation.

Since the implementation has moved on quite a lot since the discussion on this ticket, I'm going to close this ticket for now. @Boarders if you find issues with the API or its documentation or have further suggestions, please create new tickets. Thank you!