on-cdrs

今回は小ネタだ。

On Lisp: Advanced Techniques for Common Lisp

グレアム,ポール

オーム社

ポール・グレアムのOn Lispと言う本は評価が難しい本だと思う。

良い点は、それまで「サラッと」流されていたCommon Lispのマクロと言う機能の「使い方」に対して詳細な「方法論」を書いてる、って事。

この本が出るまでCommon Lispのマクロってのは「使い方が良く分からない」知る人ぞ知る、って機能だったんだ。

この本の原書が上梓されたのが1993年だったんだけど、Common Lispに限らず、Lispの登場した1960年前後から、30年以上に渡って、一般的に「マクロ」をどう使うのか、ってのは、マジでLispのディープな「専門家」以外には殆ど知られてなかった、と言って良く(※1)、初めてマクロに対する「ノウハウ」を公開した書、と言って過言じゃないだろう。

「Schemeのマクロは良く分からない」と言うのに比べると、Common Lispに於いては、ポール・グレアムのお陰で「色んなノウハウが公開された」と言って良いと思う。

まさしく「革命的な本」だったんだ。

反面、悪い点、と言うか微妙な点も結構大きい。まず、実の事を言うと「On Lisp」と言う本は厳密に言うとANSI Common Lisp対象の本じゃない。ANSI化する前のCommon Lisp 第二版と言う「草の根」共通仕様の言語に付いての本、なんだ。いや、殆どのコードはANSI Common Lispでも当然動くんだけど、原則「古い仕様の為の本だ」ってのはアタマの隅に置いておいて良いと思う。

もう一つビミョーなのは、「マクロの書き方」が分かっても、紹介されてるマクロが「全部」すんげぇ役立つユーティリティになり得るか、っつーと「う〜ん・・・?」って思うんだよな(笑)。

例えば16章ではCommon Lispの関数やマクロの「長ったらしい名前」を省略出来るマクロが紹介されている。

確かにかなりのCommon Lispの関数名やマクロ名は糞長い。MIT方式だ。「名称は明快にすべき」ってぇんで名前を見れば機能が分かる、と言うカンジで徹底してる(※2)。しかしそれだとタイピングがキツい、ってのは事実だ。

ところが、Lispは主にMITで発展してきた背景もあり、MITだと1960年代後半辺りから「補完機能ありの」テキストエディタ、今で言うIDEでの開発が割に当たり前だったんだよ。最新式のコンピュータと最新式の開発環境を持つ、ってのがMITの贅沢さだったわけ。

補完機能があるエディタで開発する、って前提のLispでは、原則、「長い名前はへっちゃら」だったわけだよな。

一方、ポール・グレアムはviユーザーだ。多分IDE化出来る変種のvimじゃないんだよ。今はMacユーザーならしいが、元々FreeBSDユーザーだ、って事もあって、Linuxなんかで有名なvimじゃない。モノホンのviだ。

んで、素のviってのは設定は色々出来るは出来るけど、ニュアンスとしてはEmacsやその他のモダンなIDEに比べると圧倒的にWindowsのメモ帳に近い。

ってこたぁ「補完機能がない」って考えてまぁいいんだよ。ポール・グレアムはそういう環境でLispを書いてるんだ。

つまり、「省略形を定義出来る」マクロ、ってのはポール・グレアムのようなviユーザーには魅力的なんだけど、EmacsをはじめとするIDE勢にとってはそれほど魅力的なマクロじゃなくなるんだ(笑)。「補完機能アリのエディタで充分じゃね?」と(笑)。

そりゃそうだろ(笑)、フツーのモダンなエディタで出来る事をわざわざマクロで解決しよう、とはしねぇだろ、って話になる(※3)。

結論としてはこのトピックは汎用的なトピックじゃなく、(vimユーザーではないので数が少ない)viユーザー向けの「限られた」話、って事になる。

とまぁ、書籍として鑑みると総評としては「ビミョー」ってのがどうしてもついて回るんだよな(笑)。もちろん「マクロを書くノウハウ」を惜しみなく提示してる、って意味ではこれほど優れた本はないわけだけど。

いずれにせよ、それくらい「汎用的なマクロ」を発想して作るのは難しい(※4)。「汎用的なマクロを書くチャンス」ってのはグレアムにしてもやっぱりなかなか無いんだ。

今回はその「ビミョー」なトコの一つを取り上げる。

