目的：より直感的に数列を作成する

前回遅延評価ライブラリを作って無限長数列を作成することができました。フィボナッチ数列の定義を再掲すると以下のようになっていました（Warning等の出力は省略）。

CL-USER> (defun fib (a b) (lcons (+ a b) 
                                 (fib b (+ a b))))
FIB
CL-USER> (defparameter y (lcons 0 (lcons 1 (fib 0 1))))
Y
CL-USER> (dotimes (i 10) (format t "~D " (lnth i y)))
0 1 1 2 3 5 8 13 21 34

しかし、以下のように不満な点がいくつかあります。

fib関数の定義からはどのような数列になっているかひと目でわからない
- そもそも数列を定義していることがひと目で分からない
fib関数の定義と初期値の付与が分離している
数列を定義するという目的に対して、（遅延評価）という実装手段がむき出し
- 特にlconsの使い方は直感的とは到底言いがたい

これらについてマクロを使って解消を図ろうというのがこの記事の趣旨です。…実はマクロでなく関数で十分かつ分かりやすいのでは？という疑問を作り終わってから持ちました。現状、この記事を書いているうちにリードマクロの活用を進めた結果、関数版を推してマクロ版を捨てる方向に動いてます。が、記事を書き進めていたのと、ブログの趣旨自体が思考の軌跡を書き記すことにあるので、例題だと思ってそのまま書き切ります。

試す人もいないと思いますが念のため。下記のgithubにソースを上げています。ただし、今回作ったマクロ版のmake-seriesは削除予定なので、"blog2-make-series-macro"タグをつけています。

eshamster/cl-lazy · GitHub

方針

さて、数列a_nの直感的な定義方法とは何でしょう。やはり数学の世界のものなので、数学を参考にすることにします。一つの定義方法はnに対する閉じた式で表す方法があります。偶数列 $a_{n}=2n$ は簡単な例です。といってもこれは次の書き方の特殊形として含められるので置いておきます。その書き方というのは漸化式です。フィボナッチ数列の定義は次のようになります。なお、"amp;"は無視してください。markdownでtex式を書いた場合に位置揃え用の"&"が変換される謎仕様のせいです*1。

${ \displaystyle a_{n}= \left \{ \begin{array}{l} 0 & n = 0 \\ 1 & n = 1 \\ a_{n-1} + a_{n-2} & n > 1 \end{array} \right. }$

このままLisp式に書き下す…訳にもいかないので要素を取り出すと、初期値を記述している部分（ $n = 0, 1$ )と、数列自身の若い要素との関係を記述している部分（ $n \ge 2$ )に分けることができそうです*2。そういったわけで次のようにフィボナッチ数列を定義できるmake-seriesマクロを作ったら幸せそうじゃないかと考えてみました。おおむね上記3つの課題は解決できていると見れないでしょうか。lnthが残っている点はまだ気持ち悪いですが、lconsよりは遥かにマシなので現状では目をつむります。

; イメージ
(make-series (0 1) (+ (lnth (- n 1) a) 
                      (lnth (- n 2) a)))

ついでに偶数列はこうです。

; イメージ
(make-series nil (* n 2))

llistマクロ

make-seriesマクロの実装に入る前に、遅延評価ライブラリに遅延リスト作成用マクロllistを付け加えます。直接make-seriesで使うわけではないですが、流用できる部分があるためです。

実装

まず参考にする標準のlist関数ですが、以下のように引数を再帰的にconsで包んだものと等価なリストを生成することが分かります。

CL-USER> (equalp (list 1 2 3)
                 (cons 1 (cons 2 (cons 3 nil))))
T

したがって、llistマクロの展開形は以下の様になればよいと推測できます。

