On Monday, 22 January 2024 at 05:22:44 UTC, Paul Backus wrote:

Not necessarily. First, any algorithm requiring a forward range wouldn’t be implemented twice. And, most importantly, a data structure would not offer input range iteration if it can offer forward range. Why would it?

The only realistic concern I see with the proposal is algorithms being implemented requiring forward ranges when they could (also) work with basic input ranges. Overconstraining input is not specific to ranges, though.

What Jonathan never mentioned in his proposal, but something that, as far as I see, is true: One can wrap any forward range to be an input range. Heck, the pointer to any forward range is an input range, assuming there is a global next(ForwardRange*) function utilizing the forward range primitives. If you pass &forwardRange to an input range algorithm, it may copy it around as it pleases, it will change the underlying range just like an input range should; and you’d have the & for an indication that it does.

A problem I see with this is composition. Requiring the lifting to a pointer requires lvalues, and composition lives on not having those. The issue will generally be negligible, as most range algorithms returning a range will for the most part want to preserve as many of the abilities of the original range as possible. The difference in the algorithm would be that, instead of:

// implement input range
static if (/* base range is forward range */)
    // implement forward range
static if (/* base range is bidi range */
    // implement bidi range
// etc.

You would have:

static if (/* base range is input range */)
    // implement input range
else:
static if (/* base range is forward range */)
    // implement forward range
static if (/* base range is bidi range */)
    // implement bidi range
// etc.

On Monday, 22 January 2024 at 05:54:59 UTC, Ben Jones wrote:

This is off-topic, but I want to mention that the implicit it confused the hell out of me when I learned Kotlin. The feature literally saves measly 6 keystrokes for it -> , 4 if you ignore spaces. In D, map!(it => it * 2) IMO, is pretty good (e.g. compared to C++). D’s lambdas have their flaws, but lack of brevity isn’t one.

On Monday, 22 January 2024 at 17:18:56 UTC, Paul Backus wrote:

You are thinking about this the wrong way. Copyability becomes a trait of forward ranges, instead of input ranges. An input range would not be copyable, therefore code which takes input ranges would have to take them by reference, or the caller would have to ensure no other copies exist. But you can still take forward ranges this way.

It is not hard to do -- you just remove the requirement for copying from isInputRange, and add it to isForwardRange.

A T[] can be used without copying it. So why can't you pass that into an algorithm that takes an input range?

The assertion is that if the range is copyable, it's now a forward range and copying is allowed. It is on you as the range developer to ensure copying does not work if it's an input range. The algorithm that says isInputRange would have to avoid copying, but that also works for forward ranges as well. There would be no need for multiple colors.

Now, in practical terms, algorithms that are input-range compatible likely would need more careful attention to avoid copies than they currently do.

-Steve

On Tuesday, 23 January 2024 at 17:25:47 UTC, Steven Schveighoffer wrote:

The only problem with this is that what you are asking the range developer to do is impossible. :)

Consider what would happen if the user creates a pointer to a non-copyable input range. The pointer (a) is inherently copyable and (b) implements the range interface (via implicit dereferencing), but (c) the copies are not independent.

(If your response to this is "ok, we'll just have isForwardRange explicitly reject pointers", keep in mind that this problem also applies to generic wrapper types that use alias this or opDispatch. Are we really going to tell our users that it's their fault if their code breaks because they put a range pointer inside one of these types?)

So, there has to be some other way of distinguishing forward ranges from input ranges, beyond just checking whether they can be copied. For example, by using next() for input ranges vs. head()/tail() for forward ranges. (As you pointed out earlier, reusing the empty/front/popFront API would not be a great idea.)

Once you have this other method of distinguishing input and forward ranges, requiring forward ranges to be copyable no longer implies that pure input ranges MUST be non-copyable. So we can allow "pointer-to-input-range" to be an input range itself, even though it supports copying, and nothing will break.

On Tuesday, 23 January 2024 at 18:21:47 UTC, Paul Backus wrote:

isForwardRange could require the range type to have empty, front, popFront defined. Not sure if that solves your alias this/opDispatch points. This would mean arrays would need the range methods built-in rather than using UFCS.

On Wednesday, 24 January 2024 at 12:26:43 UTC, Nick Treleaven wrote:

It could, but I don't think it's a great idea, because it would make ranges a special case. Along with all of the usual reasons special cases are bad, ranges are one of the first things new D programmers are going to encounter, and are pretty much the canonical example of introspection and structural typing in D. If we make ranges behave differently, users who learn from them are going to have a much harder time understanding every other use of introspection.

On Tuesday, 23 January 2024 at 18:21:47 UTC, Paul Backus wrote:

Wouldn't that be on the person who wrapped the type? I wouldn't expect RefCounted to care that it's wrapping a range for instance.

We could explicitly forbid pointers and classes, because you can't obviously implement value semantics using those.

Indeed, since copying is defined by default, it's more onorous to properly create an input range. But so what? Can I tell you how many times people copy an input range without realizing the consequences today? At least if it's explicit that input ranges should not be copyable, then you will be more aware of the issue as the compiler complains about it.

Yeah, I agree that if we change semantics, we have to change the naming, for the sake of all existing code. But the naming could be consistent between input/forward ranges as it is today. I'm not keen on the head/tail idea, as it seems way more clunky than I would like, and I'm not sold on the compiler making sure the x = x.tail operation is going to be efficient.

I don't know how bad it would be to deal with, it's not something I have put a lot of consideration into, but I had thought that this mechanism of preventing copying for things that shouldn't be used from multiple copies sounds like the proper way to prevent problems by default. Sometimes it's good to start with what is simple and correct, even if it's not what you want, and see if you can massage it into what makes sense.

-Steve

On Wednesday, 24 January 2024 at 16:18:11 UTC, Steven Schveighoffer wrote:

Yes, it would--which is exactly what I'd like to avoid. I don't want us to put ourselves in a position where we have to tell end users "you're holding it wrong" if they try to combine two generic library features like this.

In general, we should not make assumptions in our library code unless we are capable of enforcing them. Since we are, unfortunately, not capable of enforcing the assumption that all copyable ranges have forward-range semantics, we should not allow ourselves make it.

(Perhaps there's an opportunity for a language feature here? A unique(T) qualifier would help with this, for example.)

I agree that permitting input ranges to be copyable puts more of a burden on the authors of range algorithms. However, given that there are edge cases where the burden of preventing copies must fall on someone other than the range's author, I would rather that person be the author of the generic algorithm than the end user.

My hope is that in practice, if Phobos itself contains some prominent examples of non-copyable ranges, these bugs will be found quickly during testing. That's obviously not as good as a reliable compile-time error, but it's not nothing.

For what it's worth, I agree that in practice, most input ranges should be non-copyable. That readf bug we discussed a little while ago would never have existed if LockingTextReader had been non-copyable from the start, for example.

On Wednesday, 24 January 2024 at 17:35:32 UTC, Paul Backus wrote:

Having thought about it some more, this is a bad argument, and I withdraw it.

The entire range API is based on convention to begin with. Of course there's no enforcement mechanism!