原因判明
N-Prolog ver3.98で末尾再帰最適化（TCO)を導入しました。これにはまだバグがあり次のコードで動作していませんでした。
fact(N, X) :- fact_(N, 1, X).
fact_(N, P, X) :- N > 0,
N1 is N - 1,
P1 is P * N,
fact_(N1, P1, X).
fact_(0, X, X) :- !.
fact_/3はXに計算結果が累積されます。TCOによりループに変換されます。再帰動作ですとXはX->X'->X''と変数が連鎖していくのですが、繰り返しのため破壊的に変数に代入しています。変数の連鎖はありません。そうすると基底においてXの値が求まったとしても呼ぼだしもとの変数Xとのリンクが途切れてしまっています。そこで基底においては改めて呼び出しもとの変数とのUnifyが必要でした。コンパイラを改良してver4.00でTCOが完全動作するようになりました。
red-cut と green-cut
上記のコードは本来は下記のように書きます。green-cutというのだそうです。上記のように基底にカットを使うのはred-cutというのだそうです。
fact(N, X) :- fact_(N, 1, X).
fact_(N, P, X) :- N > 0,
N1 is N - 1,
P1 is P * N,
fact_(N1, P1, X).
fact_(0, X, X).
基底においてカットを使っていません。本体部でN > 0をもたせているのでバックトラックすることがありません。
しかし、これをコンパイラに理解させるのは手間がかかります。静的解析により計算しようとしている内容を把握しないといけません。意味論までかかわることになります。そこでN-Prologでは簡易的に本体部が！で終わっているかどうかで決定性を判別するようにしています。これによりコンパイラは簡単ですみます。
非効率
さて、TCOが機能したのでqsort/3を最適化してみるとかえって遅くなるのです。
% 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([], _ , [], []) :- !.
第１節の本体部においてqsort/3が２回出現します。最初の方は再帰呼び出しをし、２回めの方はループになります。これだと遅いのです。理由は変数の連鎖にあります。変数Rにソート結果が蓄積されます。最初のqsortは再帰呼び出しをされており変数の連鎖になっています。ところがそのあとのqsortは繰り返しにするために破壊的代入しその際にderefをしています。変数の連鎖をderefすると時間がかかるのです。
そういうわけでこのqsortのような２回呼び出される場合にはTCOにせず普通に決定性述語として再帰呼出しをすることにして速度を改善しています。
N-Prologは下記においてOSSとして公開しています。ぜひ、お試しください。
https://github.com/sasagawa888/nprolog