*SKILL for the Skilled: Many Ways to Sum a List (Parts 1, 2, and 3)*we looked at several ways to sum a given list of numbers. We ignored the cases of the given list being very long. In this post, we will examine a way to sum the elements of arbitrarily long lists using recursive functions.

The approach shown in this post (part 4) will only work in Virtuoso IC 6.1; it depends on features which are not available in IC 5.1.41 and earlier. In particular we'll look at the `optimizeTailCall`

status flag and at `unwindProtect`

.

You may read this post in either of two ways. If you would like a way to make arbitrarily deep recursion work in SKILL++, you can look at the usage of the `callWithOptimizeTailCall`

function in `sumlist_4a`

. If you'd like to know how it works, look at the section Some Trickery.

**What about large lists?**

`sumlist_3a`

(seen earlier) is that every pending call to a function in SKILL++ requires stack space, and stack space is limited. The two functions `sumlist_1a`

and `sumlist_3a`

differ in their ability to handle long lists. To demonstrate this limitation it helps to programmatically generate a very long list. The following expressions will generate a list of length 16,384.

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

Now what happens if we try to add up 16,384 numbers?

(sumlist_1a data) => 5160.96 (sumlist_3a data)*Error* sumlist_3a: Runtime Stack Overflow!!! <<< Stack Trace >>> sumlist_3a(cdr(numbers)) (car(numbers) + sumlist_3a(cdr(numbers))) if(numbers (car(numbers) + sumlist_3a(cdr(numbers))) 0) sumlist_3a(cdr(numbers)) (car(numbers) + sumlist_3a(cdr(numbers))) if(numbers (car(numbers) + sumlist_3a(cdr(numbers))) 0) sumlist_3a(cdr(numbers)) (car(numbers) + sumlist_3a(cdr(numbers))) if(numbers (car(numbers) + sumlist_3a(cdr(numbers))) 0) sumlist_3a(cdr(numbers)) ...

(sumlist_3b data)*Error* unknown: Runtime Stack Overflow!!! <<< Stack Trace >>> sum((sum_so_far + car(rest)) cdr(rest)) if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far) sum((sum_so_far + car(rest)) cdr(rest)) if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far) sum((sum_so_far + car(rest)) cdr(rest)) if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far) sum((sum_so_far + car(rest)) cdr(rest)) if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far) sum((sum_so_far + car(rest)) cdr(rest)) if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far) ...

It seems there is not enough stack space to add these numbers using the types of recursive functions we have seen up until now.

**Tail call optimization**

The subtle difference between `sumlist_3a`

and `sumlist_3b`

is not very important in the simple case, but allows for a very special optimization called *tail call optimization*. The maximum length of the list you may pass to function `sumlist_3a`

is limited by the stack-space. As seen in the stack-trace above, if the list is too long, we get the error `Runtime Stack Overflow!!!`

.

When tail call optimization is enabled, a function call in tail position does not consume additional stack space, thus allowing such a function call (even a recursive function call) to work like a `GOTO`

.

(defun callWithOptimizeTailCall (thunk) (let ((save (status optimizeTailCall))) (sstatus optimizeTailCall t) (unwindProtect (thunk) (sstatus optimizeTailCall save))))

In SKILL++, tail call optimization is a run-time switch. This means you need not do anything special when loading your code, but you have to enable the optimization at run-time. The function `callWithOptimizeTailCall`

, defined above, is written to allow the caller to specify which bit of code needs the optimization. It can be used as shown in `sumlist_4a`

defined here.

(defun sumlist_4a (numbers) (labels ((sum (sum_so_far rest) (if rest (sum (plus sum_so_far (car rest)) (cdr rest)) sum_so_far))) (callWithOptimizeTailCall (lambda () (sum 0 numbers)))))

**OK, Let's Test It**

So does it work?

(sumlist_4a data)==> 5160.96

Yippie! no stack trace. SKILL++ was able to make the recursive call 16,384 times with no problem.

Okay, let's stress test it.

(progn data = (append data data) data = (append data data) data = (append data data) (length data))==>131072

Now let's see if SKILL++ can add up a list of 131,072 numbers by a recursive function:

(sumlist_4a data)==>41287.68

Yes. No problem.

**Manipulating optimizeTailCall**

`callWithOptimizeTailCall`

works in order to use it. To use it, the one or more expressions you'd like to evaluate with the optimization enabled must be wrapped in `(lambda () ...)`

and that function of no arguments should be passed to the `callWithOptimizeTailCall`

. (callWithOptimizeTailCall (lambda ()... some code ... ... maybe some more code ...))

The promise of `callWithOptimizeTailCall`

is that it will call the given function with tail call optimization enabled, but have no lasting effect on the global `optimizeTailCall`

setting. I.e., if `optimizeTailCall`

was enabled, it will remain enabled; and if it was disabled, it will remain disabled.

**Some Trickery**

`callWithOptimizeTailCall`

uses some pretty low level trickery which some of the readers might find interesting. `status`

E.g., `(status debugMode)`

returns either

`t`

or `nil`

depending on the value of the named (unquoted) status flag. There are several other documented status flags in SKILL. Perhaps the most commonly used ones are `debugMode`

and `printinfix`

. See the Cadence on-line documentation for explanation of others. `debugMode`

Instructs the SKILL VM compiler to include additional debug information into the compiled instructions. `printinfix`

Instructs the SKILL pretty-printer whether to use infix operators (such as `+`

, `||`

, `'`

, and `->`

) and C-style function call syntax such as `(1+2+3)`

, or whether to use function names (such as `plus`

, `or`

, `quote`

, and `getq`

), and use lisp-style function call syntax such as `(plus 1 2 3)`

. `sstatus`

E.g., `(sstatus debugMode t)`

Sets the value of the named global status flag. All the flags which are available to

`status`

are available for `sstatus`

. `unwindProtect`

E.g., `(unwindProtect (unsafe_function) (deleteFile fileName))`

. This is used when calling a function or evaluating an expression which might trigger an error.

`unwindProtect`

takes two operands: an expression to evaluate, and a clean-up expression. The clean-up expression will get evaluated regardless of whether the first expression triggered an error or not. However, unlike `errset`

it does not suppress the error. In the example in `callWithOptimizeTailCall`

, the use of `unwindProtect`

assures that `(sstatus optimizeTailCall save)`

, i.e., the call to restore the `optimizeTailCall`

status occurs, even if the given function, `thunk`

triggered an error. `optimizeTailCall`

E.g., `(sstatus optimizeTailCall t)`

Controls whether tail-call optimization is enabled. Remember to always restore

`optimizeTailCall`

to its previous value so as never to globally effect this flag. **Quick Review**

In this post you saw a cookbook way of modifying a particular type of recursive function so that it does not need significant stack space at run-time. The main trick is to write the recursion using tail-call style, and use the function `callWithOptimizeTailCall`

to let SKILL++ do the work for you.

**More to come**

In the upcoming postings we'll look at even more variations of list summing.

**See Also**

Jim Newton

## Share Your Comment