[制約プログラミング落穂拾い] 宣言性の光と影（３）
さて、今回はいよいよ制約プログラミングを用いて実用的な問題に取り組んだときに直面する課題を具体的に見ていきます。
なお、前回も述べたように制約プログラミングのさまざまな機構の実装は処理系により異なります。従って具体的な機構の説明の部分は、あくまでも例示に過ぎないことを予めお断りしておきます。例示にあたっては、（当然のことですが）自分が実装を知っている処理系を前提としています。
前回、その課題が以下のようなものであることは既に述べました。
- 現実の問題を、用意された制約の組み合わせで表現することができるだろうか。
つまり制約記述の表現力やモデリングの巧拙の問題があります。 - 問題を表現できたとして、解をうまく求めることができるだろうか。
ここで「うまく」というのには、(a)実用上許容できる時間内に、(b)実用上許容できる
品質の解を求める、という2つの側面が含まれます。
まず1.について検討してみます。
これは一見したところ、ライブラリなり言語の仕様に依存する問題に見えます。
実際、ある部分まではそうで、あるライブラリでは表現できないものが別のライブラリで表現できることはありますし、同じ表現ができても、裏に隠れている処理の効率は一般には異なります。つまりライブラリ毎に得意・不得意があるので、もし幾つかの処理系を比較検討する余裕があるのなら、自分の解こうとしている問題への適性を評価してみるべきでしょう。処理系を提供するベンダーは、勿論、自社製品の適性については良く知っているはずですから、問い合わせてみるのも良いでしょう。逆にそうした問い合わせに適切な答えが返ってこないのであれば、2.の課題についてのサポートの方も充分に得られない可能性が高いと考えるべきでしょう。
もう一つの視点は、自分で制約を実装することができる拡張性の有無です。自分で拡張することができるのであれば、「問題の解法はすべて処理系まかせ」という「宣言性」のメリットを半ば捨てる代償として、必要な機能を自分で追加することが
できます。そしてこれができるためには、制約を実現する機構の一部がAPIとして公開されている必要があります。
勿論そうせずに済めばいいのですが、振り返って自分の経験に照らしてみると、そうせずに済んだケースはほとんど無かったように思えます。
更に言えば、現実のソフトウェア開発では解くべき問題が事前に厳密に定義できることはほとんどなく、設計を始める前に予め必要な制約記述が確定していることはほとんどないでしょうし、運用が始まってから環境の変化によって問題が変化することも想定しておく必要があるのでしょう。
そういうことを考え合わせれば、事前に豊富な制約が用意されていることよりも、拡張の手段が豊富に用意されていることの方が重要とさえ言えるかも知れません。
拡張の手段として提供されるのは、変数の状態が変化したときに実行したい処理を記述できるイベントハンドラ用のAPIです。制約プログラミングではこうしたイベントハンドラのことをデモン(demon)と呼ぶ習慣があります。そこでこれ以降はデモンという呼び名を使うことにします。
実は制約プログラミングにおける制約は被制約変数に設定されたデモンの集合に他なりません。例えば2変数間の等式制約を考えて見ましょう。等式制約というのは、一方の変数の状態が変わったら、他方の変数の状態をそれと等しい状態にするデモンなのです。従って、デモンが記述できるAPIがあるということは、制約処理系の利用者が自分で独自の制約を記述できるということに他なりません。
それではデモンを記述する際に注意すべきことはどんなことでしょうか。
最も大切なことは、処理の流れが固定されていない点に留意することではないかと私は思います。2変数間の制約を書く場合、どちらの変数にイベントが発生するかを事前に固定することはできません。等式制約の場合には関係は反射的ですから、単純に同じ処理が双方向に働くように書けばいいわけです。関係が反射的でなければ、それぞれの方向の処理を両方とも書いておく必要があります。
もうおわかりと思いますが、制約プログラミングの「宣言性」を支えているのは制御の流れを固定せずにノードである変数の値の状態の変化をその変数と他の変数の間に設定されたアークである制約を通して他の変数に伝える機構なのです。この機構のことを一般には制約伝播(Constraint Propagation)と呼びます。
一般に制約プログラミングにおける変数の評価の順序は事前に固定されているわけではありません。ある変数の状態の変化がきっかけとなって、制約というアークを通じて別の変数の評価がおきます。そうした伝播はアークの先のノードとなる変数の状態が変化しなくなるまで続きます。これは一般的なプログラミング言語の評価機構とはかなり異なっており、強いて近いものを探すとすれば遅延評価やcall by needが思い浮かびます。
関数型言語をご存知の方ならHaskellのcall by needを思い浮かべていただいてもいいですし、論理型言語をご存知の方なら、freeze述語のことを聞いたことがあるかも知れません。こうした評価機構の比較というトピックも非常に面白いと思うのですが、今回のテーマからは逸れてしまいますので、機会があればまた別に取り上げたいと思います。
一方、この機構によって現在評価された変数と制約で関連づけられた他の変数の値を事前に評価し、制約により取り得ない領域を削ることによって事前に枝刈りをする先読み(lookahead)が可能になっています。
一般には先読みと遅延評価は寧ろ対立するアプローチと見做されているかも知れません。しかし制約プログラミングにおいては、とりうる値の候補を保持する領域変数というアイデアと制約伝播機構というアイデアを組み合わせることによって先読みと遅延評価の両方を実現し、そのことによって処理を効率化していると考えることができると思います。
いずれにしても処理の流れが固定できないというのは、今日一般的に開発で用いられるプログラミング言語のパラダイムと比較して異質なものであることは否定できないでしょう。そしてそれは処理の流れを工夫することによって効率を上げるようなアプローチを直接には取れないことを意味します。
このことが直接問題になるのがまさに2.の課題です。そこで次回は引き続いて2.の課題を検討することにしたいと思います。
