namekuseijin  <namekuseijin@gmail.com> wrote:
+---------------
| "John Thingstad" <jpth...@online.no> wrote:
| > (reduce #'+ number-list)
| > This calls itself recursively on each pair of elements and then on the
| > result of the adding until all elements are merged.
| > So you create a lot of temporary data.
| > Instead you could write (loop for e in number-list summing e) which
| > creates much less temporary data.
| 
| Yeah, a shame CL doesn't enforce tail-calls optimization.
+---------------

In the case of REDUCE, the whole TCO thing is a red herring, IMHO.

What CL *really* needs here is just a small tweak to REDUCE, to add
one additional keyword argument, :MAX-ARITY, that permits REDUCE to
use a larger arity than 2 on the intermediate applications of the
function being REDUCEd. It might be defined this way:

    Function REDUCE

    Syntax:
    reduce function sequence &key key from-end start end
				  initial-value max-arity => result
    ...
    max-arity -- a designator for tha maximum number of arguments
		 to be used during each application of FUNCTION.
		 The default is 2 (also denoted by a NIL argument).
		 An argument of T denotes a value of CALL-ARGUMENTS-LIMIT.
    ...

And in the "Description:" section, change these two paragraphs:

    REDUCE uses a binary operation, FUNCTION, to combine the elements
    of sequence bounded by start and end.

    The FUNCTION must accept as arguments two elements of sequence or
    the results from combining those elements. The function must also
    be able to accept no arguments. 

to these:

    REDUCE uses an N-ary (default binary) operation, FUNCTION,
    to combine the elements of sequence bounded by start and end.

    The FUNCTION must accept as arguments MAX-ARITY elements of
    sequence or the results from combining those elements. The
    function must also be able to accept any number of arguments
    less than MAX-ARITY, including none.

With this change, (REDUCE #'+ NUMBER-LIST :MAX-ARITY T) could be
implemented *VERY* efficiently, and could even be coded by the
compiler to use whatever SIMD or vector (e.g., SSE2/3) instructions
were available on the platform.

Plus, it would improve improve portability, since the above is
almost as easy to type as (APPLY #'+ NUMBER-LIST), and would
thus discourage that latter, unsafe-for-portability practice.


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607