Reference semantic ranges and algorithms (and std.random)

monarch_dodra monarchdodra at gmail.com
Tue Sep 18 08:05:26 PDT 2012


I've been developing a PRNG recently, and studying how it behaves 
with phobos' other stuff, in particular, range and algorithm.

I quickly came to the conclusion that if a PRNG does not have 
reference semantics, it is just as good as useless.

Why? Because everything in phobos is passed "by value". For 
example:

--------
import std.random, std.stdio, std.range, std.algorithm;

void main()
{
     auto rng = MinstdRand(); rng.seed();
     auto r1 = rng.take(5).array();
     auto r2 = rng.take(5).array();
     writeln(r1);
     writeln(r2);
     copy(rng.take(5), r1);
     copy(rng.take(5), r2);
     writeln(r1);
     writeln(r2);
}
--------
[48271, 182605794, 1291394886, 1914720637, 2078669041]
[48271, 182605794, 1291394886, 1914720637, 2078669041]
[48271, 182605794, 1291394886, 1914720637, 2078669041]
[48271, 182605794, 1291394886, 1914720637, 2078669041]
--------
As you can see from the ouput, that is not very random. That's 
just the "tip of the iceberg". *Anything* in phobos that iterates 
on a range, such a fill, filter, or whatever, will not advance 
the PRNG, arguably breaking it.

At best, a "global" PRNG will work, provided it is never ever 
passed as an argument to a method.

This is issue #1: I'd propose that all objects in std.random be 
migrated to classes (or be made reference structs), sooner than 
later. This might break some code, so I do not know how this is 
usually done, but I think it is necessary. I do not, however, 
propose that they should all derive from a base class.

The second issue I've run into (issue #2) is that even with 
reference semantics, there are still some issues regarding 
phobo's behavior with references ranges: Completly un-documented 
and inconsistent.

For example, if one were to call copy(source, target), would 
"source" be advanced? would "target" be advanced? Depends really. 
You'd be surprised too: For example, fill, with an infinite 
range, would save the filler before starting.

I was making a pull for optimizing fill/copy, and the thing kind 
of exploded in my face. I decided to take this opportunity to try 
to formalize and document this behavior.

I was hoping for some info/feedback/suggestions...
The pull request is here:
https://github.com/D-Programming-Language/phobos/pull/802


More information about the Digitalmars-d mailing list