3imp ヒープ・ベース・コンパイラ/VM と CEK マシンの関係 - Tociyuki::Diary

Dybvig Three Implementation Models for Scheme (以下 3imp) のヒープ・ベース VM は、 VM だけでは CEK マシンから逸脱する動作もできてしまいますが、 コンパイラで CEK マシンに等価になるようにコード生成して制限をかけています。 複合手続きのアプリケーション評価を取り上げます。 CEK マシンでは 2 フェーズの状態遷移をおこなっていました。 式から継続を作成するフェーズと、 式評価の結果を継続に摘要するフェーズを交互に繰り返します。 アプリケーションの S 式を先頭から昇順に評価していく場合、 最初に得る式を継続メンバに記録してから実引数を評価してリストを作成していきます。 そして最後の実引数を評価してから apply フェーズへ移って、 実引数とクロージャの仮引数で新しい環境フレームを作ってクロージャの環境に追加して新しい