implied contracts in the mapping functions?

[Kent M. Pitman <kmp at MIT-MC>]

    Date: Saturday, 17 September 1983, 23:08-EDT
    From: Robert A. Cassels <Cassels%SCRC-TENEX@MIT-MC>

	Date: Sat, 17 Sep 1983  21:23 EDT
	From: Scott E. Fahlman <Fahlman@CMU-CS-C.ARPA>

	I think that "it is an error" to destructively mess around with a list
	after it has been fed to MAPCAR or even to DOLIST.  The fact that most
	implementations would do this in a certain way and the user can guess
	what that way is should not matter.  If we let people twiddle hidden
	state and count on the results, there will be no safe optimizations
	left, and all Common Lisp implementations will slow down by a
	considerable factor.

    I agree that it ought to be "an error" or left undefined
    (implementation-dependent).  Other languages with looping constructs
    have run into this problem, and most have decided to admit that there is
    "hidden state" which is implementation-dependent.

I disagree. 

Arguments that other languages do x or y prove nothing. Many other languages
are just plain afraid of anything. Or they may have sufficiently different data 
structures and types that this is reasonable. I'd want concrete examples of
design criteria from specific languages before buying a follow-the-leader
argument.

Vague arguments about possible optimizations are also a bad idea. I would 
like to hear such arguments. Generally, I would like to see optimizations 
shaped by linguistic considerations, not linguistic considerations shaped
by optimizations. Certainly without specific examples of the kinds of
optimizations you want to make, how can I understand the consequences of 
those optimizations...

While programmers are prone to occassional errors in judgment, 
I think it is important to recognize systematic "errors" that they make and
ask why they make them.  For example, it was never a documented feature of
APPEND that it would copy its first N arguments, but people still used to
write (APPEND x NIL) to cause copying to happen. There is the small issue of
whether the program was going to do 
 (IF (NULL Y) X) (REALLY-APPEND X Y))
because that would screw them but that was their only `real' error. The other
assumption (that REALLY-APPEND would really copy X) was not really just
an assumption; it was pretty much forced by the contract of APPEND. So it
isn't as unsafe as it looks at first glance. Likewise, I think, for MAPCAR,
etc. The bug GSB mentioned was one where the guy lost because he let the
NCONC get too close to the point you were scanning with the map, but the 
basic theory that you could bash something farther down the line was sound.
Now in the case of (APPEND x NIL), people got smart and just made
a subroutine, COPYLIST, for what really needed to be done. But in the case of 
this NCONCing onto lists that are being mapped, I don't really think we can 
package it quite so simply...

Also, I don't think it is ever an ERROR (signalled or otherwise) for a
user to modify later structure. At worst, it should be nondeterministic with 
respect to the algorithm. I could imagine a case with mapping down a list of 
integers numbers which you are simulataneously NCONCing with new integers and 
splicing non-primes out of and using as a sieve where it might actually be 
reasonable to not worry whether the mapping operator actually noticed the 
splice. In one case, it might take slightly longer because more numbers might 
be tested than were really necessary, but in the case I'm thinking of, it 
would not and should not affect the correctness of the algorithm and the 
programmer shouldn't take grief from other programmers about how it was an
"error" to think that way.

And I really think that there may be cases where efficiency considerations
may call for me to write something which has a tail which is known
to be more than a threshold distance from the list which is being mapped. I
only think we should even say it is undefined for the programmer to try to 
modify the current cell (ie, if I am looking at the D in (A B C D), I should
not expect that NCONCing the list would matter), but I think it is reasonable 
for a programmer to assume that if he's looking at the C, that the list can be 
NCONC'd. This is important to the Lisp programmer's view of lists as 
modifiable, shared structure.  I think we should carefully define the unusual
situations, but I think it's overly restrictive to really define that 
modifying any part of the list after the part under inspection is an error...

One side light -- Any system with multi-processing is fairly likely at one
time or another to have GET going on in one process while PUTPROP is going
on in another process for the same symbol -- perhaps not for the same indicator.
We surely don't want people claiming this is erroneous and that we need to 
lock property lists since for most applications, the programmer will (at 
least should) hand-lock any cases that matter and the rest should just take 
what comes.