Re: "optimizations"

[Dave Dyer <DDYER@USC-ISIB.ARPA>]

    From: Dave Dyer       <DDYER@USC-ISIB.ARPA>
     There should be only ONE implementation of the mapping functions,

  From: Bernard S. Greenberg <BSG%SCRC-TENEX@MIT-MC>
  I disagree with this view fairly strongly.  Different implementations
  have different instruction sets and primitives, and what appears to
  be an optimal macro expansion for one implementation is often not so
  for another.

If a different actual implementation is better for some machine, then
the implementor is free to substitute an equivalent one,  provided
it is really equivalent.  It is exactly the desire to optimize each
implementation at the expense of "minor" incompatability that in aggregate
makes putatively compatable languages incompatable, be it Lisp of Fortran.

I don't really believe that specification by implementation is ideal,
just that it is the only reliable mechanism.  No prose specification
can capture the full subtlety of MAPCAR.  To be sure, there should be
a prose specification first, and the prose should remain the ultimate
arbiter of what is correct;  but ONE program, written to be faithful
to the spec, should be the arbiter of what is an acceptable implementation.
If two implementations of the same specification behave differently
in ways not explicitly permitted by the specification, then at least
one of them is wrong.


 The laser edition of the manual states in its description of MAP:
 
   "... The result sequence is as long as the shortest of the input sequences.
      If the FUNCTION has side effects, it can count on being called
    first with all elements numbered zero, and then on all elements
    numbered one and so on. ..."

  Now, I can see that the natural behavior when FUNCTION modifies one
of the input sequences will be quite different when the input sequence
is an array verses when it is a list;  In fact there are too many to
ennumerate.  (examples:  an array-type sequence probably has a known
length.  Is it legal to assume the length won't change?  Mapping over
a list-type sequence is "naturally" unaffected by changes to the elements
already processed, whereas array-type sequences might "naturally" skip
or repeat elements if a new element is removed or added at the beginning.)

 Confronted with this variability, the current spec is inadequate. One
extreme position to correct the spec would be to make it read:

   "Side effects which change the number of elements in a sequence
    have unpredictable effects on the execution sequence."

Which would simply define a large grey area. An opposite extreme might read

   "Side effects which change the number of elements in a sequence
    are immediately effective; The N'th call to the user's function
    will be with the elements which are N'th in the source sequences
    at the time of the call."

Which would define an explicit descipline: one quite different from
the customary MAP but possibly more appropriate for arrays.  A third
proposal might read:

    "Side effects which change the number of elements are well defined
     provided that only elements not yet encountered by the iteration
     are changed."

This would allow adding or dropping elements from the REST of the list
but not changing the part already processed.  Finally, one might have:

    "Side effects which change the number of elements in a sequence
     are immediately effective; the iteration proceeds by using the
     the successor of element used on the previous iteration"

Which corresponds to the usual definition of MAP, but might be
inconvenient for sequences implemeted by arrays.


----

I have two conclusion points.  First, that given this discovery of
a hole in the specification, we have to change the specification to
correct it, even if that is to simply mark the hole.  Second, that
given the subtle ways that reasonable implementations might vary,
there should be a standard implementation that meets the spec and
that all the implementors agree to use (or at least be compatable with).

This naturally constrains implementors freedom to choose representation
and algorithm, and will sometimes extract significant performance
penalties, but is part of the price of portability.  Implementors are
free to provide nonstandard extensions they consider to be better,
but only in upward compatable ways.

-------