Home > Community > Blogs > Custom IC Design > unfinished skill for the skilled many ways to sum a list part 4

 Login with a Cadence account. Not a member yet? Create a permanent login account to make interactions with Cadence more conveniennt. Register | Membership benefits
 Get email delivery of the Cadence blog (individual posts).

## Email

Recipients email * (separate multiple addresses with commas)

Message *

 Send yourself a copy

## Subscribe

Intro copy of the newsletter section here, some intro copy of the newsletter. Instruction of how to subscribe to this newsletter.

First Name *

Last Name *

Email *

Company / Institution *

 Send Yourself A Copy

# SKILL for the Skilled: Part 4, Many Ways to Sum a List

Comments(0)In the previous posts 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.

One disadvantage of the type of recursive function shown in `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

You don't really need to understand how `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

The implementation of `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.