More on MAP, SOME, EVERY, etc.....

[Dan Corkill <cork%umass-cs.csnet@csnet-relay.arpa>]

As I expected, my flame about MAP, SOME, EVERY, etc. has raised some
important issues.....

First, RAM suggests that viewing a circular list as a dotted list
avoids the problem:

>    The definition of a normal list in the Lists chapter is one
> terminated by NIL.  By this definition, a circular list is a dotted
> list.  I believe that there was a decision at one point that functions
> which use lists as sequences (a superset of the sequence functions)
> are allowed to complain about dotted lists.  This is implied by the
> statement that Endp is the canonical list-end predicate.

However, the next sentence from that chapter argues that a circular
list CANNOT be a dotted list:

``A list whose cdr chain is terminated by some non-nil atom is called
a dotted list.''  Clearly, a circular list is not terminated by some
non-NIL atom (is it terminated at all?), and ENDP cannot be used to
detect a circular list.

~~ An aside --- As the CLM is unclear on whether or not a circular is
~~ is an ORDINARY or DOTTED list, I would argue that it is better
~~ viewed as an ORDINARY list.  In a sense a circular list is a list
~~ that shares structure with itself.  Unless destructive functions
~~ are applied to a circular list, it behaves identically to an
~~ infinite list.  Further supporting this position is the observation 
~~ that mapc, mapcar, etc. work with circular list arguments and 
~~ generate errors with dotted (non-circular) list arguments.

*** Back to the original complaint about MAP, SOME, EVERY, etc. ***

Under the premise that a circular list is NOT a dotted list, the 
implementation of MAP, SOME, EVERY, etc. should not care whether
or not an argument sequence is circular or not.  (It should be
up to the user to worry about the effects of any destructive
changes to an arglist.  I suggest that all the following should
be legal:

	(map 'list '+ '(1 2 3) (star 5))  => (6 7 8)

;; (defun star (&REST arglist)
;;    (nconc arglist arglist))

	(some 'char< "string" (star #\x)) => t

	(map 'array '#(2 3 4) (star 5))   => #(7 8 9)

	(replace '(1 2 3 4 5) (star -1) 
           :START1 2 :END1 4))            => (1 2 -1 -1 5)

;; Note that (replace (star -1) '(1 2 3 4 5) :start1 2 :end1 4)
;; should not be expected to produce (-1 -1 1 2 -1 ... ).  But
;; should be undefined as to what it does.


I agree with Dave Dyer that the programmer shouldn't have to know anything
about the lists passed to MAPxxx except that the shortest sequence (if a
list) is a proper list. 

I would hope that even the following would be legal:

	(map 'list '+ '(1 2 3) '(1 2 3 4 5 . 6)) => (2 4 6)


I also agree that the use of LENGTH for lists is a poor implementation
technique, and Dave's admonition against the use of LENGTH in system
functions unless all elements are guaranteed to be inspected is 
reasonable.  

In summary, I believe that implementations of MAP, SOME, EVERY, etc.
using LENGTH do not follow the semantics of the CLM and are inconsistent
with the usual behavior of the traditional list mapping functions.
I strongly suggest that it is the implementations that are incorrect
rather than ambiguity in the semantics and argue that merely changing
the descriptions to explicitly exclude circular lists greatly curtails
the utility of the sequence functions.

Dan Corkill
Cork@UMass