Prologの入門文書に飽きた人に

たけおか@AXE (竹岡尚三)

Update: 2007/DEC/08
Update: 2007/AUG/18
初出: 2007/MAR/10


なんだか、Webの世界には、日本語では、純粋な論理型言語としてのProlog入門の 文書しかなく。
Prologは、実用言語(を目指しているはず)なので、ピュアな論理の話だけでは、 いけないと、思い…
で、こういう雑文にて、恥をさらす。


1. 高階による後悔

実用プログラムが、あんまりに高階手続きを使っていると、それはそれで、困り そうなものなのだが…
でも、やはり、高階な呼び出しは、必要だ。
aho(X,Z) :- A =.. [plus,1,X,Z], call(A),print(Z).
という述語を定義し、 実行とその結果は次のとおり。
?- aho(4,Z).
5

Z = 5 

「call/1」 は、
引数をゴールとして、実行を行う。
「=.. 『(=..)/2』」は
=..の右辺(正確には第2引数)のリストの、
先頭の要素を、
ファンクタとして、
残りの要素を、
引数として、
項(term)を生成して、左辺の変数(正確には第1引数)にバインドする。
<-- (変数がすでにバインド済みの時は、パターンマッチを行う)>

=..で、動的に項を生成し、call/1でそれをゴールとして呼び出すことで、
高階な実行が可能。


まっとうそうな例として、map/2を書いてみた。
map(_,[]) :-!.
map(F,L) :-
	!,select(A,L,LR),
	X =.. [F,A],
	call(X),
	map(F,LR).
マップされる手続きとして、baka/1も定義。
baka(X) :- print(X),nl.
以下のようにmap/2を実行し、結果が得られる。
?- map(baka,[a,b,c,d]).
a
b
c
d
このmap/2は、
第2引数のリストの要素を1つづつ順番に、
第1引数(のアトムをファンクターとする)の述語に適用します。
実用的に、便利でしょう。



2. 動的な節定義や削除

静的な節,述語定義だけで、仕事をすすめるのは、すごくしんどい。
というわけで、データを、節として、動的に定義するのが、やはりPrologの 実用プログラミングだろう。

動的に節を定義することは、asserta/1, assertz/1で行う。
(assert/1は、処理系によっては存在しない場合があり)

動的にassert,retractされるべき節は、 dynamic宣言する (次のごとく)。これは、ISO仕様です。
:- dynamic(aaa/1).
 
この場合、aaa/1という述語がdynamicである、という指定


節を削除するのは、retract/1, retractall/1。
abolish/1が存在する処理系もあり。
※SWI-Prologでは、abolishは使用しない。 (abolishすると、dynamic属性が、無くなってしまうから)

asserta(aaa(1)).
aaa(1)という節が定義できる。データベースの先頭に。
retract(aaa(1)).
aaa(1)という(パターンにマッチした)節が削除される。
retract(aaa(_)).
aaa(_)に最初にマッチした節が削除される。
retractall(aaa(_)).
aaa(_)にマッチしたすべての節が削除される。
こういうものをもってして、変化するものでも、 グローバルに保持するべきでしょう。
あとは、プログラム中で、パターンを書けば、 Prologの持つ、強力なパターンマッチ機能の恩恵にあずかれる。

ただし、手続き(述語)は、あんまり動的に作るもんじゃないでしょう。 (これも高階です)
高階なプログラムは、他人が読むのが大変だし、デバッグも大変だし。
上手に、書いてあれば、問題ないのだけれど。 (上手なプログラマは、何をやっても、いいんですけど)

-- どうでもいいゴタク。(読む必要なし) --
ピュア関数型やピュアな論理型で、実用プログラミングも不可能ではない。
(私は、そういうプログラムも作ってみている。
また、なぜか2006,2007年の日本では、Haskellという、純粋関数型言語が流 行している(なぜなんだ??? Haskellのパターンマッチングと型推論は認める が、 型推論のある言語ならJavaでいいじゃん。すごく実用的だし))

しかし、Prolog本来の強力なパターンマッチの力を使うには、データも動的に、 データベースに登録したほうがいい。
そうでなければ、(たぶん、リスト)データを一生懸命ハンドリングすること になり、それなら、Lisp系の言語か、Haskellでプログラミングしたほうが、い いのでは?と、思う。
また、LispやPrologプログラマは、たぶん、設計しながらのコーディングであり、
プログラムは、すこしづつ作って試したいでしょ?
そういう時、すべてのデータを、引数で持って歩いていると、 実行途中で止めて、コード変更/再開とか、やりにくいでしょ。
∵プログラムを中断させたときに、実行途中のデータを、 どこに保持させるかは、大きな謎だから。
また、テスト時に、データを適当に用意して、サブルーチン単位で駆動する、 などというのも、グローバルに保持されるデータの方が、データのセットが楽 だし。
-- end of ゴタク --




