On 15 September 2010 13:15, Milan Straka wrote:

 * I see no motivation why to do it,

I think the motivation is that this lets other PRNG's share the same typeclass to improve compatability, but most of them don't support split and thus can't use the current class as-is.

 * and personally I find the `split' method very useful.

Note that the proposal isn't to do away with split, but to shift it into its own dedicated type class. This will hopefully (if implemented) result in mersenne-random-pure64, mwc-random, etc. having RandomGen instances rather than having to learn their specific API, whilst leaving split there for use with StdGen. I'm still of two minds about this proposal: I think the idea is great, but that aspects of the Random class would then require SplittableGen rather than RandomGen for "sanity" (i.e. randoms and randomRs). -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 9/14/10 23:44 , Isaac Dupree wrote:

(Oh now I see Ivan mentions existing PRNGs that don't (can't?) support split... that may be a reasonable argument; I'll have to think about it; is this the main motivation? or just one observation among many?)

I think it's the main one; that things like the Mersenne twister can't be made instances of Random has stuck in people's craws for a while. - -- brandon s. allbery [linux,solaris,freebsd,perl] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.10 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkyQRPkACgkQIn7hlCsL25WuNQCdE+XCzyytOfzO/2SAU/qk+jpj cx8Anjz9nToSZJNflAaIL3zJiI14iGc8 =nx2g -----END PGP SIGNATURE-----

On Wed, Sep 15, 2010 at 1:46 AM, Simon Peyton-Jones wrote:

| > (Oh now I see Ivan mentions existing PRNGs that don't (can't?) support | > split... that may be a reasonable argument; I'll have to think about it; is | > this the main motivation? or just one observation among many?) | | I think it's the main one; that things like the Mersenne twister can't be | made instances of Random has stuck in people's craws for a while.

In GHC's unique-supply generator we use a trick due to Lennart Augustsson to turn a linear generator (such as the Mersenne twister) into a splittable one.

Code is here: http://darcs.haskell.org/ghc/compiler/basicTypes/UniqSupply.lhs

Maybe the same would work for Mersenne.

(Yes it uses unsafeInterleaveIO under the hood.)

Simon

Here's a go at it: http://hpaste.org/30094/any_randomgen_can_be_splitable I haven't done any benchmarking to see how much overhead there is to wrapping a random generator with this. I could probably switch to using atomicModifyIORef, but I don't have much experience with it. Feedback is welcome. Antoine

Bryan, you could very well be right, I'm just asking to see if you have more evidence at your fingertips that I can look at: On 09/15/10 01:39, Bryan O'Sullivan wrote:

Actually, it's worse than that: there's no statistical basis for believing that the split operation is sound. It is sure to introduce correlations between the forked generators, [...]

Citation/argument for "It is sure to introduce correlations between the forked generators"? Did someone prove that for all possible PRNGs? Or are you just claiming a lack of anyone having proved it to be sound?

While I understand the appeal of split, it is completely unsafe to use as it stands. [...]

Split on StdGen worked fine for me displaying random smoke. The only effect of the random numbers here is how it looks. And it looked fine. Actually I re-implemented that with a linear congruential generator in C for speed. Just saying, *some* uses of random numbers don't need them to have very good properties.

[...] where the Integer term returned is an approximation to the period of the newly split PRNGs. At that point, you at least get some sort of caveat emptor that you're rapidly running out of entropy when you perform repeated splits, [...]

Are you saying that 'split' on a PRNG, such as StdGen, causes the two "splitted" result StdGens to each have a shorter period than the original StdGen? I've looked at the implementation of StdGen and its split, and although I'm not an advanced mathematician, it doesn't seem to me that "split" reduces the period in any predictable way. (Perhaps it reduces the entropy?--that's a concept I'm fuzzier about its definition--but it doesn't seem to me that it would reduce the period.) Elaborate if you please :-) -Isaac

On Wed, Sep 15, 2010 at 7:57 AM, Ian Lynagh wrote:

I approve, but what do you propose to do for haskell98:Random?

Someone (me?) should make a matching proposal to Haskell' once we have decided on a reasonable way forward. WRT H98, modifying the Haskell98 library to have an upper bound on random 1.0.x would make sense. Having two incompatible classes is rather inescapable when one is in a standard and the other is its replacement. Henning said:

class StraightRandomGen g where System.Random.next :: g -> (Int, g) System.Random.genRange :: g -> (Int, Int)

class StraightRandomGen g => RandomGen g where

I favor a clean break with the past and small flurry of fixing activity. The more concessions made in the base libraries the odder all libraries will feel. If, despite me, we do decide on these classes could the new one at least be called "BasicRandomGen" or "FundamentalRandomGen"? Cheers, Thomas

Duncan Coutts schrieb:

...

Henning said:

...

class StraightRandomGen g where System.Random.next :: g -> (Int, g) System.Random.genRange :: g -> (Int, Int)

class StraightRandomGen g => RandomGen g where I favor a clean break with the past and small flurry of fixing activity. The more concessions made in the base libraries the odder all libraries will feel.

I agree. As much as possible I think we should deal with API changes using package versioning and not by making more convoluted names.

We have to introduce one new name in any case, whether for the class that contains 'split' or for the class that does not contain 'split'. Since many people expressed here that they happily use 'split', they may also consider the class containing 'split' the main Random generator class. Now we can call the class without split 'SimpleGen' in order to match the simple name of 'SplittableGen'. However none of those names tell, that they are about random generators. If we put a "Random" part in the class name, it becomes a "convoluted" name.

On Wed, Sep 15, 2010 at 05:41:19PM +0100, Duncan Coutts wrote:

On 15 September 2010 17:08, Thomas DuBuisson wrote:

...

On Wed, Sep 15, 2010 at 7:57 AM, Ian Lynagh wrote:

...

I approve, but what do you propose to do for haskell98:Random?

Someone (me?) should make a matching proposal to Haskell' once we have decided on a reasonable way forward.  WRT H98, modifying the Haskell98 library to have an upper bound on random 1.0.x would make sense. Having two incompatible classes is rather inescapable when one is in a standard and the other is its replacement.

Right, if we change the class then we do necessarily make it incompatible with H98, so H98 will have to have its own definition of Random that does not share type or class definitions with the random package.

I think at that point having the haskell98 package depend on the random package at all makes little sense. We would just take a copy of the old H98 code and put that in the H98 package.

Right. In particular, we need to be able to build haskell98 as part of GHC, and it would be a lot simpler not to have 2 versions of the random library around.

...

Henning said:

...

class StraightRandomGen g where  System.Random.next :: g -> (Int, g)  System.Random.genRange :: g -> (Int, Int)

class StraightRandomGen g => RandomGen g where

I favor a clean break with the past and small flurry of fixing activity. The more concessions made in the base libraries the odder all libraries will feel.

I agree. As much as possible I think we should deal with API changes using package versioning and not by making more convoluted names.

I agree too. The short-term pain for those who need to update their code to include a Splittable constraint is preferable to the long-term pain of living with the suboptimal names, IMO. Thanks Ian

On Wed, Sep 15, 2010 at 12:20 PM, Henning Thielemann wrote:

I assume that there is more code that uses RandomGen in constraints than code that defines instances, thus the split of the split class might look like:

class StraightRandomGen g where  System.Random.next :: g -> (Int, g)  System.Random.genRange :: g -> (Int, Int)

class StraightRandomGen g => RandomGen g where  System.Random.split :: g -> (g, g)

All existing code that uses RandomGen in constraints would remain valid this way.

+1 ...although I don't like the name 'Straight'. =) -- Felipe.

On Thu, Oct 7, 2010 at 10:00 AM, Simon Peyton-Jones wrote:

| > The "split" routine in the RandomGen seems to be a sore spot for some | > people and is perceived to have few users (even as a percentage of | > RandomGen users).  I propose: | > | > 1) Making a class "SplittableGen": | > | > class SplittableGen g where | >   split :: g -> (g, g) | > | > 2) (re)moving the "split" routine from the RandomGen class. | > | > See ticket 4314 [1] for the patch.

The design, of having two classes, seems nearly right.  The nit is that surely RandomGen should be a superclass of SplittableGen?  I don't want to bloat my contexts too much.

+1 I did an analysys of the 254 direct reverse dependencies on random: http://bifunctor.homelinux.net/~roel/cgi-bin/hackage-scripts/revdeps/random-... 7 of those 254 packages use 'split' in test code only. 27 of those 254 packages use 'split' in production code. 11 of those 27 packages use 'split' polymorphically and have explicit type signatures which need to change when 'split' is separated from RandomGen. Attached is the detailed analysis. Regards, Bas P.S. I'm thinking about creating a tool at the upcoming Hackaton that lists the reverse dependencies of symbols. Because it's tedious and error-prone to do this manually.

The "Clean Break" would involve removing "split" from the RandomGen class and making a new class "SplittableGen" for this operation.  The thought here is that not all generators can have a "split".  Users of "split" would have to be explicit of their need for a Splittable generator.

The backward compatible change would keep "split" as a member of class "RandomGen" for which all instances would be constrained to also be instances of the "BasicRandomGen" class.  BasicRandomGen would contain the traditional routines (next, genRange).

Removing the Read and Show constraints for splittable generators would be a Really Good Thing. It turns out implementing splittable generators efficiently (eg using Lennart's notion of splittable supplies) doesn't work in the presence of these constraints ---- or rather, one is faced with the choice of Read/Show yielding irreproducible results, or using an inefficient implementation of splittable supplies. -Jan-Willem Maessen

On Sat, Oct 9, 2010 at 10:02 AM, Thomas DuBuisson wrote:

All, I have updated the ticket/patch for this proposal [1].  It seems the community has agreed on

...

class RandomGen g where    next     :: g -> (Int, g)    genRange :: g -> (Int,Int)    genRange _ = (minBound, maxBound)

...

class (RandomGen g) => SplittableGen g where    split    :: g -> (g, g)

Notice SPJs good catch that SplittableGen should be constrained by RandomGen is there (lacking discussion, but its hard to imagine objection).  I'm not sure what you, Jan, mean by removing Read and Show constraints as I don't see any.

This will break the following hackage packages (thanks Bas): mage, synthesizer, synthesizer-core, Haskelloids, ideas, local-search, comonad-random, SpaceInvaders, rsagl, pkcs1, and hsgsom

All BCCed, of these only PKCS1 doesn't have a maintainer (a production pkcs1 probably shouldn't be using split anyway).

Cheers, Thomas

[1] http://hackage.haskell.org/trac/ghc/ticket/4314

What impact does this have on the 'Random' class? Has someone already brought this up? The patch on the ticket doesn't seem to touch it. It seems that it becomes less powerful. I'm not necessarily opposed, but I just wanted to make sure it was stated explicitly. This seems that some structures which could have been randomly created lazily must now be more strict (and the instance must be re-written). I'm not sure that such instances exist, but they could be useful. Antoine

On Sat, Oct 9, 2010 at 11:02 AM, Thomas DuBuisson wrote:

All, I have updated the ticket/patch for this proposal [1].  It seems the community has agreed on

...

class RandomGen g where    next     :: g -> (Int, g)    genRange :: g -> (Int,Int)    genRange _ = (minBound, maxBound)

...

class (RandomGen g) => SplittableGen g where    split    :: g -> (g, g)

Notice SPJs good catch that SplittableGen should be constrained by RandomGen is there (lacking discussion, but its hard to imagine objection).  I'm not sure what you, Jan, mean by removing Read and Show constraints as I don't see any.

I was mis-remembering the following as a class constraint on RandomGen: data StdGen = ... -- Abstract instance RandomGen StdGen where ... instance Read StdGen where ... instance Show StdGen where ... (http://www.haskell.org/onlinelibrary/random.html) This makes it hard to impossible to implement splitting of StdGen both efficiently and correctly. -Jan