宣言型プログラミングの可能性と限界

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）