CEK機械

CEK機械とは、ラムダ計算に対して値渡し評価戦略の操作的意味論を与えるための抽象機械の1つである。CEKとは、機械の状態を構成する3つの要素である “Control string”, “Environment”, “Continuation” に由来する。
定義.
拡張ラムダ計算に対するCEKは次のように定義される。
まず、拡張ラムダ計算を次のように定義する。
formula_1
    formula_2 (変数)
  formula_3 (λ抽象)
  formula_4 (関数適用)
  formula_5 (基本定数)
  formula_6 (プリミティブ操作の適用)
formula_7
次に、CEK機械の状態を構成する要素を次のように定義する。
formula_8 (変数から、クロージャへの関数(変数とクロージャのペアの集合))
formula_9
formula_10 (ただし、formula_11の自由変数は全てformula_12の定義域に含まれる) 
formula_13 (ただし、formula_14の自由変数は全てformula_12の定義域に含まれる)
formula_16
    formula_17 (初期継続)
  formula_18 (関数適用への継続)
  formula_19 (実引数評価への継続)
  formula_20 (プリミティブ操作の実引数の評価および適用への継続)
このとき、CEK機械の状態は組formula_21と表される。
CEK機械の遷移規則は次のように定義される。
formula_22      formula_23 (formula_24 のとき)
formula_25      formula_26
formula_27      formula_28
formula_29      formula_30 (formula_14が変数でない場合)
formula_32      formula_33 (formula_14が変数でない場合)
formula_35      formula_36 (formula_14が変数でない場合)
formula_38      formula_39 (formula_14はformula_41にformula_42を適用した結果)
このとき、CEK機械による評価関数formula_43は次のように定義される
formula_44    (formula_45 のとき)
formula_46    (formula_47 のとき)
Defunctionalizationとの関係.
CEK機械は、ラムダ計算の標準的な評価関数に対して、クロージャ変換、値渡し評価戦略のCPS変換、defunctionalizationを順に適用することで導出できる。ここで、値渡し評価戦略の代わりに名前渡し評価戦略を使うとKrivineの機械が導出される。
拡張.
CEK機械はCPS変換した評価関数から導出するため、call/ccやshift/resetといったCPS変換で実装できる演算子との相性が良い。
例えば、次のように拡張することで、call/ccを追加できる。
formula_48
formula_49
formula_50      formula_51
formula_52      formula_53(formula_14が変数でない場合)
formula_46    (formula_56 のとき)