Let Over Lambdaのnlet-tailがよく分からなかったのでメモ

在庫切れになっていたLet Over Lambdaの訳本にオンデマンド版なるものが出ていることに気付いたので買って読んでいます。

作者: ダグホイト,Doug Hoyte,タイムインターメディアHOPプロジェクト
出版社/メーカー: エスアイビーアクセス
発売日: 2014/12/22
メディア: 単行本
この商品を含むブログを見る

電車で少しずつ読んでいますが、「4.4 macroletを使ったコードウォーク」に出てくるnlet-tailマクロがよく分からなかったので展開してみたメモです。なお、quicklispには同書で書かれたユーティリティ一式を備えた"let-over-lambda"が登録されているので、(ql:quicklisp :let-over-lambda)とすればすぐに試せます。

まずこの4.4節の目的は、マクロで受け取ったリスト内のシンボルをどう置き換えるかというところにあります。そんなもの、ちょっと再帰でネストしたリストを手繰ってシンボルを探すとか、sublis関数を使うとかで簡単にできるでしょ…と思えるのですが、例えばクォートされたシンボルを置き換えるのはまずいですし、letの左辺（？）を置き換えるのもまずいです。仕様上同様の考慮が必要なスペシャルフォームは25個もあるので、とてもじゃないが自力で正しくなんてできない、というのが提起されている問題です。

そこで、macroletを使うことでそれ、すなわちコードウォークをさせればよい。その例として末尾再帰最適化を明示的に行うnletマクロ、名付けてnlet-tailマクロを作る、とのことですが…

(defmacro! nlet-tail (n letargs &body body)
  (let ((gs (loop for i in letargs
               collect (gensym))))
    `(macrolet
         ((,n ,gs
            `(progn
               (psetq
                ,@(apply #'nconc
                         (mapcar
                          #'list
                          ',(mapcar #'car letargs)
                          (list ,@gs))))
               (go ,',g!n))))
       (block ,g!b
         (let ,letargs
           (tagbody
              ,g!n (return-from
                    ,g!b (progn ,@body))))))))

…すいません、分かりません。とりあえず以下を知りたいところです。

ナニコレ
macroletでコードウォークするってつまりどういうこと？

ということで、電車で脳をスタックオーバーフローさせるのはやめて家で展開してみました。展開する対象は同書でも例として挙げられている階乗計算関数の定義です。

(defun nlet-tail-fact (n)
  (let-over-lambda:nlet-tail fact ((n n) (acc 1))
    (if (zerop n)
        acc
        (fact (1- n) (+ acc n)))))

定義部分のlet-over-lambda:nlet-tail以下を展開してみます。

; macroexpandしてみる
(LET ()
  (MACROLET ((FACT (#:G990 #:G991)
               `(PROGN
                 (PSETQ ,@(APPLY #'NCONC
                                 (MAPCAR #'LIST '(N ACC)
                                         (LIST #:G990 #:G991))))
                 (GO ,'#:N988))))
    (BLOCK #:B989
      (LET ((N N) (ACC 1))
        (TAGBODY
         #:N988
          (RETURN-FROM #:B989
            (PROGN
             (IF (ZEROP N)
                 ACC
                 (FACT (1- N) (+ ACC N))))))))))

; 見づらいのでgensymで生成されたオブジェクトをそれらしい名前で書き換える
(LET ()
  (MACROLET ((FACT (n-value acc-value)
               `(PROGN
                 (PSETQ ,@(APPLY #'NCONC
                                 (MAPCAR #'LIST '(N ACC)
                                         (LIST n-value acc-value))))
                 (GO ,'tag))))
    (BLOCK blk
      (LET ((N N) (ACC 1))
        (TAGBODY
         tag
          (RETURN-FROM blk
            (PROGN
             (IF (ZEROP N)
                 ACC
                 (FACT (1- N) (+ ACC N))))))))))

; 手で最終行のFACTを展開（macroletは省略）
(LET ()
  (BLOCK blk
    (LET ((N N) (ACC 1))
      (TAGBODY
       tag
       (RETURN-FROM blk
         (PROGN
           (IF (ZEROP N)
               ACC
               (PROGN (PSETQ N (1- N)
                             ACC (+ ACC N))
                      (GO tag)))))))))

こうして展開してみると、確かに末尾再帰呼び出しをループ（このとき、goで飛ぶ手前で引数に当たるn, accをpsetqで更新）に展開していることが見てとれます。デフォルトではreturn-fromで抜けるようにして、続けたい場合はgo（goto）でreturn-fromの手前まで投げ返すのですね。乱暴な感じもしますが、マクロで隠してしまえば表にはきれいな構造しか見えないのでありだということでしょうか。ちょっと思考の幅が広がる感じがします。…ということで知りたいこと1番目の「ナニコレ」は分かりました。

次はmacroletでコードウォークってどういうことかという部分です。展開してみるまで勘違いしていたのですが、ここでの目的は任意の位置にあるシンボルを置き換えることではなく、一見関数シンボルに見せているもの（上記ではfact）を別の処理で置き換えるということでした*1。関数の位置にあるシンボルを認識して別の処理に変換する、かつクォートされたリストの先頭などの置き換えは避ける…という動作を冷静に考えると、マクロ展開の動作そのものです。そんなわけで、別に独自のコードウォークなんて書かなくても、マクロを使えば目的は達成できますよという話のようです。ここでdefmacroではなく、macroletを使うのは単純に無用な名前衝突を避けるためですね。

まだ4章までしか読めていませんが、Let Over Lambdaは面白い本ですね。不満があればなんであれ自ら書き換えるのがLisperの性質だということは納得しつつあったので、全部が全部驚くわけではないのですが。特に興味をひかれているのは第1章終わりの下記の一文です。

値割り当て可能なセルと古き良きラムダ式があれば、オブジェクトシステムは、よく言っても有効なこともある抽象化の手段に過ぎず、悪くすると特殊な場合であり余計なのである。

信奉する気はなかったにせよ、短いプログラマ人生の中でオブジェクト指向が大きい位置を占める言語（特にC#）との付き合いは長かったので、その原始的なところには何があり、便利にする過程で何をそぎ落としてしまったのか、というところは多分に興味があります。この先まだまだその源流である"let over lambda"の威力を見せつけてくれるとのことなので大変楽しみです。

*1:そのつもりで手前の文章を読み直してみると実際そう書いてありますね…