【Common Lisp】do構文の使い方と考え方（状態遷移としての反復）

do は dolist や dotimes では書きにくい「複数の状態変数が互いに依存して更新される」反復に向いています
構文は let に似ており、変数定義に「次回の値」を表す更新式を付け加えた形です
loop が「何をするか」を高水準に書く構文なら、do は「状態がどう変わるか」を直接書く構文です
末尾再帰を状態変数の更新に置き換える発想と自然に対応します

1. do が向く処理

Common Lisp で繰り返しといえば、loop マクロ、dolist や dotimes、あるいは再帰が主流です¹。
do という構文はあまり見かけません。

(do ((変数1 初期値1 更新式1)
     (変数2 初期値2 更新式2)
     ...)
    (終了条件 結果式...)
  本体...)Code language: Lisp (lisp)

典型的なリスト走査や整数カウンタには dolist や dotimes の方が短く書けますし、集約には loop の collect や sum が便利です。

それでも do が力を発揮する場面があります。
「次の状態」が単純な 1+ や cdr ではなく、複数の変数が互いの値に依存して更新されるときです²。

フィボナッチ数列がその典型です。
現在の値 a と次の値 b が、互いを参照しながら進みます。

(defun fib/do (n)
  (do ((i 0 (1+ i))
       (a 0 b)
       (b 1 (+ a b)))
      ((= i n) a)))

(fib/do 10) ;=> 55Code language: Lisp (lisp)

a の次の値は b、b の次の値は (+ a b) です。
この更新が並列に行われるので、一方が更新されても他方の更新式には更新前の値が使われます。

本体が空です。
繰り返し全体が、3つの変数の初期値と更新式と終了条件だけで構成されています。

同じ計算を、素朴な再帰、末尾再帰、loop、do で書いて並べると、do の立ち位置がはっきりします。

1.1. fib/rec（素朴な再帰）

(defun fib/naive (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib/rec (- n 1))
              (fib/rec (- n 2))))))Code language: Lisp (lisp)

数学的な定義に最も近い形です。
読みやすいですが、同じ値を何度も計算するため、n が大きくなると急激に遅くなります³。

1.2. fib/accrec（末尾再帰）

(defun fib/rec (n)
  (labels ((rec (i a b)
             (cond ((= i n) a)
                   (t (rec (1+ i) b (+ a b))))))
    (rec 0 0 1)))Code language: Lisp (lisp)

labels は局所関数を定義する構文で、ここでは補助関数 rec を fib/rec の内側に作っています⁴。
引数 (i a b) が状態変数で、再帰のたびに次の状態に進みます。

Common Lisp は、末尾位置の再帰呼び出しをスタックを増やさずに実行する末尾呼び出し最適化を処理系が必ず行うとは限りません。
大きな n ではスタックが積み上がる可能性があります⁵。

1.3. fib/do

末尾再帰形のfib/rec との対応を整理してみます。

(defun fib/do (n)
  (do ((i 0 (1+ i))
       (a 0 b)
       (b 1 (+ a b)))
      ((= i n) a)))Code language: Lisp (lisp)

rec の初回呼び出し (rec 0 0 1) が do の初期値になります。
rec の再帰呼び出し (rec (1+ i) b (+ a b)) が、do の各変数の更新式になります。
cond の基底ケース ((= i n) a) は、do の終了条件と返り値にそのまま対応します。

つまり、末尾再帰の構造は、do の変数定義と終了部に収まっています。
すべての状態遷移が更新式に収まったからです。

1.4. fib/loop

ちなみに、doは、より明示的にloopマクロで書き直すこともできます。

(defun fib/loop (n)
  (loop for i = 0 then (1+ i)
        for a = 0 then b
        for b = 1 then (+ a b)
        until (= i n)
        finally (return a)))Code language: Lisp (lisp)

