lispcommon-lispreversesbcllist-processing

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


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?


Solution

  • 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.