Execution Pipeline

処理系は、source を AST に変換し、必要な値だけを AST interpreter で評価する。

source
  ↓
lexer / parser
  ↓
desugar
  ↓
register root module
  ↓
demand-driven evaluation
  ├─ force thunk
  ├─ load imported module on demand
  ├─ evaluate expression
  ├─ compose `&`
  └─ patch `//`
  ↓
materialize
  ↓
data / diagnostics

lexer / parser

lexer / parser は source を AST に変換する。構文エラーはこの段階で diagnostic として報告する。

AST は arena に格納し、式や pattern は ExprId、PatternId のような ID で参照する。

desugar

desugar は、意味論を単純にするための表層構文変換を行う。

例として、dot-path field は nested object に変換できる。

{
    feature_hoge.enable = false;
}

{
    feature_hoge = {
        enable = false;
    };
}

この変換により、評価器は object field の再帰構造だけを扱えばよい。

module registry

module registry は、読み込んだ module を loader が返す安定 key で管理する。 CLI では canonical path を key とする。組み込み利用では、resource name や static source table の key を使える。

ModuleRegistry:
  ModuleKey -> ModuleId

処理系は、まず root module を parse / desugar して registry に登録する。 import 先 module は、この段階で全て読み込む必要はない。

import expression が評価されたとき、処理系は SourceLoader に現在の module key と import specifier を渡す。 loader は module key、表示名、source text を返す。 module registry は key が未登録なら対象 module を parse / desugar して登録する。登録された module は module root thunk を持つ。同じ module が複数回 import された場合は、同じ ModuleId を返す。

つまり import は module を即時評価しない。 module を読み込み、module root を thunk として登録するだけにする。

AST の ExprId は module-local である。そのため runtime が保持する式参照は ExprRef { module, expr } として module-qualified にする。

demand-driven evaluation

評価器は、必要になった thunk だけを force する。未参照の field、let binding、import 先の field は評価しない。

この方式により、module 間に循環 import があっても、実際に force された thunk の依存が循環しない限り評価できる。

composition

composition は、module 全体に後からかける global pass ではない。 & や // の式を評価するときに、demand-driven evaluation の中で呼ばれる演算である。

eval(A & B):
  a = eval(A)
  b = eval(B)
  compose_and(a, b)

eval(A // B):
  a = eval(A)
  b = eval(B)
  patch(a, b)

& は制約を保った合成を行い、// は右辺優先の deep patch を行う。詳細は Composition and Materialization に置く。

resolver / binder

resolver / binder は初期実装では必須ではない。評価時に environment lookup を行えば、識別子参照は実装できる。

ただし、将来的には optional phase として追加できる余地を残す。

source
  ↓
lexer / parser
  ↓
desugar
  ↓
resolver / binder
  ↓
register root module
  ↓
demand-driven evaluation

resolver / binder を追加すると、以下を早期に診断しやすくなる。

未定義識別子
shadowing の扱い
reserved word の扱い
symbol interning
import path の一部静的解決
span 付き diagnostic の精度向上

ただし、Decodal の制約検証は独立した type checking pass ではなく、& の合成時や materialize 時に行う。

materialize

通常の評価結果は runtime value であり、抽象値や default を含みうる。外部へ出力するときだけ materialize を行い、出力可能な data に変換する。

materialize は以下を行う。

必要な thunk を force する。
abstract value の default を必要に応じて force する。
concrete value が constraint を満たすか検証する。
未解決の abstract value、function value などを diagnostic にする。

4.3 KiB Raw Permalink Blame History