独学Common Lisp

(+ LIST MACRO) => FREEDOM

リスト表記とリスト構造

これまで見てきたようにCommon Lispは前置記法とラムダ計算を備えた言語ですが、Common Lispの表記法はラムダ計算のためだけにあるのではありません。

リスト表記は構文を最も簡潔に表すことができる表記方法で、XMLやJSONと比べても明らかに簡潔です。そして、人間にとって簡潔であるということは、計算機にとってもわかりやすいということです。一般的な言語では人間が書いたソースコードをパーサーで解釈して構文構造(syntax-tree)を得ます。例えば、C言語のforであれば変数の初期化、終了判定、インクリメントに続いて本文が現れるので、各要素を(;){}で分割して使っていきます。Common Lispでは((空白)と)だけが構文の区切りであり、先頭要素がオペレータで残りの要素が引数ですから、事実上構文解釈をする必要もなく、ただこの決まりに沿って関数の適用と評価が繰り返されます。

Common Lispではこのような簡潔な構文ゆえに、構文を操作するプログラムを書くことができます。つまり、人間が記述したソースコードを変形して別のソースコードに書き換えてから適用・評価を行うことができます。このような操作を行うオペレータを「マクロ」と言い、関数とは違う特徴を持ちます。今回はマクロと共にCommon Lispのソースコードを操作するためのリスト構造について説明します。

car, cdr, cons

リストの操作は実際のところ、とても簡単です。

carはリストの先頭要素を取り出します。

(car '(+ 1 2 3))
; => +

cdrは先頭以外の残りの要素を取り出します。

(cdr '(+ 1 2 3))
; => (1 2 3)

これだけでデータを関数にして適用することができます。

(apply (car '(+ 1 2 3)) (cdr '(+ 1 2 3)))
; => 6

Common Lispがやっているのはこういうことです。

リスト表記は単純ですが、このような操作がとても簡単できるのには訳があります。リストは横一列に並んでいるように見えますが、実は「コンスセル」という一対のデータ構造でできています。コンスセルを作るのはconsです。

(cons 1 2)
; => (1 . 2)

コンスセルはcar部とcdr部で構成されます。もうお分かりの通り、一つ目がcarで、二つ目がcdrです。コンスセルは真ん中にドットがついている通り、リストとは少し違います。equal述語は二つの要素が等しいかどうかを調べる関数ですので、試してみます。

(equal '(1 . 2) '(1 . 2))
; => T
(equal '(1 . 2) '(1 2))
; => NIL

リストは、コンスセルのcdr部を次のコンスセルのcar部にして参照の連鎖をしていく構造になっており、最後のcdr部はnil('())であると決められています。

(equal '(1 2) (cons 1 (cons 2 '())))
; => T

リストに対してcdrを適用すると先頭以外の残りが全部取り出されるのはそのためです。リストに対する根源的なオペレータはconscarcdrだけです。

しかし、これだけで例えば行列(二次元配列)のようなものも比較的簡単に扱えます。

(mapcar #'car '((1 2 3)
                (4 5 6)
                (7 8 9)))
; => (1 4 7)

mapcarは第二引数のリスト内の要素を順番にcarして取り出していくので、行列のようなリストであればそれにcarをすることで列を取り出すことができます。

では、二番目の要素を取り出すにはどうすればいいでしょうか。cdrしてからcarすればいいのです。

(mapcar #'(lambda (x) (car (cdr x))) '((1 2 3)
                                       (4 5 6)
                                       (7 8 9)))
; => (2 5 8)

これはとても面倒なので、cadrという関数も用意されています。

(mapcar #'cadr '((1 2 3)
                 (4 5 6)
                 (7 8 9)))
; => (2 5 8)

また、secondも同じ機能を持ちます。

(mapcar #'second '((1 2 3)
                   (4 5 6)
                   (7 8 9)))
; => (2 5 8)

second系はfirstからtenthまで用意されており、cadr系はcarからcddddrまであります。詳しくはCommon Lisp HyperSpecを参照してください(car, first)。

マクロ

リストの操作ができるということは、Common Lispのソースコードの操作ができるということです。Common Lispはソースコードを実行する前の段階で、ソースコード自体に介入するフェーズがあり、その段階の操作を「マクロ展開」と呼ばれます。