第5章で、これはマクロじゃないんだけど、次のような説明と関数が紹介されている。ちと長くなるが引用しよう。

ポール・グレアムの示唆は重要だ。プログラミングに於いての「頻出パターン」だけを取り出して纏めてしまう、ってのは要はユーティリティ作成だ。ここではLispに頻出の「再帰」をパターンとしてまとめ、「自分で再帰を書かなくても良いようにしよう」と言う提言をlrec関数、として提示している。

関数lrecを使うとCommon Lisp 第二版に含まれているユーティリティ関数を簡単に定義出来る、とグレアムは言う。

僕がまだプログラミングに於いてチンコに毛が生えてなかった頃、この項目を読んで「すげぇ!」とか思ったモンだ。なんせLispは再帰再帰言うてる言語なのに、その「再帰と言う武器」でさえ抽象化して消し去ろうとする、なんてなんつースゴイ言語、そしてテクニックなのか、と。ポール・グレアムは神なのか、と。

今だとさすがにプログラミングのチンコにちらほらと毛が生えてきてるんで、当時程のコーフンは覚えない。逆に「何故にlrecなる関数をわざわざ定義しようとしたんだ?」と疑問を感じてる。

このブログを読んでる人ならある程度予想は付くだろう。Figure5.6に挙げられた「Common Lispの組み込み関数の再実装」は、Racketならfoldrをこのように使えば実装可能だから、だ。

つまり、foldr自身が再帰の抽象化だ、ってのを僕らは既に知っている。Common Lispなら?当然reduceがある。 => reduceを使ったコード例

そしてCommon Lisp 第二版にもreduceがあるにも関わらず、ポール・グレアムはそれを使わずに、不可思議な関数lrecを定義してるんだ・・・当時の僕は気づかなかったんだよなぁ。なんつったってreduceは二引数関数を可変長引数の関数に変える高階関数だと思い込んでたんで(笑)。

なお、ポール・グレアムのlrecをRacketへと直訳すると次のようになるだろう。

(define (lrec rec base)
　(define (self lst)
　　(if (null? lst)
　　　(if (procedure? base)
　　　　(base)
　　　　base)
　　　(rec (car lst)
　　　　(lambda ()
　　　　　(self (cdr lst))))))
　self)

Racket版のlrecのbaseがオプショナル引数じゃない理由は、Common Lispの場合、オプショナル引数が与えられない時、デフォルト値がnilになるからだ・・・Common Lispだと偽値も空リストもnilなんで、意味の違う2つを統一的に扱う事が出来るが、Racketではそれは望めない。偽値は#fで空リストは真偽値では#tになる。

結果「どっちがどっちだったっけ?」となるくらいなら、明示的にbaseを与えた方がいい。

このlrecの特徴は大きく言うと2つある・・・いや、細かいトコ言うと、原作のベースケースである返り値、baseが関数だった場合も考慮してる、ってのもあるんだけど、この本の中だとbaseが関数だった事は無い・・・と思う。いや、随分昔に通読したきりなんで、記憶が曖昧なんだけど、なかったと思う。いずれにせよ「何故にbaseが関数の場合があるの?」と言うのはこの時点では一つ不思議な点だ。

しかし、大きな特徴はそこじゃない。1つ目は、この章題にあるように、これは「返り値としての関数」、つまり、関数を返り値とする高階関数になっている。

なるほど、それは特徴だろ?

もう一つは、再帰部分がラムダ式で包まれてて、呼び出し時にそこを「実行させな」アカン辺りだ。何故にこういう形式にしてんだか、これもこの時点ではハッキリしない。

