Итерация: dolist, dotimes, do и named let

Итеративные конструкции Common Lisp: dolist, dotimes, do и общий do*, плюс взгляд на named let в Scheme как на «настоящий» цикл.

do — общая итеративная форма Common Lisp: она объявляет переменные цикла с правилами обновления, условие завершения с возвращаемым значением и тело, выполняемое на каждом шаге.

Зачем это: явная итерация рядом с рекурсией

Хотя рекурсия в Lisp естественна, для счётных и накопительных циклов Common Lisp предлагает явные итеративные формы. Причина прагматична: они читаются как «цикл», не зависят от наличия TCO и часто эффективнее наивной рекурсии. Это та самая культурная черта CL, о которой мы говорили: язык не настаивает «всё через рекурсию», а даёт удобные циклы там, где они уместны. Освоив dolist, dotimes и do, вы покрываете подавляющее большинство итеративных нужд (а самый мощный loop мы разберём отдельно в продвинутом разделе).

Есть и более глубокая причина иметь явные циклы. Рекурсия, даже хвостовая, требует от читателя «развернуть её в голове»: понять базу, шаг, как накапливается результат. Для счётного цикла «пройди индексы от 0 до n» это лишняя когнитивная нагрузка — намерение проще выразить прямо. Хорошая инженерия — это выбор конструкции, которая яснее всего передаёт намерение: рекурсия отлично говорит «обработай структуру, повторяющую саму себя» (дерево, вложенный список), а цикл отлично говорит «повтори действие N раз» или «накопи по элементам». Поэтому зрелый код на CL свободно смешивает оба стиля, выбирая по задаче, а не по догме. В этом уроке мы учимся «итеративному» полюсу этого выбора.

dolist — обойти список

Самый частый цикл — пройтись по элементам списка. Для этого есть dolist: он связывает переменную с каждым элементом по очереди и выполняет тело (неявный progn). Необязательная третья форма в заголовке — значение, возвращаемое после цикла.

