ゆずとみかんといちご

ゆるゆる書きます

CPS というプログラミングスタイルの導入の話

今日 (もう昨日だけど) 大学の授業で CPS というプログラミングスタイルの話を聞きました．これを読んでいる人はきっと CPS が 'Continuation-Passing Style (継続渡し形式)' のことで，それがどのようなスタイルのプログラミング手法なのかも分かっていて，さらに JS を CPS で書いたり継続を限定してみたりしている人ばかりだと思うので，そういう「どう使うか」みたいな話はしません．できません．ケイゾクムズカシイ．

今回は授業で「プログラミング中のどこで CPS という概念に辿り着くか」という 'CPS の導入' の部分を聞いて，それが今まで聞いてきた 'CPS の導入' の話の中で一番しっくりきたので備忘録も兼ねてご紹介します．継続プロの方々には当たり前の話かもしれません．それからできるだけ分かりやすくするために細かい動きなどはあんまり言及していません．Overview だと思っていただければ幸いです．あと OCaml で書きます．

eval 関数

授業で何をしていたかというと，電卓を作っていた，つまり，ユーザが書いた式を評価するインタプリタを作っていたわけです．その '評価する' 関数が eval です．

例えばユーザが

3 + 5

という式をインタプリタにかけて計算しようとしたとき，インタプリタの中でこの式は + が関数，3 が第一引数，5 が第二引数である

+ 3 5

という関数適用の式に変換されてから，各部分式 (+, 3, 5) をそれぞれ eval して，関数適用が行われ，適用の結果がまた eval され，ユーザが求める計算結果 (8) が返ってきます． (ボトムアップのように書きましたが，本当はここは全体を eval するために各部分式を eval していく再帰構造になっています)

評価順序

さてここで先ほどの + 3 5 はどの部分式から評価されるでしょうか？はい，It's up to you です．あなたがもし関数部分 (+) から評価するインタプリタを書きたいと思ってそう開発してあげれば，+ 3 5 は関数である + から評価されます．では引数部分はどうでしょう？インタプリタ内部では各引数はリストに入っています．今回の場合は [3; 5] というぐあいです．このリストの先頭から評価するか，最後尾から評価するか，それもあなたの意思次第です．

で，実は OCaml はこのリストの最後尾から評価していく戦略を取っています．つまり，

+ 3 5

の引数部分は 5 から評価されます．もっと言うと，

3 + 5

は右側の引数から評価されます．よく分からないのですが，OCaml の場合は最後尾から評価した方が後々効率がよいのだそうです．

'式のどこから評価するか' は言語の開発者の意思次第です．普通の計算なら答えが合っていればいいと思う人もいるかもしれません．でも次の場合はどうでしょう？

ここで OCaml のお勉強です．print_string は string 型の値をもらってきたらそれを出力して unit 型の値を返します．unit は () という値しか持たない型で，とりあえず void だと思ってくれればよいです．print_newline はその () をもらってきたら改行を出力して () を返します．

また，; は逐次実行です．; はそれ以前に書いた式が返した値を破棄して次の式の評価へと進みます．上の例の * の左側の引数の場合，まず print_string "left" が返した値 () を捨てて次の式 print_newline (); の評価へと進みます．ところがここでも ; が print_newline () が返した () を捨てて次の式を評価しにいきます．最後に 5 - 3 の評価は最終的に 2 になるので，* の左側の値は最終的には 2 となり返ってきます．

実際に OCaml でこの式を評価してみると

f:id:yuzumikan15:20150424052437p:plain

OCaml は右から評価するので，ちゃんと right から出力されています．

同じような式を他の言語で書いたら，言語によって right と left の出力結果が違ってきます．これは困りものです．同じ式なのに，ユーザが見る画面に書いてあることが違ってきてしまうわけです．

評価順序を統一する

どんな言語で書いても同じ結果になるように，評価戦略によらず評価順序を統一したい．とりあえず OCaml で書くときは let 文を書いて上から順番に評価されるようにします．

let は変数束縛です．ここで束縛した変数は in 以下で使えるようになります．例の場合，n1 に

(print_string "left"; 
 print_newline ();
 5 - 3)

を評価した結果が入り，in 以下で使えるようになります．次に n2 に

(print_string "right";
 print_newline();
 5 + 3)

を評価した結果が入り，in 以下で使えるようになります．最後に，

n1 * n2

を評価した結果がこの例全体の最終的な結果として返ってきます．

