In 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.
- 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))
- 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))
- Specify a termination condition. The loop continues until this expression becomes TRUE. In this case: 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))
- 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))
- 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:
(do ((remaining numbers (cdr remaining))
(sum_so_far 0 (plus sum_so_far (car remaining))))
((null remaining)
sum_so_far))
- 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