実は、letcondなどこれまでに使ったオペレータのいくつかはマクロです。使い方は関数と同じなのですが、関数と決定的に異なる点があります。それは、引数自体を制御できることです。

関数は引数が全て評価された状態で引数を受け取ります。例えば、以下の式で+関数はaというシンボルが見えません。

(let ((a 1))
  (+ a 2))
; => 3

なぜなら、aというシンボルは1という数に束縛されているので、+に適用される前にa自身が評価されて1として+に適用されるからです。

しかし、オペレータの中にはシンボルを見る必要があるものがあります。それは束縛を伴うものです。

例えば、letのカッコの中に記述されるシンボルはまだ何にも束縛されていないので評価されると「未定義」というエラーになるはずですが、実際にはエラーにはなりません。letは式を変更してlambdaに置き換えているだけだからです。

また、condも関数ではなくマクロとして定義されなければなりません。condは束縛は伴いませんが、条件によって実行しない式を含むからです。関数の引数は必ず評価(実行)されてから関数に渡されますが、condは引数の評価を条件に応じで抑制することができます。condオペレータが行なっているのは、ifへの置き換えです。

このように、ある機能を持つオペレータはより根源的なオペレータへと置き換えることで実行されていきます。全てを根源的なオペレータで記述していくのは不便なので、Common Lispでは、関数では実現できないことも実現できるようにする機能としてマクロが用意されています。

マクロを定義するにはdefmacroを使いますが、マクロが提供するのは機能ではなくリストです。

(defmacro reset (x)
  (cons 'setf (cons x (cons 0 '()))))

(defvar num 10)
num
; => 10
(reset num)
num
; => 0

consが3つ並んでいますが、出来上がるのは(setf x 0)というリスト表記です。ただし、xの部分はdefmacroで束縛されたシンボルで置き換えられ、今回は(setf num 0)になります。

これは関数では書けません。なぜなら、関数にはnumというシンボルが見えず、10という値しか受け取れないからです。マクロにはシンボルが見えます。見える、というよりも、(reset num)という式がそのまま渡されてくるイメージです。式が渡されてくるので、(setf num 0)という式に書き換えて返します。すると、まるでそこに最初から(setf num 0)があったかのように実行されます。

マクロが行うのはこれだけです。しかし、マクロこそがCommon Lispの力です。

マクロはプログラムを生成するプログラムです。Common Lispが「プログラム可能なプログラミング言語」とか「メタプログラミング言語」と言われるのはマクロのおかげです。Common Lispのマクロは他の言語では簡単には真似できません。もとの話に戻りますが、ソースコードを操作することが容易なのは、ソースコードがリストそのものだからです。マクロはソースコードをソースコードとして見ているのではなく、リテラルとして見ることができるのです。

list, `, ,

この節のタイトルは何かのタイプミスでしょうか。いえ、間違っていません。ここではlist`'を紹介します。

前節でマクロの定義の仕方を説明しましたが、consを使ってコツコツとリスト表記を構築していくのは結構大変です。複雑な変形になればなるほどますます大変になります。そこで、もっと便利なリスト構築方法が用意されています。