for i = 0 then (1+ i) という書き方が、rec の引数 i と次の値 (1+ i) に対応しています⁶が、for や then などのloopキーワードが「わかりやすい」と取るか、「冗長」と考えるかは見方次第です。

2. dolist / dotimes / do / loop の位置づけ

4つの構文を専用度と汎用度の軸で見ると、dolist や dotimes から do を経て loop へ進むにつれ、汎用的になります。

dolist はリストを順に見るための構文です。

(dolist (x xs)
  (print x))Code language: Lisp (lisp)

dotimes は整数カウンタで指定回数だけ繰り返します⁷。

(dotimes (i 5)
  (print i))Code language: Lisp (lisp)

どちらも反復の形が先に決まっていて、覚えることが少なく、意図も読みやすいです⁸。

loop はさらに、collect、sum、count、maximize、minimize などの集約語彙を持ちます。

2.1. do の汎用性

do は、変数の初期値、更新式、終了条件、終了時の返り値をまとめて書く汎用的な構文です⁹。

リスト走査にも整数カウンタにも使えますが、それを do で書く理由はあまりありません。
do の出番は、複数の状態変数が絡み合う処理です。

ここで「複雑」という言葉には注意が要ります。
構文として覚えることが少ない順なら dolist や dotimes から do、loop の順ですが、コードが「処理の細部を露出する度合い」では do の方が loop collect より低水準で、手続きが多く見えます。

2.2. 条件式の読みにくさ

do の構文には読みにくい部分があります。

(do ((i 0 (1+ i))
     (a 0 b)
     (b 1 (+ a b)))
    ((= i n) a)
  body)Code language: Lisp (lisp)

変数定義 ((i 0 ...) ...) と終了条件 ((= i n) a) がどちらも二重括弧で始まるため、慣れないと「どこまでが変数定義で、どこからが終了条件か」が一瞬わかりにくいです。

終了条件の返り値を次の行に落とすと、少し見やすくなります。

(do ((i 0 (1+ i))
     (a 0 b)
     (b 1 (+ a b)))
    ((= i n)
     a))Code language: Lisp (lisp)

2.3. loop は意図、do は処理

loop は for、until、finally という語が見出しになるので、その点では読みやすいです。

do の終了条件は「真になったら終わる」なので、loop では基本的に until と対応します。

(loop for i = 0 then (1+ i)
      for a = 0 then b
      for b = 1 then (+ a b)
      until (= i n)
      finally (return a))Code language: Lisp (lisp)

ただし、loop には、もっと意図が出る書き方があります。
loop は「何をするか」の語彙を持っているからです。

集約の例を並べると差がよく見えます。

;; loop：意図が出る
(loop for x in xs
      when (evenp x)
      sum x)

;; do：状態変化が見える
(do ((rest xs (cdr rest))
     (sum 0))
    ((endp rest) sum)
  (when (evenp (car rest))
    (incf sum (car rest))))Code language: Lisp (lisp)

loop の sum は「合計する」という目的を直接書いています。
do の sum は「累積変数を用意して、条件が合えば加算する」という手続きを書いています。

どちらが読みやすいかは、処理の「意図」を見たいか「手続き」を見たいかで変わります。
loop はリストの走査、条件付きの集約、値の収集を高水準に書く構文で、do は状態遷移を明示する構文です。

3. doはステートマシン的な反復

do が特に合うのは、複数の状態変数が絡み合い、loop の集約語彙では表現しにくい状態機械的な処理です。

末尾再帰として設計した処理を、スタックを積まずに書きたいときも、do の更新式は自然な選択肢になります。
次の変換で do に書き換えられます。

;; 末尾再帰
(labels ((rec (var1 var2 ...)
           (if 終了条件
               result
               (rec 次のvar1 次のvar2 ...))))
  (rec 初期var1 初期var2 ...))

;; 対応する do
(do ((var1 初期var1 次のvar1)
     (var2 初期var2 次のvar2)
     ...)
    (終了条件 result))Code language: Lisp (lisp)

