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