Strongly pure random generator

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2010-11-21T15:47:51Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=5249

CC List

• andrei (@andralex)
• issues.dlang (@jmdavis)
• joseph.wakeling

Description

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

[dlangBugzillaToGithub]

issues.dlang (@jmdavis) commented on 2010-11-21T16:37:52Z

So, essentially you want a random number generator which is monadic, like you'd get in a language like Haskell.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2010-11-21T16:40:59Z

(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.

[dlangBugzillaToGithub]

bearophile_hugs commented on 2010-11-21T20:03:55Z

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);
    }
}

[dlangBugzillaToGithub]

bearophile_hugs commented on 2011-08-30T04:49:26Z

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);
}

[dlangBugzillaToGithub]

joseph.wakeling commented on 2013-08-30T04:33:02Z

(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.

[dlangBugzillaToGithub]

andrei (@andralex) commented on 2016-10-14T15:18:03Z

This would work with the smaller rngs but not very well with the Mersenne twister which has iirc 4KB of state.

We should be able to allow this to work for the appopriate rngs:

auto identity(Rng)(Rng r) pure { r.popFront; return r; }

Then threading generators about is trivial. I'll bootcamp this.