Prologにおける末尾再帰最適化判定

#はじめに
O-Prologのためのコンパイラを制作しています。JUMP計画といいます。ほぼできたのですが、未達成の課題のひとつに末尾再帰最適化があります。Prologのコードは通常、バックトラックします。しかし、特定の場合にはバックトラックをしない場合もあります。そのような場合にはC言語のLOOPに置き換えることが可能であり、スタックを消費しない効率のよいコードを生成することができます。どのような場合に末尾再帰最適化が可能なのかを判定するPrologコードについて検討しました。

#独自拡張述語

o_clause_with_arity/3
第１引数を述語名、第2引数を項数とする既に定義された節をすべて連結して第3引数にunifyします。

例

boo([]).
boo([X|Xs]) :- write(X),boo(Xs). 

| ?-o_clause_with_arity(boo,1,Y).
Y = [boo([]),boo([X|Xs]) :- write(X),boo(Xs)]
yes
| 

o_variable_convert/2
第一引数に与えられた節あるいは述語のうちProlog変数（X,Yなど）をvarX,varYというアトムに変換して第二引数にunifyします。メタな立場である解析器での変数と、扱うコード中の変数とを区別し取り扱い易くするためです。

o_predicate/1
引数がユーザー定義の述語である場合に真、そうでない場合に偽を返します。

o_builtiin/1
引数が組込述語である場合に真、そうでない場合に偽を返します。

o_is/2
第一引数がis述語である場合にその右辺の中のコンパイラ変数をリストにまとめて第二引数にunifyします。

o_clause_head/2
第一引数の節の頭部を取り出して第二引数にunifyします。

o_clause_body/2
第一引数の節の本体部を取り出して第二引数にunifyします。

#アイディア
末尾再帰最適化の述語でC言語のループに変換可能なものを次の３つの要件を満たすものと考えました。

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

#テスト

foo(0).
foo(X) :-
	X1 is X - 1,foo(X1).

fact(0, 1).
fact(X, Sum) :-
    X > 0, X1 is X - 1, fact(X1, Sum1), Sum is X * Sum1. 

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


| ?- tail_optimize(foo,1).
yes
| ?- tail_optimize(fact,2).
no
| ?- tail_optimize(nodiag,3).
yes
| 

#コード

tail_optimize(P,N) :-
	o_clause_with_arity(P,N,C),
    o_variable_convert(C,C1),
    deterministic(C1),
    tail_recursive(C1),
    unidirectional(C1).
    
    
deterministic([]).
deterministic([C|Cs]) :-
	o_predicate(C),
    deterministic(Cs).
deterministic([C|Cs]) :-
	o_clause(C),
    o_clause_body(C,Body),
    deterministic1(Body),
    deterministic(Cs).

deterministic1(Body) :-
	o_predicate(Body).
deterministic1(Body) :-
	o_builtin(Body).
deterministic1([',',Body1,Body2]) :-
	o_builtin(Body1),
    deterministic1(Body2).

lastbody(Body,Body) :-
	o_builtin(Body).

lastbody(Body,Body) :-
	o_predicate(Body).

lastbody([_,_,Body],Last) :-
	lastbody(Body,Last).

tail_recursive([]).
tail_recursive([C|Cs]) :-
	o_predicate(C),
    tail_recursive(Cs).
tail_recursive([C|Cs]) :-
	o_clause(C),
    o_clause_head(C,H),
    o_clause_body(C,B),
    tail_recursive1(H,B),
    tail_recursive(Cs).
    
tail_recursive1(Head,Body) :-
	lastbody(Body,Last),
    functor(Head,Pred1,Arity1),
    functor(Last,Pred2,Arity2),
    Pred1 == Pred2,
    Arity1 == Arity2.

unidirectional([]).
unidirectional([C|Cs]) :-
	o_predicate(C),
    unidirectional(Cs).
unidirectional([C|Cs]) :-
	o_clause(C),
    o_clause_head(C,H),
    o_clause_body(C,B),
    unidirectional1(B,H).
    

unidirectional1([',',Body1,Body2],H) :-
	o_is(Body1,Y),
    H =.. A,
	subset(Y,A).
unidirectional1([',',Body1,Body2],H) :-
	o_builtin(Body1),
    unidirectional1(Body2,H).


subset([],_).
subset([X|Sub],Set) :-
	member(X,Set),
	subset(Sub,Set).