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

Comments(2)Filed under: Virtuoso, SKILL, Team SKILL, LISP, SKILL++, summing, sumlist, Jim NewtonIn the most recent posts of SKILL for the Skilled (see previous post here) we looked at different ways to sum a given list of numbers. The goal of these articles is not really to help you sum lists better, but rather to use a simple problem to demonstrate and compare features of the SKILL++ language.

In this posting of we show yet another implementation of sumlist using an operator which will be new to many readers. While the do construct is common to many lisp dialects, particularly Scheme implementations, it is somewhat controversial as some people love it, and some people hate it. Some people find it elegant and expressive, and other find it terse and awkward. I'll present it here and let you decide for yourself.

Summing a list with the (do ...) loop

Recall the implementation of sumlist_1a which accepts a list of numbers as its argument and returns the arithmetic of these numbers.

(defun sumlist_1a (numbers)
(let ((sum 0))
(foreach number numbers
sum = sum + number)
sum))

Here is yet another implementation of the sumlist function which we've seen in the past several postings. This version of the function uses the (do ...) construct.

(defun sumlist_5a (numbers)
(do ((remaining numbers (cdr remaining))
(sum_so_far 0 (plus sum_so_far (car remaining))))
((null remaining)
sum_so_far)))

Evolution of Lisp

There is an interesting paper which is easy to find on the Internet named Evolution of Lisp by Guy Steele and Richard Gabriel. This paper chronicles many of the features of modern Lisp languages. In the paper you can see the origins of many of the features of SKILL, including the rather obscure one we are going to look at today. Although this construct was first introduced into Maclisp in 1972, Evolution of Lisp refers to it as the new-style do.

An excerpt from Evolution of Lisp:

The awful part [of do] is that it uses multiple levels of parentheses as delimiters and you have to get them right or endure strange behavior; only a diehard Lisper could love such a syntax.
Arguments over syntax aside, there is something to be said for recognizing that a loop that steps only one variable is pretty useless, in any programming language. It is almost always the case that one variable is used to generate successive values while another is used to accumulate a result. If the loop syntax steps only the generating variable, then the accumulating variable must be stepped "manually" by using assignment statements [...] or some other side effect. The multiple-variable do loop reflects an essential symmetry between generation and accumulation, allowing iteration to be expressed without explicit side effects:

Examining the example

The sumlist_5a uses do to iterate two variables remaining and sum_so_far from their respective initial values to their final values, using respective formulas to update the variables to their next values.

Breaking it down: Step by Step

As was mentioned above, the syntax of do is somewhat off-putting. There are lots of parentheses, and several interdependent components which you have to get right. The following is an itemization of the various parts of the (do ...) loop.

  1. You normally need to declare 0 or more variables: remaining and sum_so_far in this case. Two variables are specified in this case, but you may use as many as you like.
    (do ((remaining  numbers (cdr remaining))
    (sum_so_far 0 (plus sum_so_far (car remaining))))
    ((null remaining)
    sum_so_far))
  2. Specify an initial value of each variable:
    • remaining = numbers
    • sum_so_far = 0
    (do ((remaining  numbers (cdr remaining))
    (sum_so_far 0 (plus sum_so_far (car remaining))))
    ((null remaining)
    sum_so_far))
  3. Specify a termination condition. The loop continues until this expression becomes TRUE. In this case:
    • (null remaining)
    specifying to continue until the list remaining is empty.
    (do ((remaining  numbers (cdr remaining))
    (sum_so_far 0 (plus sum_so_far (car remaining))))
    ((null remaining)
    sum_so_far))
  4. If the condition is not yet TRUE, then each variable is updated as per the corresponding formula. In this case:
    • remaining = (cdr remaining)
    • sum_so_far = (plus sum_so_far (car remaining))
    (do ((remaining  numbers (cdr remaining))
    (sum_so_far 0 (plus sum_so_far (car remaining))))
    ((null remaining)
    sum_so_far))
  5. When the condition is TRUE, the loop terminates and the specified value is returned. This value is usually depends on some of the iteration variables. In this case:
    • sum_so_far
    (do ((remaining  numbers (cdr remaining))
    (sum_so_far 0 (plus sum_so_far (car remaining))))
    ((null remaining)
    sum_so_far))
  6. It is not shown above, but you may optionally include 1 or more expressions in the body of the (do ...).
    (do ((remaining  numbers (cdr remaining))
    (sum_so_far 0 (plus sum_so_far (car remaining))))
    ((null remaining)
    sum_so_far)
    (println remaining)
    (printf "partial sum = %L\n" sum_so_far))

Variations

One way to think of the SKILL do is as a mixture or generalization of several iteration constructs.

Do as for

The following is like a (for ...) loop.

(do ((i 0 i+1))
(i==100
t) ; return t because for always returns t
(println i))
... is equivalent to ...
(for i 0 100
(println i))

Do as foreach

The following is like a (foreach ...) loop.

(let ((some_list '(a b c d)))
(do ((sub some_list (cdr sub))
(item (car some_list) (cadr sub)))
((null sub)
some_list) ; return some_list because foreach returns the list it iterated over
(println item)))
... is equivalent to ...
(let ((some_list '(a b c d)))
(foreach i some_list
(println i)))

Do as a mixture of for and foreach

The (foreach ...) iterates successively through a given list of items. The (for ...) loop iterates successively through a range of integers, given the lower and upper bounds of the range. If you want to iterate one variable through a given list while simultaneously iterating another variable through a range of integers, you can use the (do ...) loop.

(let ((some_list '(a b c d ...)))
(do ((index 0 (add1 index))
(sub some_list (cdr sub))
(item (car some_list) (cadr sub)))
((null sub)
t)
(printf "The %d'th of the list is %L\n" index item)))
Which produces the following output.
The 0'th of the list is a
The 1'th of the list is b
The 2'th of the list is c
The 3'th of the list is d
The 4'th of the list is e
The 5'th of the list is f
The 6'th of the list is g

Summary

The SKILL do can be tricky to use. It allows the programmer control of several parallel iteration variables, all of which are potentially incremented according to different rules. You may also explicitly determine the return value, which is fixed and useless for other iteration constructs such as (for ...). You may also specify a series of expressions to evaluate when the iteration finishes while the iteration variables are still in scope holding their final values.

Hopefully you can use the steps above as sort of a cookbook.

More to come

In upcoming posts we'll continue to survey the SKILL++ language using the example of summing a list.

See Also

Jim Newton

Comments(2)

By Team SKILL on September 30, 2013
I recently found this reader question which was lost in my inbox.

Hello,

I discovered the "do" syntax on your latest post "skill for the skilled (part5)"

This is very interesting. But I discovered that unfortunatly, skill interpretor that is embedded with Virtuoso does not support it.

Is there any plan to support it ? Did i make a mistake trying it ?

Thanks for your feedback

Regards

Name Withheld


By Team SKILL on September 30, 2013
Glad you found the "do loop" interesting.  You'll find that it does not work in traditional SKILL, you have to use SKILL++.  So you'll need to name your file with a .ils extension, or you'll need to wrap the function definition with (inScheme ...).

Here is what happens if you try to use do directly in the CIWindow.

CIW> (inScheme (do () (t)))

t

CIW> (do () (t))

*Error* do: not supported in SKILL - do(nil (t))

<<< Stack Trace >>>


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.