std.v2020.algorithm etc[ WAS: Is run.d going to be expand for runtime and the phobos library?]

[Joseph Rushton Wakeling]

On Friday, 26 June 2020 at 16:03:23 UTC, Paul Backus wrote:
> The fact that you, personally, cannot think of a use-case for 
> immutable ranges off the top of your head is not a strong 
> argument against supporting them. All language and library 
> features ought to work together unless there is a specific 
> reason for them not to (as is the case, for example, with 
> garbage collection and BetterC).
>
> So I think the burden of proof is on you here. If we're 
> designing a new range interface, is there a good reason it 
> *shouldn't* work with const and immutable?

There's no need to be combative here.  I'm not trying to argue a 
side, but to make sure we get clarity on what it means for ranges 
to be compatible with const and immutable in this way.

Whether we like it or not, pretty much all ranges currently work 
via some under-the-hood mutability, whether it's just updating 
the pointer of a slice, incrementing an internal variable, or 
reading from some external input into an internal buffer.

In some cases there are ready ways out of that.  For a forward 
range whose internal state is cheap to duplicate, there should be 
no problem just (automatically) making a mutable deep copy to 
iterate over.  If we're talking about a range that iterates over 
the contents of some memory locations, it seems natural enough 
that it should be possible to automatically create a mutable 
shallow copy that iterates over immutable memory locations 
(analogous to immutable(T[]) => immutable(T)[] and so on).

But -- for example -- what would it mean to have an input range 
as part of a const or immutable data structure?  Forget the 
strict interpretation of the current D keywords, let's just think 
conceptually for a moment.  Do we want to think of an immutable 
input range as just a source of input, with any under-the-hood 
mutability just an implementation detail that shouldn't be of 
interest to the external caller?  Do we consider it a 
contradiction in terms?

I'm inclined to agree with the suggestion that input ranges 
should either be non-copyable or have reference semantics, but I 
don't think that really resolves the issue given the 
transitiveness of const and immutable.

I also think it may be worth making a point of comparison to 
Rust's iterators.  Obviously Rust has a different approach to 
immutability than D -- the main concern is preventing multiple 
mutable references to the same piece of data -- but there is a 
very clear separation between iterators versus what they iterate 
over, and generally speaking (probably because of that 
separation) iterators themselves seem to be always implemented as 
mutable.

> One argument in favor of requiring mutability is that using 
> tail() instead of popFront() could result in a loss of 
> performance. I am working on investigating that claim using the 
> examples provided by Jon Degenhardt earlier in this thread.

FWIW my objection to `tail` was probably misplaced.  What I was 
interested in was coming from a completely different angle to the 
const/immutable concern.

Specifically, I'm interested in drawing a clear line between 
input ranges -- where it is not really a given that `front` can 
be pre-populated -- versus forward ranges.  For example, given a 
RandomSample, one arguably does not want `front` to be 
pre-determined on construction, but from the moment one starts 
consuming the range.  Given the current range API that means some 
unpleasant is-this-the-first-call special-casing under the hood 
of the `front` method.

So, what I'm interested in is whether we can reliably rework the 
input range API such that the only way to determine the next 
element is to actually fetch it.  That would also work with a 
`tail`-like approach if the function concerned would return 
something like:

     Tuple!(Option!(ElementType, None), Tail)

... but I'm not sure if that would interfere with other concerns 
about that approach (e.g. would it get in the way of optimizing 
performance of the recursive approach?).

> Another, which I find less convincing, is that writing 
> algorithms recursively instead of iteratively would be too 
> "difficult" or "onerous". If you have any more to add, I am 
> interested in hearing them.

I don't have specific examples, but it's worth noting that one of 
the plus points of D is that it tends to allow you to write any 
given code in the simplest and most natural way, rather than 
forcing you through more complicated paradigms for the sake of it.

So, I'd personally be reluctant to force all writers of ranges to 
write their code in a more complicated/virtuous way unless their 
use case specifically requires it.

With that in mind, it might be better to identify ways to 
simplify the _implementation_ of ranges that need to support 
const/immutable use cases.  That is, keep it pay-as-you-go -- you 
don't have to write ranges in a way that supports const/immutable 
if you don't have that use-case -- but if you do, the cost you 
have to pay is less.