Re: n-ary functions rfc

[Pavel Curtis <Pavel@parc.xerox.com>]

   Date:	Fri, 12 Jun 1992 13:34:59 -0700
   From:	david carlton <carlton@husc.harvard.edu>

   I forwarded a copy of the n-ary functions proposal to a friend of
   mine, and his response was (essentially) "why not just use length and
   list-ref"?  I tend to agree with him - rather than introduce new
   syntax to support another method of handling optional arguments, why
   not use the existing syntax and procedures to support that method?  I
   don't think that it would be any more tedious to use length and
   list-ref than to use the proposed method, and I would think that
   compilers would be able to optimize either way equally well - the only
   thing that I can see preventing them from optimizing the uses of
   length and list-ref is the lack of some way to guarantee that they
   haven't been redefined by the user, but in practice the Scheme
   compilers that I'm familiar with will inline standard procedures and
   at any rate once a module system is added (if one ever is...), that
   problem would go away.

Before I respond to this suggestion, let me point out that there are several
reasons why it is better to represent n-ary function arguments with a function
rather than a list, even aside from the potential for optimization:

	* Procedures are a more fundamental data type in Scheme than lists are;
	  we have special expressions for creating and using them.  Aside from
	  history, the choice of lists for the representation of extra
	  arguments seems not just arbitrary, but foolish: vectors are clearly
	  more efficient to allocate, initialize, and access, regardless of the
	  order of the accesses.

	* Procedures are immutable, making them easier to reason about than
	  lists; even if the procedure encapsulating the extra arguments
	  `escapes' to an unknown context, the reader of the program can rest
	  assured that no change in its `contents' will take place.

	* Procedures are a more flexible representation of a sequence of
	  values; they can, for example, be composed with one another to
	  compute a new, modified version of a given sequence in constant time,
	  regardless of the number of elements.  Also, the computation of the
	  elements can be done lazily, regardless of the order in which they're
	  requested.  Having the extra arguments represented as a procedure
	  makes it very convenient to use the expressive power of the FAPPLY
	  function included in my proposal.

Now, as for optimizing the use of a list holding the extra arguments, I have a
couple of points to make.

First (and I realize that this isn't what you're suggesting, David), many brash
Lisp compiler hackers have for years claimed that it should be
`straightforward' to optimize the use of CAR, CDR, and PAIR?/NULL? in dealing
with rest lists.  `All' you have to do is a little data flow analysis to
maintain extra integer index variables along with the various sublist values
floating around.  Then a use of CAR can, in theory, simply be transformed into
an operation using the corresponding index to access the value on the stack.
As far as I know, however, not a single one of these brash compiler hackers
(myself included, since I also used to make this claim) has ever succeeded in
implementing such an optimization.

Even if they had, though, my second point would stand.  (I do understand that
performing the optimization for the LENGTH/LIST-REF case is much easier.)  That
is, it isn't portable for me to write code that counts on such an optimization
being made, since surely not all compilers will do so.  But how, I hear you
ask, can my code `count' on an optimization?

Well, clearly the presence or absence of an optimization can't change the final
outcome of my program, but it certainly *can* have so great an effect on the
performance of my program as to render it useless in non-optimizing
implementations.

For example, consider this implementation of n-ary addition:

	(define (+ . args)
	  (let ((len (length args)))
	    (case len
	      ((0) 0)
	      ((1) (list-ref args 0))
	      (else
	       (do ((i 1 (bin+ i 1))
		    (sum (list-ref args 0)
			 (bin+ sum (list-ref args i))))
		   ((= i len)
		    sum))))))

Now, in an implementation that supported the optimization you're suggesting,
David, this code would probably run quite nicely and might even be worth
considering for the `official' implementation of + in that system.

If this code is ported to a different implementation, though, in which the
optimization is *not* provided, then the function performs abominably: it
conses wildly (and uselessly) and, much worse, it is no longer even *linear* in
the number of arguments (because list-ref is not a constant-time operation)!

This unavoidable kind of performance non-portability (changing not just the
constant factors in my program's running time, but the asymptotic bound) is, I
believe, unacceptable.

The major advantage of the procedural representation here is that the required
optimization for such simple cases is so incredibly easy to provide that one
has a significant chance of many implementations doing so (and even if the
optimization is *not* provided, no change in the asymptotic bound can accrue).
I don't believe that any reasonable argument can be made that many
implementations will so optimize either the CAR/CDR/NULL? or LENGTH/LIST-REF
idioms; Scheme and Lisp implementations have existed for a long time now and
nobody's seen fit to do it yet.

In summary, then, procedures are better than lists as a representation of extra
arguments because they're 
	(1) simpler in the sense of conceptual parsimony,
	(2) easier for both humans and compilers to reason about,
	(3) more flexible (especially with the addition of FAPPLY), and
	(4) much easier to optimize.
As far as I can see, the only thing lists have going for them is history.

	Pavel