On Monday, 25 January 2016 at 18:40:59 UTC, Jonathan M Davis
wrote:
As long as the numbers are pseudo-random, then in theory,
there's no problem with a range of random numbers being a
forward range.
I thought that too, for a long time, but I came to the conclusion
it's not the case.
Here's the essence of the problem: a forward range is a promise
to the code that uses it, "I am a deterministic sequence." But
the whole point of pseudo-random sequences is that you're not
supposed to be able to tell them from actual randomness.
If you _tell_ downstream code "I am deterministic", that code may
make assumptions about how it can use you, that are valid for
"normal" deterministic sequences, but aren't valid for what are
supposedly random sequences.
Consider the typical handling of forward ranges:
auto foo (R) (R range)
if (isForwardRange!R)
{
auto rcopy = range.save;
// do something with rcopy
}
That's fine if you're dealing with something whose behaviour is
meant to be deterministic, but if you call this with a
pseudo-random sequence, than every time you call it, you will get
the same result. It won't matter if what you pass is a
reference-type -- the .save (which is correct behaviour for
handling a forward range) means you're just repeatedly using a
copy of the random sequence.
That could be useful upon occasion (similar to how it can be
useful that the same seed results in the same sequence of
numbers).
Right, but the point is that re-use of a pseudo-random sequence
should happen at programmer request only, not under the hood in
library code they call -- which is what unfortunately happens if
you implement RNGs and other random sequences as forward ranges
:-(
The problem is that if they're a forward range, then you tend
to get code that accidentally ends up reusing numbers in the
sequence and that definitely is a problem. So ultimately, they
probably should be input ranges rather than forward ranges, but
I think that it's more of an issue with human error than with
what makes sense from a technical perspective.
Again, I thought that too, but I came to the conclusion that I'd
been wrong. It's not about fallible humans, it's about the
promise a forward range makes.
Superficially, it looks like that promise is: "You can use my
deterministic nature if you need to." But actually, I think it
is really something stronger: "You can use my deterministic
nature freely and nothing will go wrong in doing so."
That's a much stronger promise than can be allowed for a
pseudo-RNG, and I think it's borne out in the way in which e.g.
phobos functionality makes use of forward ranges.
Regardless, non-pseudo random number generators obviously can't
be forward ranges though, since their state isn't savable or
repeatable.
Right -- non-PRNGs must be input ranges by design. I came to the
conclusion that pseudo-RNGs need to be input ranges, but that
implement an alternative to .save: a .dup method whose promise
is, "You can duplicate the state and hence behaviour of this
range, but you can't make any assumptions that this is a safe or
sane thing to do."
