On Saturday, 27 June 2020 at 17:16:10 UTC, Paul Backus wrote:

>> An immutable or const input range just cannot be. An input range can't not be mutable.
>> If a range itself can implement a `tail()`, it's not an input range, it's a forward range.
>
> This is false.
>
> While it is true that a pure input range cannot exist without the presence of mutable state *somewhere*, it does not follow that the mutable state must be stored in (or pointed to by) the range itself. Consider the following example:
>
>     auto fdByChar(int fd)
> ...
> Of course, there is mutable state involved here, but that state is not in the range--it's in the kernel. So the `immutable` qualifier on the range does not apply to it.

Thereby result of (input.tail == input.tail) is a coin flip? I don't think that's a sensible design.

On Saturday, 27 June 2020 at 17:30:54 UTC, Stanislav Blinov wrote:
>
> Thereby result of (input.tail == input.tail) is a coin flip? I don't think that's a sensible design.

Equality is not part of the range interface (current or proposed), so there is no guarantee that comparing two ranges with `==` will give you a useful result.

On Saturday, 27 June 2020 at 18:55:39 UTC, Paul Backus wrote:
> On Saturday, 27 June 2020 at 17:30:54 UTC, Stanislav Blinov wrote:
>>
>> Thereby result of (input.tail == input.tail) is a coin flip? I don't think that's a sensible design.
>
> Equality is not part of the range interface (current or proposed), so there is no guarantee that comparing two ranges with `==` will give you a useful result.

Equality is very much part of the struct interface though. I'll restate. What about input.tail.empty == input.tail.empty? Or input.tail.front == input.tail.front? Or, speaking of ranges, a input.tail.equal(input.tail)?..
I thought you were concerned about having to explain something to beginners ;)

If the explanation is "`tail() const` is impure, and calling it repeatedly with the same `this` produces different results, even when `this` is immutable", "WTF???" would be quite a reasonable follow-up question. This is not malloc. If we do define a `tail` primitive, it better yield the same output for the same input, meaning it would only be a primitive of forward ranges.

On Saturday, 27 June 2020 at 20:14:36 UTC, Stanislav Blinov wrote:
> Equality is very much part of the struct interface though. I'll restate. What about input.tail.empty == input.tail.empty? Or input.tail.front == input.tail.front? Or, speaking of ranges, a input.tail.equal(input.tail)?..

Does it even make _sense_ to be able to call `tail` twice on the same input range instance?

> If the explanation is "`tail() const` is impure, and calling it repeatedly with the same `this` produces different results,
> even when `this` is immutable", "WTF???" would be quite a reasonable follow-up question.

One of the problems with thinking about ranges -- and the current range API reflects this -- is that it tends to start by thinking about deterministic examples (e.g. arrays).  But while some input ranges may be deterministic in practice, it is not possible to reasonably assume "same input, same output" behaviour.  That's the whole _point_ of input ranges.

As an example: reading a stream of values from a crypto RNG, or a "true random" source measured from some ongoing physical process.

A key thing to observe there is that, immutable or no, the state of `this` doesn't give you complete information about what comes next in the sequence, and indeed the result may also depend on precisely _when_ the next element is requested (e.g. if my input range is a "true random" noise source, I'm likely to get a different value if I wait 0.1 sec to call it rather than calling it right now, even if no one else has been using that noise source).

Conceptually that doesn't fit very well with the concept of `tail`, but that's just a matter of a better name.  The real problem here isn't the indeterministic results, it's the idea that the original `this` is usable after `tail` has been called on it that is the problem.

On Sunday, 28 June 2020 at 10:42:14 UTC, Joseph Rushton Wakeling wrote:
> On Saturday, 27 June 2020 at 20:14:36 UTC, Stanislav Blinov wrote:
>> Equality is very much part of the struct interface though. I'll restate. What about input.tail.empty == input.tail.empty? Or input.tail.front == input.tail.front? Or, speaking of ranges, a input.tail.equal(input.tail)?..
>
> Does it even make _sense_ to be able to call `tail` twice on the same input range instance?

No, it does not, that's my point. "Don't do that" isn't the answer. "Can't do that" (statically disallowed, not present in the interface) is the answer.

>> If the explanation is "`tail() const` is impure, and calling it repeatedly with the same `this` produces different results,
>> even when `this` is immutable", "WTF???" would be quite a reasonable follow-up question.
>
> One of the problems with thinking about ranges -- and the current range API reflects this -- is that it tends to start by thinking about deterministic examples (e.g. arrays).

Arrays are random access ranges (which are also forward). They're not input ranges :)
The current range API incorrectly treats any range as at least an input range. If we are talking about making changes to range API - that is one of the changes that needs to be made.

> But while some input ranges may be deterministic in practice, it is not possible to reasonably assume "same input, same output" behaviour.  That's the whole _point_ of input ranges.

Yes, that is why an input range cannot be implementing `tail`. You cannot keep the original range *and* the tail. That's what forward ranges do.

