プログラムと論理との対応を利用することで、状態数の爆発を効率的に抑制出来ないかというのが論理型言語の提案だと述べた。残念ながらこの提案に対して理論的な支援は(当初は)弱く、特に関数型言語やオブジェクト指向がモジュラリティを打ち出した事と比較すれば不利な状況だったと思われる。ではこの状況で論理型言語、特にPrologがどのように戦いを挑んだのか、論理的によく書けているプログラムとはどのようなものなのか。今回はリスト結合という簡単なプログラムを例に、これを考えてみる。
Prologの教科書で必ず解説されるリスト結合述語が append/3 である。
append([], [], []).
append([1], [2], [1,2]).
.. % 果てしなく続く
?- append([1,2], [3], X).
call append([1,2], [3], X)
exit append([1,2], [3], [1,2,3])
X = [1,2,3].
可能な限りこの記述を並べる事で、リストの結合がどのようなものか(what)は記述できる。しかしこの調子ではリスト中の値が決まり決まっていて不便である。
append([], [], []).
append([I1], [I2], [I1,I2]).
.. % 果てしなく続く
?- append([a,2], [c], X).
call append([a,2], [c], X)
exit append([a,2], [c], [a,2,c])
X = [a,2,c].
こうすると少しはましになるが依然として不便に変わりはない。何故これが不便なのかというと、可能な状態の数が非常に多く存在する(もっとも資源の都合で有限ではある)ため、これらをプログラミングするのは(文字通り)骨が折れるからである。ここで冒頭に掲げた主張が活きてくる、つまり状態の爆発を抑制出来る述語を考えれば善いのである。
個々の具体的なリストから離れ、リストという集合を分類してはどうか、というメタな視点に立つ。大雑把な括りで見れば、リストというのは空っぽかそうでないのかに分類出来る。そしてリストの結合について望む事は、一つは空っぽリストと任意のリストの結合は任意のリストになる事。
% ____ ____
% X:NIL + Y:|____| = Y:|____|
%
append([], Y, Y).
もう一つは当然、空っぽではないリストと任意のリストの結合についての言及である。そこでリストの分類に少し補足を加え、空でないリストについて少し細かく見る必要がある。空でないのであれば、少くとも1つの要素と任意のリストで結合出来るはずである。だから先の要件は、空っぽでないリスト(=少くとも1つの要素と任意のリストを結合したリスト)と任意のリストの結合は、少くとも1つの要素と任意のリスト(=任意のリストと任意のリストを結合したリスト)の結合となる。
% _ ___ ____ _ ___ ____
% (X:|_| + Xs:|___|) + Y:|____| = X:|_| + (Xs:|___| + Y:|____|)
%
append([X|Xs], Y, [X|Z]) :- append(Xs, Y, Z).
斯くて教科書的な append/3 が出来あがる。この二つの述語で、先程までは延々と書き連ねる必要のあった状態集合を被覆しきる。ちなみに論理型プログラミングを発案したAlain Colmerauerらは、この述語の発見に一ヶ月を要したそうである。それでは実行過程を確認してみる。
?- append([1,2,3], [4,5], Z).
call append([1|[2,3]], [4,5], [_G1|_G2])
call append([2|[3]], [4,5], [_G3|_G4])
call append([3|[]], [4,5], [_G5|_G6])
call append([], [4,5], _G7)
exit append([], [4,5], [4,5])
exit append([3|[]], [4,5], [3|[4,5]])
exit append([2|[3]], [4,5], [2|[3|[4,5]]])
exit append([1|[2,3]], [4,5], [1|[2|[3|[4,5]]]])
Z = [1,2,3,4,5].
ここで見る事が出来る実行過程は、状態集合とどのような関係にあるのか？それは状態集合を空間として見た場合の連続した経路の事で、Prologが探索型の言語だと言われる所以である。畢竟するところ論理型プログラミングの根底には、オートマトンを如何に効率良く圧縮するかという思想が見え隠れするのである。
逆に状態集合ではなく実行過程から論理型プログラミングを見てみると、個々のステップ(というのは実体化された述語)は状態と状態を繋ぐ線であり、これはつまり継続の断片である。実行の側から見れば、論理的なプログラムとは可能な状態群を巡回する継続の集合である。そして可能な状態の抽象度を下げていけば、やがてこれは論理回路の可能な入出力値の集合となり、継続は要素の写像で、少し抽象度を上げれば機械語に対応する。
ここで視点を戻して、状態集合に立ち帰る。人間の視覚上でリストの結合は、片方のお尻に片方の頭が接する状態だと考えた方が遥かに直感的であろう。そもそもリストが空かそうでないかの分類の上で結合操作を行なう人間はまず居ない。何故なら人間はリストをもっと大雑把に「ひと連なりのもの」と捉えているからである。このときに「ひと連なりのもの」集合は、先のリストの状態集合とどのような関係にあるのか？
% リストと「ひと連なりのもの」の対応例
____ ____ __ __
|____| = |____|__.. - |__..
____ _ _
= |____|_| - |_|
____ ___ ___
= |____|___.. - |___..
.. 果てしなく続く
お尻の先をあやふやなままにしたものが「ひと連なりのもの」だと考えると、リストと一対一対応を取ることは出来ないが、少くとも(ひと連なりのもの集合からリスト集合へは)全射ではある。この大雑把な状態の分類を利用すれば、リストの結合は非常に簡単になる。
dl_append(X-Y, Y-Z, X-Z).
?- dl_append([1,2|Xs]-Xs, [3,4|Ys]-Ys, Z-[]).
call dl_append([1,2|_G1]-_G1, [3,4|_G2]-_G2, _G3-[])
exit dl_append([1,2|[3,4|[]]]-[3,4|[]], [3,4|[]]-[], [1,2|[3,4|[]]]-[])
Z = [1,2,3,4].
ご覧のようにルールすら無しに、リスト結合の状態集合を被覆する事が出来る。ちなみにこのようなリスト表現は差分リストと呼ばれ、Prologの常套手段となっている。
(続く)
0 件のコメント:
コメントを投稿