TurtleWare

Written on 2021-10-15 by Daniel 'jackdaniel' Kochmański

In this short post I'll explain my understanding of the following quote describing the iteration construct do:

The Common Lisp do macro can be thought of as syntactic sugar for tail recursion, where the initial values for variables are the argument values on the first function call, and the step values are argument values for subsequent function calls.

-- Peter Norvig and Kent Pitman, Tutorial on Good Lisp Programming Style

Writing a recursive function usually involves three important parts:

The initial values - arguments the programmer passes to the function
The base case - a case when function may return without recurring
The step values - arguments the function passes to itself when recurring

An example of a recursive function is this (inefficient) definition:

(defun fib (n)
  (cond
    ((= n 0) 0)
    ((= n 1) 1)
    (t (+ (fib (- n 1))
          (fib (- n 2))))))

The initial value here is n, base cases are (= n 0) and (= n 1) and the step values are (- n 1) and (n 2).

To make a function tail-recursive there is one more important requirement: the subsequent function call must be in a tail position, that is it must be the last function called. The definition above is not tail-recursive, because we first need to call the function and then add results. A proper tail-recursive version requires a little gymnastic:

(defun fib* (n)
  (labels ((fib-inner (n-2 n-1 step)
             (if (= step n)
                 (+ n-2 n-1)
                 (fib-inner n-1
                            (+ n-2 n-1)
                            (1+ step)))))
    (cond
      ((= n 0) 0)
      ((= n 1) 1)
      (t (fib-inner 0 1 2)))))

The initial values are 0, 1 and 2, the base case is (= step n) and the step values are n-1, (+ n-2 n-1) and (1+ step). The function fib-inner is in tail position because there is no more computation after its invocation.

A quick remainder how do works:

(do ((a 1 (foo a))
     (b 3 (bar b)))
    ((= a b) 42)
  (side-effect! a b))

First assign to a and b the initial values 1 and 3, then check for the base case (= a b) and if true return 42, otherwise execute the body (side-effect! a b) and finally update a and b by assigning to them the step values (foo a) and (foo b). Then repeat from checking the base case. The last step could be equaled to an implicit tail-call of a function. Let's put it now in terms of the function we've defined earlier:

(defun fib** (n)
  (cond
    ((= n 0) 0)
    ((= n 1) 1)
    (t (do ((n-2 0 n-1)
            (n-1 1 (+ n-2 n-1))
            (step 2 (1+ step)))
           ((= step n)
            (+ n-2 n-1))))))

This do form is a direct translation of the function fib-inner defined earlier.

I hope that you've enjoyed this short explanation. If you did then please let me know on IRC - my handle is jackdaniel @ libera.chat.

How do you DO when you do DO?