手動でCPS変換の練習
命名規則
継続はcontで表す
fという名前の関数をCPSにしたときの関数名はfcとする
1引数の単純な関数
Q.
code:hs
f x = x + 1
A.
code:hs
fc x cont = cont $ x + 1
1引数で内部で関数を呼ぶ
Q.
code:hs
g :: Int -> Int
g = undefined
f x = g x + 1
gもCPSに変えること
A.
code:hs
fc x cont = cont $ gc x $ \y -> y + 1
内部で2つの関数を呼ぶ
Q.
code:hs
h a b = f a + g b
h, f, gをCPSにする
A.
code:hs
hc a b cont = cont $ fc a $ \x -> gc b $ \y -> x + y
考え方としては、fとgを1つずつ継続渡しにしていくと良い気がするmrsekut.icon
まずhとfを継続渡しにし、gはそのままとして変換してみる
code:hs
hc a b cont = cont $ fc a $ \x -> x + g b
わかりにくければg bをなにか大きなひとかたまり♠とみなせばいい
code:hs
h a b = f a + ♠ -- もともと
hc a b cont = cont $ f a $ \x -> x + ♠ -- 継続渡し
次に、gも継続渡しに変える
code:hs
hc a b cont = cont $ fc a $ \x -> gc b $ \y -> x + y
こんなふうに改行すると演算している順序がわかりやすい
code:hs
hc a b cont = cont $
fc a $ \x ->
gc b $ \y ->
x + y
手続き的言語でこう書いているのと同じように見れる
code:js
const h = (a, b) => {
const aa = f(a);
const bb = g(b);
return aa + bb;
}
まずf aを計算して、次にg bを計算して、最後にそれらを足し合わせる、というのを順序を明示して書いている感じになっている
たぶん本当は(+)もCPSにしないといけないmrsekut.icon
単純な再帰関数
階乗fact
Q.
code:hs
fact n
| n == 0 = 1
| otherwise = n * fact(n-1)
A.
code:hs
factc n cont
| n == 0 = cont 1
| otherwise = factc (n-1) $ \x -> cont $ n * x
n==0のときは、ただたんに結果をcontに適用すればいいので簡単
otherwiseのときも、ちゃんと「演算の順序」に着目すればいい
まず最初にfact(n-1)が行われて、
その後にn * その結果の演算が行われる
と、考えれて、いったんcontの適用を無視すれば
otherwise = factc (n-1) $ \x -> n * xとかけることがわかる
contは「最終的な演算結果」に適用されれば良い
ここでの最終的な演算結果はn * xの部分になるので
ここに適用して、cont $ n * x
計算の過程を逐次的に書いてみると
code:aaaa
factc 3 id
=> factc 2 $ \x -> id $ 3 * x
=> factc 1 $ \y -> (\x -> id $ 3 * x) $ 2 * y
=> factc 0 $ \z -> (\y -> (\x -> id $ 3 * x) $ 2 * y) $ 1 * z
=> (\z -> (\y -> (\x -> id $ 3 * x) $ 2 * y) $ 1 * z) 1
=> (\y -> (\x -> id $ 3 * x) $ 2 * y ) $ 1 * 1
=> (\x -> id $ 3 * x) $ 2 * 1
=> id $ 3 * 2
=> 6
2回呼ぶ再帰関数
フィボナッチfib
「内部で2つの関数を呼ぶ」と「単純な再帰関数」の組み合わせ
Q.
code:hs
fib n
| n == 0 = 0
| n == 1 = 1
| otherwise = fib (n-1) + fib (n-2)
A.
code:hs
fibc n cont
| n == 0 = cont 0
| n == 1 = cont 1
| otherwise =
fibc (n-1) $ \x ->
fibc (n-2) $ \y ->
cont $ x + y
otherwiseの部分は上の考え方と同じようにやればできる
fib (n-2)を塊♠として、contも無視する
otherwise = fibc (n-1) $ \x -> x + ♠
♠も展開する
otherwise = fibc (n-1) $ \x -> fib (n-2) \y -> x + y
最終的な演算結果を`contに適用する
otherwise = fibc (n-1) $ \x -> fib (n-2) \y -> cont $ x + y
引数に取る関数も含めてCPSに変換数
Q.
code:hs
findFold pred pro seed [] = seed
findFold pred pro seed (x:xs)
| pred x =
let seed2 = pro x seed
in findFold pred pro seed2 xs
| otherwise = findFold pred pro seed xs
code:hs
findFoldc pred procCont seed [] cont = cont seed
findFoldc pred procCont seed (x:xs) cont
| pred x = procCont x seed $ \seed2 -> findFoldc pred procCont seed2 xs cont
| otherwise = findFoldc pred procCont seed xs cont