プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(60)

「Land of Lisp」、末尾呼び出し最適化をやっていきます。

末尾呼び出し最適化

まず例としてリストの長さを求める関数を考えていきます。

CL-USER> (defun my-length (lst)
           (if lst
               (1+ (my-length (cdr lst)))
               0))
MY-LENGTH
CL-USER> (my-length '(1 2 3))
3
CL-USER>

簡単なよくある感じのプログラムだと思います。
しかし、このタイプの関数は非常に効率が悪いそうです。
再帰で呼び出した関数が返ってきて初めてスタックから解放されるためです。
10000個の要素があるリストに対して実行した場合、9999個スタックを積んだ後にようやく1+が実行されます。
著者のCLispはクラッシュしたそうです。流石に現代のSBCLは大丈夫だと思いますが怖いのでやめときます。

どうすればいいのか、という回答のmy-lengthの改良版がこちらになります。

CL-USER> (defun my-length (lst)
           (labels ((f (lst acc)
                      (if lst
                          (f (cdr lst) (1+ acc))
                          acc)))
             (f lst 0)))
WARNING: redefining COMMON-LISP-USER::MY-LENGTH in DEFUN
MY-LENGTH
CL-USER>

よく読みます。fというローカル関数を定義。これはlstとaccを受け取り、
lstがnilでなければlstのcdrとaccに1足したものを引数に再帰的に自分を呼び出します。
そんなに難しくないですね。

さて、ここでのポイントは、「返ってきた結果に1を足していた」改良前と違い、
「1を足した引数で再帰していること」のようです。
よって再帰した結果が返ってきた後にやることがありません。最後にやっていることは自分を呼び出すことです。
これこそ「末尾呼び出し」と呼ばれるものの正体のようです。
コンパイラは末尾呼び出しを見ると、今までの処理をスタックせずに次の処理に取りかかるそう。

Common Lispと末尾呼び出し最適化

残念なこととして、末尾呼び出し最適化はANSIの規格で要求されているわけではないので、
全ての処理系で最適化されるとは限りません。Schemeでは規格で定められているよう。羨ましい。
CLISPだと末尾呼び出し最適化を有効にするために一手間いるようですが、SBCLでは何もせずとも有効なよう。

ゲームを末尾呼び出し最適化する

まずは、ターンの終わりにサイコロを補給するadd-new-dice関数に適用してみるようです。
確かこいつは、補給できるサイコロの残りの数とかをわざわざ覚えていたはずです。そこですね。

CL-USER> (defun add-new-dice (board player spare-dice)
           (labels ((f (lst n acc)
                      (cond ((zerop n) (append (reverse acc) lst))
                            ((null lst) (reverse acc))
                            (t (let ((cur-player (caar lst))
                                     (cur-dice (cadar lst)))
                                 (if (and (eq cur-player player)
                                          (< cur-dice *max-dice*))
                                     (f (cdr lst)
                                        (1- n)
                                        (cons (list cur-player (1+ cur-dice)) acc))
                                     (f (cdr lst)
                                        n
                                        (cons (car lst) acc))))))))
             (board-array (f (coerce board 'list) spare-dice ()))))
WARNING: redefining COMMON-LISP-USER::ADD-NEW-DICE in DEFUN
ADD-NEW-DICE
CL-USER>

なかなか複雑に見えますが落ち着いて見ていきたいと思います。
本体部分では、board-arrayはリストを配列にするだけだから置いといて、
fを盤面の状態をリストにしたもの、補給可能なダイスの数、空リストを引数に呼び出しています。
fの中ではまず、補給可能なダイスが無ければaccを逆順にしたものとlstをくっつけて返します。
lstがnilならaccを逆順にしたものを返します。lstがnilってことは再帰が最後のコマまでいったということだからですね。
どちらでもなければ、今みているマスのプレイヤーとダイスの数を変数に格納します。
そして補給の条件に合っているか確認し、合っていればfに残りの盤面、「新たな」補給可能数、
accに処理が済んだマスを格納し引数とします。
再帰するとき、accに前のマスから入れていくからreverseして戻り値にしているのですね。

これで完成です。
3*3のゲームが動くかどうか確認して終わります。

CL-USER> (play-vs-computer (game-tree (gen-board) 0 0 t))
current player = a
      b-1 a-1 a-1 
    a-2 b-3 b-3 
  a-1 b-1 a-2 
choose your move:
1. 3 -> 0
2. 3 -> 7
3. 8 -> 7
3

動きました。何回かやりましたが、まともにお互いにコマが揃っていると勝てないですね。

次の章はいよいよこちらの参考書でもマクロが出てきます。楽しみです。おやすみなさい。