継続渡し形式挿話。prolog と haskell でパターンマッチング

prolog と haskell の関係について質問がありましたが、そんな事私に分かるわけ無いです。しかし、両者のコードを愛でてみるのは楽しそうなのでやってみました。prolog で CPS で書くというのがどういう事か分からなかったので、普通に末尾回帰にした版を並べて書いてみました。

-- 階乗を普通に
fact 0 = 1
fact x = x * fact (x - 1)

-- 末尾回帰版
fact_cps x = fact_cps' x 1
fact_cps' 0 ans = ans
fact_cps' x tally = fact_cps' (x - 1) (tally * x)

% 階乗を普通に  ?- fact(10, X). => X = 3628800
fact(0, 1).
fact(X, Ans) :-
    X > 0,
    X1 is X - 1,
    fact(X1, Ans1),
    Ans is X * Ans1.

% 末尾回帰版  ?- fact_cps(10, X). => X = 3628800
fact_cps(X, Ans) :- fact_cps(X, 1, Ans).
fact_cps(0, Ans, Ans).
fact_cps(X, Tally, Ans) :-
    X > 0,
    X1 is X - 1,
    Tally1 is X * Tally,
    fact_cps(X1, Tally1, Ans).

確かに似てますね。パターンマッチングのある言語なら何でも prolog に似てるという話になるのかも知れない。prolog のバックトラッキングを抜いて、述語の最後の引数を戻り値だと思えばほとんど haskell ですね。