はじめに

ISO-Prologの小さなサブセットにElixirの関数を活用する機能を追加した処理系を作っています。Elxlogといいます。この目指している構想についてご紹介します。

論理型と関数型の融合

後藤滋樹先生の「記号プログラミング」だったと思います。書籍が行方不明になっており曖昧な記憶をもとに書いています。Prologの紹介のところで　X is ... の右辺数式のところを拡張していけば論理型と関数型の融合になるのではないかという趣旨の話でした。

Prologはすべてを述語で記述します。数値計算も述語で記述します。竹内関数は次のようになります。

tarai(X,Y,_,Y):-
     X=<Y,!.
tarai(X,Y,Z,R):-
     X1 is X-1,Y1 is Y-1,Z1 is Z-1,
     tarai(X1,Y,Z,R1),tarai(Y1,Z,X,R2),tarai(Z1,X,Y,R3),tarai(R1,R2,R3,R).

下記のページから引用させていただきました。高速化の工夫が面白い記事です。
https://qiita.com/smallbigcats/items/821df49b63f50ae2d566

Prologではこうした計算は苦手です。多くのProlog処理系でスタックオーバーフローを起こします。Prologはバックトラックのために必要なデータを保持しています。こうした計算ではスタックが不足してしまうのです。

そこで、X is tarai(12,6,0) と関数として記述できればこうしたPrologの弱点をカバーすることができます。Elxlogではこれを可能としています。関数部分はElixirで記述します。


Elxlog ver0.05
?- X is elx_tarai(12,6,0).
X = 12
true
?-

 def tarai(x, y, z) do
    cond do
      x <= y -> y
      true -> tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
    end
  end

elx_というprefixがついたものは述語ではなくElixirの関数として認識しています。

シンプルなシンタックス

エジンバラPrologをベースにしたISO-Prologはシンタックス面においてかなりきつい要求をしています。これを満たすためにパーサはとても複雑となります。自作のO-PrologはISO-Prolog互換を目指して改良を重ねましたが、これはたいへんに困難な仕事でした。

簡単なところでは引数なしの述語です。


a :- write('Hello').

ISO-Prologではこのようにアトムで記述することとなっています。このaが述語であるかどうかは文脈に依存しています。前方参照の制限がついているのであればともかくとして、制限なく記述できるPrologではパーサはアトムaが述語として使われているのか？　単なるアトムなのかを文脈から判断しないといけません。



a() :- write('Hello').

上記のように引数がないことが明示されていればパーサは単純にすることができます。
他にもISO-Prologのシンタックスは無理難題がてんこ盛りです。理論的に正しいとはいえ実装は困難です。またその多くの機能はあまり利用されているとは考えられません。思い切って簡素化することとしました。

手続き的なものの排除

Prologは元来、述語論理をベースにしており、Whatを記述すれば、処理系がHowをうまく処理してくれる仕組みでした。しかし、実際的なプログラミング言語としては、そうもいっておられず、カットやif_then_elseのような手続き的なことを取り込んでいます。とあるオブジェクト指向を取り入れたProlog処理系はISO-Prologで書かれているのですが、もうPrologには見えません。手続き型の嵐が吹きまくっていました。これはPrologと言えるのだろうか？このオブジェクト指向Prologの作者には怒りさえ感じました。こんなものがPrologと言えるのだろうか？！

Elxlogではこれら手続き的なものを一切、排除します。そうしたものはElixirで書いた方が明快ですし、効率もよいです。

まとめ

これらのことから、PrologとElixirを融合した処理系、Elxlogの開発を進めています。
まだまだ開発途上ではありますが、コードを GitHub にて公開しています。
https://github.com/sasagawa888/Elxlog