Prolog in Elixir
?- assert(append([], Xs, Xs)).
true
?- assert((append([X | Ls], Ys, [X | Zs]) :- append(Ls, Ys, Zs))).
true
?- append([1,2],[a,b],X).
X = [1,2,a,b]
true
?- append(X,Y,[1,2,3]).
X = []
Y = [1,2,3];
X = [1]
Y = [2,3];
X = [1,2]
Y = [3];
X = [1,2,3]
Y = [];
false
?-
はじめに
ElixirでPrologインタプリタを作っています。ISO-Prologを思いっきり簡素化したサブセットです。Prologの動作原理を説明することを目的としています。実用性能はありません。
言語仕様
実装しつつ細部を整理します。今のところのラフな仕様は下記のとおりです。（かなりラフ）
SLDの動作が確認できる程度の仕様です。Pure-Prologです。
中置記法は :- メダカ記号など一定の組込述語と数式のみ有効。
is ＝ =.. == < > =< => は中置記法。
中置記法での左辺は変数、数、述語など単項に限定する。
本体部は連言のみ、選言は除外。ifthen -> は除外。
リスト。リストの要素は数、述語、変数しか受け入れない。節は受け入れない。数式も受け入れない。
例。
A is 1+2.
A = B+C.
A =.. [foo,B,C].
fact(N,A) :- N1 is n-1,
fact(N1,A1),
A is N*A1.
パーサを単純にすることが主な目的です。
引数なしの述語
foo() でもOKとする。パーサの負担を軽減する。
実装
データ構造
述語 [:pred,[name|argument]]
節 [:clause,head,body]]
頭部 head、述語。
本体部 body、[pred1,pred2,...predn]
式 [:formula,実体]
リスト Elixirのリストを流用
変数 アトム :X 大文字。 :x アンダーバー
無名変数 アンダーバー。ISO-Prologと異なり節中の無名変数は一切、区別されない。何ともUnifyする。
α変換 再帰に備えて置換する。 {:x 1} 自然数ｎとして引数に保持する。
（注） Elixirではアトムの個数は100万個程度が限界であり、GCによりアトムは回収されません。そこで上記の方法によりアトム生成を節約しています。
環境 連想リスト
述語定義 キーワードリスト
プログラム構造
Read,Prove,Print,Prologの４つのモジュールから成ります。
Prologモジュール：
repl/0 REPLを起動する。
データタイプ判定
is_pred/1
is_builtin/1
is_var/1
is_variant/1
is_atomvar/1
ゴール中の変数を見つける
find_var
ゴールにバックトラックを尋ねるask/1を付加する。
add_ask
Readモジュール
parse/1 述語や節のパース
parse1/1 連言であった場合や、節の本体部のパース
parse/3 数式のパース
read/1 述語、リスト、アトムの読み取り
read_list リストの読み取り
read_tuple tupleの読み取り
tokeniza 入力の文字列を分解、トークン単位のリストとする。
Proveモジュール
prove １つの述語を証明する
prove_all 複数の述語からなる連言を証明する。
prove_pred 述語を証明する
prove_builtin 組込述語を証明する。
eval 数式を評価する。
deref 環境から変数の値を取得する。
Pringモジュール
print/1 述語、節、アトム、数を表示する。
print_pred 述語を表示する。
print_clause 節を表示する。
print_list リストを表示する。
print_formula 数式を表示する。
動作例
今のところ、この程度までは動作するようになりました。GitHubに置いてあります。
https://github.com/sasagawa888/Prolog
$ mix prolog
Prolog in Elixir
?- assert(fact(0,1)).
true
?- assert((fact(N,A) :- is(N1,-(N,1)),fact(N1,A1),is(A,*(N,A1)))).
true
?- fact(10,X),write(X).
3628800true
?- halt.
goodbye
おわりに
細切れ時間がとれるとは改良を繰り返しています。よかったらお試しください。