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.
What about large lists?
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.
See Also
Tail Call
Jim Newton