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

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

Common Lispを頑張る(43)

どうも。色々一段落したので今日から完全復活して頑張っていきますぜい。
当然Common Lispです。

■漏れをふさぐ
この前実装したマクロの動作に漏れがないか確認していきます。

マクロの内部動作の細部が漏れる原因は大きく分けて3つあるそうです。
...一気に説明してくれるのかと思ったらそうではないですね。一つずつ見ていきます。

まずは現在のマクロ定義を再確認します。

CL-USER> (defmacro do-primes ((var start end) &body body)
           `(do ((,var (next-prime ,start) (next-prime (1+ ,var))))
                ((> ,var ,end))
              ,@body))
DO-PRIMES
CL-USER>

3つの原因のうち上のマクロで問題なのは、部分フォームであるendが多重評価される可能性だそう。
19とかの定数でなく、(random 100)とかをendの場所においたような時が不味いそうです。
C言語のマクロなんかでもよくあるやつですかね。

CL-USER> (macroexpand-1 '(do-primes (p 0 (random 100)) (format t "~d " p)))
(DO ((P (NEXT-PRIME 0) (NEXT-PRIME (1+ P))))
    ((> P (RANDOM 100)))
  (FORMAT T "~d " P))
T
CL-USER>

げぇ。まあそうなるのはわかるんですが笑っちゃうような形です。
毎回ランダムな数値がpと比較されるのは絶対に意図したことではないでしょう。

マクロを正しく使うためには、呼び出し側で複数回endが評価されることを意識する必要があり、
これは抽象化の漏れと言えるそう。
[endにはリテラルを入れること]と規定してもよいですが、よい対応ではないですね。

マクロを実装するときには「驚き最小の法則」を守るべきだと、いい言葉が書いてあります。
簡単に解決方法を考えるとこうなりますが...。

CL-USER> (defmacro do-primes ((var start end) &body body)
           `(do ((ending-value ,end)
                 (,var (next-prime ,start) (next-prime (1+ ,var))))
             ((> ,var ending-value))
             ,@body))
WARNING: redefining COMMON-LISP-USER::DO-PRIMES in DEFMACRO
DO-PRIMES
CL-USER>

残念ながらこれでまた漏れがでます。しかも2つ。
1つは、endとして渡した式がstartよりも先に評価されてしまうことです。
とはいえこれは2行目と3行目を入れ換えてやれば済むことです。

CL-USER> (defmacro do-primes ((var start end) &body body)
           `(do ((,var (next-prime ,start) (next-prime (1+ ,var)))
                 (ending-value ,end))
             ((> ,var ending-value))
             ,@body))
WARNING: redefining COMMON-LISP-USER::DO-PRIMES in DEFMACRO
DO-PRIMES
CL-USER>

2つ目は、変数名による漏れです。下記のような場合まともに動かないはずです。

CL-USER> (macroexpand-1 '(do-primes (ending-value 0 10) (print ending-value)))
(DO ((ENDING-VALUE (NEXT-PRIME 0) (NEXT-PRIME (1+ ENDING-VALUE)))
     (ENDING-VALUE 10))
    ((> ENDING-VALUE ENDING-VALUE))
  (PRINT ENDING-VALUE))
T
CL-USER>

ending-valueだらけですね。これは駄目です。

別の駄目パターンもあるようです。

CL-USER> (macroexpand-1 '(let ((ending-value 0))
           (do-primes (p 0 19)
             (incf ending-value p))
           ending-value))
(LET ((ENDING-VALUE 0))
  (DO-PRIMES (P 0 19)
    (INCF ENDING-VALUE P))
  ENDING-VALUE)
NIL
CL-USER>

素数の合計が欲しいようで、そんな変数にending-valueなんて名前をつけるなって感じですが、
今の問題はそこじゃないですね。
ループ内の変数が外の変数を隠してしまい、本体部分で変更されるのがマクロで展開される変数となり
無限ループです。

対策として、絶対に利用されないようなめちゃくちゃな変数名をつけるとかしか思いつきませんが、
もっといい方法があるそうで、それが関数GENSYNというものだそうです。
これは呼び出されるたびにユニークなシンボルを返すもので、
Lispの読取器に決して読み取られず、どのパッケージでもインターンされない...。
インターンってなんだっけ、と調べたらこちらにわかりやすく書いてありました。
実践Common lispを読み始めた-第21章 大規模開発に向けて:パッケージとシンボル - pattersonの日記

さて、変数名の問題を解消するためにはこうです。

CL-USER> (defmacro do-primes ((var start end) &body body)
           (let ((ending-value-name (gensym)))
             `(do ((,var (next-prime ,start) (next-prime (1+ ,var)))
                   (,ending-value-name ,end))
                  ((> ,var ,ending-value-name))
                ,@body)))
