Issue: SEQUENCE-FUNCTIONS-EXCLUDE-ARRAYS (Version 2)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: 30 Apr 87 16:48 PDT
    From: Masinter.pa@Xerox.COM

    fyi, this is the reaction from our local array expert...
    ...
    Date: 30 Apr 87 15:07 PDT
    From: Pedersen.pa

    ... they seem like hacks rather than a serious approach to
    the problem. ...

My guess is that it looks hackish more from a historical perspective
than it would if you just saw a new edition of the manual that didn't
refer to these as sequence functions. Surely if you were just told from
scratch that arrays were valid arguments to MAP or COUNT, you wouldn't
have thought it even remotely hackish. You'd likely say: "Of course."

I think your view may be skewed by feeling like we'll still have a sequence
functions chapter that will say "Oh, by the way, as a special case, MAP
and count will treat arrays as sequences displaced to their storage."
The argument about displacement is the rationale for the argument (and
for why it won't be efficient) more than advice for how the result might
be presented in the manual.

    Pedersen: ... these proposals simply relieve the user of the very 
    minor chore of making displaced arrays for the rare instances where
    that is the natural thing to do -- no real value is added, ...

Actually, I bet some people don't ever used displaced-arrays because
they seem like excess hair and/or because the side-effect consequences
are hard to learn about. RPLACA and RPLACD are hard to learn, but they
are taught about in lots of classes and lots of books so people
eventually catch on.  Displaced arrays may be taught in some thorough
courses and one or two advanced books, but I bet are largely overlooked.

Not to mention the fact that they inherently seem to violate an
abstraction and some people might avoid them because of some feel that
programs which use them are not clean.  On the other hand, there's
nothing even remotely unclean about using an operator like MAP or COUNT
on an array if that operator is willing to do the work for you. It's
not the machine instructions that count, it's what the program has to
say in order to make the machine instructions get executed that's of
interest.

    Pedersen: ... but there is a cost in complexity, ...

I'd find it easier to remember a rule saying that "SUBSTITUTE does 
top-level substitution in aggregate quantities" than one that says
"SUBSTITUTE does top-level substitution in vectors" because
"aggregate quantities" is a natural concept that I've been dealing
with for much longer than programming and "vector" is a domain 
specialized (and in this case very arbitrary) restriction on that
natural concept. I'd consider it a simplification if SUBSTITUTE worked
on arrays.

    Pedersen: ... and possibly performance. ...

I bet the performance hit is not remarkably large...
 * I'd think compilers which can optimize these function calls
   based on declarations could optimize this new case just as easily.
 * Some implementations do microcode dispatch, so they don't have to
   worry. Of the others, though, I'd bet most do a sequential type
   dispatch that falls through to an error clause. If you put the
   general array case right before the error clause, it's not costing
   anyone but the people who want it (because they have to wade through
   the other cases).
 * Even so, since it's a constant-time operation to do this algorithm
   selection and since all of these operations involve loops, the
   performance hit even if you took one would be likely to get lost
   in the dust.
 * Touretzky effectively argues that there may be a speed improvement
   because you can just check for type ARRAY and not check that it's
   only a 1d array and go straight to business playing with its 
   elements. In some cases, this can speed things up by making it
   possible to remove code that did what he is suggesting are
   "gratuitous" error checks.

    Pedersen: ... The truth is that if you really want to do 
    multi-dimensioned array manipulation, you really do want something
    like APL, or close to it. Implementing an array calculus -- like APL
    -- is quite doable ... and is the right way to go for heavy array users ...
    
Well, of course, Touretzky says outright in the proposal that he realizes
this is a harder problem and that he doubts that we would be interested 
in solving that, but that the solution to the simpler problem would be
significantly interesting to him certainly and perhaps to others (a 
claim that I think he gives a credible case for).

Moreover, the more interesting case is for people who are -not- heavy
array users. They just have one array and they're in some place where they
want to count certain elements. Having to write a routine to do this can
distract from the true purpose of the function, which may be unrelated
to the array issue.

I was recently looking back over a lot of old Maclisp code I wrote
around 1979-80. I was struck by the number of times I'd written utility
functions that got used only once -- many things that now are (fortunately)
available in the system. Getting up to a conversational level with Lisp
took most of the effort -- the programs were trivial by modern standards.
I had friends who wrote shorter (but I'd say less intelligible) programs
where they didn't take the time to abstract things out and so in the
middle of some program there'd be a couple of nested DO loops taking the
MAX of something which was not very relevant in the grand scale of things,
but which took up a lot of syntactic space.

I think it's reasonable for us to consider minor extensions that aid
this end of just making certain utilities be common so that they needn't
be written be written time and time again unnecessarily. I think this is
what Common Lisp is about.