関数を返すマクロ

第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)))))

この章では，マクロによってよりよい関数生成オペレータを定義する方法について考える． 第\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を特別扱いするのは，その場合のコードを読み易くするためだけだ．

Cdr部での再帰

第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))

第\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))

第\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))))

第\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))

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))

第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))

遅延評価とは，式を，値が必要になったときにのみ評価することだ． 遅延評価の使い道の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))))

遅延をこのような裸の形で使うのはやや不便だ． 実際の応用現場では，更に抽象化の層を重ねて隠蔽することになるかも知れない．

←： アナフォリックマクロ     ↑： On Lisp     →： マクロを定義するマクロ