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 convenient.

Register | Membership benefits
Get email delivery of the Custom IC Design blog (individual posts).
 

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

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

Comments(0)Filed under: Virtuoso, Team SKILL, LISP, SKILL++, Virtuoso IC6.1.5, sum a list, Jim Newton, recursion, SKILL for the SkilledIn 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

Comments(0)

Leave a Comment


Name
E-mail (will not be published)
Comment
 I have read and agree to the Terms of use and Community Guidelines.
Community Guidelines
The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.