ここで重要なのは，let で変数が束縛されるときに = の右側の式は評価される ということです．n1 に

(print_string "left";
 print_newline ();
 5 - 3)

を入れるとき，この式は評価されるので標準出力が行われます．n2 についても同様です．例を実行してみると

f:id:yuzumikan15:20150424054751p:plain

今度は left から出力されました．このように，OCaml だったら let 文を書くことで評価順序を制御できます．

では Haskell はどうでしょう？Haskell の評価戦略は '遅延評価' と呼ばれる戦略です．これは，書いてある通りに評価を行なうのではなく，その式がどこかで本当に使われるときに初めて式の評価を行います．上の例 (と同じことが Haskell で書けたとしましょう) だと，let n1 = ... の時点で ... の部分はまだ評価されずそのままの形で n1 に入ります．n2 についても同じです．そのままの形です．最後に n1 * n2 が出てきたときにやっと，Haskell は「あ，n1 必要じゃん」と思って n1 に入っている式

(print_string "left";
 print_newline ();
 5 - 3)

を評価します (たしか Haskell は素直に左側から評価だった気が…間違ってたらごめんなさい)．この戦略だと，たとえ let を使っても，実際に変数が使われるタイミングによってやっぱり結果が違ってきてしまいます．今回の例ではきっと同じでしょうが，例えば最後を n2 * n1 と引数の順序を逆にするときっと結果が変わってきます．

カプセル化

どんな評価戦略でも評価順序を制御できるような書き方はないものでしょうか？ (反語)

元々評価したい式は

でした．これを必ず左側から評価したいとしましょう．まず，なぜ評価順序がいろいろ変わってしまうかを考えます．それは，左側も右側もどちらも評価できる式になっているから です．どちらもまだ評価できる式になっているのがダメ．ならば，どちらかを評価できない式に変えてあげましょう．今回は左側から評価したいので右側を評価できない式にします．

ここでもうちょっと OCaml のお勉強です．OCaml というかみんなだいすき TAPL のお勉強です．

OCaml で変数をスコープ内に入れる方法は2種類あります．1つはさっき使った let，もう1つは fun 文です．fun 文は要するにラムダ式 (無名関数) のことです．fun x -> x + 1 は λx.x+1 のことで，Haskell で書くと \x -> x + 1 です．これで x をスコープ内に入れて -> 以下で使うことができます．何が違うって束縛した変数が多相型か単相型かの違いですがここでは考えません．

今回評価順序を統一するにあたって fun を使うと嬉しいことがあります．fun は これ以上評価できない式 (= 値) なのです．詳しくは TAPL を読んで下さい．ここではとりあえず fun の中に書いてあることには触れられない，という説明にします．この fun を使って，評価したくない右側の式をまるっと包んでカプセル化してあげます．が，慣れていないのでまずは評価したい左側だけを let で束縛してみます．

次に let ではなく fun で n1 を束縛してみます．このとき n1 を使いたいのは左側の式を評価したあとなので左側の式のあとに fun n1 ->... を書きます (fun n1 -> 左側の式 としてしまうと，fun の中身には触れないので左側の式も評価されなくなってしまいます)．

(capsule1.ml はコピペしても実行できないので注意してください)

これで，fun の中にある右側の式には触れられなくなって，fun の前にある左側の式から評価せざるを得なくなりました．ついでに右側の式も fun を使って束縛してあげましょう．まずは先ほどと同じように let で n2 を束縛してあげます．

次に n2 を fun で束縛してそれ以降に行なう式 n1 * n2 をカプセル化します．カプセルにする fun n2 -> は右側の式を評価したあとだということに注意してください．

この式をどう読むかというと，

(print_string "left";
 print_newline ();
 5 - 3)

を評価し，その結果返ってきた値を n1 に入れて，

(print_string "right";
 print_newline ();
 5 + 3)

を評価し，その結果返ってきた値を n2 に入れて，

n1 * n2

を評価する．と読みます．

c は capsule の c

でもこれはまだ実行可能なプログラムではないですね．完全なプログラムにしてみましょう． capsule3.ml において何がおかしいかというと，左側の式

(print_string "left";
 print_newline ();
 5 - 3)

の値は 2，つまりただの数字なのに，そこに fun n1 -> ... という右側の式を引数のように渡してしまっていることです．というか，本当は 2 は n1 に入ってほしいので，

(fun n1 -> (右側の式)) 2

