今までにいろいろな関数を作ってきましたが、Lisp / Scheme や Clojure は関数だけではなく、「マクロ (macro)」を定義することができます。Clojure でプログラミングする場合、ほとんどの処理は defn で定義する関数で作成することができます。ところが、場合によっては引数を評価しない関数が必要になることもあります。ここで役に立つのがマクロなのです。また、マクロを使って新しい制御構造を定義することもできます。
Ｃ/Ｃ++ユーザーであればマクロはお馴染みの機能なので、よく使っていることと思います。ところが Lisp のマクロはちょっと毛色が変わっています。Ｃ言語のマクロは、記号を定義した文字列に置き換えるという機能です。これに対して Lisp のマクロは、まさに Lisp らしいといえる機能を持っています。Ｃ言語との対比でいえば、「S 式を置き換える」と表現することができます。
それでは、Clojure におけるマクロの使い方を説明しましょう。Lisp ではマクロを関数のように定義します。マクロを定義するには defmacro を使います。
defmacro マクロ名 [仮引数 ...] Ｓ式 ...
defmacro の構文は defn と同じです。defmacro で定義されたマクロは、次のような特徴を持ちます。
この 2 番目の機能が Lisp におけるマクロの特徴です。これを図に示すと、次のようになります。
[Ｓ式] -- 評価 --> [新しいＳ式] -- 評価 --> [マクロの返り値]
(マクロ展開)
図 : マクロの動作
S 式を評価することで新しい S 式を組み立てます。この部分がマクロ展開に相当します。そして、その S 式を評価した値がマクロの返り値となります。S 式を組み立てるということはプログラムを作ることと同じです。これは、リストにプログラムとデータの 2 つの役割を持たせている Lisp だからこそ可能なことなのです。
まず、マクロと関数の違いを理解するために、数を 2 乗する処理をマクロと関数で作ってみましょう。関数は簡単ですね。
リスト : 数を 2 乗する関数 (defn square [x] (* x x))
マクロは次のように定義します。
リスト : 数を 2 乗するマクロ (defmacro m-square [x] (list '* x x))
マクロ名は m-square としました。それでは、引数に (+ 1 2) を与えて m-square を評価してみます。
(m-square (+ 1 2))
仮引数 x に (+ 1 2) がセット (評価されないことに注意)
マクロの本体 (list '* x x) を評価する
=> (* (+ 1 2) (+ 1 2)) (Ｓ式が組み立てられる)
=> 9 (Ｓ式を評価した結果)
図 : マクロの実行
関数であれば引数 (+ 1 2) が評価されて、その返り値である 3 が square に渡されますね。マクロの場合、引数は評価されないので、仮引数 x には S 式である (+ 1 2) がそのままセットされます。
次に、マクロ本体を評価します。マクロを使いこなすポイントですが、まず評価したい S 式を組み立てることを考えます。最初の評価で S 式を組み立て、それを評価することで目的の処理を実現するのがマクロなのです。
この場合、引数の 2 乗する (* x x) という S 式を作ればいいわけです。list は引数を要素とする新しいリストを返す関数でしたね。この場合、シンボル * と x の値である (+ 1 2) が要素となったリストが返されます。
これでマクロ展開が終了しました。マクロの仮引数は、マクロ展開されるときだけ有効です。マクロ展開されたＳ式を評価するときは、それらの値は破棄されます。あとは、この S 式を評価して 9 という値が結果となります。
次に示す関数 foo をを引数に与えて square と m-square を評価すると、関数とマクロの違いがよくわかると思います。
user=> (defn foo [x] (printf "%d " x) x) #'user/foo user=> (square (foo 2)) 2 4 user=> (m-square (foo 2)) 2 2 4
関数 square は、引数が評価されるので 2 が 1 回だけ出力されます。ところが m-square では、引数は評価されずに渡されて S 式 (* (foo 2) (foo 2)) が組み立てられます。その後、この S 式が評価されるので 2 が 2 回出力されるのです。
ところで、昔の Lisp 処理系では、引数を評価するタイプを EXPR 型や SUBR 型、引数を評価しないタイプを NEXPR 型や FSUBR 型と呼び、ユーザーが NEXPR 型の関数を定義することができました。Common Lisp, Scheme, Clojure など近代的な Lisp 処理系の場合、ユーザーが定義できるのは関数とマクロだけです。特殊形式のような関数を定義する場合はマクロを使うことになります。
マクロを実行する場合、必ずマクロ展開が行われるため、通常の関数よりも実行時間は遅くなります。だったら、NEXPR 型の関数を定義できるようにした方が実行速度の点で有利なはずです。ところが、近代的な Lisp 処理系では必要最低限の特殊形式を定義し、よく使われる制御構造はマクロで定義されています。これではインタプリタでの動作が遅くなります。
では、なぜ実行速度が遅くなるのにマクロを使っているのでしょう。それは、近代的な Lisp 処理系がコンパイラの使用を前提としているからです。たとえば、Clojure はプログラムを Java のバイトコードにコンパイルします。今の実用的な Lisp 処理系のほとんどは、プログラムをバイトコードまたはネイティブコードにコンパイルすることができます。
プログラムでマクロを呼び出している場所は、コンパイル時にマクロ展開されるため、コンパイル済みのコードにはマクロ呼び出しがなくなってしまうのです。つまり、コンパイル済みのコードは、マクロを呼び出す処理とマクロ展開の処理がなくなることにより、確実にインタプリタよりも高速に実行することができるのです。逆にいえば、コンパイラを使わないとマクロを効果的に使うことはできません。ご注意くださいませ。
今度は、もう少し複雑な例を見てみましょう。リストをスタックとして操作する関数をマクロで定義してみます。Clojure にはコレクションを操作する関数 push と pop が用意されているので、マクロ名は my-push! と my-pop! にします。my-push! とmy-pop! は引数にスタックを格納している変数を受け取り、その変数の値を破壊的に修正します。my-push! は次のようになります。
リスト : my-push! (defmacro my-push! [x place] (list 'swap! place 'conj x))
それでは、実際に試してみましょう。
user=> (def a (atom '())) #'user/a user=> (my-push! 10 a) (10) user=> @a (10) user=> (my-push! 20 a) (20 10) user=> @a (20 10)
最初に変数 a を (atom '()) に初期化しておきます。my-push! は list を使って S 式を組み立てます。place には a が、x には 10 がセットされているので、(swap! a conj 10) という S 式が組み立てられます。この S 式が再度評価されて、変数 a に (10) がセットされます。マクロですから引数は評価されません。
my-pop! も同様に実現できます。
リスト : my-pop!
(defmacro my-pop! [place]
(list 'let
['x (list 'first (list 'deref place))]
(list 'swap! place 'pop)
'x))
list を多用しているため複雑になってしまいましたが、これで let の構文を組み立てることができます。もっと簡単な定義方法もあるので心配しないでください。
それでは、実際に試してみましょう。
user=> (def a (atom '(30 20 10))) #'user/a user=> @a (30 20 10) user=> (my-pop! a) 30 user=> @a (20 10) user=> (my-pop! a) 20 user=> @a (10) user=> (my-pop! a) 10 user=> @a ()
(my-pop! a) は (let [x (first (deref a))] (swap! a pop) x) という S 式に展開され、この S 式が評価されます。ちなみに、マクロ展開の結果は関数 macroexpand と macroexpand-1 を使って確認することができます。
macroexpand form macroexpand-1 form
macroexpand-1 はマクロを 1 回だけ展開します。もしも、マクロ定義の中で他のマクロが使用されている場合、そのマクロは展開されません。macroexpand はマクロを最後まで展開するので、マクロ定義以外のマクロも展開されます。
それでは (my-pop! a) を macroexpand-1 で展開してみましょう。
user=> (macroexpand-1 '(my-pop! a)) (let [x (first (deref a))] (swap! a pop) x)
このように、マクロ展開の結果を確認することができます。
ところで、(my-push! a x) をマクロ展開すると (swap! a conj x) になります。展開後の S 式に x が含まれていますね。この x は、どのように評価されるのでしょうか。次の例を見てください。
(loop [x 0] (loop [x 0]
(cond (cond
(< x 5) (my-push! a x) -- マクロ展開 --> (< x 5) (swap! a conj x)
:else (recur (inc x)))) :else (recur (inc x))))
図 : my-push! の実行環境
マクロ展開された S 式は、そのマクロを置き換えた状態で評価されます。上の例では、loop / recur の中で my-push! が評価されますが、この部分をマクロ展開後の S 式に置き換えて評価するのです。したがって、変数 x は loop で定義された局所変数として扱われます。
関数呼び出しでは、関数の仮引数やその中で定義された変数を局所変数として扱いますが、それ以外の変数は大域変数として扱われます。ところがマクロの場合、マクロ展開時には関数呼び出しと同じ規則が適用されますが、展開後の S 式を評価するときは、マクロ呼び出し時に定義されている局所変数が有効になるのです。
それでは、次の例はどうなるのでしょうか。
(def x (atom '(1 2 3 4 5)))
(loop [n 0] (loop [n 0]
(cond (cond
(< n 5)
(< n 5) (my-pop! x) (let [x (first (deref x))] ;
(swap! x pop) ; マクロ展開
x) ;
:else (recur (inc n)))) :else (recur (+ n 1))))
図 : my-pop! の実行環境
大域変数 x にリストをセットし、my-pop! で取り出します。my-pop! をマクロ展開すると、my-pop! で定義している局所変数 x が大域変数 x を隠蔽するため、このマクロは正しく動作しません。このように、マクロはマクロ展開した後で変数名が衝突することがあるのです。これがマクロの欠点で、「変数捕捉 (variable capture)」といいます。
この場合、変数名が衝突しないように新しいシンボルを作成して局所変数として使います。関数 gensym は既存のシンボルと衝突しない新しいシンボルを作成して返します。
一般に、Lisp / Scheme はシンボルを管理するための「表」を持っています。ここでは「シンボル表」と呼ぶことにしましょう。普通のシンボルは、このシンボル表に登録されています。gensym はシンボル表に存在しないシンボルを新しく作成するので、既存のシンボルと衝突することはありません。Clojure での実装方法はわかりませんが、リファレンスによると「gensym はユニークな名前を持つ新しいシンボルを返す」とのことです。
簡単な例を示しましょう。
user=> (gensym) G__3 user=> (gensym "ABC") ABC6
Clojure の場合、引数なしで gensym を呼び出すと、生成されるシンボル名は "G__ + 数字" になります。gensym に文字列を指定すると、シンボル名は "文字列 + 数字" になります。
gensym で生成されるシンボルは、それ以前の S 式で使われているシンボルと異なるわけですから、let の局所変数をこのシンボルで置き換えれば、他の変数と衝突することはなくなります。
gensym を使うと、my-pop! は次のようになります。
リスト : my-pop! の改良
(defmacro my-pop!' [place]
(let [x (gensym)]
(list 'let
[x (list 'first (list 'deref place))]
(list 'swap! place 'pop)
x)))
まず最初に、let で局所変数 x を用意し、ここに gensym で生成したシンボルをセットします。次に、この x を使ってマクロ展開する S 式を組み立てます。これは今までのマクロ定義において、x の前に付けたクォート ( ' ) を外して、x を評価するようにします。これで、マクロで使用する局所変数が、他の変数と衝突することを防ぐことができます。
gensym を使った my-pop! のマクロ展開は次のようになります。
(def x (atom '(1 2 3 4 5)))
(loop [n 0] (loop [n 0]
(cond (cond
(< n 5)
(< n 5) (my-pop!' x) (let [G__3 (first (deref x))] ;
(swap! x pop) ; マクロ展開
G__3) ;
:else (recur (inc n)))) :else (recur (+ n 1))))
図 : my-pop!’ の実行環境
define-macro でマクロ展開されるのは最後の S 式だけなので、gensym でシンボルを生成する処理はマクロ展開されませんが、生成されたシンボル G__3 を使って S 式が組み立てられるわけです。これで変数捕捉を回避することができます。
ところで、マクロを定義するとき、S 式を組み立てるため list や cons をたくさん使うことになり少々面倒です。実は、「シンタックスクォート ( ` )」という機能を使うと、S 式を簡単に組み立てることができます。Common Lisp ではバッククォートと呼ばれています。
シンタックスクォートはクォート ( ' ) と同様に引数の評価を行いません。ですが、シンタックスクォートの中でアンクォート ( ~ ) で始まる S 式があると、その S 式を評価した値で置き換えられます。なお、Common Lisp ではカンマ ( , ) を使います。簡単な例を示しましょう。
user=> (def v 'pen) #'user/v user=> `(this is a v) (user/this user/is user/a user/v) user=> `(this is a ~v) (user/this user/is user/a pen)
変数 v にはシンボル pen がセットされています。次の S 式の中で ~v は v を評価した値、つまり pen に置き換わるのです。また、S 式の評価結果がリストの場合は、スプライシングアンクォート (~@) を使うことができます。~@ を使うと、リストをはずした値と置き換わります。~@ を使う場合、値がリストでなければエラーになります。Common Lisp では ,@ を使います。
次の例を見てください。
user=> (def v '(pen)) #'user/v user=> `(this is a ~v) (user/this user/is user/a (pen)) user=> `(this is a ~@v) (user/this user/is user/a pen)
今度は変数 v にリスト (pen) がセットされました。次の S 式の中で ^v は (pen) に置き換わります。そして、その次の S 式の中では、~@v は pen に置き換わるのです。それから、~ や ~@ はシンタックスクォートの中でしか使うことができません。ほかの S 式の中で評価した場合はエラーとなります。ご注意くださいませ。
それではバッククォートを使って my-push! と my-pop! を書き直してみましょう。
リスト : my-push! と my-pop! の改良
(defmacro my-push! [x place]
`(swap! ~place conj ~x))
(defmacro my-pop! [place]
`(let [x# (first (deref ~place))]
(swap! ~place pop)
x#))
my-pop! では、変数 x の後ろに # がついています。これを auto-gensym といいます。後ろに # を付けたシンボルは、gensym で生成されたシンボルに自動的に置き換えられます。これで変数の衝突を回避することができます。
それでは実際に試してみましょう。
user=> (def x (atom '())) #'user/x user=> (dotimes [i 5] (my-push! (* i 10) x)) nil user=> @x (40 30 20 10 0) user=> (my-pop! x) 40 user=> (my-pop! x) 30 user=> (my-pop! x) 20 user=> (my-pop! x) 10 user=> (my-pop! x) 0 user=> @x ()
このように、list を使うよりもシンタックスクォートの方が、どんな S 式が組み立てられて評価されるのかよくわかると思います。ですが、関数に比べるとマクロは理解するのが難しいですね。そのマクロがどんなことをするのか、きちんとコメントを書くことをおススメします。
今回は「たらいまわし関数」を例題にして、「メモ化」と「遅延評価」について簡単に説明します。
最初に「たらいまわし関数」について説明します。次のリストを見てください。
リスト : たらいまわし関数
(defn tarai [x y z]
(if (<= x y)
y
(tarai (tarai (dec x) y z) (tarai (dec y) z x) (tarai (dec z) x y))))
(defn tak [x y z]
(if (<= x y)
z
(tak (tak (dec x) y z) (tak (dec y) z x) (tak (dec z) x y))))
関数 tarai や tak は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。
関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz, Clojure (version 1.12.0) です。
tarai 14 7 0 : 2.65 [s] tak 22 11 0 : 2.91 [s]
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数が遅いのは、同じ値を何度も計算しているためです。この場合、「表 (table)」を使って処理を高速化することができます。同じ値を何度も計算することがないように、計算した値は表に格納しておいて、2 回目以降は表から計算結果を求めるようにします。このような手法を「表計算法」とか「メモ化 (memoization または memoisation)」といいます。
Clojure の場合、メモ化はマップを使うと簡単です。マップを使うと、たらいまわし関数のメモ化は次のようになります。
リスト : たらいまわし関数のメモ化 (1)
;; メモ用のマップ
(def table (atom (hash-map)))
;; たらいまわし関数
(defn tarai-memo [x y z]
(let [key (list x y z)]
(or (get @table key)
(let [value (if (<= x y)
y
(tarai-memo (tarai-memo (dec x) y z)
(tarai-memo (dec y) z x)
(tarai-memo (dec z) x y)))]
(swap! table assoc key value)
value))))
関数 tarai-memo の値を格納するマップを大域変数 table に用意します。マップを更新していくので、atom で包んでいることに注意してください。tarai-memo は引数 x, y, z を要素とするリストを作り、それをキーとしてマップ table を検索します。table に key があればその値を返します。そうでなければ、値 value を計算して table にセットし、その値を返します。
ところで、ハッシュ表は局所変数に格納することもできます。次のリストを見てください。
リスト : たらいまわし関数のメモ化 (2)
(def tak-memo
(let [table (atom (hash-map))]
(letfn
[(tak [x y z]
(let [key (list x y z)]
(or (get @table key)
(let [value (if (<= x y)
z
(tak (tak (dec x) y z)
(tak (dec y) z x)
(tak (dec z) x y)))]
(swap! table assoc key value)
value))))]
tak)))
let でマップ table を定義します。その中で、たらいまわし関数 tak を局所関数として定義します。局所関数 tak の処理内容は tarai-memo と同じですが、x <= y のときは z を返します。最後に tak を返します。この返り値を tak-memo にセットします。マップ table が生成されるのは、tak-memo に関数をセットするときの一回だけです。これで、その関数専用のマップを局所変数に用意することができます。
このように関数をメモ化することは簡単にできますが、メモ化を行うたびに関数を修正するのは面倒です。このような場合、関数をメモ化する「メモ化関数」があると便利です。Clojure にはメモ化関数 memoize が用意されていますが、私達でも簡単にプログラムすることができます。メモ化関数については参考文献『計算機プログラムの構造と解釈 第二版 3.3.3 表の表現』に詳しい説明があります。興味のある方は参考にしてください。
プログラムは次のようになります。
リスト : メモ化関数
(defn memoize' [func]
(let [table (atom (hash-map))]
(fn [& args]
(or (get @table args)
(let [value (apply func args)]
(swap! table assoc args value)
value)))))
(def tarai (memoize' tarai))
(def tak (memoize' tak))
名前は memoize' としました。関数 memoize' は関数 func を引数に受け取り、それをメモ化した関数を返します。memoize' が返す関数はクロージャなので、memoize' の引数 func や局所変数 table にアクセスすることができます。また、無名関数の引数 args は可変個の引数を受け取るように定義します。これで複数の引数を持つ関数にも対応することができます。
args の値は引数を格納したリストになるので、これをキーとして扱います。マップ table に値がなければ、関数 func を呼び出して値を計算し、それを table にセットして値を返します。最後に、tak と tarai の値を def で再定義します。そうしないと、関数 tak, tarai の中で再帰呼び出しするとき、メモ化した関数を呼び出すことができません。ご注意ください。
それでは実際に実行してみましょう。
(tarai 120 60 0) : 0.127 [s] (tak 120 60 0) : 0.121 [s]
このように、引数の値を増やしても高速に実行することができます。メモ化の効果は十分に出ていると思います。また、同じ計算を再度実行すると、メモ化の働きにより値をすぐに求めることができます。
関数 tarai は「遅延評価 (delayed evaluation または lazy evaluation)」を行う処理系、たとえば関数型言語の Haskell では高速に実行することができます。また、Scheme や Clojure でも delay と force を使って遅延評価を行うことができます。
tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。
今回は Shiro さんの WiLiKi にある『Scheme:たらいまわしべんち』を参考に、プログラムを作ってみましょう。まず最初に delay と force を説明します。
Clojure の場合、delay はマクロで、引数 s-exp は評価されません。delay の返り値を Scheme ではプロミス (promise) といいます。本ページでは Scheme に合わせてプロミスと呼ぶことにします。s-exp はこのプロミスに保存されていて、(force promise) を実行すると、s-exp を評価してその値を返します。
このとき、値がプロミスに保存されることに注意してください。再度 (force rpomise) を実行すると、保存された値が返されます。なお、Clojure では force のほかに deref や '@ + 変数名' でプロミスを評価することができます。
簡単な使用例を示しましょう。
user=> (def a (delay (+ 10 20)))
#'user/a
user=> a
#object[clojure.lang.Delay 0x543e593 {:status :pending, :val nil}]
user=> (force a)
30
(delay (+ 10 20)) の返り値を変数 a にセットします。このとき、S 式 (+ 10 20) は評価されていません。(force a) を評価すると、S 式 (+ 10 20) を評価して値 30 を返します。また、(force a) を再度実行すると、同じ式を再評価することなく値を求めることができます。次の例を見てください。
user=> (def b (delay (do (println "oops!") (+ 10 20)))) #'user/b user=> (force b) oops! 30 user=> (force b) 30 user=> (deref b) 30 user=> @b 30
最初に (force b) を実行すると、S 式 (do (println "oops!") (+ 10 20)) が評価されるので、画面に oops! が表示されます。次に、(force b) を実行すると、式を評価せずに保存した値を返すので oops! は表示されません。
delay と force を使うと、たらいまわし関数は次のようになります。
リスト : delay と force による遅延評価
(defn tarai1 [x y z]
(if (<= x y)
y
(let [zz (force z)]
(tarai1 (tarai1 (dec x) y (delay zz))
(tarai1 (dec y) zz (delay x))
(delay (tarai1 (dec zz) x (delay y)))))))
遅延評価したい処理をプロミスにして引数 z に渡します。そして、x > y のときに引数 z のプロミスを force で評価します。すると、プロミス内の処理が評価されて z の値を求めることができます。たとえば、(delay 0) を z に渡す場合、(force z) とすると返り値は 0 になります。(delay x) を渡せば、x に格納されている値が返されます。(delay (tarai1 ...)) を渡せば tarai1 が実行されて、その値を求めることができます。
それでは、実際に実行してみましょう。
(tarai1 120 60 (delay 0)) closure : 0.017 [s]
tarai の場合、遅延評価の効果はとても大きいですね。
ところで、delay と force がなくても、クロージャを使って遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
(defn tarai2 [x y z]
(if (<= x y)
y
(let [zz (z)]
(tarai2 (tarai2 (dec x) y (fn [] zz))
(tarai2 (dec y) zz (fn [] x))
(fn [] (tarai2 (dec zz) x (fn [] y)))))))
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、(fn [] 0) を z に渡す場合、(z) とすると返り値は 0 になります。(fn [] x) を渡せば、x に格納されている値が返されます。(fn [] (tarai2 ...)) を渡せば、関数 tarai2 が実行されてその値が返されるわけです。
それでは、実際に実行してみましょう。
(tarai2 120 60 (fn [] 0)) closure : 0.002 [s]
クロージャの方が delay と force よりも速いですね。delay と force は処理が複雑になる分だけ、クロージャを使った遅延評価よりも実行速度は遅くなるようです。