Subject: Re: setf'able?
From: rpw3@rigden.engr.sgi.com (Rob Warnock)
Date: 1998/11/07
Newsgroups: comp.lang.lisp
Message-ID: <7217f4$5pqf4@fido.engr.sgi.com>
Barry Margolin  <barmar@bbnplanet.com> wrote:
+---------------
| One reason why REDUCE is often used in favor of APPLY is that REDUCE
| doesn't have a limit on the number of entries...
| However, in the case of APPEND, the performance impact of REDUCE can be
| severe.  A single call to APPEND should only need to traverse and copy each
| argument once, so it should be O(n).  REDUCE of APPEND, on the other hand,
| will end up being O(n^2) in both space and time...
+---------------

Sounds like there's a need for a REDUCE that takes another (keyword?) arg
to say how many things to pass at once to the function you're REDUCE'ing
the list on, sort of like the "xargs" program in Unix, where:

	% find {path}... {predicates}... -print | xargs foo

will never call try to call a single involcation of "foo" with more args
[in either number of total character count] than the system limit, even
though there may be many more than that generated by the "find".

With the equivalent refinement to REDUCE, you could pass large (but not
*too* large) "gulps" to APPEND at once. Maybe something like this:

    (reduce #'append a-really-big-list &max-args CALL-ARGUMENTS-LIMIT)

Or if you knew something about the way a specific compiler generated code,
e.g., that there was a limit on the number of args that could be passed
in regeisters, you might set "&max-args" lower:

    (reduce #'+ a-really-big-list-of-nums &max-args MAX-REGISTER-ARGS)

[The default for &max-args should of course be 2, for backwards compat.]


-Rob

-----
Rob Warnock, 8L-855		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA