前章で定義したマクロの幾つかは大規模なものだった．
if-matchの展開形を得るためには，\reffig{fig:FastMatchOp}のコード全てに加え，
\reffig{fig:GeneralSeqDestructuringOp}のdestrucが必要になる．
これ位の大きさのマクロからは，最後の論点へと自然に話がつながる．
埋め込み言語だ．
小さなマクロがLispの拡張に当たるなら，
大規模なマクロはLisp内部に部分言語を定義している
---そこには独自の構文や制御構造が備わっていることもある．
それへの第一歩をif-matchの中に見た．
これは変数を独自の方法で表現していた．
Lispの中に実装された言語は埋め込み言語と呼ばれる．
「ユーティリティ」と同様，この言葉に正確な定義はない．
if-matchは恐らくユーティリティに数えられようが，境界線にずいぶん近付いている．
埋め込み言語は，古典的なコンパイラやインタプリタで実装された言語とは異なる． それは既存のプログラミング言語の内部に，普通はコード変形を用いて実装される． 基盤のプログラミング言語と拡張部分の間に境界は必要ない． 二つは自由に交じり合わせることができるべきだ． 実装者にとっては，これは労力の大きな削減になり得る． 必要な部分だけを埋め込んで，残りは基盤となったプログラミング言語を利用すればよい．
Lispにおいては，コード変形はマクロを示唆する． プリプロセッサを用いても，ある程度は埋め込み言語を実装できる． しかし普通プリプロセッサはテキストにのみ作用するが， マクロはLispの独特な性質を活用できる． リーダとコンパイラの間では， LispプログラムはLispのオブジェクトのリストとして表現される． この段階でコード変形を非常に巧く行うことができる．
埋め込み言語の例で一番有名なのは，CLOSすなわちCommon Lisp Object Systemだ． 既存の言語のオブジェクト指向版が欲しくなったら，新しいコンパイラを書かなければならないだろう． Lispではそうではない． コンパイラのチューニングはCLOSの性能を向上させるだろうが， 原則的にはコンパイラを変更する必要は一切ない． 全てをLispで書くことができる．
以降の章では埋め込み言語の例を示す．
この章ではLispの中にデータベースへのクエリに答えるプログラムを埋め込む方法を説明する．
（そのプログラムはある意味でif-matchと似ていることに気づくだろう．）
第1節ではクエリを解釈するシステムの書き方を説明する．
さらにそのプログラムをクエリ・コンパイラ
---本質的には1つの大きなマクロ--- として再実装する．
すると効率は向上し，Lispとの統合性も高まる．
当面の目標のためには，データベースのスキーマは大した問題にならない． ここでは簡便さを取り，情報をリストの形で保存することにする． 例えばJoshua Reynoldsが英国人画家で，1723年から1792年まで生きたという事実は，次のように表現する．
(painter reynolds joshua english) (dates reynolds 1723 1792)
情報をリストにまとめる決まった方法はない． 大きな1つのリストを使ってもよいだろう．
(painter reynolds joshua 1723 1792 english)
データベースのエントリをどのように構成するかはユーザ次第だ． 唯一の制限は，エントリ（事実）は第1要素（述語）をキーに区別されるということだ． その制限に従う限りどんな形式でも一貫性があればよい． ただ，形式によってクエリへの反応に速い遅いの違いが出ることがある．
(defun make-db (&optional (size 100))
(make-hash-table :size size))
(defvar *default-db* (make-db))
(defun clear-db (&optional (db *default-db*))
(clrhash db))
(defmacro db-query (key &optional (db '*default-db*))
`(gethash ,key ,db))
(defun db-push (key val &optional (db *default-db*))
(push val (db-query key db)))
(defmacro fact (pred &rest args)
`(progn (db-push ',pred ',args)
',args))
\caption{データベースの基本となる関数．}
\label{fig:BasicDatabaseFunc}
どのデータベースにも最低2つの機能が必須だ． すなわちデータベースの内容の修正と，内容の問い合わせだ． \reffig{fig:BasicDatabaseFunc}のコードはそれらの機能を基本的な形で提供する． データベースは，事実のリストから成り，それらの述語をキーとするハッシュ表で表現される．
\reffig{fig:BasicDatabaseFunc}で定義されたデータベース関数は複数のデータベースに対応しているが，
デフォルトでは*default-db*に対して作用する．
Common Lispのパッケージシステムと同様，
複数のデータベースが必要でないプログラムはどのデータベースを使うかについて一切触れる必要がない．
この節では，全ての例で*default-db*のみを使う．
システムの初期化にはclear-dbを呼ぶ．
これは現在使っているデータベースを空にする．
与えられた述語から事実を検索するにはdb-queryを，
新しい事実をデータベースのエントリに挿入するにはdb-pushを使う．
第12.1節で説明したように，
インヴァージョン可能な参照に展開されるマクロはそれ自身インヴァージョン可能だ．
db-queryはそのように定義されているので，
述語でdb-queryを呼んだ結果にpushで新しい事実をただプッシュすればよい．
Common Lispではハッシュ表のエントリは（指定のない限り）nilに初期化されるので，
どのキーにも最初には空リストが関連付けられている．
最後に，マクロfactがデータベースに新しい事実を追加する．
> (fact painter reynolds joshua english)
(REYNOLDS JOSHUA ENGLISH)
> (fact painter canale antonio venetian)
(CANALE ANTONIO VENETIAN)
> (db-query 'painter)
((CANALE ANTONIO VENETIAN)
(REYNOLDS JOSHUA ENGLISH))
T
db-queryの第2返り値としてtが返されているのは，
db-queryがgethashに展開されるせいだ．
エントリが見つからない場合と，値がnilのエントリを発見した場合を区別するため，
gethashは第2返り値にフラグを返す．
db-queryを呼ぶのは，データベースの利用方法としては柔軟さに欠ける．
普通，ユーザは事実の第1要素だけに依存する質問だけをするのではない．
クエリ言語とは，複雑な質問を表現するための言語だ．
典型的なクエリ言語では，
ユーザは条件の適当な組合せを満たす全ての値を検索できる．
例えば「1697年生まれの全ての画家の名字」だ．
query : (symbol argument *)
: (not query )
: (and query *)
: (or query *)
argument : ? symbol
: symbol
: number
\caption{クエリの文法}
\label{fig:SytaxOfQuery}
これから宣言的クエリ言語を提供するプログラムを作る．
宣言的クエリ言語では，答えが満たす必要のある条件をユーザが指定し，システムに答えの生成を任せる．
このようなクエリの表現は，私達が日常会話で使う形式に近い．
我々のプログラムでは，
(painter x ...)という形の事実と(dates x 1697 ...)という形の事実が
存在するような全てのxを探すよう命じることでクエリを表現できるようにしよう．
1697年生まれの全ての画家を指定するには，次のようにする．
(and (painter ?x ?y ?z)
(dates ?x 1697 ?w))
我々のプログラムは，述語と幾つかの引数から成る単純なクエリの他，
and，or等の論理演算子で組み合わされた任意の複雑なクエリに解答できるようにする．
クエリ言語の文法は\reffig{fig:SytaxOfQuery}に示した．
事実は述語で区別されるので，変数が述語の位置に来ることはできない． 述語について順番付けのできる利点を諦めてよいなら， 常に同じ述語を使い，第1引数を事実上の述語として扱うことでこの制限を回避できる．
類似の多くのシステムと同様に，このプログラムは事実に対して懐疑的だ．
分かっている幾つかの事実の他は偽であるとする．
演算子notは，問われた事実がデータベース内にないときにマッチに成功する．
「偽」ということを明示的に指定するには，Wayne's Worldの方法がある程度使える．
(edible motor-oil not)
しかし演算子notはこれらの事実を他の事実と全く同様に扱う．
プログラミング言語にとって，インタプリタとコンパイラの違いは根元的だ． この章では，クエリについて同じ疑問を再び考える． クエリ・インタプリタは受け取ったクエリを元にデータベースから答えを引き出す． クエリ・コンパイラはクエリを受け取って，実行時に同じ結果を与えるプログラムを生成する． 以降の節ではまずクエリ・インタプリタを，次にクエリ・コンパイラを説明する．
(defmacro with-answer (query &body body)
(let ((binds (gensym)))
`(dolist (,binds (interpret-query ',query))
(let ,(mapcar #'(lambda (v)
`(,v (binding ',v ,binds)))
(vars-in query #'atom))
,@body))))
(defun interpret-query (expr &optional binds)
(case (car expr)
(and (interpret-and (reverse (cdr expr)) binds))
(or (interpret-or (cdr expr) binds))
(not (interpret-not (cadr expr) binds))
(t (lookup (car expr) (cdr expr) binds))))
(defun interpret-and (clauses binds)
(if (null clauses)
(list binds)
(mapcan #'(lambda (b)
(interpret-query (car clauses) b))
(interpret-and (cdr clauses) binds))))
(defun interpret-or (clauses binds)
(mapcan #'(lambda (c)
(interpret-query c binds))
clauses))
(defun interpret-not (clause binds)
(if (interpret-query clause binds)
nil
(list binds)))
(defun lookup (pred args &optional binds)
(mapcan #'(lambda (x)
(aif2 (match x args binds) (list it)))
(db-query pred)))
\caption{クエリ・インタプリタ．}
\label{fig:QueryInterpreter}
宣言的クエリ言語を実装するために，
第18.4節で定義したパターンマッチング・ユーティリティを使う．
\reffig{fig:QueryInterpreter}に示した関数は，\reffig{fig:SytaxOfQuery}に示した形のクエリを解釈する．
中核となる関数はinterpret-queryで，複雑なクエリの構造に対し再帰的に動作し，
束縛を順々に生成する．
複雑なクエリの評価は，Common Lispの関数の引数の評価と同様，左から右の順で行われる．
再帰が事実を表すパターンまで辿り着くと，interpret-queryはlookupを呼び出す．
ここでパターンマッチングが行われる．
関数lookupは，述語と引数リストから成るパターンを引数に取り，
パターンがデータベース内のいずれかの事実にマッチするような束縛全てから成るリストを返す．
lookupは述語に対応するデータベースのエントリそれぞれについて，
match（xckページ）を呼んでパターンと比べる．
マッチが成功する度に束縛のリストが返されるが，
lookupはそれらのリスト全てから成るリストを返す．
> (lookup 'painter '(?x ?y english)) (((?Y . JOSHUA) (?X . REYNOLDS)))
(clear-db) (fact painter hogarth william english) (fact painter canale antonio venetian) (fact painter reynolds joshua english) (fact dates hogarth 1697 1772) (fact dates canale 1697 1768) (fact dates reynolds 1723 1792)\caption{事実の例．} \label{fig:AssertionOfSampleFacts}
これらの事実は，外側の論理演算子によって処理されたり組み合わされる． 最終結果は束縛の集合から成るリストとして返される． \reffig{fig:AssertionOfSampleFacts}に示した事実があるとして， この章の始めの方で示した例を実行してみた．
> (interpret-query '(and (painter ?x ?y ?z)
(dates ?x 1697 ?w)))
(((?W . 1768) (?Z . VENETIAN) (?Y . ANTONIO) (?X . CANALE))
((?W . 1772) (?Z . ENGLISH) (?Y . WILLIAM) (?X . HOGARTH)))
一般則として，クエリを組み合わせたり入れ子にする際に制限はない． 場合によってはクエリの文法の些細な制限が顕在化するが， その点についてはこのコードの使われ方の例を幾つか見た後に考えた方がよい．
マクロwith-answerは，このクエリ・インタプリタをLispプログラム内でうまく使う方法を提供する．
第1引数には任意の可能なクエリを取り，残りの引数は本体コードとなる．
with-answerは，クエリの生成した束縛全てを集め，
クエリ内の変数をそれぞれの束縛が指定する通りに束縛して本体コードを繰り返すコードに展開される．
with-answerに渡したクエリ内に出て来る変数は（大抵は）本体コード内でも使える．
クエリが，成功はするものの変数を含まないときは，with-answerは本体コードを1度だけ評価する．
> (with-answer (painter hogarth ?x ?y)
(princ (list ?x ?y)))
(WILLIAM ENGLISH)
NIL
1697年に生まれた全ての画家のラストネーム．（最初に提示した例）
> (with-answer (and (painter ?x _ _)
(dates ?x 1697 _))
(princ (list ?x)))
(CANALE)(HOGARTH)
NIL
1772年または1792年に亡くなった人のラストネームと誕生年．
> (with-answer (or (dates ?x ?y 1772)
(dates ?x ?y 1792))
(princ (list ?x ?y)))
(HOGARTH 1697)(REYNOLDS 1723)
NIL
ヴェネツィアの画家の誰とも同じ年に生まれていない全ての英国人画家のラストネーム．
> (with-answer (and (painter ?x _ english)
(dates ?x ?b _)
(not (and (painter ?x2 _ venetian)
(dates ?x2 ?b _))))
(princ ?x))
REYNOLDS
NIL
\caption{クエリ・インタプリタの用例．}
\label{fig:QueryInterpreterInUse}
\reffig{fig:AssertionOfSampleFacts}で定義したデータベースの下でクエリを行った例を，
\reffig{fig:QueryInterpreterInUse}に，自然言語への翻訳付きで示した．
パターンマッチングがmatchによって行われているため，
パターン内でアンダースコア（下線，_）をワイルドカードとして使える．
例を長くしないために，クエリの本体内では結果の表示以外のことを行っていない．
しかし，一般にはwith-answerの本体には任意のLispの式が使える．
クエリが変数を束縛する際に制限が幾つかある． 例えば次のクエリは，
(not (painter ?x ?y ?z))
どうして?xと?yに束縛を一切与えないのだろう？\
画家の内の誰かの名前でない?xと?yには無限通りの組合せがある．
よって，次の制限を加えることにする．
演算子notは，次のように，既に生成された束縛に対して処理を行うが，
(and (painter ?x ?y ?z) (not (dates ?x 1772 ?d)))
それ自身だけで束縛を作ってくれるものではない． 画家を探して束縛の集合を生成しなければならないわけだが， それをするのは1772年に生まれていない人物を選び出せるようになる前だ． 節を逆順に指定していたら，
(and (not (dates ?x 1772 ?d)) (painter ?x ?y ?z)) ; wrong
1772年に生まれた画家が一人でもいたら結果としてnilを得るだろう．
第1の例ですら，?dの値がwith-answer式の内部で使えると期待してはならないのだ．
また(or q1 ... qn)という形の式では，
束縛が与えられることが保証されているのは全てのqiの中に現れる変数に対してのみだ．
with-answerに次の形のクエリが含まれていたとき，
(or (painter ?x ?y ?z) (dates ?x ?b ?d))
?xには必ず束縛が与えられる．
2つの部分クエリのどちらが成功しても，?xには束縛が与えられるからだ．
しかし?yと?bのいずれについても，クエリが束縛を与える保証はない．
（どちらか片方は必ず束縛が与えられるのだが．）
クエリが束縛を与えなかったパターン変数は，繰り返しの内のその回の間はnilになる．
\reffig{fig:QueryInterpreter}のコードは所望の動作を実現するが，効率がよくない．
これはクエリの構造を実行時に解析しているが，構造はコンパイル時にもう分かっている．
また，変数束縛を保持するためにリストをコンシングしているが，変数自身に値を持たせてもよいはずだ．
どちらの問題点も，with-answerの別の実装で解決できる．
(defmacro with-answer (query &body body)
`(with-gensyms ,(vars-in query #'simple?)
,(compile-query query `(progn ,@body))))
(defun compile-query (q body)
(case (car q)
(and (compile-and (cdr q) body))
(or (compile-or (cdr q) body))
(not (compile-not (cadr q) body))
(lisp `(if ,(cadr q) ,body))
(t (compile-simple q body))))
(defun compile-simple (q body)
(let ((fact (gensym)))
`(dolist (,fact (db-query ',(car q)))
(pat-match ,(cdr q) ,fact ,body nil))))
(defun compile-and (clauses body)
(if (null clauses)
body
(compile-query (car clauses)
(compile-and (cdr clauses) body))))
(defun compile-or (clauses body)
(if (null clauses)
nil
(let ((gbod (gensym))
(vars (vars-in body #'simple?)))
`(labels ((,gbod ,vars ,body))
,@(mapcar #'(lambda (cl)
(compile-query cl `(,gbod ,@vars)))
clauses)))))
(defun compile-not (q body)
(let ((tag (gensym)))
`(if (block ,tag
,(compile-query q `(return-from ,tag nil))
t)
,body)))
\caption{クエリ・コンパイラ．}
\label{fig:QueryCompiler}
\reffig{fig:QueryCompiler}では新しいwith-answerを定義している．
新型はavg（xlxページ）から始まり，if-match（rezページ）へつながった傾向に沿っている．
すなわち，旧型が実行時に行っていた処理の大半をコンパイル時に行っている．
\reffig{fig:QueryCompiler}のコードは一見\reffig{fig:QueryInterpreter}のコードと似ているが，
その中のコードで実行時に呼ばれるものは一切ない．
束縛を生成するのではなく，with-answerの展開形の一部をなすコードを生成する．
実行時には，そのコードはデータベースの現状に基づいてクエリを満たす全ての束縛を生成する．
(with-answer (painter ?x ?y ?z) (format t "~A ~A is a painter.~\%" ?y ?x))これはクエリ・インタプリタにより次のように展開される：
(dolist (#:g1 (interpret-query '(painter ?x ?y ?z)))
(let ((?x (binding '?x #:g1))
(?y (binding '?y #:g1))
(?z (binding '?z #:g1)))
(format t "~A ~A is a painter.~%" ?y ?x)))
そしてクエリ・コンパイラにより次のように展開される：
(with-gensyms (?x ?y ?z)
(dolist (#:g1 (db-query 'painter))
(pat-match (?x ?y ?z) #:g1
(progn
(format t "~A ~A is a painter.~\%" ?y ?x))
nil)))
\caption{同じクエリの2通りの展開形．}
\label{fig:TwoExpansionsOftheSameQuery}
実際のところ，このプログラムは一つの巨大なマクロなのだ．
\reffig{fig:TwoExpansionsOftheSameQuery}にはwith-answerの展開形を示した．
処理の大半はpat-match（wgcページ）が行うが，それもまたマクロだ．
すると実行時に必要になる新たな関数は，
\reffig{fig:BasicDatabaseFunc}に示した基本的データベース関数だけだ．
with-answerがトップレベルから呼ばれると，クエリのコンパイルは利点をほとんど生かせない．
クエリを表現するコードは生成され，評価された後，廃棄される．
しかしwith-answerがLispプログラムの中で使われたときは，
クエリに対応するコードはマクロ展開の一部となる．
よっってそれを含むプログラムがコンパイルされたとき，
全てのクエリに対するコードがプロセスの中にインラインでコンパイルされる．
新手法の最大の利点は速度だが，
with-answerを呼び出すコードとの統合性を高めることにもつながっている．
そのことは2か所の改善として現われる．
まず，クエリ内部の引数が評価されるようになるので，次のように書ける．
> (setq my-favorite-year 1723)
1723
> (with-answer (dates ?x my-favorite-year ?d)
(format t "~A was born in my favorite year.~%" ?x))
REYNOLDS was born in my favorite year.
NIL
クエリ・インタプリタでできない訳ではないが，evalを明示的に呼ぶという代償を払わないといけない．
そのときでさえ，クエリ引数内のレキシカル変数を参照することは無理だ．
> (with-answer (painter 'hogarth ?x ?y)
(princ (list ?x ?y)))
(WILLIAM ENGLISH)
NIL
ヴェネツィアのどの画家とも同じ年に生まれていない英国人画家のラストネーム．
> (with-answer (and (painter ?x _ 'english)
(dates ?x ?b _)
(not (and (painter ?x2 _ 'venetian)
(dates ?x2 ?b _))))
(princ ?x))
REYNOLDS
NIL
1770年から1800年の間に亡くなった全ての画家のラストネームと没年．
> (with-answer (and (painter ?x _ _)
(dates ?x _ ?d)
(lisp (< 1770 ?d 1800)))
(princ (list ?x ?d)))
(REYNOLDS 1792)(HOGARTH 1772)
NIL
\caption{クエリ・コンパイラの用例．}
\label{fig:QueryCompilerInUse}
クエリ内部の引数が評価されるようになり， 評価結果が自分自身にならない任意のリテラル引数（自然言語文など）にはクォートをつける必要がある． （\reffig{fig:QueryCompilerInUse}を参照）
新手法の利点その2は，一般のLispの式をクエリ内に混ぜることがずっと容易になったことだ．
クエリ・コンパイラではオペレータlispを追加されたが，それには任意のLisp式を続けることができる．
演算子notと同様，lisp自身は束縛を作れないが，
式がnilを返すような束縛を選び出すことはできる．
オペレータlispは > などの組込み述語を利用するのに便利だ．
> (with-answer (and (dates ?x ?b ?d)
(lisp (> (- ?d ?b) 70)))
(format t "~A lived over 70 years.~%" ?x))
CANALE lived over 70 years.
HOGARTH lived over 70 years.
NIL
高度に作りこまれた埋め込み言語は， 基盤のプログラミング言語と一体化したインタフェイスを持つことができる．
これらの追加機能 ---引数の評価とオペレータlisp--- を除けば，
クエリ・コンパイラの提供するクエリ言語はインタプリタの提供するものと同じだ．
\reffig{fig:QueryCompilerInUse}には，
\reffig{fig:AssertionOfSampleFacts}で定義されたデータベースに基づいた
クエリ・コンパイラの動作結果の例を示した．
第17.2節では，式をコンパイルすることがevalにリストとして渡すことより優れている理由を2つ挙げた．
コンパイルした方が速いし，式をその外側のレキシカル環境内で評価することができる．
クエリのコンパイルの利点も全く同じことだ．
今まで実行時に行われていた処理が，コンパイル時に行われるようになった．
クエリがその外側のLispコードの断片と共にコンパイルされるせいで，レキシカル・コンテキストが活用できる．