Email list hosting service & mailing list manager

Improper lists Olin Shivers (29 Jun 1999 13:03 UTC)
Re: Improper lists sperber@xxxxxx (29 Jun 1999 14:09 UTC)

Improper lists Olin Shivers 29 Jun 1999 13:09 UTC

    I think that the whole idea of "robustness" (meaning don't break under
    any circumstances) is not in a Scheme tradition:

Depends on what you mean by robustness! Scheme has a great tradition of
the kind of robustness associated with "safe" languages.

    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.

What I meant by robust was "has a spec that operates on the full set of
possible input values." But let's not get hung up on a word.

    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?

Even Scheme 48's weak-sister type checker will warn of this.

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

NULL? accepts any value, and tests for (). This is straightforward.
There is no LIST? -- as you point out, it is not a useful concept.
There is PROPER-LIST?, DOTTED-LIST? and CIRCULAR-LIST?.

It's *easier* and *simpler* to define these list-processing primitives
to work on improper lists. You basically write your recursions/loops
    (if (pair? lis)
        <recursive/iterative case>
        <base case>)
instead of the common pattern
    (if (null? lis)
        <base-case>
        <recursive/iterative case>)

Notice that the common pattern makes things *harder* for a soft-typing
optimiser, since you *don't know* in the recursive/iterative case that
LIS is a pair -- you only know that it is not null. This means that the
car and cdr operations you will perform on LIS in the recursive/iterative
arm of the conditional have to be run-time type checked.

In the first pattern, the type optimiser *knows* that LIS is a pair
in the recursive/iterative arm of the IF. So pair-processing code in
that arm is properly guarded, and can be optimised to run without
run-time checks.

Let's consider a binary (APPEND x y). Here's the traditional pattern:

    (let recur ((x x))
      (if (null? x)
          y
          (cons (car x) (recur (cdr x)))))

Again, the (CAR X) and (CDR X) expressions are not guaranteed to
work. If you focus on *pairness*, they are guaranteed to work:

    (let recur ((x x))
      (if (pair? x)
          (cons (car x) (recur (cdr x)))
          y))

Now, you can focus on pairness, and still rule out improper lists by
writing this definition:

    (let recur ((x x))
      (cond ((pair? x) (cons (car x) (recur (cdr x))))
            ((null? x) y)
            (else (error ...))))

All this means, however, that we basically coded in a gratuitous
restriction to our definition that wasn't at all needed. It is not
one with the structure of the problem; we just bolted it on.

I feel it's bogus. Go with the structure of the system.
    -Olin