(dolist (x '(10 20 30))
  (format t "элемент: ~a~%" x))
;; печатает три строки, возвращает NIL

;; с возвращаемым значением и внешним накопителем
(let ((total 0))
  (dolist (x '(1 2 3 4) total)     ; вернёт total после цикла
    (incf total x)))               ; => 10

По умолчанию dolist возвращает nil. Если внутри встречается return, цикл прерывается и возвращает указанное значение — dolist устанавливает неявный блок nil, так что (return value) работает. Это удобно для досрочного выхода: «нашёл — верни».

dotimes — повторить N раз

Когда нужно «сделать ровно N раз» или пройти по индексам, берут dotimes. Переменная пробегает целые от 0 до N-1 включительно (N не входит), после цикла возвращается необязательное значение.

(dotimes (i 5)
  (format t "i = ~a~%" i))
;; печатает i = 0 ... i = 4, возвращает NIL

;; сумма квадратов 0..9 через накопитель
(let ((s 0))
  (dotimes (i 10 s)               ; вернёт s
    (incf s (* i i))))            ; => 285

Важно помнить границу: верхняя граница исключается. (dotimes (i n) ...) — это «n итераций», индексы 0..n-1. Это полупростая частая ошибка: ждать, что i дойдёт до n. Как и dolist, dotimes поддерживает return для досрочного выхода.

do — обобщённый цикл

do — самая общая из «классических» итеративных форм; dolist и dotimes можно считать её частными случаями. Её синтаксис поначалу пугает, но логичен. Заголовок состоит из трёх частей:

(do ((var1 init1 step1)            ; переменные: имя, начальное, как обновлять
     (var2 init2 step2))
    (end-test result-forms)        ; условие конца и что вернуть
  body-forms)                      ; тело (неявный progn), на каждом шаге

Цикл работает так: связать все переменные их начальными значениями; проверить end-test — если истинно, вычислить result-forms и вернуть последнее; иначе выполнить тело; затем одновременно обновить все переменные их step-формами и повторить с проверки. Ключевое слово — «одновременно»: все шаги вычисляются от старых значений переменных, а потом присваиваются. Это позволяет красиво менять переменные местами без временной.

;; числа Фибоначчи итеративно: a и b обновляются одновременно
(defun fib (n)
  (do ((i 0 (1+ i))
       (a 0 b)                     ; новое a = старое b
       (b 1 (+ a b)))              ; новое b = старое a + старое b
      ((= i n) a)))                ; когда i достигнет n, вернуть a

(fib 10)   ; => 55

Параллельное обновление здесь критично: a получает старое b, а b — сумму старых a и b. Если бы обновление было последовательным, a уже изменилось бы к моменту вычисления b. Для последовательного обновления существует do* — он обновляет (и инициализирует) переменные по очереди сверху вниз, что иногда нужно, когда одна переменная зависит от уже обновлённой другой.

Стоит остановиться на досрочном выходе, потому что это частая практическая нужда. Все рассмотренные циклы (dolist, dotimes, do) устанавливают неявный блок с именем nil, поэтому внутри них работает (return значение) — он немедленно прерывает цикл и делает это значение результатом всего цикла. Это идиома «нашёл — выходи»: пробегаем коллекцию, при выполнении условия возвращаем ответ, не дожидаясь конца. Без досрочного выхода пришлось бы заводить флаг и проверять его — менее ясно и медленнее.

;; найти первый элемент списка больше порога; вернуть его сразу
(defun first-above (lst threshold)
  (dolist (x lst nil)            ; если не нашли — вернётся nil
    (when (> x threshold)
      (return x))))              ; нашли — выходим из цикла с этим значением

(first-above '(1 5 3 9 2) 4)    ; => 5  (первый больше 4)
(first-above '(1 2 3) 10)       ; => NIL (ничего не нашли)

Заметьте разницу между return и result-формой заголовка. Result-форма (третий элемент заголовка dolist/dotimes) выполняется при нормальном завершении цикла — когда коллекция исчерпана. А return прерывает цикл посреди работы. Вместе они дают полный контроль: «что вернуть, если дошли до конца» и «что вернуть, если нашли раньше».

Сравнение и выбор

Named let в Scheme как цикл

В Scheme нет ни dolist, ни dotimes в ядре языка — там идиоматичный цикл строят на named let, опираясь на гарантированный TCO. Это поучительный контраст: одна конструкция Scheme заменяет целое семейство циклов CL, потому что хвостовая рекурсия в Scheme безопасна по памяти.

;; Scheme: счётный цикл через named let (аналог dotimes)
(define (sum-squares n)
  (let loop ((i 0) (s 0))
    (if (= i n)
        s
        (loop (+ i 1) (+ s (* i i))))))

(sum-squares 10)   ; => 285

;; обход списка через named let (аналог dolist)
(define (print-all lst)
  (let loop ((xs lst))
    (unless (null? xs)
      (display (car xs)) (newline)
      (loop (cdr xs)))))

Видно философское различие: Scheme минималистична и выводит итерацию из рекурсии, Common Lisp прагматична и даёт специализированные циклы под частые задачи. Оба подхода рабочие; знать стоит оба, чтобы читать чужой код на любом диалекте.

Сделаем практический вывод о выборе между всеми этими инструментами, потому что новичка обилие вариантов (dolist, dotimes, do, do*, рекурсия, а ещё loop и mapcar впереди) поначалу парализует. Эвристика проста. Если задача — «применить функцию к каждому элементу и собрать результаты», часто яснее всего не цикл, а функция высшего порядка mapcar/remove-if/reduce (они декларативны и без явного счётчика). Если нужны побочные эффекты по элементам списка — dolist. Если «повторить N раз» — dotimes. Если несколько связанных переменных-счётчиков или нестандартное условие конца — do. Если структура данных вложенная/древовидная — рекурсия. А сложные накопления с фильтрами и несколькими аккумуляторами — это территория loop (отдельный урок). Эта лесенка «от декларативного к ручному» помогает каждый раз брать минимально достаточный по сложности инструмент — признак зрелого кода.

Как работает под капотом

Итеративные формы CL — это макросы. dotimes разворачивается в do со счётчиком и сравнением; do разворачивается в комбинацию block/tagbody/go — низкоуровневых примитивов «метка + переход», которые и реализуют настоящий цикл (а не рекурсию). Поэтому циклы CL не зависят от TCO: под капотом это goto, а не вызовы функций. Именно tagbody с go — это «ассемблер управления» Lisp, и из него собраны все циклические макросы. Знание этого помогает понять, почему циклы CL работают в постоянной памяти стека независимо от реализации: они вообще не используют стек вызовов для повторения.

Любопытно, что tagbody и go — это, по сути, структурированный goto внутри Lisp, наследие очень ранних версий языка. Но в современном коде их почти никогда не пишут руками: они существуют как «целевой язык» для макросов-циклов, а не как инструмент прикладного программиста. Это ещё один пример слоистости Lisp: на дне — примитивные «метки и переходы», над ними — удобные структурные циклы (do, dotimes), а ещё выше — декларативный loop и функции высшего порядка. Прикладной код живёт на верхних слоях, но понимание дна объясняет, почему всё работает именно так и откуда берётся независимость циклов от TCO. Когда вы видите в дизассемблере или в развороте макроса tagbody с go — это и есть «настоящий цикл», в который свелась ваша красивая запись.

Частые ошибки

• Ждать, что dotimes дойдёт до N. Верхняя граница исключается: индексы 0..n-1. Чтобы включить N, считайте до (1+ n) или используйте do.
• Последовательное обновление вместо параллельного в do. do обновляет все переменные одновременно от старых значений. Если нужна зависимость от уже обновлённой — берите do*.
• Менять переменную цикла вручную в теле. В do/dotimes обновление — задача step-формы; ручной setf переменной счётчика приводит к путанице. Меняйте логику через шаг.
• Забыть, что возвращается nil. Без явной result-формы dolist/dotimes возвращают nil. Чтобы вернуть накопленное — укажите его третьим элементом заголовка.
• Искать dolist в Scheme. Его там нет; цикл — это named let (или библиотечные for-each/do).

Итоги

• dolist обходит элементы списка; dotimes повторяет N раз (индексы 0..n-1).
• do — общий цикл: переменные с правилами обновления, условие конца с результатом, тело.
• do обновляет переменные параллельно; do* — последовательно.
• Все эти формы поддерживают return для досрочного выхода и result-форму для возврата значения.
• В Scheme роль всех циклов играет named let поверх гарантированного TCO.
• Под капотом циклы CL — это tagbody/go, поэтому не зависят от стека вызовов и TCO.