CPS変換

継続渡し形式(CPS)変換とは何か？ - 言語ゲームをRubyで写経してみました。Rubyでは末尾再帰が最適化されないので、わざわざCPS変換で書く意味はないと思います。しかしCPS変換で書かれたプログラムってすんなりと理解できるものなのでしょうか？ 僕にはまだ無理です。

# 普通の階乗。
def fact(n)
  if n == 0
    1
  else
    n * fact(n - 1)
  end
end

p fact(10) # => 3628800

# CPS変換版の階乗。
def fact_cps(n, cont)
  if n == 0
    cont[1]
  else
    fact_cps(n - 1, lambda {|a| cont[n * a] })
  end
end

p fact_cps(10, lambda {|a| a }) # => 3628800

そういえば、HaskellでもCPS変換ってあんまり使わないような。こういう場合は正格評価するのがセオリーだと思います。

sum_cps 0 cont = cont 0
sum_cps n cont = sum_cps (n - 1) (\ a -> cont $ n + a)

sum2 0 a = a
sum2 n a = seq a $ sum2 (n - 1) (n + a)

*Main> sum_cps 1000000 id
*** Exception: stack overflow
*Main> sum2 1000000 0
500000500000