next up previous
Contents Next: Local Variables Using Up: Recursion and Iteration Previous: Another Example

Iteration Using Dotimes

Common Lisp provides several means to do iteration, including loop, do, do*, dotimes, and dolist. Comprehensiveness is not our aim here, so you are referred to Steele for information on loop, do, and do*. Here, we will discuss two simple iteration macros, dotimes and dolist.

The specification for dotimes is as follows:

        (dotimes (<counter>  <limit>  <result> ) <body> )
Counter is the name of a local variable that will be initially set to 0,then incremented each time after body is evaluated, until limit is reached; limit must, therefore, evaluate to a positive integer. Result is optional. If it is specified, then when limit is reached, it is evaluated and returned by dotimes. If it is absent, dotimes returns nil. The body of a dotimes statement is just like the body of a defun -- it may be any arbitrarily long sequence of Lisp expressions.

Here is power defined with dotimes:

         (defun power-i (x y)
            (let ((result 1))
               (dotimes (count y result)
                  (setf result (* x result)))))
For the moment, ignore the let statement here, except to note that it establishes a local variable called ``result'' whose initial value is 1. Concentrate on the dotimes. What happens when the interpreter evaluates (power-i 3 4)? First x and y are set to 3 and 4, as before. Then count is intialized at 0. Since count does not equal y, the body -- (setf result (* 3 result)) -- is evaluated. Since result is initially 1, its new value is 3. Then count is incremented to 1, which is again not equal to y, so body is evaluated again. This time the existing value of result, i.e. 3, is multiplied by 3, so the new value of result is 9. As you can see, the body will be evaluated four times before count eventually is equal to 4 and the value of result is returned. (1 * 3 * 3 * 3 * 3) = 81, so the correct answer to (power 3 4) is returned.

The correct performance of power-i clearly depends on the variable ``result'' having the right initial value. If for example, result started at 0, 0 multiplied by 3, four times, would still be 0. We could define result as a global variable and set it to 1 before evaluating the dotimes. This approach is messy for two reasons. First, there is the possibility of another function using a global variable called result. If power-i changes that value, this may cause the other function to malfunction, and vice versa. Second, once power-i has returned its answer we no longer need result for anything. However, if result is a global variable it will keep on using up memory.

The proper way to handle the result variable is to treat it as a local variable, accessible only to power-i. A local variable cleanly disappears when power-i is done, so neither of the aforementioned problems arises. The let statement is what enables us to create local variables.



next up previous
Contents Next: Local Variables Using Up: Recursion and Iteration Previous: Another Example



© Colin Allen & Maneesh Dhagat
March 2007