3.1. 結果変数を宣言する

doは、更新式を省略することもできます。

(do ((rest xs (cdr rest))   ; 毎回 cdr で進む
     (acc '()))             ; 更新式なし、本体で push する
    ((endp rest) (nreverse acc))
  (push (* 2 (car rest)) acc))Code language: Lisp (lisp)

acc は自動更新されず、本体で push して変化します。
let で局所変数を導入する感覚で使えます¹⁰。

3.2. do と let との類似

do の構文は let にも似ています。

let の各束縛に、更新式が1つ増え、終了条件式と返り値を付け加えた形です。

;; let
(let ((x 0)
      (y 1))
  body)

;; do
(do ((x 0 step-x)
     (y 1 step-y))
    (end-test result)
  body)Code language: Lisp (lisp)

do の変数更新は並列的で、更新式はすべて更新前の値を使って計算されます¹¹。

fib/do が正しく動くのは do の並列更新のおかげです。

(do ((a 0 b)
     (b 1 (+ a b)))
    ...)Code language: Lisp (lisp)

a の更新式 b と b の更新式 (+ a b) は、どちらも更新前の値を使います。

ちなみに、let と let* の関係と同じく、do と do* があり、逐次的に前の変数の新しい値を後の変数の更新式で参照することもできます。

Peter Seibel は Practical Common Lisp の中で、do は dolist と dotimes の土台になる汎用的なループ構文であり、loop は Lisp らしくない独自ミニ言語だと説明しています。 – Macros: Standard Control Constructs – Practical Common Lisp
CLHS では do を「任意個の反復変数を並列にステップさせながら、終了条件が真になるまで本体を繰り返す構文」と定義しています。 – CLHS: Macro DO, DO*
素朴な再帰による Fibonacci の時間計算量は O(2^n) です。fib/naive は (fib/naive 35) あたりから体感できるほど遅くなります。メモ化や反復への書き換えが実用上の対策になります。 – The Common Lisp Cookbook – Loop, iteration, mapping
CLHS では labels を「ローカルな関数束縛を確立し、その本体が相互再帰を含めた再帰呼び出しを許す特殊オペレータ」と定義しています。flet と異なり、labels では自分自身を再帰呼び出しできます。 – CLHS: Special Operator FLET, LABELS, MACROLET
ANSI Common Lisp 規格は末尾呼び出し最適化を要求しておらず、処理系依存です。SBCL はコンパイル済みコードで多くの場合 TCO を行いますが、デバッグ設定によっては無効になります。主要実装ごとの TCO 対応状況については 0branch.com の調査がまとまっています。 – Tail Call Optimisation in Common Lisp Implementations
loop の for var = init then step 構文は、初回に init を評価し、以降の反復では step を評価して変数を更新します。これが do の更新式に最も近い loop 構文です。 – The Common Lisp Cookbook – Loop, iteration, mapping
CLHS では dotimes を「count-form が 0 以下なら本体を実行しない」と定義しており、返り値として result-form を評価できます。 – CLHS: Macro DOTIMES
Practical Common Lisp では「do は強力だが、単純な用途には大げさに見える。dolist と dotimes はよくあるケースに使いやすい」と説明しています。 – Macros: Standard Control Constructs – Practical Common Lisp
CLHS は do をより原始的な block、let、loop、tagbody、psetq で説明しています。変数更新が psetq に対応することが、並列更新の根拠になっています。 – CLHS: Macro DO, DO*
Common Lisp Cookbook では do について「複数のステップ変数を明示的に制御したいとき、あるいはループ DSL より Lisp らしい括弧表現を好むときに便利」と述べています。 – The Common Lisp Cookbook – Loop, iteration, mapping
CLHS の説明では「do ではすべての step-form が評価されてから変数への代入が行われ、これは psetq による並列代入と同等である」とあります。do* では setq による逐次代入になります。 – CLHS: Macro DO, DO*