N-Prolog コンパイラ最適化

はじめに

N-Prologはコンパイラも装備しています。当初、最適化を施していないため、インタプリターに比し40%程度の改善しか見られませんでした。一定の決定性かつ末尾再帰の述語につき最適化をいれました。

例

下記はQueens問題のコードの一部です。クイーンが利き筋にあるかどうか？を判定するものです。これは最適化が可能です。

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

生成するCコード

int b_nodiag(int arglist, int rest);
int b_nodiag(int arglist, int rest){
int n,head,varD1,varN,varL,varB,varD,var2,var1;
n = Jlength(arglist);
if(n == 3){
loop:
Jinc_proof();
var2 = Jmakevariant();
var1 = Jmakevariant();
head = Jwcons(NIL,Jwcons(var2,Jwcons(var1,NIL)));
if(Jcar(arglist) == NIL && 1) return(Junify(arglist,head));
varN = Jcar(Jcar(arglist));
varL = Jcdr(Jcar(arglist));
varB = Jcar(Jcdr(arglist));
varD = Jcar(Jcdr(Jcdr(arglist)));
{if(!Jnot_numeqp(Jderef(varD),Jminus(Jderef(varN),Jderef(varB)))) return(NO);
if(!Jnot_numeqp(Jderef(varD),Jminus(Jderef(varB),Jderef(varN)))) return(NO);
varD1 = Jplus(Jderef(varD),Jmakeint(1));
arglist = Jwcons(varL,Jwcons(varB,Jwcons(varD1,NIL)));
goto loop;
}}return(NO);
}

ベンチマーク

世界最高速級のSWI-Prologと比較しました。9queensを表示なして１６回連続して実行するものです。

２２％程度遅くなっています。しかし、歴史のあるswiに比較してまあまあ悪くはない速度を出しています。

さらに

さらに最適化可能なコードの守備範囲を広げていく予定にしています。

コンパイラのための独自拡張述語

n_clause_with_arity/3　第1項に述語名、第２項に項数を与え、その要件を満たすすべての節、述語を第３項にunifyする。

n_variable_convert/2　第１項に与えられた節に含まれる変数をvar＊形式してリストとして第２項にunifyする。
n_atom_convert/2 第１項に与えられたアトムをC言語の関数名として使えるように変換する。
今のところ：を＿に変更しているだけ。
n_filename/2　第１項で与えられたファイル名から識別子を取り除いたアトムを第２項にunifyする。
n_arity_count/1　第１項で与えられたアトムを述語名とするすべての節、述語の項数をリストにして第２項にunifyする。
n_reconsult_predicate_list/1　reconsult/1で読みこだファイルのすべての述語、節の述語名と項数を　P/Aの形式にしたリストにして第１項へunifyする。

n_reconsult_predicate/1 reconsult/1 で読み込んだファイルのすべての述語名を第1項に
unifyする。バックトラックする。
n_defined_predicate/1 節の定義を述語ならyes、そうでなければno
n_compiler_variable/1　コンパイラで使用する形式の変数ならyes　そうでなければno（例　varX)
n_generate_variable/2　第１項の節に含まれる変数をvarXのような形式でリストとして第２項にunifyする。
n_generate_all_variable/1　第１項で与えられたアトムを述語名とするすべての述語、節で使用されている変数をvar＊の形式でリストとして第２項にunifyする。
n_compiler_anoymous/1　第１項が　var_　のようにコンパイラ内部形式の無名変数である場合にyes　そうでなければno
n_compiler_variable/1　第1項が　varX　のようにコンパイラ内部形式の変数である場合にはyes　そうでなければno
n_argument_list/2 第一引数の述語の項部分をリストに変換して第二引数にunifyする。
n_decompose/3 第一引数をそれがなんであれ、carとcdrに分解し、第二、第三引数にunifyする。
n_property/2 第一引数に応じて第二引数に次のアトムをunifyする。
組込述語＝builtin、ユーザー述語＝predicate、関数＝function、オペレーション＝operation、コンパイル済み述語＝compiled

n_findatom　第一引数のアトムで第二引数の属性をもつものの実アドレスを第3引数にunifyする。
属性は下記の通り。
組込述語＝builtin、ユーザー述語＝predicate、関数＝function、オペレーション＝operation、コンパイル済み述語＝compiled