という関数適用が正しい形のはずです．では，(左側の式) (fun x -> 右側の式) を受け取ったら (fun x -> 右側の式) (左側の式) という関数適用を行なう関数を定義してしまいましょう．

終了です．c は capsule の c です．決して continu(ry

皆さん OCaml くらい書けると思うので説明はいらないかと思いますが，

let capsule x c = ...

は

let capsule = fun x -> fun c -> ...

と同じです．要するに関数 capsule は x と c という2つの引数をもらってきますよ，と読みます．

ではこの capsule を使って実際に capsule3.ml を動かすプログラムを書いてみます．

最初の capsule の第一引数 x に

(print_string "left"
 print_newline ();
 5 - 3)

が入って，第二引数 c に

(fun n1 -> capsule (print_string "right";
                               print_newline ();
                               5 + 3)
                               (fun n2 -> n1 * n2)
 )

が入っていて，capsule x c = c x なので

(fun n1 -> capsule (print_string "right";
                               print_newline ();
                               5 + 3)
                               (fun n2 -> n1 * n2)
 ) (print_string "left"
    print_newline ();
    5 - 3)

が実行されることになります．fun n1 -> ... の中には入れないので置いておいて，引数部分を評価しに行きます．ここで left と改行が出力されて 5 - 3 を評価し，2 が返ってきます．引数がやっと値になったので今度は関数適用が行われ，n1 に 2 が入った状態で fun n1 -> 以降の式を実行しにいきます．

次の capsule についても同様の動きです．n2 には 8 が入り，n1 * n2 が実行されて最終結果は 16 になります．

f:id:yuzumikan15:20150424082633p:plain

c は continuation の c

さて，長かったですがやっとどんな評価戦略であっても評価順序が同じになるプログラムを書くことができました．何をしたかというと，まだ評価してほしくない部分を fun でカプセル化して中を触れないようにし，先に評価してほしい式から返ってきた値を fun で束縛している変数に入れて -> の先の式を評価しに進んでいくのでした．

先に評価してほしい式に対して，あとで評価してほしい式のことを 'continuation, 継続' と呼びます．あとで評価してほしい式は先に評価してほしい式の '継続' になっている，という使い方をします．

そして，あとで評価してほしい式を fun でくるんで継続にして持ち歩くプログラミングスタイルのことを 'Continuation-Passing Style, 継続渡し形式' と呼びます．一般的に，さっき引数で書いた c は k というアルファベットで書きます．これは 'continuation' の 'c' がギリシャ語だかラテン語だかでは k になるからだとかなんとか…？

最後に，授業で紹介された Continuation-Passing Style (CPS) の約束事を書いて終わりにします．

  • 常に (serious な) 関数適用は末尾呼び出しになっている
  • serious な関数には 'その後の仕事' を表す引数 k が1つ増える (= 継続)
  • 値を返すときには k に渡す

ここで serious な関数というのは '評価順序を気にしたい' 関数 (= CPS で書きたい関数)という意味だそうです．反意語は 'trivial' な関数．例えば + という関数が serious か trivial かはプログラマの意思に依存します．+ の評価順序が左からだろうが右からだろうが関係ないと思えば + は 'trivial' な関数になり，きちんと厳密に評価順序を制御したいと思えば 'serious' な関数になります．

CPS で書くことの特徴として，システムの stack に今後の仕事を積んでいく代わりに，自前で関数の形で作って持ち歩いているということがあります．これによって，例えば評価中のどこかでエラーが発生したときにそのエラーを今後の仕事に propagate していくのではなく，エラーになったら今後の仕事は全部捨ててそのまますぐにエラーを返す，ということができます．無駄を省けます．

今後の授業 (この分野に詳しい人向け)

この授業，情報科の大学院の授業で，数理論理学の人たちと私が所属している研究室 (型理論とか証明とか) の人たちが主な参加者です．もちろん CPS という単語は知っていますし，今までのゼミでも書いたことがある人たちが多いです．ではどうして CPS なんかやったのかというと，授業では big-step semantics と small-step semantics と abstract machine の話をするらしく，今のところの目標として，big-step semantics と small-step semantics を行き来する (変換する) プログラムを書くからのようです．どういうことかというと，big-step と small-step を行き来する道具として，CPS の big-step + α を用いるのだそうです．もうちょっと言うと，big-step semantics の継続が small-step semantics になっている のだそうです．ふむふむ．なんかそんな感じする．

概念だけ聞いてるととても面白いんですけどね，継続…