Home > Community > Blogs > Custom IC Design > unfinished skill for the skilled many ways to sum a list part 2
 
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 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 2, Many Ways to Sum a List

Comments(0)Filed under: Virtuoso, SKILL, Team SKILL, SKILL++, software development, summing, sum a list, Jim NewtonIn the previous posting, SKILL for the Skilled: Many Ways to Sum a List (Part 1), I showed a couple of ways to arithmetically sum up a given list of numbers. In particular, I presenting the following function definition.
(defun sumlist_1b (numbers)
  (apply plus numbers))

In this posting, (Part 2), we'll look at improving this implementation by using the apply function with more than two arguments to enable handling of short lists.

Limitations of the sublist_1b

This function, sumlist_1b, is usually able to add up the numbers in a given list. It is the fastest way I know of from SKILL++ to sum a list, and because of that it is tempting to ignore several cases where it fails.

  1. the nil list
  2. a singleton list
  3. a list whose length is longer than 65535 in length.

An attempt to sum the elements of the empty list results in the following:

(sumlist_1b nil)
*Error* plus: too few arguments (at least 2 expected, 0 given) - nil
<<< Stack Trace >>>
apply(plus numbers)
sumlist_1b(nil)

An attempt to sum the elements of a singleton list results in the following:

(sumlist_1b '(3.4))
*Error* plus: too few arguments (at least 2 expected, 1 given) - (3.4)
<<< Stack Trace >>>
apply(plus numbers)
sumlist_1b('(3.4))

It is somewhat curious but notable that the SKILL plus function is unable to be called with zero or a single argument.

Sometimes you may be able to ignore this limitation

If you are in charge of the data, for example if your program is generating the lists of numbers which you'd like to sum up, you may already know that that in your application sumlist_1b will never be called with nil, singleton lists, or extremely long lists. If that is the case there is no need to worry; sumlist_1b works just fine despite its limitation. However, you need a more robust version of this function, read on.

Try #1 to fix sumlist_1b

The first two of the above limitations can be solved in a straightforward way as special cases in the function implementation.

(defun sumlist_2a (numbers)
  (cond
    ((cdr numbers)          ; if there is more than one element
     (apply plus numbers))
    ((null numbers)         ; if zero elements
     0)
    (t                      ; a singleton list
     (car numbers))))

The sumlist_2a function contains special cases for the nil list and for a singleton list. The tests in the (cond ...) are ordered such that the most common case comes first: (cdr numbers). If the given list has more than one element, then the cdr function will return non-nil. I am assuming that this is the most common situation.

Using apply with 3 or more arguments

Rather than adding additional complexity as in sumlist_2a, there is a simpler way to extend sumlist_1b to work on nil and singleton lists.

With two arguments, the apply function, calls the designated function with the given argument list. A standard (and handy) feature of apply is that if it is given more than two arguments, the second to penultimate ones have the special meaning that they are implicitly prepended to the final one. For example:

(apply plus 1 2 3 '(4 5 6 7 8))

is equivalent to

(apply plus '(1 2 3 4 5 6 7 8))

This feature of apply is pretty common for Lisp dialects such as Common Lisp, elisp (emacs lisp), and MIT/GNU Scheme. One would naturally expect the apply function in SKILL to work the same way, and fortunately it does.

This feature of apply is of course not very interesting for lists whose contents are explicitly given, because if you can type (apply plus 1 2 3 '(4 5 6 7 8)) you can as easily type (apply plus '(1 2 3 4 5 6 7 8)). But it does allow us to rewrite the sumlist_1b function as follows.

(defun sumlist_2b (numbers)
  (apply plus 0 0 numbers))
Why does this work?

This works because prepending 0 twice to the argument list of plus assures that plus has at least two arguments. Also, zero is the arithmetic identity for addition. Arithmetically adding two zeros does not effect the sum -- neither in value nor in type.

Similar problems

Is there a way to construct a function such as sumlist_1b, sumlist_2a, or sumlist_2b which will work for other types of operations like maximization and minimization?

Using the model shown in sumlist_1b, we can implement a function that will return the maximum element of a given list, provided the list has more than one element.

(defun maxlist_2c (numbers)
  (apply max numbers))

However, maxlist_2c fails if the list has one or zero elements. If you want to be able to maximize a list even it it is nil or a singleton list, you can do something similar to sumlist_2a. The maximum element of a singleton list is the first (only) element. However, you'd have to define what you mean by the maximum element of an empty list. It does not really make sense in general because the max operation does not have an identity element. While x+0=0+x=x, there is no number, I, such that max{x,I}=max{I,x}=x. For this reason the function maxlist_2d triggers an error for the empty list.

Even though it does not make sense in general, for your particular application it very well might have a meaning; so you can change the call to error by some other code as you like.

(defun maxlist_2d (numbers)
  (cond
    ((cdr numbers)
     (apply max numbers))
    ((null numbers)
     (error "cannot find maximum of the empty list"))
    (t
     (car numbers))))

More to come

See Also

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.