Re: SRFI-1 round 3 discussion Sergei Egorov (29 Jun 1999 06:28 UTC)
Improper lists [Was: SRFI-1 round 3 discussion] sperber@xxxxxx (29 Jun 1999 07:35 UTC)
Re: Improper lists [Was: SRFI-1 round 3 discussion] Lars Thomas Hansen (29 Jun 1999 14:09 UTC)
Re: Improper lists Olin Shivers (29 Jun 1999 15:23 UTC)
Re: Improper lists Marc Feeley (29 Jun 1999 15:42 UTC)

Re: SRFI-1 round 3 discussion Sergei Egorov 29 Jun 1999 06:30 UTC

* Naming: right & left variants

I prefer FOLD and FOLD-RIGHT (and DROP / DROP-RIGHT).
FOLD-LEFT and FOLD-RIGHT are also good choices.

*IMPROPER LISTS

Olin Shivers writes:
>I try for an "accept a wide spectrum" approach to the inputs the list
>functions take, and intend to spec as many of these procedures to work on
>improper lists as possible. Procedures that work on improper lists must be
>able to treat any non-pair as a list-tail signifying the end of the list --
>that is, the empty list. E.g. a robust LENGTH function that handles
improper
>lists must be spec'd so that both of these calls return three:
>    (length '(a b c . ())) => 3 ; Proper
>    (length '(a b c . d))  => 3 ; Improper

I think that the whole idea of "robustness" (meaning don't break under
any circumstances) is not in a Scheme tradition: after all these years
spent trying to convince programmers that (car '()) is an error,
we are back to (length "abc") => 0. Since "improper list" is synonymous
to "any object" (anything or a pair = anything), we will end up with a
list library that accepts (and often produces) nonsensical data.

correct code:
(filter even? '(2 7 1 8 2))  => (2 8 2)

incorrect code, but no error is likely to be signalled, because
the list is never 'applied' (but improperness is propagated)
(filter '(2 7 1 8 2) even?) => #{procedure even?}

This "result" can be propagated further without any warning:
(length (filter '(2 7 1 8 2) even?)) => 0 ;no even numbers?

Olin Shivers writes:
>This is the simplest, most consistent spec that covers improper lists.

>The functions in the current reference implementation have this property.

>
>In this spirit, *all* of the procedures in list-lib are defined to work
>on improper lists.

The last phrase translates as follows: "*all* of the procedures in list-lib
are defined to accept *any* objects, not only lists". And still, the
"consistency"
will require to redefine NULL? and LIST? to return #t on all atoms
(actually,
LIST? should return #t on everything)...

Couple more nonsensical (but legal under this SRFI) expressions:

(length (current-input-port)) => 0
(append 1 2 3 4) => 4 ;improperness is propagated
(append "foo" "bar") => "bar"

Olin Shivers writes:
>There is a trade-off here. On one hand, widening the set of arguments
>acceptable to our utilities reduces our ability to provide error-checks
>when an improper list means an error. On the other, it widens the
>applicability of these procedures. I tilt towards the latter. Scheme
>supports improper lists; so I will support them. Were this ML, the issue
>would not arise -- tuple-trees and lists are statically distinguished by
>the type system.

My own experience (~8 years of Scheme programming) tells that
improper lists are VERY rear (probably because Scheme discouraged
their use for a long time); the only exceptions are pieces of compilers/
interpreters dealing with lambda lists. So widening the applicability
to cover improper lists (i.e. everything else) in this manner doesn't
give too much; on the other hand, it seriously affects understanding
and reasoning about Scheme code. There are other, less dramatic
ways to widen the applicability of these functions: allow them to
handle vectors, strings and other sequences. This is done nicely
in OakLisp; I don't insist that this is a good idea in general, but it
doesn't affect understanding and doesn't complicate type inference.

It is certainly true that Scheme supports improper lists; R2RS
even had a special term "proper list" and both kinds were treated
as equally important. But starting from R3RS, Scheme is moving
away from improper lists in both terminology and functionality.
Anybody can build improper and circular "lists", but I think
that corresponding functions should be named accordingly
and moved out of the *list* library. Things like IMPROPER-LIST-LENGTH
are much easier to spot in somebody else's code: you can see that
something unusual is going on there.

>
>Or, let's put it another way: CONS, CAR and CDR support improper lists,
>so we need to follow through.

This is a terminological error: CAR and CDR work on pairs, which are
neither subset or superset of lists. Nonempty lists is proper subset
of pairs; this allows us to use CAR and CDR on nonempty lists. CONS
accepts any objects and returns a pair; it has a property that if its
second argument is restricted to lists, its result will be a nonempty list.
As I mentioned before, "improper list" means "any object". CONS,
CAR and CDR do not support "any objects"; they obey rules that
are not as easy as I would like them to be, but these rules can be
used by soft-typing compiler and enforced at run time.

Regards,
Sergei