3.テイル・リカーシブ

3.1. テイル・リカーシブな呼び出し

Prologでは、ループは、再帰で記述する。
looop(0).
looop(X) :- print(X),nl,X1 is X - 1, looop(X1).
%
?-looop(5).
5
4
3
2
1
 
一般にどんな言語でも、サブルーチン(手続き)の呼び出しは、 呼び出し元へ戻るための情報を記憶しておかねばならない。

それでは、Prologは、非効率的な言語なのか?
そんなことは、ない。

一般に、手続きの末尾からの再帰呼び出しは、gotoを使用した単純なループに 変換できることが知られている。
※手続きの末尾からの再帰呼び出しは「テイル・リカーシブな呼び出し」とか、「末 尾再帰呼び出し」と言われる。

したがって、まともなProlog処理系であれば、上記のlooop/1は、実行時には、 無駄な記憶を使用したりはしない。

しかし、複雑なコンパイルを行わない、単純なインタープリタでそのようなこ とが実現できるのであろうか。
(※コンパイルなどの変換を行うなら、変換時に末尾再帰呼び出しは、gotoに よる繰り返しに置き換えることができる。しかし、単純なインタープリタは、 その節を実行する時にならなければ末尾再帰であることがわからない。それで うまくいくのか?)


3.2. テイル・リカーシブ・インタープリタ
(※ここは特に実用性はないので、読み飛ばしても可)

そこで、テイル・リカーシブ・インタープリタというインタープリタの実現方法が、 大事である。
テイル・リカーシブ・インタープリタは、 実行時に、実行のために明らかに不要な情報を記憶しない。
これは、当然のようであるが、素朴な古い実装では、なかなか難しい。

古い素朴なインタープリタ実現の話をしよう。
例えば、古いLispインタープリタでは、関数実行の本体(中心部)であるevalと いう関数が、eval自身を再帰的に呼び出す実現が素朴に行われている。
これでは、何があっても、新しい関数を実行するたびに、evalが前のevalに戻 るための情報を、記憶せねばならない。したがって、実行対象のソースコード が末尾再帰になっていても、前のevalのための情報が必ず記憶され、まったく最適 化(節約)が、なされない。
下の模式evalで、eval中からevalを再帰的に呼び出す。このeval呼び出しによっ て、「残りを実行」のための情報を記憶する。したがって、呼び出しの度に、記 憶している情報はどんどん増える。
-- 昔風、素朴なevalを、なんとなくC言語のようなもので記述した。 --

eval(関数)
{
  :
  関数をどんどん実行する
  :
  if(関数呼び出しに出会った)
      eval(新しい関数);
  残りを実行
  :
}

--
 

テイル・リカーシブな実現のインタープリタで有名な言語は、Schemeである。
Schemeは、その言語定義で、テイル・リカーシブなインタープリタの実現が義 務付けられている。

では、テイルテイル・リカーシブ・インタープリタとはどのようなものか?
それは、次のようなものだ。
-- テイル・リカーシブなevalを、なんとなくC言語のようなもので記述した。 --

eval(関数)
{
eval_loop:
  :
  関数をどんどん実行する
  :
  if(関数呼び出しに出会った){
   if(新しい関数呼び出しの後に、仕事はある?){
      今evalしている情報を、スタックへ退避
   }
   プログラムカウンタ=新しい関数;
   goto eval_loop;
  }
 ※1
  残りを実行
  :
 ※2
  if(スタック!=空){
    スタックから、情報を戻す
    goto eval_loop;
  }
}

--
 
※2のあたりで、うまいこと、eval_loopへgotoできるように、インタープリタを 作成するのがコツであり、難しいところかな。
※1の「残りを実行」は、なるべく無くすのが、インタープリタをすっきりさ せるためには、良いだろう。


つまり、evalそのものが大きなループになっている。
そして、新しい関数の実行をしても、evalの呼び出しは深くならない。
もちろん、実行途中の関数を継続するために必要な情報は、ソフトウェアで作った スタックに格納する。したがって、テイル・リカーシブでない呼び出しは、 普通に記憶を消費する。
しかし、関数の末尾からの関数呼び出しの場合は、本来、何も記憶する必要 がない。よって、テイル・リカーシブ・インタープリタは、何も記憶しない。

