CPS - mrsekut-p

CPS

continuation-passing style

全ての関数呼び出しを継続渡しにする

換言すれば、全ての関数呼び出しを継続渡しとして定義し直す

IR (中間表現)としても使われる

CPSって「継続を自由にとって来れない言語でもcall/cc的なことをするために使える」という感じで説明されることも有るのかmrsekut.icon

CPSで書くことで、全ての関数呼び出しは「リターンアドレスの記憶」しなくていい

通常の関数呼び出しのような入れ子構造は消え、次の処理、その次の処理、と数珠繋ぎ的に処理が行われるようになる

例

hの中でgを呼び、その中でfを呼んでいる

直接スタイルで書いたもの

code:hs

f x = 1 + x

g x = 10 * f x

h x = g x * id x

-- 利用

h 100

id xの部分は別になくても良いんだけど、「残りの処理」感を出すために書いてるmrsekut.icon

こんな感じで処理が進む

https://gyazo.com/52073d54ee182464bb187ad57745487c

それぞれの関数が呼ばれ、処理が終わると呼ばれた箇所へ戻ってきている

CPSで書いたもの

code:hs

fc 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を渡してるmrsekut.icon

https://gyazo.com/cc57499aa8df463346772f27fbf34996

一度呼んだら、もう戻ってこない

これ、コード上の記号の付け方合ってるかな、微妙に自信がないmrsekut.icon

これ、「CPS」と呼ぶためには、idも継続渡しで書かないといけなかったかmrsekut.icon

idc x cont = cont $ id x