宣言型プログラミングの可能性と限界
宣言型プログラミングとは
命令型プログラミングと対比されるもう1つの大きな流れとして、ハードウエアとは独立した、数理論理学に根ざした流れが存在します。（純粋な）関数プログラミングや論理プログラミング、制約プログラミングなど、いろいろな理論に根ざしたプログラミングモデルが存在しますが、ここではそれらを総称して、宣言型プログラミングと呼ぶことにします。
宣言型プログラミングは、問題の解法、すなわちデータ構造とアルゴリズムを記述する命令型プログラミングとは対照的なプログラミングパラダイムです。宣言型プログラミングが記述するものは、問題の定義、すなわち解くべき問題の性質や、その際に満たすべき制約の記述です。
問題の定義は、問題の解法とはなるべく独立しているべきです。なぜならば、問題の効率的な解き方は、実行環境に依存したさまざまなやり方が考えられるからです。たとえ、ある環境では効率的な解き方であっても、別の環境では非効率になってしまう場合もあります。
命令型のプログラムを記述する場合、まずは問題をどのようなデータ構造で表現すれば良いのか？どのようなアルゴリズムでデータを処理すれば良いのか？というような、低レベルなデータ構造とアルゴリズムについて考えなければなりません。そのような実装の詳細の決定は、システムの隅々にまで影響を与え、後の変更を困難にするため、できるだけ先延ばしにできた方が良いのです。
命令型のスタイルは、実行環境に深く依存したデータ構造とアルゴリズムを駆使して、非常に効率的な解法を記述できる可能性があります。しかしその半面、実行環境が変わるたびにプログラムを大きく書き直す必要が出てきます。また、問題とは直接関係無い、さまざまな非本質的な記述がプログラムの中に混在することになるので、どこがプログラムの本質なのかがわかりにくくなってしまいます。
論理型プログラミング言語Prolog
宣言的なプログラミング言語の1つに論理型プログラミングPrologがあります。あまりなじみの無い方がほとんどだと思いますが、その歴史は古く、70年代から主に自然言語処理などのAI（人工知能）分野においてよく使われています。Prologは、PROgramming in LOGic（論理によるプログラミング）という名前の通り、普及している命令型のプログラミングとはかなり異なる「プログラミング」の可能性を示した言語です。
論理プログラムの特徴として、制御構造（処理の流れ）という、命令型プログラムでは空気のように当たり前の概念が（理論上は）存在しないことが挙げられます。
もちろんPrologは現実のプログラミング言語ですから、言語処理系内に組み込まれたアルゴリズムによって、最終的には命令型言語と同様に実行されます。その際の効率のために、命令的な記述を許すように拡張された処理系もあります。
しかし、「純粋な論理プログラム」が記述するものは、あくまでもロジックであり、手続きそのものではないのです。宣言性が高い、つまり制御構造を意識しないで済むプログラムは、自然と双方向性を持つ、より汎用的なものとなります。
例えば、図1に示す有名なプログラムappendは、第一引数のリストXと第二引数のリストYを連結したものを第三引数のZに返す、という通常の関数的な使い方以外にも、リストを分解し、すべての分解パターンの可能性をしらみつぶしに探すというようにも使うことができます。
Prologと宣言型プログラミング
本連載では、Prologを、単なる一プログラミング言語仕様としてではなく、宣言型プログラミングの象徴として扱います。Prologは、当初は論理型プログラミング言語として開発されましたが、その後はさまざまな研究成果を取り込み、宣言型パラダイムの実験場のような言語へと変化してきているからです（図2）。
Prologプログラムは、問題を解くための手続きではなく、問題間の関係を記述します。関係は「述語(引数, ...)」という形式で、述語の定義によって記述されます。述語は関数に似ていますが、真か偽かのいずれかの値のみを取るという点が異なります。
述語の引数には、数値やシンボルなどの定数や、それらを組み合わせた項やリストなどのさまざまなパターンをリテラル記述することができます。これこそが、Prologプログラムが「宣言的」と言われる理由です。宣言的なパターンのマッチングによる探索が、Prologの根幹を成すメカニズムとなります。
確定節と証明による計算メカニズム
例えば、花子は太郎を好きであるという述語は「好き(花子,太郎).」と書けます。最も単純なPrologプログラムは、このように具体的な事実を書き並べたものとなります。変数を使うと、より一般的な「好き(花子,X).」のような述語が書け、Xが花子が好きな人ならば真、それ以外は偽という定義が記述できます。
その際に「花子は身長180cm以上の男子が好きである」というより複雑な条件については、「好き(花子, X) :- 男(X), 身長(X, Y), Y >= 180.」と記述することができます。このような特別な形の論理式のことを、確定節と呼びます。先に述べた具体的な事実は、ほかに条件が存在せず、無条件に真（しん）なので「:-」の右側を省略した確定節です。
もちろん、単に論理式を記述しただけでは、そこからどのような帰結が得られるのかは簡単にはわかりません。Prologは、確定節という扱いやすい形で論理式を記述し、SLD（Selective Linear Resolution for Definite Clause）導出というアルゴリズムで証明を行います。ここで言う証明というのは、通常の数学の証明とは異なり、条件を満たす具体例を実際に作って示すことです。
先の例で言うと、「『花子はXを好き』という述語を満たす具体例を作るためには、男子であり、身長Yが180以上という条件を満たすXを、事実の定義の中からしらみつぶしに探せば良い」という風に、述語の宣言的な記述を、手続きとして読み替えることによって、論理式を実行することが可能になります。このような宣言の手続き的解釈こそが、論理によるプログラミングの基本を成すアイデアと言えます。
このようにPrologプログラムには、直接問題の解法を書かなくても、問題に関する事実や関係を書き並べていくだけで、自動的に言語処理系が解答を探し出してくれるという、ほかのプログラミング言語とは決定的に異なる特徴が生まれます。これはすなわち、開発したいソフトウエアの仕様記述自体を動かして動作を確かめることができるという、画期的なアイデアであると言えます。
プログラミングの際、実は一番難しいのは、プログラムを書くことではなく、解くべき問題の仕様をはっきりさせることだと言えます。問題の仕様さえ明確な形で記述できれば、後はその仕様を直接SLD導出などのアルゴリズムで実行し、「仕様のデバッグ」を行うことができるというのが、宣言型パラダイムの最大の強みであると言えます。
PrologとSQLの関係
Prologは従来のプログラミングの概念とはあまりにもかけ離れているため、なかなかピンとこないかもしれません。そこで一度、一般に普及しているデータベース問い合わせ言語であるSQLについて考えてみましょう。
実は動作原理的には、SQLとPrologはほとんど同じ動きをします。どちらの言語も、データベースの中からクエリに対する解答を探し出すアルゴリズム（自動探索）が実行メカニズムとなっています。そしてSQLは、Prologと同様に、データベース内のデータに対する具体的なアクセス方法ではなく、必要なデータが満たすべき性質や制約のみを記述します。
例えば、図3のPrologプログラムに対して、好き(花子, X)というクエリを与えたとき、好き(花子,和哉)と好き(花子,洋一)という結果が得られます。これは、図3のSQLクエリをデータベースに問い合わせて得られるデータに対応します。ただし、Prologは再帰的な定義を許しますが、SQLは許さないなど、必ずしも1対1に対応するわけではないことに注意してください。
結局のところ、Prologが提供する能力は魔法ではなく、SQLのようにひたすら条件を満たすデータを探索し、試行錯誤を繰り返すだけの単純愚直なアルゴリズムということです。
宣言型プログラミングの問題点
Prologは強力な抽象化を提供し、プログラミングの既成概念を打ち破る大きな貢献をしました。しかし、現実的には、言語処理系に固定されたアルゴリズムとデータ構造しか選択肢が無いという大きな効率上の欠点があったため、汎用プログラミング言語とはとても呼べないものでした。
例えば、「宣言型」と言いながらも、実用的なプログラムを記述する際には、効率的に解くためのヒントなどを詳細に記述しなければ、遅過ぎて使えない場合が多々あります。また、言語処理系に組み込まれた実行アルゴリズムを深く理解していないと、非効率過ぎる定義を簡単に書けてしまうという問題もあります。SQLに精通された方は、クエリの書き方によって効率が全く異なってしまうことを理解していると思います。
実は、先ほどの例題では、先に性別を選ぶことにより、一気に探索範囲を半減させています。花子が好きなのは必ず男なので、女子は探索対象から外してかまわないのですが、この定義順が逆だと、女子に対しても延々と無駄な条件判定を行ってしまうので、非効率的になってしまいます。
宣言型パラダイムの問題点は、プログラムの実行効率を改善するための手段が限られていることです。これは、命令型記述を捨て、記述力を高めるために払った代償と言えます。DSLによって生み出される宣言的な能力も、同様の問題を抱えています。Lispの上に構築されたPrologシステムを動かす際、LispコンパイラはLispプログラムを最適化するための知識しか知らないので、Prologプログラムの最適化はできないのです。そのため、抽象化の階層を積み重ねれば積み重ねるほど、一般的に処理効率は低下していきます。
最終回で詳しく触れますが、等価変換型プログラミングの視点から宣言型プログラミングの問題点を考察すると、仕様とプログラムを異なるものとして扱う理論が無いという点に尽きます。そのせいで、仕様の記述が解法のアルゴリズムやデータ構造の影響を受けてしまい、結局のところ、解法とは独立した仕様を記述していたつもりが、実は単なる高級な手続きの記述になってしまっている、という本末転倒に陥りやすいのです。
なお、専門的になってしまいますが、本稿の執筆にあたって、以下を参考にしました。
Olof Torgersson『A Note on Declarative Programming Paradigms and the Future of Definitional Programming（http://www.cs.chalmers.se/~oloft/Papers/wm96/wm96.html）』（発行年：1996）