つまり、テイル・リカーシブ・インタープリタであれば、局所しか見ない、単 純な構成のインタープリタによる実行でも、末尾再帰ループの場合に、無駄な 記憶を消費することがない。
Prologインタープリタや、コンパイルされたコードを実行する仮想マシンの インタープリタ(実行系)は、テイル・リカーシブ・インタープリタとして実現さ れているのが、普通である。




4. Cutをめぐる葛藤


カット(Cut)が、実用プログラムにとても大事である話。

カットが、バックトラックを制御するというのは、入門書に書いてあり。
カットを超えると、それ以降のゴールの試行で失敗があると、 その述語全体が失敗となる。
aaa1 :- bbb(X),ddd(X).
aaa2 :- bbb(X),!,ddd(X).

bbb(a).
bbb(b).
bbb(c).
bbb(d).

ddd(X) :- print(X),read(Y),X == Y.
aaa1を実行すると、
まず、bbb(a)とマッチして、Xがaになり、ddd(X)が失敗すると、
次にbbb(X)が次の候補を探し、bbb(b)となり、Xがbになり、 そこでまたddd(X)が失敗すると、
次にはbbb(c)となる…

aaa2を実行すると、
まず、bbb(a)とマッチして、Xがaになり、それでcutを超える。
そこで、もしddd(X)が失敗すると、いきなりaaa2が失敗となり、終わる。

そんなことは、もう判った。
ここでは、実用上、もっと大事な話をする。


Prologは、バックトラックという強力な機構で、少ないコード行数で、 大きなことをしてくれる。
しかし、バックトラックを実現するためには、ゴールの残りの候補を記憶し たり、そのために変数にバインドされた、中間的なデータも、すべて記憶して おかねばならない。 バックトラックのために、記憶というものが消費されているのである。

カット以降で失敗すると、節の全体を失敗で終わらせれば良い。他の候補を 試行してはいけない。
つまり、カットを通過すると、それ以前のゴール候補の選択肢が不要になる。
ということは、カットを通過した時点で、処理系は、これまでのゴールの候 補のための情報を記憶しておかなくてもよい。
そこで、カットを通過すると、ゴールの候補のための記憶は解放される。こ の情報の中には、一時的変数にバインドされた中間的なデータも含まれる。
プログラムによっては、巨大な中間データを持っていることも多々あるだろ う。こういう巨大な中間データが開放されることは、実用プログラムでは重要 だ。

というわけで、実用的なPrologプログラムは、なるべく、節の始めの方にカッ ト演算子を入れ、不要な記憶を消費しないようにする。


ちなみに、普通の手続き的なサブルーチンを書いているときは、節の先頭に カットを入れれば良い、という、素晴しいコツがある。
当然、条件判断が必要な節で、そんなことをしてはいけない。
条件判断が必要なときは、条件判断が終わったところに、カットを入れる。 (次の例を参照)
-- カットの入れ方の典型例

a) 単純な手続き (先頭にカットを入れる)
subroutine1(X) :- !, XX is X + 1, print(XX). 



b) 条件判断がある時 (条件判断が終わったところで、カット)
condSubr(X) :- XX is X + 2, XX == 3,!,print('One').
condSubr(X) :- !,print('not One').

上を、C言語の if() ... else... で書くと、
condSubr(X)
{
 XX = X + 2;
 if(XX == 3)
   printf("One");
 else
   printf("not One");
}



c) if()..else if()..else if()... の例

condSubr(0) :- !,print('Zero').
condSubr(1) :- !,print('One').
condSubr(2) :- !,print('Two').
condSubr(X) :- X < 0,!,print('minus').
condSubr(X) :- !,print('too much').

上を、C言語の if() ... else... で書くと、
 if(X == 0)
   printf("Zero");
 else if(X == 1)
   printf("One");
 else if(X == 2)
   printf("Two");
 else if(X < 0)
   printf("minus");
 else
   printf("too much");

 Prologは、「==」の条件判断と呼び出しが、同時にできて、強力〜♪

--


カットを入れまくったプログラムには、一階述語論理の風情など、どこにもない。
ただの手続き型のサブルーチンの集まりだ。
でも、ユニフィケーションという、Prologのもう一つの強力な道具は、活用 されている。
やはり、Prologは強力なのだ。




続かない、たぶん…
たけおかのPrologページ 目次

実際にProlog処理系を使ったときの、あれこれ

GnuEmacsと、Prologを一緒に使うと便利! こちら。

Prologを使う(動作確認 程度のProlog入門)

Prologで記述した、StarTrek(1976年頃流行した古いゲーム)

たけおか(竹岡尚三)のホームページ