継続渡渡しスタイル（CPS, Continuation Passing Style）とは、計算の結果を通常の戻り値として返さず、その結果を受け取るための関数（継続子）を引数として受け渡して処理を実行する手法です。これに対して、値自体をそのまま返却する従来の手法は直列的スタイルとも呼ばれます。

計算の連鎖と CPS 変換

通常の実装と比較すると、CPS を適用した関数は結果を即座に処理ではなく、次のステップへ委譲する形になります。以下の例は、ピタゴラスの定理を計算するプロセスを変換したものです。

-- 直接スタイルの実装
calcVal :: Num a => a -> a
calcVal x = x * x

calcSum :: Num a => a -> a -> a
calcSum a b = a + b

runGeometry :: Num a => a -> a -> a
runGeometry x y = calcSum (calcVal x) (calcVal y)

-- CPS 形式への書き換え
type Cont a r = a -> r

calcValCPS :: Num a => a -> Cont a r -> r
calcValCPS x k = k (x * x)

calcSumCPS :: Num a => a -> a -> Cont a r -> r
calcSumCPS a b k = k (a + b)

runGeometryCPS :: Num a => a -> a -> Cont a r -> r
runGeometryCPS x y k = 
    calcValCPS x $ \v1 ->
    calcValCPS y $ \v2 ->
    calcSumCPS v1 v2 k

上記の `runGeometryCPS` では、各計算段階で結果が変数に束縛されるのではなく、`k` と呼ばれる継続関数を介して順次結合されています。

継続子の結合演算子

CPS による処理の流れをつなぐ際、共通の組み合わせロジックを用意すると記述が簡潔になります。これはしばしば Monadic bind に相当する機能を持ちます。

-- 汎用的な CPS 接続コンテナ
flowCont :: Cont a r -> (a -> Cont b r) -> Cont b r
flowCont sa fb = \k -> sa (\x -> fb x k)

-- 組み合わせた実装
runGeometryFluent :: Num a => a -> a -> Cont a r -> r
runGeometryFluent x y k =
    flowCont (calcValCPS x) $ \vx ->
    flowCont (calcValCPS y) $ \vy ->
    flowCont (calcSumCPS vx vy) k

これにより、中間状態の変数名を明示せずに処理パイプラインを構築することが可能になります。

具体的な CPS 活用事例

単純な計算だけでなく、再帰処理やリスト操作などにも CPS は有効に機能します。以下に代表的な関数の CPS 変換例を示します。

平方根の計算

safeSqrt :: Floating a => a -> Cont a r -> r
safeSqrt x k = k (sqrt x)

useSqrt :: Double
useSqrt = safeSqrt 4.0 (+ 2)

階乗の累算

再帰的な階乗計算において、CPS 化することで末尾再帰最適化を活用しやすくなります。

factorialCPS :: Integral a => a -> Cont a r -> r
factorialCPS 0 k = k 1
factorialCPS n k = factorialCPS (n - 1) $ \acc -> k (n * acc)

resultFact :: Integer
resultFact = factorialCPS 4 ($ (+ 1))

リスト長のカウント

リスト要素数を CPS でカウントする場合、継続関数の合成を用いて効率よく実装できます。

listLenCPS :: [a] -> Cont Integer r -> r
listLenCPS [] k = k 0
listLenCPS (_ : xs) k = listLenCPS xs (k . succ)

totalLen :: Integer
totalLen = listLenCPS [1..100] id

実行フローの確認

これらの関数を実際に実行し、標準出力や値評価を確認する例です。

mainTest :: IO ()
mainTest = do
    -- 通常形式と CPS 形式の結果比較
    putStrLn $ show $ runGeometry 3.0 4.0
    runGeometryCPS 3.0 4.0 putStr
    
    -- 特殊ケース
    print $ safeSqrt 16.0 (+ 10)
    print $ factorialCPS 5 id