一つ目は、すでに何度も使ってきたquote(')によるリストです。

(defmacro reset (x)
  '(setf x 0))

このマクロは欠陥があり、ある条件の時しか動きません。それは、(reset x)という形で呼び出され、操作すべきシンボルがxの時だけ正常に動作します。なぜなら、マクロの引数リストでxが使われていますが、リストの中で返されるのは'x、つまり文字通りのxだからです。quoteはリテラルだけを返す場合には使えますが、リテラルでないものを含む場合には使えません。

二つ目は、list関数を使うことです。これは文字通りリストを作って返すものです。

(defmacro reset (x)
  (list 'setf x 0))

引数の数は何個でも構いません。ここではsetfにはquoteがついていますが、xにはついていませんので、xは引数で渡されたシンボルに評価されてからlistでリストの要素になります。

三つ目は、`,を使う方法です。これらは純粋に記号として定義されていますが、一般的にbackquote(またはquasiquote)とcomma(またはunquote)と呼ばれます。これらはquoteを拡張したものです。

(defmacro reset (x)
  `(setf ,x 0))

`'のように動作しますが、,がついているものは'されないという便利な使い方をすることができます。今回の場合、xはリテラルにしたくありませんから、,で解除しています。一般的にはこの`,の組み合わせが最も使われます。

,@

リストの操作にはもう一つ便利な記号があります。,@です。これは、リストを分解することができます。この記号は、&bodyとセットで使われることが多いです。試しに、自分でletを実装してみましょう。

まず、これから定義するmy-letの使い方のイメージを1つのリスト表記で記述してみます。

(my-let ((a 1)
         (b 2))
  (+ a b))
; => 3

これをlambdaで書き換えるとこのようになります。

((lambda (a b)
   (+ a b))
 1 2)
; => 3

変形前と変形後を見比べると、どのようなリスト操作が必要かがわかります。

分解の方法はすでに学びました。二次元配列的な分解と全く同じです。ただし、(a b)mapcarで作れるとしても1 2はどうしても作ることができません。なぜならmapcarはリストで返しますが、1 2はリストではなく12という二つの数にまで分解されているからです。このように、リストを分解する(カッコを消す)のが,@で、リストの前に付けると分解することができます。

では、my-letをマクロで定義してみましょう。

(defmacro my-let (args body)
  `((lambda ,(mapcar #'car args)
      ,body)
    ,@(mapcar #'cadr args)))

このマクロは、一見正しく動くかもしれません。しかし、lambdaの定義が2つ以上の式の場合には正しく動きません。引数のbodyが定義を一つしか束縛できないからです。

可変個の式を束縛するには&bodyを使います。lambdadefun)の&optional&keyと同じように使うことができ、意味としては&restと同じですが、インデントがマクロに適した形で展開されるのでマクロでは&restよりも&bodyが使われます。

(defmacro my-let (args &body body)
  `((lambda ,(mapcar #'car args)
      ,@body)
    ,@(mapcar #'cadr args)))

(my-let ((a 1)
         (b 2))
  (+ a b))
; => 3

,(mapcar #'car args)というのは慣れないと難しいと思いますが、(mapcar #'car args)のリテラル化を一時解除しているので、argsの1列目(ここでは(a b))が得られます。,@(mapcar #'cadr args),@なので、argsの2列目(ここでは(1 2))のリストも解き放たれて1 2に展開されます。

gensym

前回のおまけでフィボナッチ数列を生成するラムダを返す関数を定義しました。その際、フィボナッチ数列をずらしながら束縛するコードを使いました。抽出すると、以下の部分です。

(let ((fib (+ f1 f2)))
  (setf f1 f2)
  (setf f2 fib))

このコードを複数の箇所で記述する場合、マクロによって抽象化することを検討してもいいかもしれません。シンボルへの値の代入を伴うので関数としては定義できませんが、マクロなら簡単に書くことができます。

(defmacro fib-mac (f1 f2)
  `(let ((fib (+ ,f1 ,f2)))
     (setf ,f1 ,f2)
     (setf ,f2 fib)
     fib))

(let ((a 0)
      (b 1))
  (fib-mac a b)
  (fib-mac a b)
  (fib-mac a b)
  (fib-mac a b)
  (fib-mac a b))
; => 8

しかし、このfib-macマクロには唯一欠陥があります。abかのどちらかをfibというシンボルで使った時には、エラーも出ませんが正常には動きません。

(let ((fib 0)
      (fib2 1))
  (fib-mac fib fib2)
  (fib-mac fib fib2)
  (fib-mac fib fib2)
  (fib-mac fib fib2)
  (fib-mac fib fib2))
; => 1

原因を調べるにはmacroexpand-1が便利です。

(macroexpand-1 '(fib-mac fib fib2))
; => (LET ((FIB (+ FIB FIB2))) 
;      (SETF FIB FIB2) 
;      (SETF FIB2 FIB) 
;      FIB)
;    T

macroexpand-1はマクロを展開する関数です。多値を返すのでTは今は気にしないでください。問題はfibが重複していることです。この現象を「変数の補足(variable capture)」と言います。

これを回避するのは簡単で、マクロの中で用いる変数には重複しないシンボルを使うことです。とても珍しい長い名前にして防ぐこともできますが、Common Lispには重複しないことが保証されるシンボルを生成する関数gensymがあります。

(defmacro fib-mac (f1 f2)
  (let ((fib (gensym)))
    `(let ((,fib (+ ,f1 ,f2)))
       (setf ,f1 ,f2)
       (setf ,f2 ,fib)
       ,fib)))

(let ((fib 0)
      (fib2 1))
  (fib-mac fib fib2)
  (fib-mac fib fib2)
  (fib-mac fib fib2)
  (fib-mac fib fib2)
  (fib-mac fib fib2))
; => 8

(gensym)は重複しないシンボルを生成するので、そのシンボルをfibで束縛しておきます。マクロで生成するリスト表記ではそのシンボルに展開されるよう、fib,でリテラル化を解除します。この変更だけで誤作動を防ぐことができます。

試しに、macroexpand-1してみてください。

(macroexpand-1 '(fib-mac fib fib2))
; => (LET ((#:G558 (+ FIB FIB2))) 
;      (SETF FIB FIB2) 
;      (SETF FIB2 #:G558) 
;      #:G558)
;    T

#:G558は環境によって異なりますが、#<Anonymous Function ...>のようにCommon Lispが読み取れないデータを表しますが、これはシンボルの一種です。fibというシンボル名は隠蔽されて、決して重複しないシンボルに置き換えられているのが分かります。

マクロを書くときはまず普通に書いて、後で束縛を伴う部分をgensymで隠蔽して変数補足を防ぎます(実際にはパッケージシステムも変数補足を防ぐのに役立ちますが、それはまた別のページで紹介します)。

Vocabulary + Syntax = Language

「言語」は「語彙」と「構文」で構成されます。Common Lispにおいて語彙を増やす方法がdefundefvarであるのに対し、構文を増やす方法がdefmacroです。英語を学ぶときは英単語と英文法を覚えなければなりませんが、Common Lispを学ぶときは最低限の関数とラムダ計算だけを覚えて、あとは自分で語彙と構文を増やすという使い方ができます。実際、Common Lispの便利な機能の多くはマクロによって構築されています。言語仕様に含まれる構文も、自分で作ったマクロによる構文も全く同じように動作させることができるというのは、Common Lispの哲学を反映しています。

Common Lispはユーザーを信じる言語です。LISPには「今のユーザーよりも将来のユーザーの方が賢い」と考える文化があり、実際にそのようにして様々な機能が追加されていきました。マクロも一番最初のLISPにあった訳ではありませんが、途中で提案されて便利だということで追加されて定着しました。そのとき、構文上の制約が言語の拡張を制限しないように、構文すらも自分で構築できるようにマクロシステムを組み込んだのです。言語の設計者は平凡なプログラマよりも賢いことが多いですが、Common Lispは間抜けなユーザーが誤って変数補足をして誤作動する自由を提供するとともに、言語設計者よりも賢い将来のハッカーが便利な機能を追加する余地を残しているのです。

私はLISP語族のSchemeも実用で使ったことがありますが、どうしてもマクロシステムで納得がいきませんでした。Schemeのマクロはリスト表記を直接操作するのではなく、「構文オブジェクト」を操作する「トランスフォーマー」としてマクロを定義します。構文オブジェクトは、リスト表記がどのソースファイルのどの行の何文字目に記述されていたかという文脈情報を内包したデータであり、このことによって変数補足を自動的に回避することができますが、安全性と引き換えに簡潔さと自由さを損ない、LISPの本質的な部分を自ら手放してしまったように感じました。Common Lispのマクロは間違えて自分自身を撃ってしまうような危険性がありますが、やっていることはソースコードの変形だけであり、とても自由で気持ちの良いものです。

関数で書けるものは関数で書いた方が分かりやすいのでいいのですが、「こう書きたい」という希望はソースコード全体の簡素化・明瞭化に寄与するかもしれません。今回の場合、「フィボナッチ数列を計算する」という意味が重要であれば、その計算の手続きをマクロで隠蔽することでソースコード全体の簡潔性が向上するかもしれません。

マクロは自由なCommon Lispの哲学を代表するものです。恐れず使うことでCommon Lispの世界にどっぷり浸ることができます。C言語のポインタがエラーの原因にもなりうるからといってポインタの使用を控えるべきだという人はいません。Common Lispのマクロも同じです。自由を謳歌しましょう。

参考文献


Copyright © 2017- satoshiweb.net All rights reserved.