前の章ではマクロで実装しなければならないオペレータを何種類か論じた. この章で論じる種類の問題は,関数でも解決できるが,マクロの方が効率的になるようなものだ. 第8.2節ではある状況においてマクロを使うことの長所と短所を列挙した. 長所の中には「コンパイル時の計算処理」というものがあった. オペレータをマクロとして定義することで, 作業の一部をオペレータが展開されるときに行わせることができる場合がある. この章ではこの可能性を活用するマクロを見ていく.
第8.2章ではマクロを使って計算処理をコンパイル時に行わせる可能性を提起した.
そこでは例として,引数の平均値を返すマクロavg
を定義した.
> (avg pi 4 5) 4.047...
第\ref{fig:ShiftingComputation}図ではavg
を最初は関数として,次にマクロとして定義した.
avg
がマクロとして定義されると,length
はコンパイル時に呼ばれることになる.
マクロ版では,実行時に&rest
パラメータを操作することの負担も回避している.
多くの処理系ではavg
はマクロとして書いた方が速い.
(defun avg (&rest args) (/ (apply #'+ args) (length args))) (defmacro avg (&rest args) `(/ (+ ,@args) ,(length args)))\caption{平均値を得るとき,計算処理をコンパイル時にずらす.} \label{fig:ShiftingComputation}
展開時に引数の数を知っていることから来るような類の処理の節約は,
in
(sdfページ)で得られるような処理の節約と組み合わせることができる.
そこでは幾つかの引数の評価すら回避できたのだった.
第\ref{fig:ShiftingAndAvoiding}図には2通りのmost-of
を示した.
これは引数の過半数が真を返すならば真を返すものだ.
> (most-of t t t nil) T
(defun most-of (&rest args) (let ((all 0) (hits 0)) (dolist (a args) (incf all) (if a (incf hits))) (> hits (/ all 2)))) (defmacro most-of (&rest args) (let ((need (floor (/ (length args) 2))) (hits (gensym))) `(let ((,hits 0)) (or ,@(mapcar #'(lambda (a) `(and ,a (> (incf ,hits) ,need))) args)))))\caption{計算処理をコンパイル時にずらし,さらに回避する.} \label{fig:ShiftingAndAvoiding}
マクロ版は,in
と同様に,必要なだけの引数を評価するようなコードに展開される.
例えば(most-of (a)
(b) (c))
は次のような等価な式に展開される.
(let ((count 0)) (or (and (a) (> (incf count) 1)) (and (b) (> (incf count) 1)) (and (c) (> (incf count) 1))))
一番都合が良い場合には,ちょうど過半数の引数だけが評価される.
(defun nthmost (n lst) (nth n (sort (copy-list lst) #'>))) (defmacro nthmost (n lst) (if (and (integerp n) (< n 20)) (with-gensyms (glst gi) (let ((syms (map0-n #'(lambda (x) (gensym)) n))) `(let ((,glst ,lst)) (unless (< (length ,glst) ,(1+ n)) ,@(gen-start glst syms) (dolist (,gi ,glst) ,(nthmost-gen gi syms t)) ,(car (last syms)))))) `(nth ,n (sort (copy-list ,lst) #'>)))) (defun gen-start (glst syms) (reverse (maplist #'(lambda (syms) (let ((var (gensym))) `(let ((,var (pop ,glst))) ,(nthmost-gen var (reverse syms))))) (reverse syms)))) (defun nthmost-gen (var vars &optional long?) (if (null vars) nil (let ((else (nthmost-gen var (cdr vars) long?))) (if (and (not long?) (null else)) `(setq ,(car vars) ,var) `(if (> ,var ,(car vars)) (setq ,@(mapcan #'list (reverse vars) (cdr (reverse vars))) ,(car vars) ,var) ,else)))))\caption{コンパイル時に分かっている引数の利用.} \label{fig:UseOfArgsKnownAtCompileTime}
マクロは特定の引数の値が知られているときにも,計算処理をコンパイル時にずらせるかも知れない.
第\ref{fig:UseOfArgsKnownAtCompileTime}図にはそのようなマクロの例を示した.
関数nthmost
は数n
と数からなるリストを取り,リスト内でn
番目に大きい数を返す.
他のシーケンス用関数と同様に,最初は0番目とされる.
> (nthmost 2 '(2 6 1 5 3 4)) 4
関数版はとても単純に書かれている.
それはリストを整列させ,それを引数にnth
を呼ぶ.
sort
は破壊的なので,nthmost
は整列前にリストをコピーしている.
このように定義されると,nthmost
は2点で非効率的になる.
コンシングを起こす点と,
関心があるのは大きい順にn
個までなのに引数のリスト全体を整列させる点だ.
n
がコンパイル時に分かっていれば,この問題には別の方法で取り組める.
第\ref{fig:UseOfArgsKnownAtCompileTime}図の後半ではマクロ版のnthmost
を定義した.
このマクロが最初に行うことは,第1引数を調べることだ.
第1引数が数定数でないときには,上で見たものと同じコードに展開される.
第1引数が数定数だと,別の手段に移る.
例えば皿の上の3番目に大きいクッキーを取りたいときは,
それぞれのクッキーを順番に眺め回し,
その間ずっとそれまでに見たクッキーの内の大きい順に3個を手に取っておけばよい.
全てのクッキーを見た後は,手の中の1番小さいクッキーが求めていたものだ.
n
が小さい定数で,クッキーの総数に比例しないならば,
この方法により,最初に全てのクッキーを整列させるときよりも少ない労力で求めるクッキーが手に入る.
n
が展開時に知られている場合にはこの戦略に従う.
上のマクロは展開中にn
個の変数を生成し,nthmost-gen
を呼んで,
それぞれのクッキーを見ているときに評価されなければならないコードを生成する.
第\ref{fig:ExpansionOfNthmost}図にはマクロ展開の例を示した.
マクロnthmost
は元の関数と全く同じ動作をするが,apply
の引数として渡せない点が違っている.
マクロを使うことを正当化するのは,純粋に効率性という観点だ.
マクロ版は実行時にコンシングを起こさず,更にn
が小さい定数のときには比較回数が少なくて済む.
効率的なプログラムを得るには,このように大きなマクロを書くような骨折りが必要なのだろうか?
この場合には,恐らくそうではないだろう.
2通りのnthmost
は一般原則の例として意図されたものだ.
幾つかの引数がコンパイル時に知られているならば,マクロを使って効率のよいコードを生成できる.
恐らくこの可能性を利用するかどうかは,利益のためにどれ程の負担に耐えられるかということと,
効率的なマクロ版を書くためにどれ程の労力が必要かということに依る.
マクロ版のnthmost
は長く複雑なので,極端な状況でしか書く価値はないだろう.
しかしコンパイル時に得られる情報は,それを利用しないことに決めたときさえ含め,
常に考慮に値する要素なのだ.
(nthmost 2 nums)これは次のように展開される.
(let ((#:g7 nums)) (unless (< (length #:g7) 3) (let ((#:g6 (pop #:g7))) (setq #:g1 #:g6)) (let ((#:g5 (pop #:g7))) (if (> #:g5 #:g1) (setq #:g2 #:g1 #:g1 #:g5) (setq #:g2 #:g5))) (let ((#:g4 (pop #:g7))) (if (> #:g4 #:g1) (setq #:g3 #:g2 #:g2 #:g1 #:g1 #:g4) (if (> #:g4 #:g2) (setq #:g3 #:g2 #:g2 #:g4) (setq #:g3 #:g4)))) (dolist (#:g8 #:g7) (if (> #:g8 #:g1) (setq #:g3 #:g2 #:g2 #:g1 #:g1 #:g8) (if (> #:g8 #:g2) (setq #:g3 #:g2 #:g2 #:g8) (if (> #:g8 #:g3) (setq #:g3 #:g8) nil)))) #:g3))\caption{
nthmost
の展開形.}
\label{fig:ExpansionOfNthmost}
with-
系マクロ(第11.2節)と同様に,コンパイル時の処理のためのマクロは,
汎用ユーティリティとしてよりもある特定のアプリケーションのためのものとして書かれることが多い.
汎用ユーティリティは,コンパイル時にどれだけの情報を得られるだろうか?
それは与えられた引数の数と,場合によればそれらの値だ.
他の制約条件を使いたいならば,
それらはきっと個々のプログラムに課されたものでなければならないだろう.
例として,この章ではBézier(ベジェ)曲線の生成がマクロによりどれだけ高速化できるかを示す. Bézier曲線がインタラクティブに操作されるときは,高速に生成しなければならない. 曲線が幾つの部分から成るかがあらかじめ分かっているなら, 処理の大部分をコンパイル時に行えることが明らかになる. 曲線生成ルーチンをマクロとして書くことで,計算済みの値をコード内に織り込むことができる. これより一般的な,値を配列に保持する最適化手法よりも,こちらの方が速いはずだ.
Bézier曲線は4個の点から定義される ---2個の端点と2個の制御点だ. 2次元について考えるとき, これらの点は曲線上の点のx座標とy座標を定める方程式の媒介変数表示を定義する. 2個の端点を (x0, y0) と (x3, y3) とし,2個の制御点を (x1, y1) と (x2, y2) とすると, 曲線上の点を定義する方程式は次のようになる.
x = (x3 - 3x2 + 3x1 - x0)u3 + (3x2 - 6x1 + 3x0)u2 + (3x1 - 3x0)u + x0
y = (y3 - 3y2 + 3y1 - y0)u3 + (3y2 - 6y1 + 3y0)u2 + (3y1 - 3y0)u + y0
これらの方程式を0から1までのuのn個の値について評価すれば, 曲線上の点がn個得られる. 例えば曲線を20分割して表示したいときは, 上の方程式をu = .05, .1, ..., .95について評価することになる. 方程式をu = 0または1で評価する必要はない. u = $では開始端点(x0, y0)が,u = 1では終了端点(x3, y3)が得られるからだ.
明らかな最適化手段は,nを固定し,u,u2... をあらかじめ計算し, そしてそれらを(n-1) * 3配列に蓄えることだ. 曲線生成ルーチンをマクロとして定義することで,効率をずっと上げることができる. nがコンパイル時に知られていれば,プログラムは曲線を描くコマンドn個に展開できる. あらかじめ計算したu,u2,... は,配列に蓄えるのではなく, マクロの展開形の中に定数値としてそのまま挿入できる.
(defconstant *segs* 20) (defconstant *du* (/ 1- 0 *segs*)) (defconstant *pts* (make-array (list (1+ *segs*) 2))) (defmacro genbez (x0 y0 x1 y1 x2 y2 x3 y3) (with-gensyms (gx0 gx1 gy0 gy1 gx3 gy3) `(let ((,gx0 ,x0) (,gy0 ,y0) (,gx1 ,x1) (,gy1 ,y1) (,gx3 ,x3) (,gy3 ,y3)) (let ((cx (* (- ,gx1 ,gx0) 3)) (cy (* (- ,gy1 ,gy0) 3)) (px (* (- ,x2 ,gx1) 3)) (py (* (- ,y2 ,gy1) 3))) (let ((bx (- px cx)) (by (- py cy)) (ax (- ,gx3 px ,gx0)) (ay (- ,gy3 py ,gy0))) (setf (aref *pts* 0 0) ,gx0 (aref *pts* 0 1) ,gy0) ,@(map1-n #'(lambda (n) (let* ((u (* n *du*)) (u^2 (* u u)) (u^3 (expt u 3))) `(setf (aref *pts* ,n 0) (+ (* ax ,u^3) (* bx ,u^2) (* cx ,u) ,gx0) (aref *pts* ,n 1) (+ (* ay ,u^3) (* by ,u^2) (* cy ,u) ,gy0)))) (1- *segs*)) (setf (aref *pts* *segs* 0) ,gx3 (aref *pts* *segs* 1) ,gy3))))))\caption{Bézier曲線を生成するためのマクロ.} \label{fig:MacroForBezier}
第\ref{fig:MacroForBezier}図にはこの戦略に基づく曲線生成マクロを示した. これは曲線を即座に描くのではなく,生成した座標を配列に蓄える. 曲線がインタラクティブに動かされているときは,個々の曲線は2回ずつ描かれなければならない. 表示するために1回,そして次を描く前に消去するために(訳注:背景色で)1回だ. その間,どこかに座標を保存しなければならない.
n = 20では,genbez
は21個のsetf
に展開される.
u,u2,... はコード内に直接使われるので,
それらを実行時に配列から探す負担と,開始時に計算する負担が削減できる.
u,u2,... と同様に,配列のインデックスも展開形内には定数として現れるので,
(setf aref)
の範囲チェックもコンパイル時に行われる.
この後の章にはコンパイル時に利用できる情報を活用するマクロが他にも幾つか載っている.
よい例はif-match
(cvnページ)だ.
パターンマッチャは,2つのシーケンス(変数を含んでよい)を比較し,
変数に値を代入して2つのシーケンスを等しくする方法があるかを調べる.
if-match
の構成は,シーケンスの片方がコンパイル時に分かっていて,
そちらだけが変数を含んでいるならば,マッチングを効率的に行えることを示している.
実行時に2つのシーケンスを比較し,
その間に生成された変数束縛を保持するリストを,コンシングで作り上げるのではなく,
分かっているシーケンスから決定される単純な比較を行うコードをマクロに生成させ,
束縛をLispの真の変数に蓄えることができる.
また第19-24章で説明する埋め込み言語も,コンパイル時に得られる情報を大部分で活用している. 埋め込み言語は一種のコンパイラなので,そのような情報を使うべきであるのは自然なことだ. 一般則としては,マクロは精巧であればある程,より多くの制約を引数に課すことになり, これらの制約条件を効率的なコードの生成に利用できる確率が一層高まる.