はじめに

平成30年4月に自作O-Prologのコンパイラに末尾再帰最適化の機能を追加しました。まだまだ改良を要するものですが、記憶の新しいうちにそのアイディア、実装方法について書き記すこととしました。

単純な例

次のコードはO-Prologで最適化できるもっとも単純な例です。

foo(0).
foo(N) :-
    N1 is N-1,foo(N1).

is/2が使われていますのでバックトラックすることはありません。単純に整数を１だけ減算していくだけですから最適化が可能です。

コンパイルの様子は下記のようです。

opl -c compiler.pl
O-Prolog Ver0.81
| ?- compile_file('test.pl').
pass1
pass2
compiling tail foo
invoke gcc
yes
| ?- ['test.o'].
yes
| ?- time(foo(10000000)).
Elapsed Time=0.140009 (second)
yes
| 

最適化をしているため高速に実行することができます。

生成されているCコード

o-prologはPrologコードをC言語に変換し、それをコンパイルしたものを動的にリンクさせています。上記のfoo/1により生成されるコードは下記の通りです。コンパイラはインデントをつけていませんので、手修正によりインデントをつけて読みやすくしています。

#include "jump.h"
int b_foo(int nest, int n);
int b_foo(int nest, int n){
    int arg1,save1,varN1,varN;
    if(n == 1){
    arg1 = save1 = Jderef(Jget_goal(2));
    loop:
    if(Jnumeqp(Jmakeint(0),arg1) && 1){
        if(Junify(arg1,Jmakeint(0))==NO) goto exit1;
        Junify(save1,arg1);
        return(YES);
    }
    exit1:
    varN = arg1;
    varN1 = Jminus(Jderef(varN),Jmakeint(1));
    {arg1 = varN1;
    goto loop;
    return(NO);
    }return(NO);
}
void init_tpredicate(void){
(deftpred)("foo",b_foo);
Jset_aux(Jmakesym("foo"),SYS);
}
void init_declare(void){}

b_foo() というのが述語の本体です。再帰をループに変換しています。変数Nを頭部が取り込む際、通常ですとunifyをしますが、バックトラックをしないことからC言語の局所変数を割り当て破壊的代入をしています。

最適化の判断

どのような場合に最適化が可能なのか？は以前に検討していました。https://qiita.com/sym_num/items/82e42f740fc02d27eda6

決定性　その節の本体部が決定性の述語で構成されている。
末尾再帰　その節の本体部の最後が頭部と同じ述語名であり項数が同じである。
単方向性　その節の本体部のいずれかにis述語が使われていて、その右辺にある変数は節の頭部の変数でもあること。

この３つの要件を満たしたときに最適化可能であると判断しています。

最適化がうまくいかない例

上述のように考えていろいろなPrologコードを最適化できるか？と試してみました。これだけではうまくいかない例がみつかりました。

例1

下記はM.HiroiさんのページのAnother Problem例題集のコードです。

make_list(0, _, []).
make_list(N, X, [X | Xs]) :-
    N > 0, N1 is N - 1, make_list(N1, X, Xs).

このコードは上述の3要件を満たしています。ところが2番目の頭部で第3項は[X | Xs]となっています。Xsの計算は末尾の再帰呼び出しが終わらないと値が得られません。単純にはいきません。日本Prolog協会の紀さんからいただいた助言によれば昔はGスタックを利用してやる方法がとられていたということでした。しかしながら、今回はこれの最適化を見送り、後日取り組むこととしました。

このようなタイプの末尾再帰を最適化の対象外とするために変数の依存性をチェックすることとしました。末尾再帰で使われている変数に依存した頭部をもつ場合はこれを対象外にすることとしました。

例２

次のコードもM.Hiroiさんの例題集にあるものです。当初、コンパイラはこれも最適化可能であると判断していました。

combination(0, _, []).
combination(N, [X | Xs], [X | Zs]) :- N > 0, N1 is N - 1, combination(N1, Xs, Zs).
combination(N, [_ | Xs], Zs) :- N > 0, combination(N, Xs, Zs).

2番目の節の頭部に注目しますと、変数Xは第２、３項のいずれにも登場します。いずれかが他方に依存しているはずです。こういう場合にはunifyをせざるを得ません。頭部での変数の依存性も考慮して判定することし、このようなタイプのコードは今回の最適化から除外することとしています。

例3

M.HIroiさんの例題集からです。

divisor_sub(_, 0, Acc, [1 | Acc]).
divisor_sub(P, N, Acc, Ans) :-
    N > 0,
    M is P ^ N,
    N1 is N - 1,
    divisor_sub(P, N1, [M | Acc], Ans).

これは最適化可能な例です。当初、基底の第３項の[1 | Acc]のリストの部分を分解してcarの要素が１であるかを判定していました。そうしますとうまく基底で終了せずに無限ループになってしまうことがわかりました。定数は無視することとして対処しています。

以上、実際にやってみてわかったことから、対処療法的にコンパイラを修正しました。

効率化の測定

9queensのベンチマークコードを例にして測定を繰り返していました。最適化をしない以前のコンパイラは1秒以上かかっていました。ところがSWI-PrologやGNU-Prologはこれを20ミリ秒程度で実行します。

O-Prologで最適化を導入した後の実行速度は下記の通りでした。

O-Prolog Ver0.81
| ?- ['queens.o'].
yes
| ?- time(test).
Elapsed Time=0.024944 (second)
no

9queensを1回計算させるのにおよそ25ミリ秒です。かなり世界水準に近い値を出せるようになりました。ベンチマークのコードは下記の通りです。

% 9-queens program

test16 :- between(1,16,X),test,fail.

test :- queen([1,2,3,4,5,6,7,8,9],X),fail.

queen(Data, Out) :-
    queen_2(Data, [], Out).

queen_2([], _, []).
queen_2([H|T], History, [Q|M]) :-
    qdelete(Q, H, T, L1),
    nodiag(History, Q, 1),
    queen_2(L1, [Q|History], M).



qdelete(A, A, L, L).
qdelete(X, A, [H|T], [A|R]) :-
    qdelete(X, H, T, R).


nodiag([], _, _).
nodiag([N|L], B, D) :-
    D =\= N - B,
    D =\= B - N,
    D1 is D + 1,
    nodiag(L, B, D1).

最適化の対象になるのはnodiag/3です。これは最適化の要件をすべて満たしています。破壊的代入とループによる単純なコードに置き換えられます。9Queensの1回の実行にはおよそ36万回の述語呼び出しがされることがわかりました。このうちnodiag/3が呼び出されているのはおよそ30万回です。大部分を占めています。ここを単純なループに置き換えることにより大幅な実行時間の改善ができました。

これに気をよくしてcomp lang prolog に投稿したところ、Jekejeke-PrologのBurse先生より質問がありました。16回連続で9Queensを実行できるか？というものでした。Betweenの頑強性に問題があり、ここを改善してtest16/0のコードが動作するようになりました。

| ?- time(test16).
Elapsed Time=0.525179 (second)
no
| 

SWIやGNUはこれを300ミリ秒台で実行します。OPLは途中GCを起動しておりそこで約100ミリ秒をタイムロスしています。なかなか世界水準に達するのはたいへんなことです。改良を要するところです。

今後の展望

他にもnreverseですとかベンチマークをしてみるとSWIなどはかなり高速です。かなり最適化が施されているようです。おそらくバックトラックを要しないものを丁寧に抽出して効率の良いコードに変換しているのだろうと思われます。OPLはようやく最適化への第一歩を踏み出したところです。世界水準の実行速度を求めて今後とも改良を重ねる所存です。