F#で継続渡し形式(CPS)変換を抽象的に考えてみたら、それってつまりHaskellの継続モナドみたいなものでした。ということで継続ワークフロー(簡易版)作った。

[前置き]

継続とは

プログラミングにおいて「継続」とは、ある計算のある時点における「残りの計算」を表す概念のこと。
つまり、ある計算過程の瞬間におけるその過程の未来全体を表すものを意味する。
プログラミング言語で継続を扱う機能を導入すると、ユーザによるプログラムの実行順序の制御が可能になる。
プログラミングスタイルとして継続を表現したのが、継続渡しスタイルである。

詳しくは、下記のページを参照されたい。
なんでも継続
http://practical-scheme.net/docs/cont-j.html

継続渡し形式(CPS)とは

継続渡しスタイル(Continuation Passing Styleの頭文字をとってCPS)は、実際のプログラムの中では
継続をクロージャとしてコールバック関数として渡すような関数を定義するプログラミングスタイルのこと。

[本題]

F#で継続渡しスタイル(CPS)変換を抽象的に考えてみたら、それってつまりHaskellの継続モナドみたいなものでした。

檜山正幸のキマイラ飼育記 - CPS（継続渡し方式）変換をJavaScriptで説明してみるべ、ナーニ、たいしたことねーべよ
http://d.hatena.ne.jp/m-hiyama/20080116/1200468797

を読んでいて、「CPS変換を行うメタメタ関数」ってのが面白いなあと思いまして、
継続渡しスタイル(CPS)を抽象的に考えて、F#でもCPS変換を簡易的に行えるメタメタ関数を作ったら面白そうかなと考えていました。
しばらくして、そういえばHaskellにそんなんあったっけなあ・・。そこで思い出したのがHaskellの継続モナド。

モナドのすべてより「Continuationモナド(継続モナド)」
http://www.sampou.org/haskell/a-a-monads/html/contmonad.html

上記リンク先の説明にあるように、継続モナドはCPSの計算を抽象的に表現しているモナドです。
継続渡しスタイルな関数(以下CPS関数)は、引数に関数をとり、自身の処理の最後でその関数(継続)を呼ぶというもので、CPS関数に継続として別のCPS関数を渡し、その別のCPS関数に継続として更に別のCPS関数を渡してゆく連鎖、つまりCPS関数のネストが、全体として継続渡しスタイルなプログラムを形成することになる。
CPS関数をモナドにくるんで >>=(bind関数)で繋ぐことで、継続モナドはCPS変換を行うメタメタ関数な表現を実現していると言える。

F#で継続ワークフロー(簡易版)を作ってみましょう

よろしいならばF#で継続ワークフローだ。
ということで、簡易なCPS変換をサポートする継続ワークフローを作ってみる。

ContinuationWorkflow.fs

#light
namespace Workflow

///継続ワークフロー
type ContinuationBuilder() = 
  ///CPS変換します
  member this.Return(a) = fun k -> k a
  ///継続バインド
  member this.Bind(m,f) = fun k -> m (fun a -> f a k)

module ContinuationWorkflow = 
 ///ContinuationBuilderを生成します
 let cps = new ContinuationBuilder()

たったこんだけです。基本的にHaskellの継続モナドからパクっただけみたいなってゆー(笑
モナドで包む部分とcallCCについては、よくわからない＆面倒くさい＆今回の主目的ではないので華麗にスルーしました。

ちなみに、Haskellの継続モナドの定義

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) } 
  
instance Monad (Cont r) where 
    return a       = Cont $ \k -> k a                       
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k) 

class (Monad m) => MonadCont m where 
    callCC :: ((a -> m b) -> m a) -> m a 
 
instance MonadCont (Cont r) where 
    callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

継続ワークフローをお試し

では、さっそく継続ワークフローを味見してみる。

ContinuationWorkflowTest.fs

#light
open System
open Workflow.ContinuationWorkflow 

module CpsTest = 
 let Test1 =
  let f x = cps {return "F",x }
  let sharp (x,y) = cps {return  x + "#", y}
  let beginner (x,y) = cps {return y + "は" + x + "初心者です。"}
  let expert (x,y) = cps {return y + "は" + x + "達人です。"}

  //継続ワークフローで継続渡しスタイル (遅延評価)
  let fsharp x =
    cps {let! a = f x
         let! b = sharp a 
         match x with 
         "zecl"   -> let! c = beginner b
                     return lazy c
         | _      -> let! c = expert b
                     return lazy c
        }

  //お試し
  printfn "%s" <| fsharp "zecl" (fun x -> x.Force ())
  printfn "%s" <| fsharp "Don Syme" (fun x -> x.Force ())
  printfn ""


 let Test2 =
  //ふつうのフィボナッチ数列
  let rec fibo n =
    if n <= 1 then 1
    else fibo (n - 1) + fibo (n - 2)

  //継続渡しスタイルで書いたフィボナッチ数列
  let rec fiboCps n cont =
    if n <= 1 then cont 1
    else fun x -> fiboCps (n - 2) <| fun y -> cont (x + y)
         |> fiboCps (n - 1) 


  //継続渡しスタイルのフィボナッチ数列関数で周期 (遅延評価)
  let fiboCpsCycle n m =
    cps {let! a = fiboCps n 
         return lazy (a % m)
        }

  //ふつうのフィボナッチ関数を継続ワークフローで継続渡しスタイルに
  let fibo2 n = cps {return fibo n}
  //継続ワークフローでCPS変換したfibo2を使って周期 (遅延評価)
  let fibo2Cycle n m = 
    cps {let! a = fibo2 n
         return lazy (a % m)    
        }

  //print_anyして改行
  let panyn = print_any >> Console.WriteLine
  //お試し
  for i = 0 to 10 do (fibo i |> panyn)
  printfn ""
  for i = 0 to 10 do (fiboCps i (fun x -> panyn x))
  printfn ""
  for i = 0 to 10 do (fiboCpsCycle i 2 (fun x -> x.Force () |> panyn))
  printfn ""
  for i = 0 to 10 do (fibo2Cycle i 2 (fun x -> x.Force () |> panyn))

#if COMPILED
[<STAThread()>]
do
 CpsTest.Test1 
 CpsTest.Test2 
let key = Console.ReadKey ()
#endif

実行結果

zeclはF#初心者です。
Don SymeはF#達人です。

1
1
2
3
5
8
13
21
34
55
89

1
1
2
3
5
8
13
21
34
55
89

1
1
0
1
1
0
1
1
0
1
1

1
1
0
1
1
0
1
1
0
1
1

これはやさしいCPS変換サポーターですね。
脳内CPS変換が苦手な人にもかなり有用だと思います。継続ﾜｰｸﾌﾛｰ(ﾟДﾟ)ｳﾏｰ!!!
ですが、多様は禁物。やはりご利用は計画的にといった感じでしょうか。

ちなみに、C#でもクロージャ(ラムダ式)が使えるので、C#で継続渡し形式っぽく
プログラムを書くことも可能といえば可能なんだけど、
可読性やパフォーマンスの観点から言って、C#でやる意味は皆無っぽいですね。