[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: n-ary functions rfc
Date: Fri, 12 Jun 1992 13:34:59 -0700
From: david carlton <firstname.lastname@example.org>
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
For example, consider this implementation of n-ary addition:
(define (+ . args)
(let ((len (length args)))
((1) (list-ref args 0))
(do ((i 1 (bin+ i 1))
(sum (list-ref args 0)
(bin+ sum (list-ref args i))))
((= i len)
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
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.