Email list hosting service & mailing list manager

A proposed solution to the iteration problem Daphne Preston-Kendal (01 Dec 2021 21:00 UTC)
Re: A proposed solution to the iteration problem Arthur A. Gleckler (01 Dec 2021 21:54 UTC)
Re: A proposed solution to the iteration problem Marc Nieper-Wißkirchen (02 Dec 2021 12:42 UTC)
Re: A proposed solution to the iteration problem Marc Nieper-Wißkirchen (03 Dec 2021 07:21 UTC)
Re: A proposed solution to the iteration problem Daphne Preston-Kendal (03 Dec 2021 09:16 UTC)
Re: A proposed solution to the iteration problem Marc Nieper-Wißkirchen (03 Dec 2021 12:50 UTC)
Re: A proposed solution to the iteration problem Marc Nieper-Wißkirchen (03 Dec 2021 14:56 UTC)
Re: A proposed solution to the iteration problem Daphne Preston-Kendal (04 Dec 2021 11:09 UTC)
Re: A proposed solution to the iteration problem Marc Nieper-Wißkirchen (04 Dec 2021 13:54 UTC)

Re: A proposed solution to the iteration problem Daphne Preston-Kendal 04 Dec 2021 11:09 UTC

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.

> 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.

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.

> 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?

> 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.

</bikeshed>

Daphne