双方向性のある階乗

はじめに

双方向性のあるプログラムを書くのはなかなか難しい。階乗を計算する双方向性のあるプログラムをPrologで書いたので、公開する。

双方向性のない直感的なプログラム

ソース

fact(0,1).
fact(X, X*Y2) :-
	X2 is X-1,
	fact(X2, Y2), !.

末尾再帰に見えるかもしれませんが、末尾再帰じゃないです。

双方向性のあるプログラム

ソース

f(0,1).
f(X,Res) :- f(1, X, 1, Res).

f(X, Max, Acc, Res) :-
	(X == Max, Res is X*Acc);
	(Acc == Res,
		((X == 1, Max is X);
		(X > 1, Max is X-1))).

f(X, Max, Acc, Res) :-
	(X @< Max; Acc @< Res),
	X2 is X+1,
	Acc2 is X*Acc,
	f(X2, Max, Acc2, Res).

実行例

| ?- f(0,X), f(1,Y), f(2,Z).

X = 1
Y = 1
Z = 2 ? ;

no
| ?- f(10,X).

X = 3628800 ? ;

(1 ms) no
| ?- f(X,1).

X = 0 ? ;

X = 1 ? ;

no
| ?- f(X,0). 

no
| ?- f(X,3628800).

X = 10 ? ;

no
| ?- 

終わりに

実は授業の課題。双方向である必要はないけど、せっかくなので。