Dconf 2015 talks...

[Joseph Rushton Wakeling via Digitalmars-d]

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