WARNING: redefining COMMON-LISP-USER::DO-PRIMES in DEFMACRO
DO-PRIMES
CL-USER> (macroexpand-1 '(do-primes (ending-value 0 10) (print ending-value)))
(DO ((ENDING-VALUE (NEXT-PRIME 0) (NEXT-PRIME (1+ ENDING-VALUE)))
     (#:G574 10))
    ((> ENDING-VALUE #:G574))
  (PRINT ENDING-VALUE))
T
CL-USER>

ending-value-nameに2回値を設定しているのでちょっと変な感じがしますが、
1回目はdoの外で変数名を与え、2回目は変数が示す値を入れているのですね。
ちょっと立ち止まれば感覚的にはわかるのですが、上手いこと他人に説明できる気がしません...。
まあ、展開形を見れば一発ですね。マクロ本体にはletは含まれていないので。
gensymがくれた変数名はマクロを呼び出すたびに変わり、同じ呼び出しの中ではふらふら変わったりしない。
それで十分です。

ちゃんと読んだらしっかりした説明がありました。「varとそんなに変わらんよ」とあります。
言われてみればその通りですね。varも何かしらの別名を与えられ、その名前で値を設定されます。
大事な違いは、「varの値はマクロフォームが読み取られたときに読取器によって作られる」
「ending-value-nameの値はマクロのコードが実行されるときにプログラムで作られる」ということ。

#:という謎の記号は、インターンされていないシンボルを表わすようです。

マクロ展開でリテラル名を絶対に使ってはいけない、という訳ではないようですが、
gensymで安全な名前を設定することに悪いことは何もないようなのでそうしたほうがよいのでしょう。

上のマクロで抽象化が漏れていた部分は全てふせげたようです。
マクロを書くことに慣れてしまえば、ちゃんと最初から漏れのないものを書けるようになるらしいです。
大まかなルールは以下。
1.特別な理由がない限り、マクロを呼び出すときに出現するのと同じ順序で評価されるように
全ての部分フォームを配置すること。
2.特別な理由がない限り、部分フォームが一度だけ評価されるようにすること。
展開形の中で引数のフォームを評価した値を保持する変数を作り、
展開形の別の場所で引数を使う必要がある場合はその変数を使うようにすること。
3.展開形の中で使う変数の名前は、マクロ展開時にGENSYMを使って作ること。

マクロを書くマクロ

マクロの仕事は関数にまつわるものだけに限りません。
マクロの仕事は「共通するシンタックス上のパターンを抽象化すること」とあります。
つまり、マクロを書くときに使うマクロだってあっていいということですね。

先程のdo-primesであったように、多くのマクロはGENSYMしたシンボルを
展開形の中で使う名前に束縛するLETから始まっているそうで、それは抽象化したいですね。
with-gensymsというマクロを説明してもらえるようです。期待。

マクロを書くマクロでも3ステップは変わらないはずです。再掲。
■マクロを書くときのステップ
1.マクロ呼び出しのサンプルを書き、その展開形を書く。あるいはその逆。
2.展開形を生成するコードを書く。
3.マクロによる抽象化に漏れがないことを確認する。

さて、まずは1です。do-primesを作るときにこう書けるようになりたい!

(defmacro do-primes ((var start end) &body body)
  (with-gensyms (ending-value-name)
                `(do ((,var (next-prime ,start) (next-prime (1+ var)))
                      (,ending-value-name ,end))
                     ((> ,var ,ending-value-name))
                   ,@body)))

そんでこれが下記のように展開されて欲しいわけです。

(defmacro do-primes ((var start end) &body body)
           (let ((ending-value-name (gensym)))
             `(do ((,var (next-prime ,start) (next-prime (1+ ,var)))
                   (,ending-value-name ,end))
                  ((> ,var ,ending-value-name))
                ,@body)))

さて...素直にいくとこんなんですね。

CL-USER> (defmacro with-gensyms (name &body body)
           `(let ((,name (gensym)))
              ,@body))
WITH-GENSYMS
CL-USER>

書きながら、「これじゃwith-gensymだな」と思いました。
というわけで本物はこちら。

CL-USER> (defmacro with-gensyms ((&rest names) &body body)
           `(let ,(loop for n in names collect `(,n (gensym)))
              ,@body))
WARNING: redefining COMMON-LISP-USER::WITH-GENSYMS in DEFMACRO
WITH-GENSYMS
CL-USER>

むむむ、本筋に関係ないところが難しい。一つずつ理解しなくては。
まずはただの知らなかった案件なのですが、(&rest names)と引数を定めることで
本体でnamesという名前のリストとして扱えるのですね。
そしてloopをアンクォートしているのがわからぬ...。これは一体。
試すしかなさそうです。

CL-USER> `(let ,(loop for n in '(a b c) collect `(,n (gensym))))
(LET ((A (GENSYM)) (B (GENSYM)) (C (GENSYM))))
CL-USER> `(let (loop for n in '(a b c) collect `(,n (gensym))))
(LET (LOOP FOR N IN (QUOTE (A B C)) COLLECT `(,N (GENSYM))))
CL-USER> `(let ,(loop for n in '(a b c) collect `(n (gensym))))
(LET ((N (GENSYM)) (N (GENSYM)) (N (GENSYM))))
CL-USER> `(let ,(loop for n in '(a b c) collect (n (gensym))))
; in:
;      SB-INT:QUASIQUOTE (LET ,(LOOP FOR N IN '(A B C)
;                                COLLECT (N (GENSYM))))
;     (N (GENSYM))
; 
; caught STYLE-WARNING:
;   undefined function: N
; 
; compilation unit finished
;   Undefined function:
;     N
;   caught 1 STYLE-WARNING condition
; Evaluation aborted on #<UNDEFINED-FUNCTION N {10049FFB63}>.
CL-USER> `(let ,(loop for n in '(a b c) collect (,n (gensym))))
; Evaluation aborted on #<SB-INT:SIMPLE-READER-ERROR "Comma not inside a backquote." {1004BCA223}>.
CL-USER> 

よし、わかってきた気がします。
展開したときに評価値が欲しい場合はその部分をアンクォートしておかねばいけないから
そうしているというだけですね。
そして一回アンクォートしてしまったら中は全部普通に評価されてしまうので、
されてほしくない場所はバッククォートすると。

さて、さっきの「こう書けるようにしたい!」コードはちゃんと動くのか。

CL-USER> (defmacro do-primes ((var start end) &body body)
  (with-gensyms (ending-value-name)
                `(do ((,var (next-prime ,start) (next-prime (1+ var)))
                      (,ending-value-name ,end))
                     ((> ,var ,ending-value-name))
                   ,@body)))
WARNING: redefining COMMON-LISP-USER::DO-PRIMES in DEFMACRO
DO-PRIMES
CL-USER> (macroexpand-1 '(do-primes (p 0 10) (format t "~d " p)))
(DO ((P (NEXT-PRIME 0) (NEXT-PRIME (1+ VAR)))
     (#:G585 10))
    ((> P #:G585))
  (FORMAT T "~d " P))
T
CL-USER>

動きます。感動的ですね。

さて、異なるマクロが展開されるタイミングについてはっきり意識しなくてはなりません。
do-primesを定義をコンパイルするとき、with-gensymsフォームは展開されてコンパイルされます。
do-primesを使う関数をコンパイルするときは、with-gensymsで生成されたコードが
do-primesの展開形を生成するために実行されます。
この時はwith-gensymsそのものは、do-primesの中で展開が完了されているためもはや必要ないそうです。

今まででてきたマクロは、タイピングを節約する程度のものであり根本的に
新しい表現を可能にするようなものではありませんでした。
次の章では、マクロなしでは不可能に思えるようなことをするそうです。
楽しみですね。しかし今日はここまでとします。

と見せかけて。

切れ味の鋭いマクロ

コラムみたいな感じで、マクロを書くマクロのよくある例が紹介されております。
once-onlyという、生成されたコードが特定の順番で一度だけ評価されるような
コードを生成するものだそう。
切れ味の鋭いマクロを習得したければ解読してみるがいい、ということなので頑張ります。

CL-USER> (defmacro once-only ((&rest names) &body body)
           (let ((gensyms (loop for n in names collect (gensym))))
             `(let (,@(loop for g in gensyms collect `(,g (gensym))))
                `(let (,,@(loop for g in gensyms for n in names collect ``(,,g ,,n)))
                   ,(let (,@(loop for n in names for g in gensyms collect `(,n ,g)))
                      ,@body)))))
ONCE-ONLY
CL-USER>

難しい。多段のアンクォートやバッククォートは一瞬混乱させてくるぐらいですが、
それ以上にこれがどうやって役に立つのかがわかりません。
とりあえず展開します。

CL-USER> (macroexpand-1 '(once-only (hoge)
                          (princ hoge)))
(LET ((#:G595 (GENSYM)))
  `(LET (,`(,#:G595 ,HOGE))
     ,(LET ((HOGE #:G595))
        (PRINC HOGE))))
T
CL-USER>

うむむ。結果としては、本体でhogeが使えるようになるのが大事ですよね。
本体でhogeを使うと、それはgensymされたものを指し、外側のletではhogeを指し、
更に外側では...いや、違う。考える順序が逆だ。
そして大事なのは本体でhogeが使えることだけではなく、引数が一度しか評価されないことでした。

CL-USER> (macroexpand-1 '(once-only ((random 10))
                          (princ hoge)))
(LET ((#:G608 (GENSYM)))
  `(LET (,`(,#:G608 ,(RANDOM 10)))
     ,(LET (((RANDOM 10) #:G608))
        (PRINC HOGE))))
T
CL-USER>

う~ん。...。よし。今後の課題とします。本当に一回しか評価されないのかすらわかりません。
おやすみなさい。