N-Prolog ver3.98において末尾再帰最適化(tco)を導入しました。あれこれとバグを潰してver3.99においてほぼ満足のいく状態になりました。lispではSchemeにおいてtcoは必須とされていますし、多くのlisp処理系ではtcoに対応しています。これをPrologに応用しました。Prologの場合にはバックトラック、ユニフィケーションがあるのでlispほど単純ではありません。いろいろと試行錯誤しました。忘れないうちに書きとどめて置こうと思います。ご興味ありましたらお付き合いください。
N-Prologにおけるtco
ループに変換しています。以下は単純なtcoの例です。
foo(0) :- !.
foo(X) :- write(X),X1 is X-1,foo(X1).
|
v
//second clause
Jset_ac(save3,th);
Junbind(save2,th);
Jset_wp(save1,th);
varX1 = Jmakevariant(th);
varX = Jmakevariant(th);
save1 = Jget_wp(th);
if(Junify_var(arg1,varX,th) == YES && 1)
if (Jcall(1159,Jwlistcons(varX,NIL,th),th) == YES)if(Junify(varX1,Jminus(Jderef(varX,th),Jmakeint(1),th),th)==YES && Jinc_proof(th)){
arg1 = Jcopy_work(Jderef(varX1,th),th);
Junbind(save2,th);
Jset_ac(save3,th);
goto loop1;
このようにgotoによるループに変換しています。これにより再帰呼出しを抑えています。
割と単純な実例
下記は9queensのコードの一部です。Queenが利き筋にないことを確認するための述語です。
nodiag([], _, _).
nodiag([N|L], B, D) :-
D =\= N - B,
D =\= B - N,
D1 is D + 1,
nodiag(L, B, D1).
N-Prologのanalizerはパス１においてまず確実に停止する基底をカウントします。基底は[]を引数としてもっています。これはバックトラックが起きないことを示しています。もしも引数が数ですとバックトラックの可能性がのこされています。しかし、[]の場合にはそれ以上には計算の進めようがありません。
さらにパス２において決定性述語で構成されていることと、末尾再帰であることを見出します。算術演算などの多くの組み込み述語は決定性です。is/2などはバックトラックしません。さらに末尾で再帰しています。この時点でtco可能な述語であると判断します。
次の述語はtcoとなりません。
fact(0,1).
fact(N,X) :-
N1 is N-1,
fact(N1,X1),
X is N*X1.
基底の引数は数です。第一引数が０で止まったとしても、バックトラックをする可能性があります。もっとも、その場合には計算は終わりませんのでリソースエラーとなります。
決定性の述語とされるには基底を次のようにする必要があります。
fact(0,1) :- !.
fact(N,X) :-
N1 is N-1,
fact(N1,X1),
X is N*X1.
ただし、末尾再帰ではありません。しかし、バックトラックすることはありません。決定性の述語と判断することができます。
複雑な例
次のコードはベンチマークにあったクイックソートの例です。
% Quicksort
qsort([X|L], R, R0) :-
partition(L, X, L1, L2),
qsort(L2, R1, R0),
qsort(L1, R, [X|R1]).
qsort([], R, R) :- !.
% Partition list for quicksort
partition([X|L], Y, [X|L1], L2) :-
X < Y, !, partition(L, Y, L1, L2).
partition([X|L], Y, L1, [X|L2]) :-
!,partition(L, Y, L1, L2).
partition([], _ , [], []) :- !.
N-Prologのanalizerはパス１においてそれぞれが確実に停止する基底をもつことを認識します。
次にパス２において、partition/4が決定性の述語であることを判定します。末尾再帰をしていますが、tcoの対象にはなりません。第３引数において第１引数の変数Xを参照してリストを構成しています。これを行うには再帰呼出しをしないとできません。単純なループには変換できません。analizerは引数の独立性を解析しています。
この段階でqsort/3は判断がつきません。partition/4が決定性の述語であるかどうかはわからなかったからです。そこでパス３において判定にとりかかります。qsort/3は 確実に停止する基底をもっていますので決定性です。さらに末尾で再帰をしています。そこでtco可能と判断できそうです。しかし、N-Prologでうまく計算できません。R変数に結果が返されるのですが、RはUnifyによって次々に束縛されていきます。どうもこのあたりがうまくいっていないようです。このように直前に再帰がある場合にはtcoの対象とはせず、決定性の述語であると判断するようにしています。
実行効率
tcoにより再帰呼出しからgotoに置き換えることができます。変換されたCコードにおいて関数呼び出しよりもgotoによるループの方が効率がよいはずです。しかし、引数の値が破壊されないためにワーキング領域にコピーをするのでそこが若干のオーバーヘッドです。queensのnodiag/3をtcoにして計測すると次のとおりでした。
図
再帰呼出しの場合とほとんど変わりありませんでした。それでも10MLIPS程度を出すことができ以前よりは進歩しています。
Prologの性能を引き出す
Prologはユニフィケーションとバックトラックがその特長であり、計算のための思考をHowからWhatに集中させることができます。その分、計算機にとっては処理が重くなりlispのような単純なものよりも時間コストがかかります。その中にあってもバックトラックを必要としない決定性の述語、さらには末尾再帰になっているものがあります。それらを単純な計算に置き換えることによりPrologの特長を活かしつつ計算コストを下げることが可能です。以前、自作のEasy-ISLispにおいてtcoを実装しましたが、N-Prologにおけるtcoはそれより遥かに難しいものでした。analizerをPrologで書くことによってtcoに対する理解が深まったように感じています。