CL-USER> (macroexpand-1 '(llist 1 2 3))
(LCONS 1 (LCONS 2 (LCONS 3 NIL)))

引数の個数分lconsとの組み合わせを作っているところを見るに、引数を'(1 2 3)というリストと見た再帰処理の匂いがします。マクロは再起を直接扱うことはあまり得意ではない（という認識）ので、まずは補助関数llist-bodyを作成します。

(defun llist-body (lst)
  (labels ((f (llst rest-arg)
             (if (null rest-arg)
                 llst
                 (f (cons 'lcons (list (car rest-arg) llst)) 
                    (cdr rest-arg)))))
    (f nil (reverse lst))))

これは例えばリスト'(1 2 3)を受け取ると、(lcons 3 nil)→(lcons 2 (lcons 3 nil))→(lcons 1 (lcons 2 (lcons 3 nil)))と徐々にlconsをくっつけたリストで包んでいくだけの単純な関数です。ここではlconsをただのシンボルと見てリストを作成しているわけで、こういうものを書くと「LispのプログラムはLispのデータ」を実感します。さて、このただのリストをプログラムコードとして設置する*3のがllistマクロ本体です。単純にllist-bodyで作成したリストをプログラムとして設置するだけです。

(defmacro llist (&rest rest)
  `,(llist-body rest))

マクロである必然性

蛇足ですが、llistがマクロである必要性について考えます。冒頭少し触れたようにmake-seriesがマクロであるべきか関数であるべきかは自明ではないのですが、llistの方にはマクロとして書く必然性があります。なぜか。

そもそもライブラリの目的は遅延評価です。したがってllistの引数には「後で（使うときに）評価したい式」を渡します。しかし、Common Lispを含め多くの言語の関数に共通した性質として、「引数は関数に渡す前に評価される」というものがあります。つまり、llistを関数として書いた時点で「引数を後で評価する」という目的が果たされなくなります。例えば、(llist (heavy-func 0) (heavy-func 1))などとすると、この時点でheave-funcが2つも評価されてしまいます。逆にマクロとして書いておけば、llistを呼び出した時点では各要素は「（たまたま先頭が関数シンボルである）ただのリスト」として扱われ、目的を果たすことができます*4。

make-seriesマクロ

前置きが長すぎる気もしますが本題です。まずはマクロの展開例と完成したマクロそのものとを示します。

; フィボナッチ数列の展開例（適宜整形済み）
CL-USER> (macroexpand '(make-series (0 1) (+ (lnth (- .n 1) .a)
                                             (lnth (- .n 2) .a))))
(LET ((.A NIL))
  (LABELS ((f (.N)
             (LCONS (PROGN (+ (LNTH (- .N 1) .A)
                              (LNTH (- .N 2) .A)))
                    (f (1+ .N)))))
    (SETF .A (CL-LAZY::LLIST-WITH-TAIL (f 2) 
                                       0 1))))

; （ほぼ）完成形。llist-with-tailは後ほど定義
(defmacro make-series (init-nums &body body)
  (let ((f (gensym)))
    `(let ((.a nil))
       (labels ((,f (.n) 
                  (lcons (progn ,@body) 
                         (,f (1+ .n)))))
     (setf .a (llist-with-tail (,f ,(length init-nums)) 
                                   ,@init-nums))))))

基本的に冒頭で述べたイメージの通りになっていることが分かるかと思います。

まず展開例でのmake-seriesの使い方に着目します。突然現れた".a", ".n"の2つ*5はmake-seriesマクロの中で定義を展開しているため、上記の展開例のように既知の変数として扱うことができます。いわゆるアナフォリックマクロです。アナフォリックマクロはよほど自明な場合かコンセンサスが広くとれている場合以外は避けるべきというのが基本であると思います。今回の場合、数学的な数列定義という既知の記法に紐付けているので許容可能な範囲だろうと考えました。

次に定義（defmacro）側では、大きく2つのパートに分かれています。最初に内部関数fの方を見ると、ほぼ冒頭のfib関数の定義に対応していることが分かります（計算式本体と次の要素の関数呼び出しをlconsで包んでいる）。主な違いは引数の部分で、fib関数では必要な値を直接渡していたのに対し、make-seriesマクロの方では引数として現在のインデックス.nを渡しています。またクロージャによって自身の無限長配列.aにアクセスすることができます。こうすることで、より若い要素を自由に取り出して柔軟な処理が可能になります（自身以上の要素を取ろうとすると当然アウトです…）。もちろん速度が犠牲になっていますが*6。

定義側のもう一つのパートはsetfからなる初期化の行です。初期化した無限長配列を.aにセットすることで、できあがった（できつつある）無限長配列に.aを通してアクセスできます。問題は初期化に使っているllist-with-tailマクロですが、次のような変換を行います。操作の目的は、fib関数版の(defparameter y (lcons 0 (lcons 1 (fib 0 1))))と同じく初期値の付与になります。

CL-LAZY> (macroexpand-1 '(llist-with-tail (f 2) 0 1))
(LCONS 0 (LCONS 1 (F 2)))

よく見るとllistが行っている操作と瓜二つです。違いは最後にnilが置いてあるか第一引数が置いてあるか程度です。ということなので、以下のようにllist-body関数を拡張し、これを使ってllist-with-tailマクロを作成します。

(defmacro llist-with-tail (tail &rest rest)
  `,(llist-body rest :tail tail))

(defun llist-body (lst &key (tail nil))
  ; 略：上記llist-body定義のnilをtailで書き換えただけ
   )

全体を示すと以下のようになります。アナフォリックシンボル.a, .nは必ずしも利用しない（例えば偶数列の定義では.aは不要である）ため、警告抑止のignorableをつけています。

(defmacro make-series (init-nums &body body)
  (let ((f (gensym)))
    `(let ((.a nil))
       (declare (ignorable .a))
       (labels ((,f (.n)
          (declare (ignorable .n))
          (lcons (progn ,@body) 
                         (,f (1+ .n)))))
     (setf .a (llist-with-tail (,f ,(length init-nums)) 
                                   ,@init-nums))))))

(defmacro llist-with-tail (tail &rest rest)
  `,(llist-body rest :tail tail))

(defun llist-body (lst &key (tail nil))
  (labels ((f (llst rest-arg)
         (if (null rest-arg)
         llst
         (f (cons 'lcons (list (car rest-arg) llst)) (cdr rest-arg)))))
    (f tail (reverse lst))))

最後に、念のため実行例です。

CL-USER> (defparameter y (make-series (0 1) (+ (lnth (- .n 1) .a)
                                               (lnth (- .n 2) .a))))
Y
CL-USER> (dotimes (i 10) (format t "~D " (lnth i y)))
0 1 1 2 3 5 8 13 21 34

感想

でき上がったものを見ると単純ですが、マクロに不慣れなこともありだいぶ試行錯誤しました。というより何から手を付けてよいかという糸口をつかむのに苦労しました。そんなわけで最初に動いた時は中々嬉しかったです。今回得た教訓としては以下の3つです。

一にも二にも具体例（展開前後の形）
一にも二にも具体例（展開前後の形）
可能な限り要素に分解して考える

これらは普通にプログラムを書いていても当然重要な事ではあるのですが、マクロにおいては特に意識したほうが良いと感じました。「具体例」に関して言うと、大抵のプログラムは論理と大体のイメージが納得できれば少しずつ書き進められるのですが、マクロは形から形への変換になるためか、まず明瞭で曖昧さのない例を作らないと書き始められませんでした（単純に慣れの問題もありそうですが）。次に「要素分解」について、どんなプログラムを書いても当たり前のことではあるのですが、特にマクロでは意識的に行う必要があると感じました。というのは、前提となる「具体例」の弊害として、なまじ形が見えすぎているのでつい一度に全体をつくろうと考えてしまいがちになるためです。

次回へ

次回はリードマクロの実装の話…はまだ置いておき、いい加減そもそもの目的であった「遊ぶ」方に行ってみたいと思います。具体的に言うと、リードマクロを使ってできた最終？形については形を示すにとどめて、それを使って色々な（数）列を作って遊んで見たいと思います。

シリーズリンク

*1:一応preタグで囲うという回避策があるようですが、この式より下側にコードブロックを書くと、なぜかtex式として認識されなくなる（このコードだけでなく以降のtex式すべて）という謎バグがあったので諦めました。全体的にtex式のパージングが怪しすぎます。

*2:マクロの実装自体は見捨てつつあるとはいえ、ここまでの数学的な記法を参考にするという方針自体は変わっていません

*3:まだ深い理解はできていないので、いまいちどういう動詞が適切か分からないです…

*4:llistの引数はlconsに渡されますが、lconsもマクロであるため同様です。最終的にはlazyマクロに引き渡され、lambda式で包まれて返されます

*5:ドットがついているのは、単に"a", "n"とするとパッケージからエクスポートした時に名前衝突するので泣く泣くつけただけです。ちなみに、アナフォリックなシンボルもエクスポートしないとuse-packageで見えるようにならないということは初めて知りました

*6:body内部を解析して必要な個数の値を渡すようにする…、なんてことができたら速くなりそうですが、今のところ追求する気はないです

eshamster’s diary

Common Lispで遅延評価を作って遊ぶ（2）　－数列生成マクロ

目的：より直感的に数列を作成する

方針

llistマクロ

実装

マクロである必然性

make-seriesマクロ

感想

次回へ

シリーズリンク