http://d.puremagic.com/issues/show_bug.cgi?id=5249

           Summary: Strongly pure random generator
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2010-11-21 15:47:51 PST ---
As pure functions become more and more common in D2 programs, I'd like to generate some random values inside them too. So I suggest to add to the std.random module a strongly pure function that keeps no state and generates random values.

This code shows that it's doable (but it's just for demonstration, because this pseudo random generator is too much weak):


import std.stdio: writeln;

immutable struct rndPair {
    double seed, rnd;
}

// strongly pure
// Probably with DMD 2.050 a std.typecons.Tuple can't
// be used as return value here
pure nothrow rndPair nextRandom(const double seed, const double max) {
    enum int IA = 3_877, IC = 29_573, IM = 139_968;
    immutable double new_seed = (seed * IA + IC) % IM;
    return rndPair(new_seed, max * (new_seed * (1.0 / IM)));
}

// strongly pure
pure double[] foo(const int n, const double firstSeed=42) {
    double seed = firstSeed;
    auto res = new double[n];
    foreach (ref r; res) {
        auto seed_rnd = nextRandom(seed, 1.0);
        r = seed_rnd.rnd;
        seed = seed_rnd.seed;
    }
    return res;
}

void main() {
    writeln(foo(5));
    // Output:
    // [0.37465, 0.729024, 0.636467, 0.793481, 0.538545]
}


If you want two different strongly pure functions may be added, one good enough generator and one better generator.


Once some unpacking syntax for tuples is present in DMD the foo() may become
more elegant, similar to (this uses what Andrei calls the 'banana syntax', but
other syntaxes are possible):


pure double[] foo(const int n, const double firstSeed=42) {
    double seed = firstSeed;
    auto res = new double[n];
    foreach (ref r; res)
        (|r, seed|) = nextRandom(seed, 1.0);
    return res;
}


See also bug 5124

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5249


Jonathan M Davis <jmdavisProg@gmx.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jmdavisProg@gmx.com


--- Comment #1 from Jonathan M Davis <jmdavisProg@gmx.com> 2010-11-21 16:37:52 PST ---
So, essentially you want a random number generator which is monadic, like you'd get in a language like Haskell.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5249



--- Comment #2 from bearophile_hugs@eml.cc 2010-11-21 16:40:59 PST ---
(In reply to comment #1)
> So, essentially you want a random number generator which is monadic, like you'd get in a language like Haskell.

Right, but it's not a replacement for the normal random generator, it's one more function added.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5249



--- Comment #3 from bearophile_hugs@eml.cc 2010-11-21 20:03:55 PST ---
A bit more realistic (but not complete, not commented, etc) test using one of the rnd generator of the std.random module:


pure nothrow UIntType pureLinearCongruential(UIntType, UIntType a, UIntType c,
UIntType m)
                                            (UIntType x0) {
    // perform compile-time tests on a, c, m here...

    static if (m) {
        UIntType _x = x0 % m; // slow?

        static if (is(UIntType == uint) && m == uint.max) {
            immutable ulong x = (cast(ulong) a * _x + c);
            immutable ulong v = x >> 32;
            immutable ulong w = x & uint.max;
            immutable y = cast(uint)(v + w);
            _x = (y < v || y == uint.max) ? (y + 1) : y;
        } else static if (is(UIntType == uint) && m == int.max) {
            immutable ulong x = (cast(ulong) a * _x + c);
            immutable ulong v = x >> 31;
            immutable ulong w = x & int.max;
            immutable uint y = cast(uint)(v + w);
            _x = (y >= int.max) ? (y - int.max) : y;
        } else {
            _x = cast(UIntType) ((cast(ulong) a * _x + c) % m);
        }
    } else {
        UIntType _x = a * _x0 + c;
    }

    return _x;
}

alias pureLinearCongruential!(uint, 16807, 0, 2147483647) pureMinstdRand0;

import std.stdio: writeln;

void main() {
    uint rnd = 100000;
    foreach (_; 0 .. 10) {
        rnd = pureMinstdRand0(rnd);
        writeln(rnd);
    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5249


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei@metalanguage.com
         AssignedTo|nobody@puremagic.com        |andrei@metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5249



--- Comment #4 from bearophile_hugs@eml.cc 2011-08-30 04:49:26 PDT ---
In dmd 2.055 you are allowed to assign to an immutable value the result of strongly pure functions. So purity becomes even more useful, and things that break purity are even less handy. If you want to fill an array of immutables you can't currently use uniform() as in gen2() because it's not pure:


import std.random;

struct Foo { int x; }

immutable(Foo[]) gen1(in int n) pure {
    auto foos = new Foo[n];
    foreach (i, ref f; foos)
        f = Foo(i);
    return foos;
}

// gen2 can't be pure because of uniform(),
// so I can't cast its result to immutable
const(Foo[]) gen2(in int n) /*pure*/ {
    auto foos = new Foo[n];
    foreach (ref f; foos)
        f = Foo(uniform(0, 100));
    return foos;
}

void main() {
    immutable foos1 = gen1(10);
    //immutable foos2 = gen2(10);
    const foos2 = gen2(10);
}



With a strongly pure rnd generator functions you are allowed to generate an array of immutable random values efficiently (efficiently means without using array append):


import std.random;

struct Foo { int x; }

Tuple!(Foo[], TSeed) gen3(TSeed)(in int n, in TSeed seed) pure {
    auto foos = new Foo[n];
    foreach (ref f; foos) {
        (int rndValue, seed) = nextUniform(seed, 0, 100);
        f = Foo(rndValue);
    }
    return typeof(return)(foos, seed);
}

void main() {
    immutable foos3 = gen3(10);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5249


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5249


Joseph Rushton Wakeling <joseph.wakeling@webdrake.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |joseph.wakeling@webdrake.ne
                   |                            |t


--- Comment #5 from Joseph Rushton Wakeling <joseph.wakeling@webdrake.net> 2013-08-30 04:33:02 PDT ---
(In reply to comment #0)
> As pure functions become more and more common in D2 programs, I'd like to generate some random values inside them too. So I suggest to add to the std.random module a strongly pure function that keeps no state and generates random values.

It's theoretically possible for quite a few existing RNGs to have a much better degree of purity.

If we consider the range interface, then we'd like to have:

    enum bool empty = false;

    auto front() @property @safe const pure nothrow {}

    void popFront() @safe pure nothrow {}

Among the current challenges are that the existing design/use of RNGs means that initialization cannot be assumed, so many (e.g. Mersenne Twister) have conditions inside front, popFront, etc. which amount to

    if (/* is not initialized */)
    {
        seed();
    }

... which kills const (where desirable) and may have an impact on purity as
well.

Some RNGs also have internals which mitigate against @safe.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------