Общая путаница в общей структуре Lisp

Question

Я читаю книгу «Практический общий Лисп», и в сноске 5 главы 22, стр. 284 я увидел фрагмент кода, который запутал меня.

Я знаю, что список переменных и хвост имеют общую структуру списка, но я путаю, что поскольку tail будет присваиваться значение 'new' каждый раз во время итерации, почему (setf (cdr tail) new) будет влиять на состояние списка переменных？

(do ((list nil) (tail nil) (i 0 (1+ i)))
    ((> i 10) list)
  (let ((new (cons i nil)))
    (if (null list)
        (setf list new)
        (setf (cdr tail) new))
    (setf tail new)))

;;; => (0 1 2 3 4 5 6 7 8 9 10)

Answer 1

Инвариант состоит в том, что tail всегда является последней конс-ячейкой list.

На каждой итерации создается новая ячейка cons, содержащая новое значение car. В первый раз, list устанавливается на эту ячейку cons, и tail тоже. На всех последующих итерациях к новой ячейке cons добавляется установка cdr последней ячейки, а затем установка tail для новой ячейки для воссоздания инварианта.

После первой итерации:

 [ 0 | nil ]
   ^- list
   ^- tail

После второго:

 [ 0 | -]--->[ 1 | nil ]
   ^- list     ^- tail

Третье:

 [ 0 | -]--->[ 1 | -]--->[ 2 | nil ]
   ^- list                 ^- tail

Answer 2

Форма do в вашем примере содержит указатель на хвостовые концы, чтобы сделать добавление элемента в конец списка дешевой операцией.В противном случае необходимо будет постоянно просматривать список, чтобы найти последние недостатки - например, с помощью append или nconc.Другим способом было бы собрать новые элементы в заголовке и в конце обратить список результатов.

Можно было бы ожидать, что макрос LOOP реализует что-то эффективное путем преобразования выражения цикла более высокого уровня в эффективный код.

Форма макроса

(loop for i upto 10 collect i)

может расшириться до чего-то, что внутренне похоже на ваш do пример.Преимущество loop заключается в том, что вам не нужно реализовывать логику для отслеживания хвоста, поскольку именно этот макрос должен сделать для вас.