`sumlist_2b`

as a function that would sum lists of length 0, 1, or more. (defun sumlist_2b (numbers) (apply plus 0 0 numbers))

Unfortunately `sumlist_2b`

cannot handle extremely long lists. In this posting, I will introduce `sumlist_6`

which does not suffer from this limitation.

This posting will not introduce any new SKILL++ primitives. Instead, it will use several primitives which have been introduced in the previous several postings to implement an algorithm which you may not have seen before. If any of these are unknown or mysterious to you, please consult previous postings of *SKILL for the Skilled* or the Virtuoso on-line documentation.

`apply`

used to call a function indirectly given the function object and a list of arguments. `sstatus`

modify a status variable of the SKILL virtual machine. `optimizeTailCall`

makes function calls in tail position be stack-space neutral. `labels`

defines local function functions which may be mutually recursive `unwindProtect`

defines a clean-up procedure which is executed even if an error is triggered. #### Very long lists

If you attempt to use `sumlist_2b`

on extremely long lists it will fail. You can generate a very long list as follows:

data = (list 1.1 -2.1 2.3 -.04) (for i 1 15 data = (append data data))

This produces a list of length 131072. If you attempt to sum this list with `sumlist_2b`

you get the following error.

*Error* plus: too many arguments (at most 65535 expected, 131074 given) - (0 0 1.1 -2.1 2.3 ... ) <<< Stack Trace >>> apply(plus 0 0 numbers) sumlist_2b(data)

The error message complains about a list of length `131074`

. This is because `data`

has length `131072`

, but `sumlist_2b`

prepends two additional `0`

's to the argument list. `131072 + 2 = 131074`

.

#### An esoteric issue?

You may very well consider this an esoteric issue. And you would be right. If you are in charge of generating the data, and you know the number of elements in your list is less than `16K`

, then there is no need to worry about this corner case. I suspect very few of the readers of this blog have ever, or will ever encounter such a situation. Even with that being the case, I discuss this here in the hopes that some of the techniques may prove useful, even if the exact problem never occurs.

Another reason to present a solution to this particular problem is that in so doing we can combine several other concepts which have been discussed in the previous *SKILL for the Skilled* blog postings.

#### The applyReduce function

The following implementation of `applyReduce`

takes advantage of `(sstatus optimizeTailCall t)`

and `unwindProtect`

as seen in a previous post of *SKILL for the Skilled*.

(defun applyReduce (fun args @key (maxArgs 8192) identity) (labels ((apply_head (fun args tail) (let ((save (cdr tail))) (setcdr tail nil) (unwindProtect (apply fun args) (setcdr tail save)))) (apply_reduce (args) (let ((tail (nthcdr (sub1 maxArgs) args))) (if (cdr tail) (apply_reduce (cons (apply_head fun args tail) (cdr tail))) (apply fun args))))) (cond ((cdr args);; if args has more the two elements(let ((save_optimizeTailCall (status optimizeTailCall))) (sstatus optimizeTailCall t) (unwindProtect (apply_reduce args) (sstatus optimizeTailCall save_optimizeTailCall)))) (args;; if args has exactly one element(car args)) (t;; if args is nilidentity))))

#### How does it work?

The `applyReduce`

function above calls the given function multiple times, but each time with a maximum of `maxArgs`

number of arguments. The `maxArgs`

parameter defaults to `8192`

but you may override it to something smaller, especially to understand better how the function works.

(trace plus) (applyReduce plus '(.1 .2 .3 .4 .5 .6 .7 .8 .9 .11 .12 .13 .14 .15 .16 .17 .18 .19) ?maxArgs 5) (untrace plus)

In the trace output you can see that the `plus`

function is called several times, but never with more than 5 arguments. After the initial call, the first argument to `plus`

is the return value of the previous call.

||||||||||||||(0.1 + 0.2 + 0.3 + 0.4 + 0.5) ||||||||||||||plus --> 1.5 ||||||||||||||||(1.5 + 0.6 + 0.7 + 0.8 + 0.9) ||||||||||||||||plus --> 4.5 ||||||||||||||||||(4.5 + 0.11 + 0.12 + 0.13 + 0.14) ||||||||||||||||||plus --> 5.0 ||||||||||||||||||||(5.0 + 0.15 + 0.16 + 0.17 + 0.18) ||||||||||||||||||||plus --> 5.66 ||||||||||||||||||(5.66 + 0.19) ||||||||||||||||||plus --> 5.85

Now we can use `applyReduce`

to create an efficient `sumlist_6`

function which is able to add up the elements of an arbitrarily long list. We can use `sumlist_6`

to add up the 131072 elements of the list `data`

created above.

(defun sumlist_6 (numbers) (applyReduce plus numbers ?identity 0))

Testing it, we can see that it works and returns the correct result. We need to test `sumlist_6`

for a very long list, as well as for the nil list and a singleton list.

(sumlist_6 data) --> 41287.68 (sumlist_6 nil) --> 0 (sumlist_6 '(42)) --> 42

#### What about the performance?

Recall the algorithm implemented as `sumlist_1a`

.

(defun sumlist_1a (numbers) (let ((sum 0)) (foreach number numbers sum = sum + number) sum))

On the Linux machine which I normally use, evaluating `(sumlist_1a data)`

takes approximately `0.02`

seconds, while evaluating `(sumlist_6 data)`

takes about `0.003`

. I.e., `sumlist_6`

is about 6 times faster for large lists.

#### Summary

The technique shown in `sumlist_2b`

is very simple, and requires very little code. Nevertheless, it has the caveat that it will fail for arbitrarily long lists. This usually does not matter, and because this corner case is relatively unlikely to occur, the technique is tempting to use, and in fact is a good solution if the data is under your control and you know the length of the list in question is not extremely large.

The technique shown in `sumlist_6`

is more correct, at the sacrifice of being more complicated code. That being said, because the complication of `sumlist_6`

is factored into the implementation of the function `applyReduce`

, the actual implementation of `sumlist_6`

is as simple as `sumlist_2b`

. I would suggest putting a copy of `applyReduce`

in your personal SKILL function library, with the appropriate customer prefix of course.

#### More to come

In upcoming posts we'll continue to survey the SKILL++ language using the example of summing a list.

Jim Newton

**Previous blog posts in this series**

SKILL for the Skilled: Many Ways to Sum a List (Part 5)

SKILL for the Skilled: Many Ways to Sum a List (Part 4)

SKILL for the Skilled: Many Ways to Sum a List (Part 3)

## Share Your Comment