> As an example: reading a stream of values from a crypto RNG, or a "true random" source measured from some ongoing physical process.
>
> A key thing to observe there is that, immutable or no, the state of `this` doesn't give you complete information about what comes next in the sequence, and indeed the result may also depend on precisely _when_ the next element is requested (e.g. if my input range is a "true random" noise source, I'm likely to get a different value if I wait 0.1 sec to call it rather than calling it right now, even if no one else has been using that noise source).

> Conceptually that doesn't fit very well with the concept of `tail`, but that's just a matter of a better name.

It isn't. It's a matter of semantics of the range. You can only consume or discard an input range. You can't fork it. Conversely, if you *can* fork a range - it's a forward range. Therefore, an input range cannot have a `tail` :)

> The real problem here isn't the indeterministic results, it's the idea that the original `this` is usable after `tail` has been called on it that is the problem.

We cannot, in the language, statically, express a "usability" of an lvalue.

On Sunday, 28 June 2020 at 11:33:39 UTC, Stanislav Blinov wrote:
>> Does it even make _sense_ to be able to call `tail` twice on the same input range instance?
>
> No, it does not, that's my point. "Don't do that" isn't the answer. "Can't do that" (statically disallowed, not present in the interface) is the answer.

Indeed.  You seem to be thinking I'm disagreeing with you, when actually we are in agreement on this point ;-)

>> One of the problems with thinking about ranges -- and the current range API reflects this -- is that it tends to start by thinking about deterministic examples (e.g. arrays).
>
> Arrays are random access ranges (which are also forward). They're not input ranges :)

That's not strictly true: one can reasonably _interpret_ an array as an input range if that's what is desired.  What makes an input range distinct is not whether the actual elements come from some impure input source (it can be deterministic under the hood, whether from iterating over array elements, or a deterministic generative mechanism like a PRNG, or whatever), but what assumptions the caller can make about how to use and interact with it.

> The current range API incorrectly treats any range as at least an input range. If we are talking about making changes to range API - that is one of the changes that needs to be made.

That doesn't really make sense to me.  Why is it not possible to interact with any other range via input range semantics?

>> But while some input ranges may be deterministic in practice, it is not possible to reasonably assume "same input, same output" behaviour.  That's the whole _point_ of input ranges.
>
> Yes, that is why an input range cannot be implementing `tail`. You cannot keep the original range *and* the tail. That's what forward ranges do.

Right, _you cannot keep the original range and the tail_.  But that doesn't block you having a method which takes the original range as input, and returns the updated range.  The issue is stopping you using the _original_ range (e.g. requiring it to be passed into the method via a move rather than by reference?).

On Sunday, 28 June 2020 at 12:43:53 UTC, Joseph Rushton Wakeling wrote:
> On Sunday, 28 June 2020 at 11:33:39 UTC, Stanislav Blinov wrote:
>>> Does it even make _sense_ to be able to call `tail` twice on the same input range instance?
>>
>> No, it does not, that's my point. "Don't do that" isn't the answer. "Can't do that" (statically disallowed, not present in the interface) is the answer.
>
> Indeed.  You seem to be thinking I'm disagreeing with you, when actually we are in agreement on this point ;-)

Ah, that wasn't evident from the question :*)

>>> One of the problems with thinking about ranges -- and the current range API reflects this -- is that it tends to start by thinking about deterministic examples (e.g. arrays).
>>
>> Arrays are random access ranges (which are also forward). They're not input ranges :)
>
> That's not strictly true: one can reasonably _interpret_ an array as an input range if that's what is desired.

That does not make arrays input ranges. They remain random-access ranges.

> What makes an input range distinct is not whether the actual elements come from some impure input source (it can be deterministic under the hood, whether from iterating over array elements, or a deterministic generative mechanism like a PRNG, or whatever), but what assumptions the caller can make about how to use and interact with it.

That would be design by convention, which I'm strongly opposed to, and arguing against. There's no need to *document* caller's assumptions when we can devise an API that drives them. What makes an input range distinct is that, unlike other kinds, it can only be consumed once - there's no need for any other assumptions. The current range API does not enforce this in any way, hence the copying conundrum and Jonathan's "don't use original after you make a copy" or other similar statements that amount to "you should know what you're doing".

>> The current range API incorrectly treats any range as at least an input range. If we are talking about making changes to range API - that is one of the changes that needs to be made.
>
> That doesn't really make sense to me.  Why is it not possible to interact with any other range via input range semantics?

Because they have different semantics! The current range API attempts to differentiate solely on interface (which can indeed appear intersecting) but not semantics. What I meant is, today in Phobos, there are algorithms that do this:

auto algo(Range)(Range range)
if (isInputRange!Range)
{
    /* ... */
    static if (isForwardRange!Range)
    {
        /* ... */
    }
}

Input ranges are treated as a subset of forward ranges. But they're not - they're distinct, non-intersecting sets. If we do change the API, the above will have to become either (depending on the algorithm):

auto algo(Range)(Range range)
if (isInputRange!Range)
{ /* ... */ }

auto algo(Range)(Range range)
if (isForwardRange!Range)
{ /* ... */ }

// OR, given a hypothetical `isSomeRange` test

auto algo(Range)(Range range)
if (isSomeRange!Range) // note: isSomeRange, not isInputRange
{
    /* use common API, if any ... */
    static if (isForwardRange!Range)
    {
        /* ... */
    }
}

> Right, _you cannot keep the original range and the tail_.  But that doesn't block you having a method which takes the original range as input, and returns the updated range.  The issue is stopping you using the _original_ range (e.g. requiring it to be passed into the method via a move rather than by reference?).

Yes, i.e. the free function implementation of `tail` that I posted previously (which would work correctly for both input ranges and forward ranges, *assuming* input ranges aren't copyable and forward ranges are).

On Saturday, 27 June 2020 at 20:14:36 UTC, Stanislav Blinov wrote:
>
> If the explanation is "`tail() const` is impure, and calling it repeatedly with the same `this` produces different results, even when `this` is immutable", "WTF???" would be quite a reasonable follow-up question. This is not malloc. If we do define a `tail` primitive, it better yield the same output for the same input, meaning it would only be a primitive of forward ranges.

It sounds like what you are really trying to say here is that input ranges and forward ranges should not use the same interface, and that input ranges should instead implement only `Option!T next()`. I agree that this would be ideal, and that if this change were made, tail() would be required only for forward ranges and up. In that case, requiring tail() to be pure would make sense.

My example was a response to the specific claim that "an immutable input range cannot exist." Specifically, it was a counterexample demonstrating that the claim is false. As I'm sure you can see, the claim is still false even if we agree to use next() instead of tail() for input ranges, since next() is obviously allowed to be impure.

On Sun, Jun 28, 2020 at 02:00:42PM +0000, Stanislav Blinov via Digitalmars-d wrote: [...]
> What makes an input range distinct is that, unlike other kinds, it can only be consumed once - there's no need for any other assumptions. The current range API does not enforce this in any way, hence the copying conundrum and Jonathan's "don't use original after you make a copy" or other similar statements that amount to "you should know what you're doing".

This is not a sufficient assumption, because there remains the question of what state a range should be in after you iterate over it partially, say, using a foreach loop:

	MyRange r = ...;
	foreach (e; r) {
		if (someCondition) break;
	}
	foreach (e; r) {
		// Do we get the remaining elements of r here, or do we
		// get all the elements from the beginning again?
	}

Even if we grant that r is a forward range, the semantics of the above code is still underspecified.

And it's not just a matter of specifying that the semantics should be; there's also the question of whether we should specify anything at all, keeping in mind that the more specific the definition, the less room there is for efficient implementation of ranges (i.e., some optimizations may be excluded if there are too many semantic requirements on ranges).


[...]
> Input ranges are treated as a subset of forward ranges. But they're not - they're distinct, non-intersecting sets.

OTOH, there is a great deal of advantage in using the subset of semantics in which input ranges *are* subsets of forward ranges, because this allows us to unify a lot of iteration logic.  Otherwise, like you say below, every algorithm will need to be duplicated, once for input ranges, once for forward ranges, which will instantly double the size of Phobos algorithms.


[...]
> auto algo(Range)(Range range)
> if (isInputRange!Range)
> { /* ... */ }
> 
> auto algo(Range)(Range range)
> if (isForwardRange!Range)
> { /* ... */ }
[...]


T

-- 
If it tastes good, it's probably bad for you.

On Sunday, 28 June 2020 at 14:12:39 UTC, Paul Backus wrote:

> It sounds like what you are really trying to say here is that input ranges and forward ranges should not use the same interface, and that input ranges should instead implement only `Option!T next()`.

Not exactly. A given forward range may also implement such a `next`. Taking your example, with a seekable file and `pread`. Which would, of course, narrow the set of "files" it would be able to work with. A forward range need not, necessarily, have a `front` and a `popFront` (see that funky List that Andrei posted a while back). We should differentiate by some other artifact. I maintain that artifact should be copyability. Or we can keep the distinction based on the presence of save(), and live forever with the ambiguous semantics and the "don't use original after copy unless you know what you're doing" convention (yuck). Are there even other options besides accepting UB?

> My example was a response to the specific claim that "an immutable input range cannot exist." Specifically, it was a counterexample demonstrating that the claim is false. As I'm sure you can see, the claim is still false even if we agree to use next() instead of tail() for input ranges, since next() is obviously allowed to be impure.

I can't see that. I don't see how you're falsifying that claim when in order to implement the range you need mutable state. "It's mutable, but the compiler can't see that, therefore it's immutable" - that is a dangerous justification. There are indeed some legitimate applications for it (allocators, mutexes), but this isn't one of them. If `a.tail` is not returning the tail of `a`, then it's either a bug in the design (shouldn't be called `tail`) or in the implementation (should not mutate *any* state).