Help us understand the problem. What is going on with this article?

Prologの竹内関数

More than 1 year has passed since last update.

Prolog Advent calendar 2018 の25日が埋まっていません。
最後のみ投稿が無いのは残念ですので不束ながら埋め草の投稿をしたいと思います。

M.Hiroi's Home Pageを拝見しますと、よくベンチマークの一例として
たらいまわし関数(竹内関数)が出てきます。またその高速化の話も出てきます。
これに関しprologに関して知りたいと思い検索しましたが、見つけられませんでした。
そこで自分で考えてみました。Prologをされている多くの方には既知のことかもしれませんが、
超初心者(今時いれば)の方には多少は参考になるかもしれません。
まず、M.Hiroiさんのjuliaのコードです。

function tarai(x, y, z)
  if x <= y
    y
  else
    tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
  end
end

これをPrologに移すのですが、prologは結果の戻り方が他の言語と違いますので、ちと面倒です。

%tarai(12,6,0,R)     
%:-initialization(tarai(12,6,0,R)).   

tarai(X,Y,_,Y):-
     X=<Y,!.
tarai(X,Y,Z,R):-
     X1 is X-1,Y1 is Y-1,Z1 is Z-1,
     tarai(X1,Y,Z,R1),tarai(Y1,Z,X,R2),tarai(Z1,X,Y,R3),tarai(R1,R2,R3,R).

が考えられます。
しかし、これでは私の環境では、tarai(14,7,0,R)でも時間がかかります。
そこで高速化ですが、M.Hiroiさんは、Juliaの一例としてクロージャを使ったものを示されています。

function tarai_lazy(x, y, z)
  if x <= y
    y
  else
    zz = z()
    tarai_lazy(tarai_lazy(x - 1, y, () -> zz),
               tarai_lazy(y - 1, zz, () -> x),
               () -> tarai_lazy(zz - 1, x, () -> y))
  end
end

これと同じ動作をするコードをprologで書きたいのです。
swi-PrologにFreeze/2やwhen/2という述語がありますが、この例での使い方はよくわかりません。
Goalを呼び出す述語にcall(Fn)やL=[H|T],apply(H,T)などがありますので、これを使ってみます。
call(Fn)では値が取り出せません(多分)ので実行後Fn=..L(ユニブ)でリストにします。

%SWI-Prolog version 7.4.2
%tarai(14,7,[self,0],R)     
%:-initialization(tarai(14,7,[self,0],R)).   

self(_).

tarai(X,Y,_,Y):-
     X=<Y,!.
tarai(X,Y,Z,R):-
     Z=[H|T],apply(H,T),last(T,Z0),X1 is X-1,Y1 is Y-1,Z1 is Z0-1,
     tarai(X1,Y,Z,R1),tarai(Y1,Z0,[self,X],R2),tarai(R1,R2,[tarai,Z1,X,[self,Y],_],R).  
%SWI-Prolog version 7.4.2
%tarai(14,7,self(0),R)     
%:-initialization(tarai(14,7,self(0),R)).     

self(_).

tarai(X,Y,_,Y):-
     X=<Y,!.
tarai(X,Y,Z,R):-
     Z,Z=..L,last(L,Z0),X1 is X-1,Y1 is Y-1,Z1 is Z0-1,
     tarai(X1,Y,Z,R1),tarai(Y1,Z0,self(X),R2),tarai(R1,R2,tarai(Z1,X,self(Y),_),R).

自分自身を返す関数が見つかりませんでしたのでself/1を定義しました。
4行目のZはcall(Z)と同じです。
両方とも適当に変数の値を表示させると、Juliaのコードと同じ結果が出ます。
しかし実は、

self(_).

tarai(X,Y,_,Y):-
     X=<Y,!.
tarai(X,Y,Z,R):-
     Z,Z=..L,last(L,Z0),X1 is X-1,Y1 is Y-1,Z1 is Z0-1,
     tarai(X1,Y,Z,R1),tarai(Y1,Z0,self(X),R2),tarai(R1,R2,_,R).       

でも同じ結果が出ます。
つまり最後のtarai(Z1,X,self(Y),_)は評価されていないようです。
(wikipediaにもzの値は結局使っていないと書いてありました。)
ということで、M.HiroiさんのJuliaと同じ結果の出るコードは書けるけれど正しいかどうかわからない
という結果になってしまいました。

お粗末でした。

追加。
蛇足ですが、高速化すると、変数を表示させたときに元の関数と異なるのが不思議です。

smallbigcats
30年以上の日曜プログラマ。 スパゲッティプログラムの癖が抜けません。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away