CPS
continuation-passing style
全ての関数呼び出しを継続渡しにする
換言すれば、全ての関数呼び出しを継続渡しとして定義し直す
継続渡しの特殊版
違いは継続渡しとCPSの差異に書いた
対概念は直接スタイル
IR (中間表現)としても使われる
CPSって「継続を自由にとって来れない言語でもcall/cc的なことをするために使える」という感じで説明されることも有るのか
CPSで書くことで、全ての関数呼び出しは「リターンアドレスの記憶」しなくていい
通常の関数呼び出しのような入れ子構造は消え、次の処理、その次の処理、と数珠繋ぎ的に処理が行われるようになる
例
h の中で g を呼び、その中で f を呼んでいる直接スタイルで書いたもの
hsf x = 1 + x
g x = 10 * f x
h x = g x * id x
-- 利用
h 100 id x の部分は別になくても良いんだけど、「残りの処理」感を出すために書いてるこんな感じで処理が進む
それぞれの関数が呼ばれ、処理が終わると呼ばれた箇所へ戻ってきている
CPSで書いたもの
hsfc x cont = cont $ 1 + x
gc x cont = cont $ fc x $ \y -> 10 * y
hc x cont = cont $ gc x $ \y -> y * id x
-- 利用
hc 100 id利用時もcontを渡さないと行けないので、とりあえず
id を渡してる
一度呼んだら、もう戻ってこない
これ、コード上の記号の付け方合ってるかな、微妙に自信がない
これ、「CPS」と呼ぶためには、
id も継続渡しで書かないといけなかったか idc x cont = cont $ id x 関連
起源
wikipの最初の方に書いてる
参考
参考文献もいっぱい書いてるから慣れてきたら読んでみたいな
いろいろ丁寧に書いてて参考になった
関数合成の順序が逆転する