前回は Lisp の伝統的なマクロについて説明しました。今回は Scheme の健全なマクロについて説明します。なお、最近 Scheme は仕様書が R5RS から R6RS に改訂され、マクロにも新しい機能が追加されましたが、このドキュメントで取り上げるマクロは R5RS の範囲とさせていただきます。あしからずご了承ください。
Scheme の「健全なマクロ (hygienic macro) 」は syntax-rules という独自のパターン言語を使ってマクロを記述します。そして、define-sytax で大域的なマクロを、let-sytax と letrec-syntax で局所的なマクロを定義します。sytax-rules の構文を下図に示します。
(syntax-rules (literal ...) (pattern_1 template_1) (pattern_2 template_2) ... (pattern_n template_n)) 図 : sytax-rules の構文
pattern は S 式の入力パターンを表します。S 式がパターンとマッチングする場合、それに対応するテンプレート template に変換します。パターンは、リスト、識別子 (literal)、定数、パターン変数、省略子 (...) などから構成されます。通常、パターンはリストの先頭にマクロ名を書き、そのあとにパターン変数などを記述します。なお、マクロ名はアンダーバー ( _ ) で代用することができます。
テンプレートはパターン変数、識別子、省略子などを使ってマクロ展開する S 式を記述します。入力された S 式とパターンがマッチングすると、パターン変数に対応する値が束縛され、その値を使って S 式が組み立てられます。このため、伝統的なマクロのように、バッククオートを使う必要はありません。
おおざっぱな説明ですが、あとは習うより慣れろということで、簡単なマクロを作っていきましょう。詳細な説明は Scheme の仕様書 (R5RS) をお読みくださいませ。
簡単な例として、数を 2 乗する処理をマクロで記述します。
リスト : 数を 2 乗するマクロ
(define-syntax m-square
(syntax-rules ()
((_ x) (* x x))))
マクロ名は m-square で、x がパターン変数です。このパターンは S 式 (m-square s-exp) にマッチングします。たとえば、S 式 (m-square (+ 1 2)) は (_ x) とマッチングし、パターン変数 x の値は (+ 1 2) になります。テンプレートは (* x x) なので、(* (+ 1 2) (+ 1 2)) という S 式にマクロ展開されます。
それでは実行してみましょう。
gosh> (m-square (+ 1 2)) 9 gosh> (m-square (begin (display "oops") (+ 1 2))) oopsoops9
m-square は伝統的なマクロと同じく、S 式 (* (+ 1 2) (+ 1 2)) が組み立てられ、それを評価した結果が 9 になります。oops を表示させてみると、引数の S 式が 2 回評価されていることがわかります。
次はスタックを操作するマクロ my-push! と my-pop! を作りましょう。次のリストを見てください。
リスト : スタックの操作
; データの追加
(define-syntax my-push!
(syntax-rules ()
((_ place x) (set! place (cons x place)))))
; データの取得
(define-syntax my-pop!
(syntax-rules ()
((_ place)
(let ((x (car place)))
(set! place (cdr place))
x))))
my-push! と my-pop! は簡単です。たとえば、(my-push a 10) はパターン変数 place に a がセットされ、x に 10 がセットされます。テンプレートは (set! a (cons 10 a)) になり、この S 式が評価されてリストの先頭に 10 が追加されます。(my-pop! a) はパターン変数 place に a がセットされるので、テンプレートは次のように展開されます。
(let ((x (car a)) (set! a (cdr a)) x)
この S 式が評価されるので、my-pop! はリストの先頭要素を取り除き、その値を返します。
それでは実行してみましょう。
gosh> (define a '()) a gosh> (my-push! a 10) (10) gosh> (my-push! a 20) (20 10) gosh> (my-pop! a) 20 gosh> (my-pop! a) 10 gosh> a ()
my-pop! では let で局所変数 x を使っていますが、Scheme の健全なマクロは変数名の衝突 (変数捕捉) を気にしなくても大丈夫です。次の例を見てください。
gosh> (define x '(1 2 3 4 5)) x gosh> (let loop ((n 0)) (cond ((< n 5) (display (my-pop! x)) (loop (+ n 1))))) 12345#<undef>
伝統的なマクロでは、let で局所変数 x を定義すると大域変数 x を隠蔽してしまいますが、健全なマクロは変数捕捉を回避してくれるので正常に動作します。これが健全なマクロの良いところです。
もう一つ、伝統的なマクロとの違いを示しましょう。次のリストを見てください。
リスト : マクロ arithmetic-if
(define-syntax arithmetic-if
(syntax-rules ()
((_ test neg zero pos)
(let ((var test))
(cond ((< var 0) neg)
((= var 0) zero)
(else pos))))))
マクロ arithmetic-if は述語 test の返り値が負ならば引数 neg を、0 ならば引数 zero を、正ならば引数 pos を評価します。簡単な実行例を示します。
gosh> (arithmetic-if -10 (print -1) (print 0) (print 1)) -1 #<undef> gosh> (arithmetic-if 0 (print -1) (print 0) (print 1)) 0 #<undef> gosh> (arithmetic-if 10 (print -1) (print 0) (print 1)) 1 #<undef>
伝統的なマクロは標準関数 < を書き換えると arithmetic-if は正常に動作しなくなりますが、健全なマクロならば大丈夫です。次の例を見てください。
gosh> (let ((< (lambda (x y) (> x y)))) (arithmetic-if 10 (print -1) (print 0) (print 1))) 1 #<undef> gosh> (let ((< (lambda (x y) (> x y)))) (arithmetic-if -10 (print -1) (print 0) (print 1))) -1 #<undef>
正常に動作していますね。このように、伝統的なマクロの問題点は健全なマクロを使うと回避することができます。
識別子を定義すると、それをキーワードとして利用することができます。たとえば、cond や case には else 節がありますが、else を識別子として定義すると、それをキーワードとしてマクロ定義に使うことができます。
簡単な例として、if に then と else というキーワードを追加してみましょう。マクロ名は my-if とします。簡単な使用例を示します。
gosh> (my-if #t then 'OK else 'NG) OK gosh> (my-if #f then 'OK else 'NG) NG gosh> (my-if #t then 'OK) OK gosh> (my-if #f else 'NG) NG
プログラムは次のようになります。
リスト : if - then - else のマクロ定義
(define-syntax my-if
(syntax-rules (then else)
((_ test then e1 else e2) (if test e1 e2))
((_ test then e1) (if test e1 #f))
((_ test else e1) (if test #f e1))))
syntax-rules の次のリストに、識別子 then と else を定義します。パターンに識別子が含まれている場合、識別子は自分自身とマッチングします。最初のパターンは then と else の両方がある場合で、(if test e1 e2) に変換します。次のパターンは then だけがある場合で、(if test e1 #f) に変換します。最後のパターンは else だけがある場合で、(if test #f e1) に変換します。
健全なマクロは再帰定義することもできます。簡単な例として and をマクロ定義してみましょう。次のリストを見てください。
リスト : and のマクロ定義
(define-syntax my-and
(syntax-rules ()
((_) #t)
((_ a) a)
((_ a b ...) (if a (my-and b ...) #f))))
マクロ名は my-and とします。最初のパターンは引数がない場合とマッチングします。この場合、テンプレートは #t になります。次のパターンは引数が一つの場合とマッチングします。この場合、引数 a の評価結果が my-and の返り値になるので、テンプレートは a になります。
最後のパターンは引数が 2 個以上の場合とマッチングします。第 1 引数はパターン変数 a とマッチングし、第 2 引数は b とマッチングします。残りの引数は省略子 ( ... ) とマッチングします。このように、省略子を使うと可変個の引数を取るマクロを定義することができます。テンプレートは (if a (my-and b ...) #f) です。if の then 節で my-and を再帰呼び出しします。これで、b と残りの引数に対して my-and のマクロ展開が行われます。なお、パターン引数 b を省略するとエラーになります。ご注意ください。
それでは実行してみましょう。
gosh> (my-and) #t gosh> (my-and 1) 1 gosh> (my-and 1 2) 2 gosh> (my-and 1 2 3) 3 gosh> (my-and 1 2 #f 3) #f
正常に動作していますね。
ところで、健全なマクロは万能ではなく、syntax-rules だけでは簡単に実現できない場合もあります。たとえば、Common Lisp の block のように、評価中の S 式から脱出して値を返すマクロを考えてみましょう。
Common Lisp の block は return-from tag-name で block から脱出するのですが、今回は tag-name を評価すると block から脱出することにします [*1]。この処理は継続を使うと簡単です。プログラムは次のようになります。
リスト : マクロ block の定義
(define-syntax block
(syntax-rules ()
((_ tag e1 ...)
(call/cc
(lambda (tag) e1 ...)))))
(block tag e1 ...) を (call/cc (lambda (tag) e1 ...)) に変換するだけです。これで tag を評価すると block から脱出することができます。簡単な実行例を示します。
gosh> (block return (dotimes (x 10) (if (< 5 x) (return #f) (print x)))) 0 1 2 3 4 5 #f
それでは、tag-name の指定を省略して、block の中で return が評価されたら脱出するようにプログラムを修正してみましょう。簡単だと思われるかもしれませんが、次のようにプログラムしても動作しません。
リスト : マクロ block1 の定義 (間違い版)
(define-syntax block1
(syntax-rules ()
((_ e1 ...)
(call/cc
(lambda (return) e1 ...)))))
ラムダ式の引数 return は自由変数なので、健全なマクロは「変数捕捉」が起きないように S 式をマクロ展開します。このため、block の中では return という名前で継続にアクセスすることができなくなるのです。実際に実行すると次のようになります。
gosh> (block1 (dotimes (x 10) (if (< 5 x) (return #f) (print x)))) 0 1 2 3 4 5 *** ERROR: unbound variable: return
このような場合は伝統的なマクロを使うとうまくいきます。プログラムは次のようになります。
リスト : マクロ block1 の定義 (define-macro (block1 . args) `(call/cc (lambda (return) ,@args)))
伝統的なマクロは S 式を単純に置換するだけなので、block の中では return という名前で継続にアクセスすることができます。それでは実行してみましょう。
gosh> (block1 (dotimes (x 10) (if (< 5 x) (return #f) (print x)))) 0 1 2 3 4 5 #f
正常に動作していますね。伝統的なマクロの弱点である「変数捕捉」も、使い方によっては役に立つこともあります。伝統的なマクロの使い方は、Common Lisp ですが下記参考文献で詳しく説明されています。マクロに興味のある方は一読することをお勧めします。
今回は「たらいまわし関数」を例題にして、「メモ化」と「遅延評価」について説明します。なお、このドキュメントは拙作のページ Algorithms with Python 再帰定義 (たらいまわし関数) のプログラムを Scheme で書き直したものです。内容は重複していますが、ご了承くださいませ。
最初に「たらいまわし関数」について説明します。次のリストを見てください。
リスト : たらいまわし関数
(define (tarai x y z)
(if (<= x y)
y
(tarai (tarai (- x 1) y z) (tarai (- y 1) z x) (tarai (- z 1) x y))))
(define (tak x y z)
(if (<= x y)
z
(tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))))
関数 tarai や tak は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。
関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Windows XP, celeron 1.40 GHz, Gauche (version 0.8.14) です。
tarai 12 6 0 : 2.42 [s] tak 18 9 0 : 2.89 [s]
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数が遅いのは、同じ値を何度も計算しているためです。この場合、表 (table) を使って処理を高速化することができます。同じ値を何度も計算することがないように、計算した値は表に格納しておいて、2 回目以降は表から計算結果を求めるようにします。このような手法を「表計算法」とか「メモ化 (memoization または memoisation) 」といいます。
Scheme の場合、メモ化は「ハッシュ表 (hash table) 」を使うと簡単です。Scheme の仕様書 (R5RS) にハッシュ表は定義されていませんが、多くの Scheme 処理系でハッシュ表を使うことができます。もちろん、Gauche にもハッシュ表が用意されています。ここで簡単にハッシュ表の使い方を説明しましょう。なお、ハッシュ表の仕組みについては拙作のページ ヒープとハッシュ法 をお読みください。
ハッシュ表を作るには関数 make-hash-table を使います。
引数 type はハッシュ表の種類を表します。type はシンボルで指定します。ハッシュ表の種類を下表に示します。
| タイプ | 機能 |
|---|---|
| eq? | キーを eq? で比較する |
| eqv? | キーを eqv? で比較する |
| equal? | キーを equal? で比較する |
| string=? | キーを string=? で比較する (キーは文字列) |
type を省略した場合、キーは eq? で比較されます。
ハッシュ表の読み書きは関数 hash-table-get と hash-table-put! で行います。
hash-table-get は hash-table から key を検索し、格納されているデータを返します。キーが見つからない場合は default を返しますが、default を省略した場合はエラーが送出されます。hash-table-put! は hash-table に key と value を格納します。すでに key が存在する場合は value で上書きされます。
関数 hash-table-delete! はハッシュ表からキーと値を削除します。関数 hash-table-clear! はハッシュ表を空にします。
hash-table-delete! は hash-table の key とそれに対応する値を削除します。削除できた場合は #t を、削除する key が見つからない場合は #f を返します。hash-table-clear! は hash-table からすべてのキーと値を削除します。
ハッシュ表にキーがあるか調べるには関数 hash-table-exists? を使います。
hash-table に key があれば #t を、なければ #f を返します。
簡単な例を示しましょう。
gosh> (define ht (make-hash-table 'string=?)) ht gosh> (hash-table-put! ht "abc" 10) #<undef> gosh> (hash-table-put! ht "def" 20) #<undef> gosh> (hash-table-get ht "abc" #f) 10 gosh> (hash-table-get ht "def" #f) 20 gosh> (hash-table-get ht "ghi" #f) #f gosh> (hash-table-exists? ht "abc") #t gosh> (hash-table-delete! ht "abc") #t gosh> (hash-table-exists? ht "abc") #f
このほかにも便利な関数が用意されています。詳細は Gauche のユーザーリファレンスをお読みください。
ハッシュ表を使うと、たらいまわし関数のメモ化は次のようになります。
リスト : たらいまわし関数のメモ化 (1)
; メモ用のハッシュ表
(define *table* (make-hash-table 'equal?))
; たらいまわし関数
(define (tarai-memo x y z)
(let ((key (list x y z)))
(if (hash-table-exists? *table* key)
(hash-table-get *table* key)
(let ((value (if (<= x y)
y
(tarai-memo (tarai-memo (- x 1) y z)
(tarai-memo (- y 1) z x)
(tarai-memo (- z 1) x y)))))
(hash-table-put! *table* key value)
value))))
関数 tarai-memo の値を格納するハッシュ表を大域変数 *table* に用意します。関数 tarai-memo では、引数 x, y, z を要素とするリストを作り、それをキーとしてハッシュ表 *table* を検索します。キーはリストなのでハッシュ表の種類は equal? になります。*table* に key があればその値を返します。そうでなければ、値 value を計算して *table* にセットし、その値を返します。
ところで、ハッシュ表は局所変数に格納することもできます。次のリストを見てください。
リスト : たらいまわし関数のメモ化 (2)
(define tak-memo
(let ((table (make-hash-table 'equal?)))
(letrec ((tak
(lambda (x y z)
(let ((key (list x y z)))
(if (hash-table-exists? table key)
(hash-table-get table key)
(let ((value (if (<= x y)
z
(tak (tak (- x 1) y z)
(tak (- y 1) z x)
(tak (- z 1) x y)))))
(hash-table-put! table key value)
value))))))
tak)))
let でハッシュ表 table を定義します。その中で、たらいまわし関数 tak を局所関数として定義します。局所関数 tak の処理内容は tarai-memo と同じですが、x <= y のときは z を返します。最後に tak を返します。この返り値を tak-memo にセットします。ハッシュ表 table が生成されるのは、tak-memo に関数をセットするときの一回だけです。これで、その関数専用のハッシュ表を局所変数に用意することができます。
このように関数をメモ化することは簡単にできますが、メモ化を行うたびに関数を修正するのは面倒です。このような場合、関数をメモ化する「メモ化関数」があると便利です。メモ化関数については Structure and Interpretation of Computer Programs (SICP) 3.3.3 Representing Tables に詳しい説明があります。
プログラムは次のようになります。
リスト : メモ化関数
(define (memoize func)
(let ((table (make-hash-table 'equal?)))
(lambda args
(if (hash-table-exists? table args)
(hash-table-get table args)
(let ((value (apply func args)))
(hash-table-put! table args value)
value)))))
; たらいまわし関数
(define (tarai x y z)
(if (<= x y)
y
(tarai (tarai (- x 1) y z) (tarai (- y 1) z x) (tarai (- z 1) x y))))
(define (tak x y z)
(if (<= x y)
z
(tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))))
; メモ化
(set! tak (memoize tak))
(set! tarai (memoize tarai))
関数 memoize は関数 func を引数に受け取り、それをメモ化した関数を返します。memoize が返す関数はクロージャなので、memoize の引数 func や局所変数 table にアクセスすることができます。また、無名関数 lambda の引数 args は可変個の引数を受け取るように定義します。これで、複数の引数を持つ関数にも対応することができます。
args の値は引数を格納したリストになるので、これをキーとして扱います。ハッシュ表 table に値がなければ、関数 func を呼び出して値を計算し、それを table にセットして値を返します。最後に、tak と tarai の値を set! で書き換えます。そうしないと、関数 tak, tarai の中で再帰呼び出しするとき、メモ化した関数を呼び出すことができません。ご注意ください。
それでは実際に実行してみましょう。実行環境は Windows XP, celeron 1.40 GHz, Gauche (version 0.8.14) です。
tarai (192, 96, 0) : 0.39 [s] tak (192, 96, 0) : 4.89 [s]
このように、引数の値を増やしても高速に実行することができます。メモ化の効果は十分に出ていると思います。また、同じ計算を再度実行すると、メモ化の働きにより値をすぐに求めることができます。
関数 tarai は「遅延評価 (delayed evaluation または lazy evaluation) 」を行う処理系、たとえば関数型言語の Haskell では高速に実行することができます。また、Scheme でも delay と force を使って遅延評価を行うことができます。
tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。
今回は Shiro さん の WiLiKi にある Scheme:たらいまわしべんち を参考に、プログラムを作ってみましょう。まず最初に delay と force を説明します。
delay はシンタックス形式で、引数 s-exp を評価しないでプロミス (promise) というデータを返します。s-exp はこのプロミスに保存されていて、(force promise) を実行すると、s-exp を評価してその値を返します。このとき、値がプロミスに保存されることに注意してください。再度 (force rpomise) を実行すると、保存された値が返されます。
簡単な使用例を示しましょう。
gosh> (define a (delay (+ 10 20))) a gosh> a #<promise 0pb91c50> gosh> (force a) 30
(delay (+ 10 20)) の返り値を変数 a にセットします。このとき、S 式 (+ 10 20) は評価されていません。(force a) を評価すると、S 式 (+ 10 20) を評価して値 30 を返します。また、(force a) を再度実行すると、同じ式を再評価することなく値を求めることができます。次の例を見てください。
gosh> (define b (delay (begin (display "oops!") (+ 10 20)))) b gosh> (force b) oops!30 gosh> (force b) 30
最初に (force b) を実行すると、S 式 (begin (display "oops!") (+ 10 20)) が評価されるので、画面に oops! が表示されます。次に、(force b) を実行すると、式を評価せずに保存した値を返すので oops! は表示されません。
delay と force を使うと、たらいまわし関数は次のようになります。
リスト : delay と force による遅延評価
(define (tarai1 x y z)
(if (<= x y)
y
(let ((zz (force z)))
(tarai1 (tarai1 (- x 1) y (delay zz))
(tarai1 (- y 1) zz (delay x))
(delay (tarai1 (- zz 1) x (delay y)))))))
遅延評価したい処理をプロミスにして引数 z に渡します。そして、x > y のときに引数 z のプロミスを force で評価します。すると、プロミス内の処理が評価されて z の値を求めることができます。たとえば、(delay 0) を z に渡す場合、(force z) とすると返り値は 0 になります。(delay x) を渡せば、x に格納されている値が返されます。(delay (tarai1 ...)) を渡せば tarai1 が実行されて、その値を求めることができます。
それでは、実際に実行してみましょう。実行環境は Windows XP, celeron 1.40 GHz, Gauche (version 0.8.14) です。
tarai 192 96 0 closure : 0.18 [s]
tarai の場合、遅延評価の効果はとても大きいですね。
ところで、delay と force がなくても、クロージャを使って遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
(define (tarai2 x y z)
(if (<= x y)
y
(let ((zz (z)))
(tarai2 (tarai2 (- x 1) y (lambda () zz))
(tarai2 (- y 1) zz (lambda () x))
(lambda () (tarai2 (- zz 1) x (lambda () y)))))))
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、(lambda () 0) を z に渡す場合、(z) とすると返り値は 0 になります。(lambda () x) を渡せば、x に格納されている値が返されます。(lambda () (tarai2 ...)) を渡せば、関数 tarai2 が実行されてその値が返されるわけです。
それでは、実際に実行してみましょう。実行環境は Windows XP, celeron 1.40 GHz, Gauche (version 0.8.14) です。
tarai 192 96 0 closure : 0.050 [s]
実行時間が速いので、今回は tarai 192 96 0 を 10 回実行した時間から 1 回の実行時間を求めました。クロージャの方が delay と force よりも速いですね。delay と force は処理が複雑になる分だけ、クロージャを使った遅延評価よりも実行速度は遅くなるようです。
ところで、クロージャを使わなくても、関数 tarai を高速化する方法があります。C++:language&libraries (cppll) で Akira Higuchi さん が書かれたＣ言語の tarai 関数はとても高速です。Scheme でプログラムすると次のようになります。
リスト : tarai の遅延評価
(define (tarai3 x y z)
(if (<= x y)
y
(tarai-lazy (tarai3 (- x 1) y z) (tarai3 (- y 1) z x) (- z 1) x y)))
(define (tarai-lazy x y xx yy zz)
(if (<= x y)
y
(let ((z (tarai3 xx yy zz)))
(tarai-lazy (tarai3 (- x 1) y z) (tarai3 (- y 1) z x) (- z 1) x y))))
関数 tarai-lazy の引数 xx, yy, zz で z の値を表すところがポイントです。つまり、z の計算に必要な値を引数に保持し、z の値が必要になったときに (tarai xx yy zz) で計算するわけです。実際に実行してみると tarai 192 96 0 は 0.0047 [s] になりました。Akira Higuchi さんに感謝いたします。