On Friday, 16 January 2015 at 14:59:10 UTC, Dicebot wrote:
> To specify : the way I see it you either want PRNG to be a forward range and that fits with value semantics. Or you want reference semantics and it naturally becomes input range.

Here's the problem with value semantics.  This is a real problem with actual Phobos code right now.

////////////////////////////////////////////////////
import std.random, std.range, std.stdio;

void main()
{
    // Create RNG instance with unpredictable seed
    auto rng = Random(unpredictableSeed);

    // Generate sample of 3 numbers from sequence
    // 0, 1, ..., 9 using rng as source of randomness
    // and write to console
    iota(0, 10).randomSample(3, rng).writeln;

    // Do again.  We'd expect a different result
    // but actually we get just the same
    iota(0, 10).randomSample(3, rng).writeln;
}
////////////////////////////////////////////////////

Note that because randomSample generated a wrapper range (RandomSample), we can't simply pass the RNG by ref.  It's copied (and because RNGs are currently value types, it's copied by value).

Note also that the above is a problem whether or not Random is a forward or input range.

What's needed here is for the source of randomness to be updated whenever it's used, so that you don't get unintended correlations like this.  Reference types give this, but it shouldn't be necessary to interfere with the forward-range status of the RNG, which depends entirely on whether it's a deterministic pseudo-RNG or not.

Conversely, suppose that we have some function that takes a forward range as input and uses the ability to repeat the sequence.  Here's a naive example:

void foo (FRange) (FRange range)
    if (isForwardRange!FRange)
{
    foreach (i; 0 .. 10)
    {
        // silly example :-P
        auto r = range.save;
        r.take(10).writeln;
    }
}

This is a problematic design if FRange is a reference type, because (by design) if the values in it are used, they should be consumed.  So e.g. if you were passing a reference-type RNG to a function that does this, you'd like to guarantee that (i) the function is able to use the ability to repeat the sequence, but (ii) consumes from the original exactly once.

If you don't get that, you will wind up with unintended correlations in your use of random numbers.

On Friday, 16 January 2015 at 16:12:23 UTC, Joseph Rushton Wakeling wrote:
> void foo (FRange) (FRange range)
>     if (isForwardRange!FRange)
> {
>     foreach (i; 0 .. 10)
>     {
>         // silly example :-P
>         auto r = range.save;
>         r.take(10).writeln;
>     }
> }
>
> This is a problematic design if FRange is a reference type, because (by design) if the values in it are used, they should be consumed.  So e.g. if you were passing a reference-type RNG to a function that does this, you'd like to guarantee that (i) the function is able to use the ability to repeat the sequence, but (ii) consumes from the original exactly once.
>
> If you don't get that, you will wind up with unintended correlations in your use of random numbers.

While the first example is indeed problematic, this one actually is not. If this does not print the same 10 numbers every time, your save method is wrong.
Regardless of being a reference type or not it has to clone the RNG state or it doesn't do its job.

On Friday, 16 January 2015 at 17:09:47 UTC, Tobias Pankrath wrote:
> While the first example is indeed problematic, this one actually is not. If this does not print the same 10 numbers every time, your save method is wrong.
> Regardless of being a reference type or not it has to clone the RNG state or it doesn't do its job.

I think you've misunderstood what I was getting at, probably because I didn't explain myself well.

Obviously it's correct that the second function example should print out the same thing 10 times.  However, what is wrong is that at the end of that function, the source range -- if a reference type -- should itself have been popFront'ed a sufficient number of times, but it hasn't been.

That's a design fault in the function implementation, which doesn't take into account the desirable behaviour (for the caller) if the range given to the function is a reference type.

On Friday, 16 January 2015 at 17:13:33 UTC, Joseph Rushton Wakeling wrote:
> I think you've misunderstood what I was getting at, probably because I didn't explain myself well.

There's a concrete example of the problem I can demonstrate from some Phobos functionality, but off the top of my head I can't remember what it is.  I'll try and look it up when I get home later this evening.

The essence is that, as a caller, I have this problem:

    auto range = SomeReferenceTypeForwardRange(whatever);

    foo(range); // prints one set of 10 values

    foo(range); // should print different set of 10 values
                // but won't because foo()'s implementation
                // doesn't take into account possibility of
                // reference type input

On Friday, 16 January 2015 at 17:13:33 UTC, Joseph Rushton Wakeling wrote:
> On Friday, 16 January 2015 at 17:09:47 UTC, Tobias Pankrath wrote:
>> While the first example is indeed problematic, this one actually is not. If this does not print the same 10 numbers every time, your save method is wrong.
>> Regardless of being a reference type or not it has to clone the RNG state or it doesn't do its job.
>
> I think you've misunderstood what I was getting at, probably because I didn't explain myself well.
>
> Obviously it's correct that the second function example should print out the same thing 10 times.  However, what is wrong is that at the end of that function, the source range -- if a reference type -- should itself have been popFront'ed a sufficient number of times, but it hasn't been.
>
> That's a design fault in the function implementation, which doesn't take into account the desirable behaviour (for the caller) if the range given to the function is a reference type.

Ah, now I understand you. Since copy-construction is undefined for ForwardRanges, you cannot guarantee this. Things would be better, if we had required that this(this) does the same as .save or must be @disabled.

Than it would be clear that you either had to use a reference or a pointer as argument to the function.

On Friday, 16 January 2015 at 17:22:42 UTC, Tobias Pankrath wrote:
> Ah, now I understand you. Since copy-construction is undefined for ForwardRanges, you cannot guarantee this. Things would be better, if we had required that this(this) does the same as .save or must be @disabled.

I'm not sure I follow what you mean by this ... ?

> Than it would be clear that you either had to use a reference or a pointer as argument to the function.

I don't see how that would affect the undesirable behaviour of the implementation.

On Friday, 16 January 2015 at 18:12:03 UTC, Joseph Rushton Wakeling wrote:
> On Friday, 16 January 2015 at 17:22:42 UTC, Tobias Pankrath wrote:
>> Ah, now I understand you. Since copy-construction is undefined for ForwardRanges, you cannot guarantee this. Things would be better, if we had required that this(this) does the same as .save or must be @disabled.
>
> I'm not sure I follow what you mean by this ... ?

If you pass a forward range of type T (something that passes isForwardRange!T) to a function you have no guarantees on what will happen. It could be:

    • compilation failure
    • reference semantics (changes are reflected outside the function
    • value semantics (no change are reflected outside the function)

The implementer of the range can choose one. Although I tried it now, and @disable this(this) does prevent isForwardRange!T to pass. I don't know if that changed recently or is just out of line with the documentation/specification.

On Fri, Jan 16, 2015 at 06:34:08PM +0000, Tobias Pankrath via Digitalmars-d wrote:
> On Friday, 16 January 2015 at 18:12:03 UTC, Joseph Rushton Wakeling wrote:
> >On Friday, 16 January 2015 at 17:22:42 UTC, Tobias Pankrath wrote:
> >>Ah, now I understand you. Since copy-construction is undefined for ForwardRanges, you cannot guarantee this. Things would be better, if we had required that this(this) does the same as .save or must be @disabled.
> >
> >I'm not sure I follow what you mean by this ... ?
> 
> If you pass a forward range of type T (something that passes isForwardRange!T) to a function you have no guarantees on what will happen.  It could be:
> 
>     • compilation failure
>     • reference semantics (changes are reflected outside the function
>     • value semantics (no change are reflected outside the function)

* The range is left in an inconsistent state. :-)


> The implementer of the range can choose one. Although I tried it now, and @disable this(this) does prevent isForwardRange!T to pass. I don't know if that changed recently or is just out of line with the documentation/specification.

IIRC, this is because the test checks if it's possible to assign the range to a local variable. This is quite widely used in Phobos; @disable this(this) would make the range unusable with a *lot* of Phobos algorithms. In fact, pretty much *all* wrapper algorithms that have to assign the range to a field in the wrapper range.

Besides, I think this approach doesn't really address the root of the problem, which is that the semantics of assigning a range (without using .save) is not specified by the range API. Yet code like `auto r = range;` is used all over the place in Phobos code, with various hidden assumptions about what '=' does, which may or may not correspond with reality.

Ultimately, this is also the root cause of the transient range problem: the range API did not specify the semantics of `auto x = range.front;`. It's simply assumed that this copies the value of range.front... which, in a sense, it does, but what's hidden behind the '=' can be very complex semantics that breaks the algorithm's assumptions. In this case, it breaks because when range.front is a reference to a buffer reused by popFront, this causes the unexpected result that calling popFront also changes x. Had the range API specified the expected behaviour of assigning .front to a variable, this problem would not have arisen, or at least the possible problems would have been anticipated, instead of transience coming to bite us from behind when we least expect it.


T

-- 
I think the conspiracy theorists are out to get us...

On 16/01/15 07:38, H. S. Teoh via Digitalmars-d wrote:
> I've been wondering about that. Must ranges have an "underlying"
> container? Or are they allowed to be more abstract entities that
> basically function as generators, producing data on demand? (This
> distinction is also somewhat related to transient ranges, in that the
> difference between providing a "view" of some static underlying data vs.
> computing something on-the-fly in a buffer that gets reused, could serve
> as a deciding factor on how to deal with transient ranges.)

This is almost a surprising question for me, because I've taken it for granted for so long that one of the most powerful tools they offer is lazily-generated data that is not based on underlying storage.  The examples you cite (iota, recurrence) are good examples, RNGs are another.

> In this sense, an RNG could be thought of as a complex variant of
> recurrence(), except with a far more complicated generating expression
> than what one would normally use with recurrence(). If recurrence()
> qualifies as a range (and a forward range, no less), then an RNG ought
> to qualify too.

Yes, theoretically you can envision a pseudo-RNG as being defined by a state variable, and a pure function that transforms this into a new state variable. And then those individual states can be mapped to the individual variates in different ways, depending on the type of variate you want to generate.

The practical range implementation obfuscates this a bit (helpfully) by encapsulating the state (which in practice we update via mutation), and implementing a particular state-to-random-variate method in .front, resulting in the desired effect of a range whose elements are the individual random variates you care about.