Am Sa., 4. Dez. 2021 um 12:09 Uhr schrieb Daphne Preston-Kendal <xxxxxx@nonceword.org>:
On 3 Dec 2021, at 15:56, Marc Nieper-Wißkirchen <xxxxxx@gmail.com> wrote:

> The more I think about it, the more I am convinced that it is the consumer interface of your cursor proposal that counts and not the particular implementation or particular constructors.

Yes, exactly — I came up with the idea of this interface first and then tried to work out the implementation, so the implementation is what I’d like to replace.

Great!
 
> What we really want is the stream destructor API without the uniform constructors of streams.
>
> So let's define a cursor as an object C (of a distinguished type but not necessarily disjoint) for which the following expressions make sense:
>
> (cursor-end? C)
> (cursor-head C)
> (cursor-next C)
> (cursor-next! C)
>
> [snip, see below for bikeshedding]


Though it is not a perfect analogy of the (current) stream, with the ! variant (which may not actually be guaranteed to mutate, of course, in the version of the proposal you lay out below). ‘Non-consing whenever possible’ might be a better way to describe it.

There are two ways to specify `cursor-next!`.  Either as a mutating procedure or as a linear-update procedure.  In the former case, it makes imperative programming easier but it restricts the number of possible implementations/incarnations of cursors.  In the latter case, I wouldn't say anything but allow the procedure to mutate the argument.  "Not-consing whenever possible" would not make sense in an implementation that has a fast allocator but where writing on the store is slow.
 
Not requiring cursors to be disjoint is fine by me.

> On the other hand, unlike in your current proposal, I wouldn't specify a distinguished constructor (as it would suggest a certain implementation).  Instead, let us define a number of constructors neither one more primitive than the other.

This also seems like a good approach.

We would have to write down a list of all constructors that we want to be made possible.
 
> A Scheme system can then decide to implement cursors using the most effective data structure on such a system.  One approach would be to make cursors a record that is basically just a method table for the four fundamental destructors.  Another approach, suitable for other systems, is to make SRFI 41 streams actually synonymous with cursors (after amending streams to support multiple values).  A third approach suitable for systems with fast ad-hoc overloading is to actually dispatch the destructors on different types (so that, say, `list->cursor` can actually become a no-op in such a system).

To what extent does this require generic functions/multiple dispatch? Not at all, I suppose, if the choice of what is ‘primitive’ is left up to a Scheme implementation, but let’s say I have my own list type, like a (mutable) doubly-linked list: can I define a cursor constructor for it that’ll be as efficient as if the Scheme implementation knew about it like it knows about singly-linked lists come from pairs?

In the third approach, a Scheme system could have a general cursor type plus a number of specialized cursor types (like lists, procedures acting as generators, etc.).  User-created cursor types would build on the general cursor type which doesn't have to be slower than in the first approach.
 
> I am not sure whether "cursor" is the best name because we really model streams (or potentially infinite sequences), but I'll stick to the name until someone finds a better one.
> […]
> Or, maybe, to retain compatibility with SRFI 127, they should better be called
>
> (cursor-empty? C)
> (cursor-first C)
> (cursor-rest C)
> (cursor-rest! C)
>
> but that is bike-shedding at the moment.

I’m not really happy with my names either, especially ‘cursor’ and ‘cursor-head’. (My imagined analogy was to the read head of a device that reads magnetic tape, a metaphor even I’m too young to appreciate except for music cassettes …) But neither do I like ‘first’, because it suggests the first in the sequence when it’s actually getting the *current* item in the sequence. ‘rest’ is sort of okay.

`First` makes sense when you think of the cursor not representing the original entire sequence but only an end-segment of it (which it actually does represent!).  For your metaphor to make more sense, a cursor would need to have the ability to rewind to earlier parts as well.

It's really a stream that the proposed cursors are modeling but, alas, the notion of a stream has already been taken.

Marc
 
</bikeshed>


Daphne