do v. do*: Why does the same code produce a different result?

Question

I'm was playing around with the do macro, and I decided to write a function to reverse a list:

(defun my-reverse (my-list)
  (do ((alist my-list (cdr alist))
       (acc nil (cons (car alist) acc)))
      ((null alist) acc)
    (format t "current: ~a~%" (car alist))))

--output:--
CL-USER> (my-reverse '(10 20 30))
current: 10
current: 20
current: 30
(30 20 10)

All good so far. But I discovered that changing do to do* produced a different result:

(defun my-reverse (my-list)
  (do* ((alist my-list (cdr alist))
        (acc nil (cons (car alist) acc)))
      ((null alist) acc)
    (format t "current: ~a~%" (car alist))))

--output:--    
(CL-USER> (my-reverse '(10 20 30))
current: 10
current: 20
current: 30
(NIL 30 20)

What is the explanation for that?

Also, because (car alist) appears twice in the code, I thought I would try to initialize a variable and set it equal to (car alist) in order to simplify the code:

(defun my-reverse (my-list)
  (do* ((alist my-list (cdr alist))
        (x (car alist))
        (acc nil (cons x acc)))
      ((null alist) acc)
    (format t "current: ~a~%" x)))

--output:--
CL-USER> (my-reverse '(10 20 30))
current: 10
current: 10
current: 10
(10 10 10)

Okay, x needs a stepper:

(defun my-reverse (my-list)
  (do* ((alist my-list (cdr alist))
        (x (car alist) (car alist))
        (acc nil (cons x acc)))
      ((null alist) acc)
    (format t "current: ~a~%" x)))

--output:--
CL-USER> (my-reverse '(10 20 30))
current: 10
current: 20
current: 30
(NIL 30 20)

That didn't work either.

Next, I tried doing the accumulation in the body:

(defun my-reverse (my-list)
  (do* ((alist my-list (cdr alist))
        (x (car alist) (car alist))
        (acc nil))
      ((null alist) acc)
    ((setf acc (cons x acc))
     (format "current: ~a~%")
     ))

But, I got an "illegal function call" error for:

(setf acc (cons x acc))

Is the body allowed to change the loop variables?

Answer 1

The relation between do and do* is similar to that between let and let*: parallel assignment vs sequential.

Quoting from the hyperspec:

For do, all the step-forms are evaluated before any var is updated; the assignment of values to vars is done in parallel, as if by psetq. Because all of the step-forms are evaluated before any of the vars are altered, a step-form when evaluated always has access to the old values of all the vars, even if other step-forms precede it.

So in (cons (car alist) acc), the value of alist is the previous one, not what it's set to for this iteration.

Initially, alist is '(10 20 30), and acc is nil. In the second iteration, alist is '(20 30) and acc is '(10), and so on.

Whereas with do*,

For do*, the first step-form is evaluated, then the value is assigned to the first var, then the second step-form is evaluated, then the value is assigned to the second var, and so on; the assignment of values to variables is done sequentially, as if by setq.

so it's seeing the current version of alist, which, in the second iteration is '(20 30) (And so 20 is appended to acc) and in the last iteration is nil, and (car nil) is nil.

Answer 2

Your last try:

• a body can't have extra parentheses around it
• the format form additionally does need an output and an arg

The syntax for DO*:

1. a list of binding lists
2. a list with a test and result forms
3. then follow several statements or tags, the body

The corrected code:

(defun my-reverse (my-list)
  (do* ((list my-list      (rest list))  ; bindings
        (x    (first list) (first list)) ; bindings
        (acc  nil))                      ; bindings
       ((null list) acc)                 ; test & result
    (push x acc)                         ; body
    (format t "current: ~a~%" x)))       ; body

Note the indentation of above.

trying it:

CL-USER 1 > (my-reverse '(10 20 30))
current: 10
current: 20
current: 30
(30 20 10)

Usage

One would typically use do or do* when one needs to iterate over multiple things. This makes it necessary to understand the differences in bindings and scope -> also to test it.

For one list to iterate over, we can, for example, use dolist:

(defun my-reverse (list &aux result)
  (dolist (element list result)
    (push element result)))