Re: Generic Length (was: Closures versus objects)

> On Feb 20, 2007, at 2:49 AM, Pascal Costanza wrote:
>
> (defun length (x)
>   (typecase x
>    (null 0)
>    (cons (+ 1 (length (cdr x))))
>    (string (array-dimension x 0))))
>

    The problem with the example of length is, I think, specific to
length, but interesting in its own right.  There are two distinct and
separate ideas of length at play here, which we might call 'collection
length' and 'string length' (or more general versions of these two
ideas).  All objects that can contain other objects (including
themselves, for example) have a well-defined length, including
sometimes infinity, when they form a cycle.  String length delves into
the inner structure of a special-purpose data type.  For example, one
could define 'integer length' as the number of bits or digits in an
int, and 'byte length' as the amount of memory used by an object, but
these are not the same category as the length of a list. 
List/collection-length wise, it is appropriate to ask the length of a
string, but the answer will always be zero.  With this definition the
problem can be seen as conflating two operations into a single
generic.

    But what about the times you want to iterate over the "well known"
interpretation of the number of elements in an object, and want to use
one generic to do it?  This could still work, if you recognize that
the *initial* dispatch based on type selects the *kind* of length to
apply recursively to the rest of the object.  Then once you have
started looking at an object in terms of collection-length, it would
be a logic error to switch to string-length for the tail of the
object.  Thus a single generic would give well-defined answers for
proper lists, strings, and improper lists ending in strings.

    Note that it may not be immediately intuitive what the answer is in
the last case though: improper lists would always have the same length
as proper lists ending in 'nil'; that is, improper tails would
contribute zero to the length instead of one.  This is arguably
exactly the right thing to do, as the improper tail is arguably part
of the 'backbone' or structure of the list and not its 'payload'.  A
'cons' cell can contain one object and a rest; both 'nil' and a string
can contain zero objects and no rest, and thus are equivalent 'dead
end' nodes in the list structure as far as computing lengths is
concerned.