Improper lists Olin Shivers (29 Jun 1999 13:09 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