[cdr-discuss] What about CDR 3, then?

[Christophe Rhodes]

Pascal Costanza <pc at p-cos.net> writes:

> To be more concrete: You could regard lazy lists and streams as kinds
> of sequences, and they could indeed be made subtypes of 'sequence. In
> those cases, though, it doesn't make a lot of sense that concatenate-
> sequence supports them, for example, especially when they model
> infinite sequences (like "all prime numbers", or so).

I agree that infinite sequences aren't amenable to being termed CL
sequences, because one of the things that a CL sequence has is a
length, which must be a non-negative integer.  So, indeed, things with
infinite size aren't sequences.  But that doesn't stop all sorts of
other things from being sequences: even a class of lazy list which
knows its length (but not its elements) in advance.  I don't know how
useful one of the latter would be, I admit.

> I think a different way to say this is as the following question:
> What guarantees do the existing sequence functions give us? For
> example, do they have to terminate?

Yes, modulo the usual constraints about the resource limits of the
physical hardware that might prevent them from doing so.

> What other kinds of subtypes of sequence do you have in mind?

Briefly, off the top of my head: other sequential data structures,
such as doubly-linked lists, queues, hash-consed lists and
flexichains; then also application-specific data structures, such as
editor buffers, HTML DOM elements in a document, compiler blocks in an
intermediate representation for a program; maybe also system objects
like memory-mapped files.  I could probably go on :-)

The point of making these sequences is that then these objects can be
used as arguments to the standard CL functions: you don't have to
reimplement the whole (or even part) of the sequence library yourself;
you can simply call functions which express what you mean.  (In some
cases above, some sequence operations may not make conceptual sense --
for instance, you're unlikely to want to call SORT on compiler blocks
-- but that's not to say that the operation doesn't make sense on the
data structure itself, only on its contents when considered
semantically from the application point of view.)

I have prepared a paper discussing these and other issues (including
implementational issues) whose publication I am trying to arrange;
when I hear back from the ILC program committee about my grossly
over-the-page-limit proposal, I may be in a position to disseminate
code and documentation more widely.

Cheers,

Christophe