; lengthの動作
> ((lrec (lambda (x f) (add1 (f))) 0) (list 1 2 3 4))
4
> ((lrec (lambda (x f) (add1 (f))) 0) (list))
0
>
; everyの動作
> ((lrec (lambda (x f) (and (char? x) (f))) #t) '(#\a #\b #\c))
#t

しかし、再帰部分をラムダ式でラップする必要がなかったら、lrecもfoldrで書けてしまう。foldrを「関数を返す関数」にしたければ、一種のカリー化を施せばいいんだ。

(define (lrec rec base)
　(lambda (lst) ; 一種のカリー化
　　(foldr rec base lst)))

こっちの方がfをカッコで包まなくて良い分、見た目はシンプルになる。

; lengthの動作
> ((lrec (lambda (x f) (add1 f)) 0) (list 1 2 3 4))
4
> ((lrec (lambda (x f) (add1 f)) 0) (list))
0
; everyの動作
> ((lrec (lambda (x f) (and (char? x) f)) #t) '(#\a #\b #\c))
#t

もちろん、ANSI Common Lispでも同様に書ける。

(defun lrec(rec &optional base)
　#'(lambda (lst)
　　　(reduce rec lst :from-end t
　　　　　　　　　　:initial-value base)))

もし、foldrの使用が「手抜き」だと思うのなら、教科書的なfold-rightの実装を参考にして、lrecは次のように書けるだろう。

(define (lrec rec base)
　(lambda (lst)
　　(if (null? lst)
　　　base
　　　(rec (car lst) ((lrec rec base) (cdr lst))))))

ANSI Common Lispでも似たようなコードになる。

(defun lrec(rec base)
　#'(lambda (lst)
　　　(if (null lst)
　　　　base
　　　　(funcall rec (car lst) (funcall (lrec rec base) (cdr lst))))))

繰り返すが、再帰部分をラムダ式で包まなければ、実行形式もコード自体もちょっとはシンプルになる。

このように、reduce/foldには長い歴史があるんで、フツーに安定性を考えると、なんか突飛な実装を「新しく作らなきゃならない」理由は通常は無い。

そして続編がある。今度は15章に於いて、グレアムは次のようなコードを提示する。

あらすじ: lrecはアナフォリックマクロとして生まれ変わった(※5)。そしてそれを利用してマクロon-cdrsへと進化を遂げたのだ。

ここでまたもやグレアムは、マクロon-cdrsを使ってCommon Lispの組み込み関数の再実装例を挙げている。

つまり、通常の再帰関数で書くより、on-cdrsマクロを使った方が遥かに短く書ける、と言うのがポール・グレアムの主張だ。

「ドヤァ」って声が聞こえてこないか(笑)。

ポール・グレアム渾身のドヤ顔(違

しかしちょっと待って欲しい。

ちとRacketのfoldrを使ったヴァージョンと並べて比較してみよう。

こう並べてみるとこの2つは殆ど同じだと言う事が分かるだろう。on-cdrs ≒ foldrなんだ。

見た目で違うのは、foldrはラムダ式を要してるんだけど、on-cdrsはラムダ式が要らない。そして、on-cdrsが最終型なんだとしたら、単純に考えると、lrecやalrecなんつーのを経由せんでも、最初っからfoldrをマクロでラッピングすれば充分なんじゃないの?ってのがここで出てくる。

ポール・グレアム流に言えば、そっちの方がより「人生の面倒を取り除いてくれる」。

ここでマクロ展開を考えるんだが、これは極めて簡単だ。on-cdrsは直接ラムダ式を持つfoldrへと展開される。

そしてon-cdrsの第一引数はそのままラムダ式内へと埋め込まれる。

図示するとこんなカンジだ。

exprは式で、内部にitとrecと言うアナフォラを持つ。Racketのsyntax-rulesではアナフォリックマクロは書けないんで、ここでsyntax-caseの登板だ。そしてitとrecはsyntax(構文要素)になる。

(define-syntax on-cdrs
　(lambda (x)
　　(syntax-case x ()
　　　((on-cdrs expr base lst ...)　; このパターンを
　　　(with-syntax ((it (datum->syntax #'on-cdrs 'it))
　　　　　　　　　(rec (datum->syntax #'on-cdrs 'rec)))
　　　　#'(foldr (lambda (it rec)　; このパターンに置き換える
　　　　　　　　expr) base lst ...))))))

これだけ、だ。

実際問題、複雑になりかねないsyntax-caseを使ったマクロとしては極めて簡単な部類に入るんじゃないか。なんせホンマに置き換え、しかしていない。

注意点が一つ。syntax-rulesに慣れていると、マクロの引数パターンを書く際に、ついついワイルドカード的な_(アンダースコア)を使って

(_ expr base lst ...)

と書きかねない。しかし、これはsyntax-caseでは止めた方がいい。

これをやっちゃうと、with-syntax内でdatum->syntaxを使ってitとrecをsyntax化してるんだけど、「on-cdrs内ではitとrecをsyntaxとする」と言う指令が上手く働かなくなる。

よって、明示的に

(on-cdrs expr base lst ...)

と書くようにしよう。じゃないとハマって「なんで?」となる(っつーかハマってた・笑)。

> (require (only-in srfi/1 lset-union lset-difference))
> (define (unions . sets)
　　(on-cdrs (lset-union eqv? it rec) (car sets) (cdr sets)))
> (unions '(a b) '(b c) '(c d))
'(d a b c)
> (define (differences set . outs)
　　(on-cdrs (lset-difference eqv? rec it) set outs))
> (differences '(a b c d e) '(a f) '(d))
'(b c e)
>

これで僕らは「ラムダ式要らずの」foldrの変種を手に入れた。ラムダ式を書く代わりにアナフォラitとrecを使って直接式を記述出来る。

ANSI Common Lispでも、reduceを利用して同様のマクロon-cdrを書くことが出来る。

(defmacro on-cdrs (rec base &rest lsts)
　`(reduce #'(lambda (it rec) ,rec) ,@lsts
　　　　　:from-end t
　　　　　:initial-value base))

しかし、この章で挙げられてるon-cdrs利用例で、次の関数だけは上手く動かない、と言う事が生じる。数値リストの最大値と最小値を同時に返す関数、だ。

;; Common Lisp
(defun maxmin (args)
　(when args
　　(on-cdrs (multiple-value-bind (mx mn) rec
　　　　　　　(values (max mx it) (min mn it)))
　　　　　　(values (car args) (car args))
　　　　　　(cdr args))))
; Racket
(define (maxmin args)
　(unless (null? args)
　　(on-cdrs (let-values (((mx mn) rec))
　　　　　　　(values (max mx it) (min mn it)))
　　　　　　(values (car args) (car args))
　　　　　　(cdr args))))

例えばRacketだと次のようなエラーが出る。

これは当然で、上の関数だとbaseに与える初期値が多値で、またexprが返す値も多値だ。しかしながらfoldrは多値を受けたり返す、と言う前提の関数じゃない。

ポール・グレアムが最初にlrecを作った際に、再帰呼び出し部分をラムダ式で包んだのは「ここ(多値返し)を簡単に実行させない」為なんだ。

ポール・グレアムはこう書いている。

recは値でなく呼び出しを参照するので，on-cdrsを使って多値を返す関数を生成できる．

さすがポール・グレアム!と言いたいトコだが本当にそうだろうか(笑)。

そもそもこの関数、内部的に多値を受け渡しせなアカン構造だろうか。

僕も多値は好きなんだけど、そもそも「多値を返す」事はあっても「多値を受け取る」事はそんなにあるだろうか、と言う疑問がある。そして、関数の引数は多値をそのまま受け取らない。

結果、複数の引数を持つ関数が多値を受け取ろうとする際、それこそ外部的にその関数を、ANSI Common Lispならmultiple-value-bind、Racketならlet-valuesで包まなきゃならなく、あまり美しくならないように思う。

ましてや、このケースのように、内部的にわざわざ多値を使ってやり取りせんでもエエだろう、ってのが本当のトコだ。

どうしても内部的に多値でやり取りしたい、って場合、on-cdrs自体を弄るよりもexprとbaseに値を与える方法を工夫すべきじゃないか。

少なくとも、Racketにはdelayとforceがある。

(define (maxmin args)
　(unless (null? args)
　　(force
　　　(on-cdrs (let-values (((mx mn) (force rec)))
　　　　　　　　(delay (values (max mx it) (min mn it))))
　　　　　　　(delay (values (car args) (car args)))
　　　　　　　(cdr args)))))

多値を返すvaluesの実行をdelayで遅らせてプロミスを作る。let-valuesで多値を変数mx、mnの２つに束縛する直前にrecをforceで実体化する、だけで済む。

また、on-cdrsの返り値もプロミスになるんで、やっぱりforceで実体化する。

これで済む筈なんだ。

> (maxmin '(3 4 2 8 5 1 6 7))
8
1

あるいは、さっきも書いた通り、そもそも内部的に多値を受け渡しする必要があるのか、って問題がある。返り値を多値として欲しいだけ、なんじゃないか。

従って、関数maxminは、本来だったら次のように書けば直球勝負になる筈、なんだ。

(define (maxmin args)
　(unless (null? args)
　　(apply values
　　　　　(on-cdrs (match-let ((`(,mx ,mn) rec))
　　　　　　　　　　`(,(max mx it) ,(min mn it)))
　　　　　　　　　`(,(car args) ,(car args))
　　　　　　　　　(cdr args)))))

内部的にはbaseをリストにし、exprの返り値もリストでいい。そして最後にon-cdrsの返り値のリストを多値化する。

こっちの方がシンプルだろう。

Common Lispならこうだ。

(defun maxmin (args)
　(when args
　　(apply #'values
　　　　　(on-cdrs (destructuring-bind (mx mn) rec
　　　　　　　　　　`(,(max mx it) ,(min mn it)))
　　　　　　　　　`(,(car args) ,(car args))
　　　　　　　　　(cdr args)))))

いや、ひょっとしたらポール・グレアムの書いたコードは、彼の「Common Lisp 第一版」の長い経験故に書かれたモノかもしんない。と言うのも、マクロdestructuring-bindはCommon Lisp第二版で初めて登場した新マクロだった、からだ。

Schemeの仕様にmatch及びmatch-letは無いが、現代の僕らが使用するScheme実装及びRacketにはこのテのパターンマッチ機構がある(※6)。

一方、Scheme/Racketのmatch-letに当たるdestructuring-bindは「On Lisp」が上梓された時点では登場から日が浅く、Scheme/Racketのmatch-letで行うような事は多値を使って束縛する、ってのがポピュラーだったのかも。じゃないとリストを自ら分解して個別に束縛せんとアカンかったんだろうしね。

しかし、どっちにせよ、現代では、「多値の可能性を考慮した」再帰を抽象化した関数を作ってマクロ化するより、foldr/reduceをマクロでただラッピングした方がシンプルでマシだと思うし、上のように、多値が必要ならon-cdrsを呼び出した側で何とかした方がいいと思っている。

ポール・グレアム方式のon-cdrsは現代だとやっぱビミョーな実装なんじゃないか。

と言うのが個人的な意見だ。

分からんけどね。

今回は、以上。

※1: とは言っても最初期のLispからマクロがあったわけじゃない。「人が読み書き出来るアセンブリ」として計画されたLispには構文木を直接弄る、と言うアイディア自体は元々内包されていたが、マクロとして結実したのは登場から数年経った1963年、Timothy P. HartによるLisp実装が初、だと言われる。

※2: 「あれ?carやcdrって意味不明な省略型も多いけど?」と不思議に思うかもしれないが、それはそれら関数が登場した「時期」のコンピュータやOSが、長い名前を禁止してたから、だ。古い時代のコンピュータだと結構字数制限が厳しかった、と言う事に由来する。

Lispは歴史が長いんで、「古い時代での命名」の関数と「比較的最近での命名」の関数が混在してる。言い換えると、「短い省略法」で命名された関数はLispの総初期からあった古い関数で、「長い命名」をされた関数は、比較的登場が新しい、と考えていい。

※3: テキストエディタとIDEのどっちがいい?って論争がたまに起こるみたいだが(最近はそうでもない?)、このテの論争はハッキリ言ってかなり下らない。

そうじゃなくって、あるのは、プログラミング言語自体の設計段階で、「素のテキストエディタ前提」で設計されたのか、「IDE使用前提」で設計されたのか、って事だけだ。

C言語は「素のテキストエディタ」前提で開発されてる。だから省略形だらけだ。

Lispは「IDE前提で」開発された言語だ、ってだけだ。だから殆どが「冗長な」名前を持つ。

Rubyのendも打つのが面倒くさいが、Matz氏によると「Emacsの補完でイケる」との事で、結果RubyもIDE前提で設計された言語だ、って事だ。

オブジェクト指向の言語は表現が全般的に長ったらしくなる傾向があるんで、これも「IDE前提で設計された」と言う事だろう。

IDE頼りで設計された言語を素のテキストエディタで使おうとすると面倒くさくなるだけだし、逆に素のテキストエディタで書かれる想定の言語をIDEで書こうとすると、オーバースペックでIDEの重さだけが際立つ、ってのも良くある話だ。

プログラミング言語には「開発環境の想定」ってのが含まれているんだ。

※4: 結局、マクロはあるプログラムを書く際に作るDSL(ドメイン特化言語)を書く機能の側面が強いんだろう・・・文法はともかくとして、元々「一般論をする」のが難しい機能だ、と言う事だ。

言い換えるとある特定のプログラムに於いて、「特化した」マクロを書く方が簡単だ、っつー事だが、それを本にして書くのは難しい。