あどけない話

インターネットに関する技術的な話など

GHC の STG に関するまとめ

理解が深まれば、適宜更新します。

G-machine

  • グラフ簡約のためのスタックマシン
  • 関数適用が連なる spine (背骨)を持ち、愚直にカリー化を実現する
  • 簡約のたびに、それぞれの項を更新
  • ローカル関数はラムダリフティングしてグローバル関数に直す必要がある
    • ラムダリフティングされた関数はスーパーコンビネータと呼ばれる
  • Gコード
  • push/enter 方式

Spineless G-machine

  • Spineless: 引数が充足している関数は、一気に呼び出す
    • このころまでに標準の G-machine も spineless だったらしい
  • サンクは共有されているときだけ更新 (これが重要)
  • G コードに対して 5 つの新しいコードを追加
  • push/enter 方式

Spineless Tagless G-machine

  • Tagless: 統一された書式になって、先頭の tag がなくなった。先頭は info へのポインタ
  • T コード
  • case 文での分岐は、評価する式が vectorized returns を返すので、直接分岐へ飛べる
  • push/enter 方式

Spineless Tagless G-machine Version 2.5

  • 低レベルなコードをやめ、拡張ラムダ式をそのまま使う高水準な language になった
  • セマンティクスが明確になった
    • 関数の適用は末尾呼び出し(jump)
    • let 式はヒープの割り当て
    • case 式は評価
    • コンストラクタの適用は継続への復帰 (case of の間を評価したあとに分岐という継続に戻る)
  • case 文での分岐は、評価する式が vectorized returns を返すので、直接分岐へ飛べる
  • push/enter 方式

STG(Shared Term Graph) language and STG(Spineless Tagless G) machine

疑問

  • update しなくていいサンクって、どうやって値を保持するんだろう?