第5章では関数を返す関数の書き方を示した. マクロはオペレータの組み合わせをずっと容易にしてくれる. この章では第5章で定義したものと同じ抽象化構造を, マクロを使ってきれいにかつ効率的に構築する方法を示す.
fとgが関数ならば,f◯g(x)=f(g(x))である.
第5.4節では,演算子◯をLispの関数compose
として実装する方法を示した.
> (funcall (compose #'list #'1+) 2) (3)
(defmacro fn (expr) `#',(rbuild expr)) (defun rbuild (expr) (if (or (atom expr) (eq (car expr) 'lambda)) expr (if (eq (car expr) 'compose) (build-compose (cdr expr)) (build-call (car expr) (cdr expr))))) (defun build-call (op fns) (let ((g (gensym))) `(lambda (,g) (,op ,@(mapcar #'(lambda (f) `(,(rbuild f) ,g)) fns))))) (defun build-compose (fns) (let ((g (gensym))) `(lambda (,g) ,(labels ((rec (fns) (if fns `(,(rbuild (car fns)) ,(rec (cdr fns))) g))) (rec fns)))))\caption{汎用の関数生成マクロ.} \label{fig:FuncBuildMacro}
この章では,マクロによってよりよい関数生成オペレータを定義する方法について考える.
第\ref{fig:FuncBuildMacro}図には,汎用の関数生成オペレータfn
を示した.
これは関数の仕様に基づいて合成関数を構築するもので,
( <オペレータ> . <引数> )
という形の式を引数に取る.
<オペレータ>には関数またはマクロの名前か,特別扱いのcompose
が指定できる.
<引数>には1個の引数を取る関数またはマクロの名前か,fn
の引数になり得る式が入る.
例えば,
(fn (and integerp oddp))
が生成する関数は次のものに等価だ.
#'(lambda (x) (and (integerp x) (oddp x)))
<オペレータ>にcompose
を指定すると,<引数>の合成になっている関数が得られる.
しかしcompose
が関数として定義されていたときに必要だったfuncall
は,
陽に使う必要がなくなっている.
例えば,
(fn (compose list 1+ truncate))
は次のように展開される.
#'(lambda (#:g1) (list (1+ (truncate #:g1))))
こうするとlist
や1+
等の小さな関数のインライン・コンパイルが可能になる.
マクロfn
は一般的な意味でのオペレータの名前を取る.
すなわち,次の例のようにλ式も使える.
(fn (compose (lambda (x) (+ x 3)) truncate))
これは次のように展開される.
#'(lambda (#:g2) ((lambda (x) (+ x 3)) (truncate #:g2)))
ここでλ式として表現された関数は確かにインライン・コンパイルされることになる.
というのもcompose
の引数として渡されたシャープクォート付きλ式は
funcall
されなければならないからだ.
第\ref{fig:FunctionBuilders}図には,fif
,fint
にfun
といった
3個の関数生成オペレータの定義を示した.
これらは汎用マクロfn
に統合されることになる.
and
を<オペレータ>に指定すると,<引数>の関数の交わりが得られる.
> (mapcar (fn (and integerp oddp)) '(c 3 p 0)) (NIL T NIL NIL)
それに対し,or
では合併が得られる.
> (mapcar (fn (or integerp symbolp)) '(c 3 p 0-2)) (T T T NIL)
そしてif
では本体が条件によって変わる関数が得られる.
> (map1-n (fn (if oddp 1+ identity)) 6) (2 2 4 4 6 6)
しかしこれら3個以外のLispの関数も利用できる.
> (mapcar (fn (list 1- identity 1+)) '(1 2 3)) ((0 1 2) (1 2 3) (2 3 4))
そしてfn
の<引数>自体も式であってよい.
> (remove-if (fn (or (and integerp oddp) (and consp cdr))) '(1 (a b) c (d) 2 3-4 (e f g))) (C (D) 2 3-4)
fn
にcompose
を特別扱いさせても,それが強力になる訳ではない.
fn
の<引数>を入れ子にすれば,関数の合成になるからだ.
例えば,
(fn (list (1+ truncate)))
は次のように展開され,
#'(lambda (#:g1) (list ((lambda (#:g2) (1+ (truncate #:g2))) #:g1)))
次と同様の動作になる.
(compose #'list #'1+ #'truncate)
マクロfn
がcompose
を特別扱いするのは,その場合のコードを読み易くするためだけだ.
第5.5,5.6節では,再帰関数を生成する関数の書き方を示した. ここからの2節では,そこで定義した関数に対して アナフォリックマクロならどのようにきれいなインタフェースを提供できるかを示す.
第5.5節では,平坦なリストに対する再帰関数を生成するlrec
の定義方法を示した.
lrec
を使えば,次の関数our-every
を,
(defun our-every (fn lst) (if (null lst) t (and (funcall fn (car lst)) (our-every fn (cdr lst)))))
例えばoddp
に適用して呼び出すのは,次のように表現できる.
(lrec #'(lambda (x f) (and (oddp x) (funcall f))) t)
ここでマクロが人生の面倒を取り除いてくれる.
再帰関数を表現するのに,指定しなければならない事柄はどれ程だろうか?
リストの現在のcar部と再帰呼び出しをアナフォラを使って
(それぞれit
とrec
として)表現できたら,次のようにすればよくなる.
(alrec (and (oddp it) rec) t)
(defmacro alrec (rec &optional base) "cltl2 version" (let ((gfn (gensym))) `(lrec #'(lambda (it ,gfn) (symbol-macrolet ((rec (funcall ,gfn))) ,rec)) ,base))) (defmacro alrec (rec &optional base) "cltl1 version" (let ((gfn (gensym))) `(lrec #'(lambda (it ,gfn) (labels ((rec () (funcall ,gfn))) ,rec)) ,base))) (defmacro on-cdrs (rec base &rest lsts) `(funcall (alrec ,rec #'(lambda () ,base)) ,@lsts))\caption{リストでの再帰のためのマクロ.} \label{fig:MacrosForListRec}
第\ref{fig:MacrosForListRec}図には,次のようなことを可能にしてくれるマクロの定義を示した.
> (funcall (alrec (and (oddp it) rec) t) '(1 3 5)) T
このマクロは,第2引数として与えられた式をlrec
に渡す関数に変換することで動作する.
第2引数はアナフォリックにit
やrec
を参照しているかもしれないので,
マクロの展開型内では,
関数の本体はそれらのシンボルが生成する束縛のスコープ内に置かれていなければならない.
実際には第\ref{fig:MacrosForListRec}図には2種類のalrec
の定義を示してある.
上の例で使った方にはシンボル・マクロ(第7.11節)が必要になる.
シンボル・マクロは最近のCommon Lispでしか使えないので,
第\ref{fig:MacrosForListRec}図には少々利便性の劣るalrec
も示した.
こちらではrec
はローカル関数として定義されている.
関数にしたことの代償は,rec
を括弧で囲まなければならないという点だ.
(alrec (and (oddp it) (rec)) t)
symbol-macrolet
を提供するCommon Lisp処理系では,元の方が好ましい.
Common Lispでは関数の名前空間が独立しているので, これらの再帰関数生成マクロで名前のある関数を定義するとぎこちなくなってしまう.
(setf (symbol-function 'our-length) (alrec (1+ rec) 0))
第\ref{fig:CommonLispFuncsDefinedWithOncdr}図の最後のマクロは,これを抽象化するためのものだ.
on-cdrs
を使えば,上の代わりに次のようにすればよい.
(defun our-length (lst) (on-cdrs (1+ rec) 0 lst)) (defun our-every (fn lst) (on-cdrs (and (funcall fn it) rec) t lst))
(defun our-copy-list (lst) (on-cdrs (cons it rec) nil lst)) (defun our-remove-duplicates (lst) (on-cdrs (adjoin it rec) nil lst)) (defun our-find-if (fn lst) (on-cdrs (if (funcall fn it) it rec) nil lst)) (defun our-some (fn lst) (on-cdrs (or (funcall fn it) rec) nil lst))\caption{Common Lispの関数を
on-cdr
を使って定義した例.}
\label{fig:CommonLispFuncsDefinedWithOncdr}
第\ref{fig:CommonLispFuncsDefinedWithOncdr}図には,
この真マクロを使って定義した既存のCommon Lispの関数を幾つか示した.
on-cdrs
を使って表現すると,これらの関数は最も基本的な形に還元される.
また,そうしなければ明らかにはならなかったこれらの関数の間の類似性にも気付かされる.
(defun unions (&rest sets) (on-cdrs (union it rec) (car sets) (cdr sets))) (defun intersections (&rest sets) (unless (some #'null sets) (on-cdrs (intersection it rec) (car sets) (cdr sets)))) (defun differences (set &rest outs) (on-cdrs (set-difference rec it) set outs)) (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))))\caption{
on-cdrs
を使って定義された新ユーティリティ.}
\label{fig:UtilsWithOnCdrs}
第\ref{fig:UtilsWithOnCdrs}図には,
on-cdrs
を使って容易に定義される新ユーティリティを幾つか示した.
始めの3個,unions
,intersections
にdifferences
は,
それぞれ合併集合,共通集合に補集合を実装している.
Common Lispにはそれらの操作のための組み込み関数が備わっているが,
それらは1回に2つのリストしか引数に取れない.
そのため,3つのリストの合併を得るためには次のようにする必要がある.
> (union '(a b) (union '(b c) '(c d))) (A B C D)
新しく作ったunions
はunion
と同様に動作するが,任意個数の引数を取れる.
だから次のようにできる.
> (unions '(a b) '(b c) '(c d)) (D C A B)
union
と同様に,unions
は要素の元のリスト内での順番を保たない.
Common Lisp組み込みのintersection
と,
より一般的なintersections
との関係もこれと同じだ.
intersections
の定義では,効率性のために最初に空引数を調べる動作が追加された.
集合の1つが空のときには,これは比較を省略する.
Common Lispにはset-difference
という関数も備わっている.
これは2つのリストを引数に取り,1番目の要素だが,2番目の要素ではないものを返す.
> (set-difference '(a b c d) '(a c)) (D B)
上の新ユーティリティでは,-
(マイナス)と同様に複数個の引数を扱える.
例えば(differences x y z)
は(set-difference x (unions y z))
と等価だ.
しかし後者に伴うコンシングが不必要になっている.
> (differences '(a b c d e) '(a f) '(d)) (B C E)
これらの集合用オペレータは単なる例であって,実際に必要になることはない.
組み込み関数reduce
が既に扱っていた,
リストに対する再帰の特別な場合を代表しているに過ぎないからだ.
例えば次のようにする代わりに,
(unions ...)
ただこうすればよい.
((lambda (&rest args) (reduce #'union args)) ...)
しかし,一般的な状況ではon-cdrs
の方がreduce
よりも強力だ.
recは値でなく呼び出しを参照するので,on-cdrs
を使って多値を返す関数を生成できる.
第\ref{fig:UtilsWithOnCdrs}図の最後の関数maxmin
はこの可能性を活用し,
リストを1回探索するうちに最大の要素と最小の要素の両方を発見する.
> (maxmin '(3 4 2 8 5 1 6 7)) 8 1
on-cdrs
はこの後の章で出てくるコードに使うこともできるだろう.
例えばcompile-cmds
(ldqページ)は,
(defun compile-cmds (cmds) (if (null cmds) 'regs `(,@(car cmds) ,(compile-cmds (cdr cmds)))))
次のように簡潔に定義できる.
(defun compile-cmds (cmds) (on-cdrs `(,@it ,rec) 'regs cmds))
リストに対する再帰へのマクロの応用は,ツリーに対する再帰にも適用できる. この節では、マクロを使って第5.6節で定義したツリーに対する再帰関数への よりきれいなインタフェースを定義する.
第5.6節では,ツリーに対する再帰関数を生成する関数を2つ定義した.
ttrav
は常にツリーの全体を探索するもので,
またtrec
の方は複雑だが,再帰の停止を制御できるようになっている.
これらの関数を使えば,次のour-copy-tree
は,
(defun our-copy-tree (tree) (if (atom tree) tree (cons (our-copy-tree (car tree)) (if (cdr tree) (our-copy-tree (cdr tree))))))
こうして表現できる.
(ttrav #'cons)
また次のrfind-if
の,
(defun rfind-if (fn tree) (if (atom tree) (and (funcall fn tree) tree) (or (rfind-if fn (car tree)) (and (cdr tree) (rfind-if fn (cdr tree))))))
例えばoddp
への適用は,こうして表現できる.
(trec #'(lambda (o l r) (or (funcall l) (funcall r))) #'(lambda (tree) (and (oddp tree) tree)))
前節でlrec
に対してインタフェースを作ったのと同様,
アナフォリックマクロはtrec
へのより良いインタフェースを作れる.
一般的な場合にも十分対処できるマクロは,以下の3つをアナフォリックに参照できるようでなければならない:
現在,対象となっているツリー(it
と呼ぶことにする),
左の部分ツリーに対する再帰(left
と呼ぶ),
そして右の部分ツリーに対する再帰(right
と呼ぶ)だ.
これらを慣習として定めれば,上に示した関数は新マクロを使って次のように表現できる.
(atrec (cons left right)) (atrec (or left right) (and (oddp it) it))
第\ref{fig:MacrosForRecOnTree}図には,このマクロの定義を示した.
(defmacro atrec (rec &optional (base 'it)) "cltl2 version" (let ((lfn (gensym)) (rfn (gensym))) `(trec #'(lambda (it ,lfn ,rfn) (symbol-macrolet ((left (funcall ,lfn)) (right (funcall ,rfn))) ,rec)) #'(lambda (it) ,base)))) (defmacro atrec (rec &optional (base 'it)) "cltl1 version" (let ((lfn (gensym)) (rfn (gensym))) `(trec #'(lambda (it ,lfn ,rfn) (labels ((left () (funcall ,lfn)) (right () (funcall ,rfn))) ,rec)) #'(lambda (it) ,base)))) (defmacro on-trees (rec base &rest trees) `(funcall (atrec ,rec ,base) ,@trees))\caption{ツリーに対する再帰のためのマクロ.} \label{fig:MacrosForRecOnTree}
symbol-macrolet
をサポートしないLisp処理系では,
atrec
は第\ref{fig:MacrosForRecOnTree}図の2番目の形で定義できる.
こちらではleft
とright
をローカル関数として定義しているので,
our-copy-tree
は次のように表現される必要がある.
(atrec (cons (left) (right)))
利便性のために,マクロon-trees
も定義した.
これは前節のon-cdrs
に似ている.
第\ref{fig:FuncDefinedUsingOnTrees}図には,第5.6節の関数のon-trees
を使った定義を示した.
(defun our-copy-tree (tree) (on-trees (cons left right) it tree)) (defun count-leaves (tree) (on-trees (+ left (or right 1)) 1 tree)) (defun flatten (tree) (on-trees (nconc left right) (mklist it) tree)) (defun rfind-if (fn tree) (on-trees (or left right) (and (funcall fn it) it) tree))\caption{
on-trees
を使って定義した関数.}
\label{fig:FuncDefinedUsingOnTrees}
第5章で注意したことだが,
そこで定義した再帰関数生成関数の構築した関数は末尾再帰的にはならない.
on-cdrs
やon-trees
を使って関数を定義すると,必ずしも最高の効率を持つ実装はできない.
基盤となっているtrec
やlrec
と同様に,
これらのマクロは主にプロトタイプや,プログラム中で効率性が至上とされない部分で使うものだ.
しかしこの章と第5章の基盤となる考えは,
関数生成関数を書いて,それにマクロのきれいなインタフェースを被せることができるということだ.
これと同じ技法は,特に効率的なコードを生成する関数生成関数を構築するときにも同様に使える.
(defconstant unforced (gensym)) (defstruct delay forced closure) (defmacro delay (expr) (let ((self (gensym))) `(let ((,self (make-delay :forced unforced))) (setf (delay-closure ,self) #'(lambda () (setf (delay-forced ,self) ,expr))) ,self))) (defun force (x) (if (delay-p x) (if (eq (delay-forced x) unforced) (funcall (delay-closure x)) (delay-forced x)) x))\caption{
force
とdelay
の実装.}
\label{fig:ImplementationOfForceAndDelay}
遅延評価とは,式を,値が必要になったときにのみ評価することだ.
遅延評価の使い道の1つは,遅延と呼ばれるオブジェクトを作ることだ.
遅延とは何らかの式の値を保持するもので,
式の値を,いつか後で必要になったときには確かに与えるという約束を表現する.
ところで約束はLispのオブジェクトなので,それが表現する値の目的の多くに対して役立つ.
そして式の値が必要になったときには,遅延が値を返すことができる.
Schemeには遅延の組み込みサポートがある.
Schemeのオペレータforce
とdelay
は,
Common Lispでは\ref{fig:ImplementationOfForceAndDelay}図のように実装できる.
遅延は2個のメンバを持つ構造体delay
として表現される.
1番目のメンバはこの遅延がすでに評価されたかどうかを表し,評価されていたときにはその値を含む.
2番目のメンバはクロージャを含むが,これを呼ぶとこの遅延が表現する値が得られる.
マクロdelay
は式を引数に取り,その値を表現する遅延を返す.
> (let ((x 2)) (setq d (delay (1+ x)))) #S(DELAY ...)
遅延の中のクロージャを呼ぶことは,遅延に対して強制(force)を行うことと同じだ.
関数force
は任意のオブジェクトを引数に取る.
普通のオブジェクトに対しては,そのものを返す関数identity
として動作するが,
遅延に対しては,その遅延が表現する値の要求となる.
> (force 'a) A > (force d) 3
force
は,遅延かも知れないオブジェクトを扱っているときにはいつでも使える.
例えば,遅延を含むかもしれないリストを整列させるときには,次のようにできる.
(sort lst #'(lambda (x y) (> (force x) (force y))))
遅延をこのような裸の形で使うのはやや不便だ. 実際の応用現場では,更に抽象化の層を重ねて隠蔽することになるかも知れない.