スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#入門初級編 第8回 CPS (Continuation Passing Style)(1)

Continuation PassingStyleとは関数に、(1)parameter群と(2)「なんらかの評価が終わったときに次に何を計算するのかを指示する関数(後で適用する関数)」を与えることによって、計算をさせる方法です。
継続渡しスタイル (CPS) 」と訳されます。
 
例えば
let contExp0 x y (cont:int -> int) = cont (x + y)
 
は「第一引数xと第二引数yを加えたものに、関数contを適用する」という関数となります。
 
> let contExp0 x y (cont:int -> int) = cont (x + y);; 
 
val contExp0 : int -> int -> (int -> int) -> int
 
> contExp0 3 5 (fun x -> x);;
val it : int = 8
 
> contExp0 3 5 (fun x -> 2*x);;
val it : int = 16
 
またcontExp0は次のようにも書けます。
 
let contExp0 x y cont = (fun x y -> (x+y) |> cont)
 
CPS を使うと再帰呼び出しを末尾再帰に変換することができます。たとえば、階乗の計算を CPS でプログラムすると次のようになります。 
 

let rec fact n cont =
    if n = 0 then 
        1 |> cont
    else
        fact (n-1) (fun x -> n *x |> cont) 
        
ここで、説明の為に(fun x -> n * x)を f_nと書くことにします。
つまり、引数をn倍するという作用をもつ関数です。
 
それでは、f 4 contがどのように評価されるかを考えてみたいと思います。
 
fact 4 cont =
    fact 3 (fun x -> 4*x |> cont)
   =fact 3 (f_4 >> cont) //この行以下は疑似コードです(f_4は後で実行される)
   =fact 2 (fun x -> 3*x |> (f_4 >> cont))  
   =fact 2 (f_3 >> f_4 >> cont)
   =fact 1 (fun x -> 2*x |> (f_3 >> f_4 >> cont))
   =fact 1 (f_2 >> f_3 >> f_4 >> cont)
   =fact 0 (fun x -> 1*x |> (f_2 >> f_3 >> f_4 >> cont))
   =fact 0 (f_1 >> f_2 >> f_3 >> f_4 >> cont)
   = 1 |> (f_1 >> f_2 >> f_3 >> f_4 >> cont)
 
すなわち fact (n-1) (fun x -> n *x |> cont) 
という式の(fun x -> n *x |> cont) のn *xの部分は、nより後の継続の計算結果をxとしてnの段階で、その値にどのような作用を加えるかを表したものとなります。
この部分は、上の例の場合
fact (n-1) (fun x -> cont(n*x))とも
fact (n-1) (fun x -> n*x |> cont)とも
fact (n-1) (((*) n) >> cont) とも書けます。
 
nの値が減るにつれて、渡されるパラメーターcont(その後で施す作用)が累積(合成)されていっていき、底までいった段階で、その関数が適用されることに留意してください

また
fact 4 (fun x -> ??)と実行するときの、(fun x-> ??)の部分は出来上がった数(この場合は4!)に対し最後に一回だけ適用される、関数蓄積の為の「種」兼「蓋」のような役割をする関数となっています。 
 
では実行してみます。
 
> let rec fact n cont =
    if n = 0 then 
        1 |> cont
    else
        fact (n-1) (fun x -> n *x |> cont);;
 
val fact : int -> (int -> 'a) -> 'a
//contは(int -> 'a)型
 
> fact 4 (fun x -> x);;
val it : int = 24
 
> fact 4 (fun x -> printfn "result = %d" x);;
result = 24
val it : unit = ()
 
 
次はリストを対象にしてみます。
まずは、List.iter系の例です。
 
let rec ListAllDisp lst (cont: unit -> unit) =
    match lst with
    | [] -> 
        () |> cont
    | hd :: tl ->
        ListAllDisp tl (fun () -> printfn "%A" hd |> cont ) 
 
        
> ListAllDisp [1;2;3] (fun () -> printfn "終わり") ;;
3
2
1
終わり
val it : unit = ()
 
逆順で表示されることに留意してください。
 
これを一般化すると次のようになります。
 
let rec ListRevIter (lst: 'a list) (g:'a ->unit) (cont: unit -> unit) =
    match lst with
    | [] -> 
        cont()
    | hd :: tl ->
        ListRevIter tl g (fun () -> g hd |> cont) 
        
> ListRevIter [1;2;3] (fun e -> printfn "ele = %d" e) (fun () -> printfn "終わり");;
ele = 3
ele = 2
ele = 1
終わり
val it : unit = ()
 
次はリストの長さを求める関数をこのスタイルで書いてみます。
 
let rec myLen lst cont =
    match lst with
    | [] ->
        0 |> cont
    | hd :: tl ->
        myLen tl (fun x -> x + 1 |> cont)
 
実行例
> myLen [0;1;2;3;4] (fun x-> x);;
val it : int = 5
 
F#では(fun x -> x)という関数はidという名前で登録されていますので、上は次のようにも書けます。
 
> myLen [0;1;2;3;4] (id);;
val it : int = 5
 
 
myLenは次のようにも書けます。
 
let rec myLen lst cont =
    match lst with
    | [] ->
       0 |>  cont
    | hd :: tl ->
        myLen tl (fun x -> cont(x + 1))
        
 
let rec myLen lst cont =
    match lst with
    | [] ->
       0 |>  cont
    | hd :: tl ->
        myLen tl (((+) 1) >> cont)
        
 
(練習)リスト内のすべての要素を加えた和を返す関数myListSumを上のスタイルで書いてみてください。
 
(解答例)
 
let rec myListSum lst cont =
    match lst with
    | [] ->
       0 |>  cont //もしくはcont 0
    | hd :: tl ->
        myListSum tl (((+) hd) >> cont) 
        //myListSum tl (fun x -> cont(hd + x))
        //myListSum tl (fun x -> x + hd |> cont)

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。