gprolog の残念な実装

prolog というプログラミング言語を使ったことのある人は，恐らくかなり少ないでしょう。prolog は、backtrack を言語として自然に持っていて、パズルを解くなどのことは、C 等の所謂手続き型言語に比べて、簡単に書くことの出来る言語です。コンピュータ関係に従事している人は、常識の一つとして知っておいても損はありません。

prolog の一つの処理系に、gprolog という、GNU の prolog 処理系があります。これを大学で演習に利用することになったのですが、少し複雑な再帰を書くと、すぐにメモリを大幅に使ってしまい、GLOBAL stack overflow で処理系ごと落ちてしまうということが良く有ります。

実は、gprolog は、GC の実装があまり良くありません。gprolog のソースを読んでみると分かりますが、実際に GC が起こる場合は、unification が fail し、backtrack が起こったときだけです。従って、いかにして backtrack を起こすか、ということが重要になります。また、gprolog は、末尾再帰を実装しておらず、これも、メモリを大幅に使ってしまう一つの要因となります。

以下の節で、gprolog で有効に GC を起こし、gprolog を快適に利用する方法を紹介します。(prolog 自体を有効に使いたい人には、gprolog はお勧めしません。SWI-prolog などを使うのが良いでしょう。)

失敗駆動ループ

先程も述べた様に、gprolog でメモリを解放するには、fail し、backtrack することが必要です。従って、失敗駆動ループを使えば、メモリを有効に使うことが可能です。

失敗駆動ループとは、fail し、backtrack することによって loop させる方法で、一般に次のように定義された述語 repeatを使って loop させます。

一般に、次の様な方法で用いることが多い様です。

規定回数 loop させたい場合は、for を使った loop にするのが良いでしょう。

ただ、これらの方法は、作り方を多少考える必要があるため、今まで手続き型や、関数型言語に慣れている人には少々使いにくい方法かもしれません。

findall

gprolod で depth first search を失敗駆動ループを使わずに書くと、Memory がいくらあっても足りません。しかし、findall を使うと、簡単に GC を起こすことが出来、メモリを節約することが出来ます。

例えば次のような述語を考えます(かなり適当に書いてます。メンバチェックも省略してますし。)。これは、Start から End への経路を探しているものですが、どこにも fail がないため、GC が起こりません。not_member や next で fail する可能性はあります。しかし、Start から End を見つけるまでに述語を呼び出し、それで起こった unification によって使われたメモリは、解放されません。

失敗駆動ループを使わずにこれを防ぐには、depth_first_search に findall を一段挟むのが効果的です。

この findall 自体に意味はありませんが、findall は、backtrack を勝手に行うので、GC が起こり、メモリを有効に利用することが出来ます。