HaskellのSTG言語
この記事では GHC 8.0.1 を用いています.
STG言語
STG(Spinless Tagless G-machine)とは,遅延評価で高階関数をサポートする関数型言語のための抽象機械である.
STG(Shared Term Graph*1)言語はSTG機械のための言語で,GHCでは Haskellソース → Core言語 → STG言語 → C-- → アセンブラ,LLVM というコンパイル過程で中間言語として現れる.
STG言語は,ghcで --ddump-stg オプションをつけてコンパイルすると出力される.
Core言語
Core言語は概ねHaskellのサブセットであり,脱糖したHaskellとみることができる.Haskellと異なる点は,
- 多相関数が引数に明示的に型パラメータをとる(@ a)
- パターンマッチはcase式でのみ可能で,ネストしたパターンは使えない.
変数はリネームされ,情報が付与されている.
Core言語は,ghcで --ddump-prep または -ddump-simpl(中間Core形式)オプションをつけてコンパイルすると出力される.
foo :: a -> a foo x = x -- 中間Core foo :: forall a_aoY. a_aoY -> a_aoY [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType] foo = \ (@ a_awd) (x_aw3 :: a_awd) -> x_aw3 -- 中間Core(整形後) foo :: forall a. a -> a foo = \ (@ a) (x :: a) -> x -- Core Main.foo :: forall a_aoY. a_aoY -> a_aoY [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType, Unf=OtherCon []] Main.foo = \ (@ a_awd) (x_sP3 [Occ=Once] :: a_awd) -> x_sP3 -- Core(整形後) Main.foo :: forall a. a -> a Main.foo = \ (@ a) (x :: a) -> x
構文
STG言語はCore言語をさらに限定的にしたような構文をもつ.Core言語との違いは,
foo :: a -> a foo x = x -- STG Main.foo :: forall a_aoX. a_aoX -> a_aoX [GblId, Arity=1, Caf=NoCafRefs, Str=DmdType, Unf=OtherCon []] = \r srt:SRT:[] [x_sFZ] x_sFZ; -- STG(整形後) Main.foo :: forall a. a -> a = \r [x] x;
以降のSTG言語は断りのない限り,変数名を変えたり余計な情報を省いて整形したものとする.
クロージャ
foo :: a -> a foo x = x -- STG Main.foo :: forall a. a -> a = \r [x] x;
"\"から始まるクロージャは,更新可能フラグ(r),引数のリスト([x]),本体(x)からなる.
u - updatable 更新可能(thunk) 評価されるとその結果に書き換えられる
r - re-entrant 再入可能(関数)引数をとる
s - single-entry 再入不可(IO関係)
コンストラクタ
コンストラクタへの引数はリストで表され,引数が全て埋まっている必要がある.
引数が充足していないコンストラクタ適用はクロージャになる.
one :: Int one = 1 jtrue :: Maybe Bool jtrue = Just True just :: a -> Just a just = Just -- STG Main.one :: GHC.Types.Int = NO_CCS GHC.Types.I#! [1#]; Main.jtrue :: GHC.Base.Maybe GHC.Types.Bool = NO_CCS GHC.Base.Just! [GHC.Types.True]; Main.just :: forall a. a -> GHC.Base.Maybe a = \r [t] GHC.Base.Just [t];
(NO_CCSはNo Cost Centre Stack,負荷プロファイルに使用されないというアノテーション)
関数適用
関数へ与える引数は全て変数で,式を与える場合は予めletで一つ一つ変数に束縛する.
twice :: (a -> a) -> a -> a twice f x = f (f x) threeTimes :: (a -> a) -> a -> a threeTimes f x = f (f (f x)) -- STG Main.twice :: forall a. (a -> a) -> a -> a = \r [f x] let { x0 :: a = \u [] f x; } in f x0; Main.threeTimes :: forall a. (a -> a) -> a -> a = \r [f x] let { x1 :: a = \u [] let { x0 :: a = \u [] f x; } in f x0; } in f x1;
case式
対象の式を評価し,パターンマッチを行う.ネストされたパターンは受け付けない.
ofの後の変数には評価後の値を束縛する.
fromMaybe :: a -> Maybe a -> a fromMaybe a Nothing = a fromMaybe _ (Just a) = a -- STG Main.fromMaybe :: forall a. a -> GHC.Base.Maybe a -> a = \r [a m] case m of _ { GHC.Base.Nothing -> a; GHC.Base.Just a1 -> a1; };
型クラス
型クラス制約付きの多相関数は,型クラス辞書(メンバ関数の実装を保持する辞書,C++の仮想関数テーブルに近い)を引数に明示的にとる.
inc :: Num a => a -> a inc x = x + 1 -- STG Main.inc :: forall a. GHC.Num.Num a => a -> a = \r [$dNum x] let { num1 :: a = \u [] let { int1 :: GHC.Integer.Type.Integer = NO_CCS GHC.Integer.Type.S#! [1#]; } in GHC.Num.fromInteger $dNum int1; } in GHC.Num.+ $dNum x num1;
$dNumが型クラス辞書.
class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool data LR = L | R instance Eq LR where L == L = True R == R = True _ == _ = False a /= b = not (a == b) foo = L == R -- STG -- メンバ関数 Main.== :: forall a. Main.Eq a => a -> a -> GHC.Types.Bool = \r [dic] case dic of _ { Main.C:Eq eq _ -> eq; }; Main./= :: forall a. Main.Eq a => a -> a -> GHC.Types.Bool = \r [dic] case dic of _ { Main.C:Eq _ neq -> neq; }; -- メンバ関数の実装 $eqLR :: Main.LR -> Main.LR -> GHC.Types.Bool = \r [a b] case a of _ { Main.L -> case b of _ { Main.L -> GHC.Types.True []; Main.R -> GHC.Types.False []; }; Main.R -> case b of _ { Main.L -> GHC.Types.False []; Main.R -> GHC.Types.True []; }; }; $neqLR :: Main.LR -> Main.LR -> GHC.Types.Bool = \r [a b] let { isEq :: GHC.Types.Bool = \u [] Main.== Main.$fEqLR a b; } in GHC.Classes.not isEq; -- 辞書 Main.$fEqLR :: Main.Eq Main.LR = NO_CCS Main.C:Eq! [$eqLR $neqLR]; -- Main.foo :: GHC.Types.Bool = \u [] Main.== Main.$fEqLR Main.L Main.R;
型クラス辞書は単純にコンストラクタとして表現されていることが分かる.
メンバ関数では,型クラス辞書から該当する実装を取り出すだけである.
インスタンス宣言をすると,クラスと型に対応した辞書が作られる.
実行時表現
STGは実行時の動作に素直に対応する.
- let式 - ヒープオブジェクトの生成
- case式 - thunkをWHNFまで評価して分岐
- 関数適用 - ジャンプ
ヒープオブジェクト
データ型やクロージャはヒープか静的領域に置かれ,ポインタで参照される.
これらのオブジェクトは [header][payload..] の形をとる.
header(infoポインタ)は静的領域の info table を指す.
Info Table
info table はクロージャに必要な情報を持つ.
[layout][closure type][SRT bitmap][entry code] の形をとる.
データコンストラクタ
[header][payload..]
haeder がコンストラクタの種類を表し,引数が続く.
無引数のコンストラクタは静的領域に置かれる.
Thunk
[header][payload..]
header が関数のコードを指し,引数が続く.
関数との違いは更新可能であること.
部分適用
[header][arity][no. of words][function closure][payload..]
関数適用のうち引数が足りないもの.
- arity - 残りの引数の数
- no. of words - すでに適用された引数の数
- function closure - 関数クロージャ
- payload - すでに適用された引数
Selector thunk
[header][pointer]
コンストラクタから一部を取り出すだけのthunk. 例:
case x of (a,b) -> a
ガベージコレクト
Constant Applicative Forms
Constant applicative form (定作用形,CAF) は,スーパーコンビネータ(*1)のうちλ抽象"でない"ものを指す.
自由変数を含まないことから,CAFはつねにトップレベルの(環境に依存しない)関数になる.よってCAFはこれを参照する他の式から共有され,一度きりの評価で済む.
(*1) Super combinator
自由変数(引数でない変数)を含まない式のみから成り立つ式.
-- スーパーコンビネータ 0 \x y -> x + y \f -> f (\x -> x + x) -- スーパーコンビネータでない(λ抽象内で,引数以外の変数y,gが現れている) \x -> y + x \f g -> f (\x -> g 2 x)
CAF自体は静的領域に置かれるが,評価後の式の一部はヒープに置かれ,巨大なものかもしれない.GCはこれを追跡する必要がある.
Static Reference Table
静的クロージャのうちCAFを(あるいは間接に)参照しているものをCAFFYと呼ぶ.
全ての info table は Static Reference Table(静的参照テーブル,SRT)を持ち,そのクロージャが参照するCAFFYをリストする(実際はビットマスクで管理).
foo :: a -> a foo = id -- STG Main.foo :: forall a_aoZ. a_aoZ -> a_aoZ [GblId, Str=DmdType] = \u srt:SRT:[r2A :-> GHC.Base.id] [] GHC.Base.id;
STG中の srt:SRT:[r2A :-> GHC.Base.id] がSRTを表す.GHC.Base.idを参照していることが明記されている.