Zenn
Open32

ToyLisp devlog 3 (単相の型推論、フィボナッチ関数、診断情報〜言語サーバ再建まで予定)

#
自作言語
#
salsa
toyboot4etoyboot4e

toylisp devlog 3 (1, 2)

前回に引き続き自作ゲーム用スクリプト言語を作っていきます。元は rust-analyzer をなぞっていましたが、 salsa-2022 が出たので dada 寄りのコードになりました。

今回はフィボナッチ数列を実行したり、エディタ補完等が本格的に動くようにしたいと思います。意外と目標近くまで来ている気がしますが、どうなるでしょうか。

https://github.com/toyboot4e/tlp

toyboot4etoyboot4e

演算子の型は引数の型による

関数 body の Expr, Pat に型情報を外付けしました。関数と引数の型チェックなども実施できます [1] 。しかし + や * のような builtin 演算子は、引数の型に応じてオーバーロードします。したがって型情報の伝播・単純な型推論が必要でした。

MinCaml の型推論

今回は 速攻 MinCaml コンパイラ解説 の typing モジュールをざっくり読んでみます。

構文

MinCaml の型推論を読むためには、 MinCaml の構文をある程度理解する必要があります:

syntax.ml
type t = (* MinCamlの構文を表現するデータ型 *)
  | Unit
  | Bool of bool
  (* ~~~~ *)

  (* <1> *)
  | Add of t * t
  | Sub of t * t
  | FNeg of t
  | FAdd of t * t
  | FSub of t * t
  (*~~~~ *)

  | If of t * t * t

  (* <2> *)
  | Let of (Id.t * Type.t) * t * t
  (* <3> *)
  | Var of Id.t

  (* <4> *)
  | LetRec of fundef * t
  | App of t * t list
  | Tuple of t list
  | LetTuple of (Id.t * Type.t) list * t * t

  (* <5> *)
  | Array of t * t
  | Get of t * t
  | Put of t * t * t
and fundef = { name : Id.t * Type.t; args : (Id.t * Type.t) list; body : t }
id.ml
type t = string (* 変数の名前 *)
(* ~~~~ *)
  • <1>: MinCaml では構文レベルで Int/Float 用演算子が区別されています。 その手があったか 。 Int の演算子は +, -, *, / ですが、 Float の演算子は +., -., *., /. と書きます。これは OCaml も同様のようです。
  • <2>: Id.t は string (変数名) です。 Type.t の部分は構文に現れず、一旦 Var (型変数) と置かれて推論されます。
  • <3>: 変数名を表す構文があります。これも Var という名前なので、 Type.t の Var と Syntax.t の Var を混同しないように気をつけます。
  • <4>: その他のややこしそうな構文は飛ばします。
  • <5>: 配列の構文が 3 つあります。 Get などは意味深な名前ですが、気にしなくて良いことが分かります。
    • Array: Array.make len data のように配列を初期化します。
    • Get: array.(2) のように配列の要素にアクセスします (0-based index) 。
    • Put: array.(2) <- 42 のように配列の要素を更新できます。副作用が書き放題だと、 Rust より OCaml を好む理由があるのかと気になりますが……。

型変数の扱い方

まずは型の表現を見ます:

type.ml
type t = (* MinCamlの型を表現するデータ型 *)
  | Unit
 (*~~~~ *)
  | Var of t option ref

未知の型は『型変数』として保存されます (Var) 。 Var of t option ref の部分を Rust に翻訳するとこんな具合です:

enum T {
    Unit,
    // ~~
    Var { contents: Option<T> }, // `contents` は mutable なので `:=` で書き換えられる
}
  • t option ref の順番で Option<Ref<T>> を表すようです。リストの場合は t list となります。
  • ref を書くと contents フィールドみたいなもの (後述) が自動的に生えます。うーん肌に合いません。
  • Var の contents := Some(t) とすれば、型変数を書き換えられます。

実際、 typing.unify では以下のようにマッチしています:

typing.ml
let rec unify t1 t2 = (* 型が合うように、型変数への代入をする *)
  match t1, t2 with
  (* <1> *)
  | Type.Unit, Type.Unit | Type.Bool, Type.Bool | Type.Int, Type.Int | Type.Float, Type.Float -> ()
  (* ~~~~ *)

  (* <2> *)
  | Type.Var(r1), Type.Var(r2) when r1 == r2 -> ()

  (* <3> *)
  | Type.Var({ contents = Some(t1') }), _ -> unify t1' t2
  | _, Type.Var({ contents = Some(t2') }) -> unify t1 t2'

  (* <4> *)
  | Type.Var({ contents = None } as r1), _ -> (* 一方が未定義の型変数の場合 *)
      if occur r1 t2 then raise (Unify(t1, t2));
      r1 := Some(t2)
  | _, Type.Var({ contents = None } as r2) ->
      if occur r2 t1 then raise (Unify(t1, t2));
      r2 := Some(t1)

  (* <5> *)
  | _, _ -> raise (Unify(t1, t2))
  • <1>: 型が一致する場合は完了です。
  • <2>: 型変数同士が一致する場合は完了です。両方未知の場合も例外は投げません。そういうケースはどうするんだろう……？
  • <3>: 一方が既知の型変数であれば、その中身を取り出して他方と比較します。
  • <4>: 一方が未知の型変数であれば、その型変数に他方の型を代入します。無限ループを避けるために occur check を行なっています (本家を参照) 。
  • <5>: 型が不一致の場合は例外 (?) を投げます。

型推論のやり方

ある変数の型が確定した場合、その変数を参照するすべての式 (Expr::LocalVariable 的なもの) の型も変える必要があります。 MinCaml がその辺をどう扱っているのか気になります！

typing.g がいわゆる infer 関数のようです。 エラーハンドリング を行なっています:

typing.ml
(* type inference/reconstruction *)

open Syntax

exception Unify of Type.t * Type.t
exception Error of t * Type.t * Type.t

(* ~~~ *)

let rec g env e = (* 型推論ルーチン *)
  try
    match e with
    | Unit -> Type.Unit
    (* ~~~~ *)
  with Unify(t1, t2) -> raise (Error(deref_term e, deref_typ t1, deref_typ t2))

関数本体は:

let rec g env e = (* 型推論ルーチン *)
  try
    match e with
    | Unit -> Type.Unit

    (* ~~~~ *)

    (* <1> *)
    | Not(e) ->
        unify Type.Bool (g env e);
        Type.Bool
    (* ~~~~ *)

    (* <2> *)
    | Let((x, t), e1, e2) -> (* letの型推論 *)
        unify t (g env e1);
        g (M.add x t env) e2

    (* <3> *)
    | Var(x) when M.mem x env -> M.find x env (* 変数の型推論 *)

    (* <4> *)
    | Var(x) when M.mem x !extenv -> M.find x !extenv
    | Var(x) -> (* 外部変数の型推論 *)
        Format.eprintf "free variable %s assumed as external@." x;
        let t = Type.gentyp () in
        extenv := M.add x t !extenv;
        t

    (* <5> *)
    (* ~~~~ *)
  with Unify(t1, t2) -> raise (Error(deref_term e, deref_typ t1, deref_typ t2))
  • <1>: unify を呼び出すことが型推論です。予期された型と実際の型を比較します。
  • <2>: Let of (Id.t * Type.t) * t * t でしたから、 Let ((x, t), e1, e2) は Let((パタン名, パタンの型), パタンの値、式) という形です。次の行の unify で t の中身 := g env e1 となります。その次の行では env に (x, t) を追加して e2 の推論に入っています。
  • <3>: ここでいう Var は変数名を表す構文です (型変数ではありません) 。環境内の型変数を書き換えれば、変数名に対応する型変数が連動して変化します。
  • <4>: 外部変数というのは MinCaml 独自の機能なので読み飛ばして良いと思います。 OCaml にはありません。
  • <5>: 以下省略。再帰とか関数適用も重要そうではありますが。

感想

短いながらもサクっと読めるようなコードではなく、 OCaml 自体の知識を補填して読みました。 流れは思っていた通りのもので、順番に式を歩いていくだけです 。単相の型推論だと、連立方程式を解くような高度な推論は必要無いのかもしれません。これは Hindley-Milner 型推論の一番簡単なやつということになるのでしょうか……？　型推論の知識はアクセスが良くないですね。

次は toylisp に型推論 (infer 関数) を追加してみたいと思います。 + や - をオーバーロードしてほしい！

脚注

  1. ユーザ定義関数を解析する機能はまだありません。 ↩︎

toyboot4etoyboot4e

名前解決して型情報を共有してみた

簡易型推論を実装中です。今回の成果は:

(let x 10)
(+ x 5)    ;; 式 `x` は、 `let` 式のパタン `x` と型情報を共有します

型情報は以下のように持ちました。グローバル変数の型はコピーしようかなと思います。アイテムの型は別のテーブルに置いて参照できるようにしようと考えています:

struct Collect {
    // 型情報との対応を記録
    expr_types: FxHashMap<Expr, TyIndex>,
    pat_types: FxHashMap<Pat, TyIndex>,
    // 型情報は一箇所に保存
    types: TiVec<TyIndex, WipTypeData>,
    // ~~~~
}

TiVec は Vec<T> の亜種です。

推論中には未解決の状態を許容します (WipTypeData::Var) 。推論後、未解決の型変数は TypeData::Unknown に変換します:

pub enum WipTypeData {
    /// 未解決の型変数
    Var,
    Data(TypeData),
}

pub enum TypeData {
    Unknown,
    Primitive(PrimitiveType),
    // ~~~~
}

型変数の扱い方が標準的ではない気もしますが動いています。

toyboot4etoyboot4e

論理型と論理演算子の追加

型推論を含め、すべてのパスが繋がりました。コンパイル用のパスを足したい気もしますが……ここまで来れば、インクリメンタルな開発ができます。今回は 1 日で bool 型を実装できました。

true, false リテラルの追加

テストケース:

#[test]
fn boolean() {
    test_expr("true", true);
    test_expr("false", false);
}
パスの編集
パス 変換 書き換え
lex String → [Token] true, false, nil などは種別を分けてトークン化します [1]
parse [Token] → CST / AST true, false トークンは Literal::Bool ノードにラップします
lower_body AST → Body ast::Literal::Bool を expr::Literal::Bool に変換します
lower_scope [Item], Body → Resolver expr::Literal::Bool はスコープに影響を与えません
lower_ty Body → TypeTable expr::Literal::Bool から PrimitiveType::Bool を取り出します
compile (Body, TypeTable) → Chunk expr::Literal::Bool を TypedLiteral::Bool として push します
vm - bool とバイト列間の変換を追加しました

教科書的なコンパイラの作り方を『row-based』、インクリメンタルな作り方を『column-based』だと称した記事がありました。それぞれのパス (row) に機能追加の改修 (column) を加えていくのは確かに column-based です。もう一度あの記事を読みたいな……。

and, or の追加

テストケース:

#[test]
fn boolean_operators() {
    test_expr("(and false false)", false);
    test_expr("(and true false)", false);
    test_expr("(and false true)", false);
    test_expr("(and true true)", true);

    test_expr("(or false false)", false);
    test_expr("(or true false)", true);
    test_expr("(or false true)", true);
    test_expr("(or true true)", true);

    // `let` もいけます
    test_expr("(let b false) (or b true)", true);
    test_expr("(let b true) (and b true)", true);
}
パスの編集
パス 変換 書き換え
lex String → [Token] なし (and, or は Ident トークンにします)
parse [Token] → CST / AST ast::{And, Or} を追加しました
lower_body AST → Body expr::{And, Or} への変換を追加しました
lower_scope [Item], Body → Resolver expr::{And, Or} を歩く分岐を追加しました
lower_ty Body → TypeTable expr::{And, Or} の子要素を PrimitiveType::Bool と unify しました
compile (Body, TypeTable) → Chunk expr::{And, Or} を命令列に変換します
vm - Jump 命令を追加しました

Jump 命令を作ったので、制御構文をサクサク足せる気がします。やっとここまで来ました。

Jump 先のアドレスは後で書き換える

or 演算子のコンパイルは大体この形です:

compile_or_oper()
let mut anchors = Vec::new();

for &expr in exprs {
    let expr_data = &body_data.tables[expr];
    // `or`: short circuit on `true`
    let anchor = self.chunk.write_jump_if_u16()
    anchors.push(anchor);
}

let ip = self.chunk.bytes().len() as u16;

for anchor in anchors {
    anchor.write_ip(&mut self.chunk, ip);
}

Jump 命令で使用するアドレス位置を JumpAnchor として受け取って、後からアドレスを書き換えています。 Crafting Interpreters も同じやり方なのでこれで良いでしょう。

https://craftinginterpreters.com/jumping-back-and-forth.html

and, or のショートサーキットについて

and や or の評価は短絡する可能性があります。コンパイルに工夫が必要です。たとえば以下の toylisp は次のような命令列に変換しています:

main.tlp
(proc main ()
    (let b false)
    (or b true))

  0: alloc-frame-8   1    # コールフレームの作成 (変数の数 1)

# (let b false)
  2: push-const-8    0    # 0 番目の定数 (`false`) を stack に push
  4: set-local-8     0    # Stack を pop して0 番のローカル変数に書き込み

# (or b true)
  6: push-true            # Stack に `true` を書き込み
  7: push-local-8    0    # 0 番のローカル変数を stack に push
  9: jump-if-16      0 19 # Stack を pop して `true` ならアドレス `19` へ飛ぶ
 12: push-const-8    1    # 1 番目の定数 (`true`) を stack に push
 14: jump-if-16      0 19 # Stack を pop して `true` ならアドレス `19` へ飛ぶ
 17: discard              # アドレス `2` で作成した `true` を破棄
 18: push-false           # Stack に `false` を書き込み

 19: ret

jump-if-16 命令では stack を pop し、 true だった場合は指定されたアドレスに飛びます。 or においては、

  • ジャンプした場合アドレス 6 で設定した true 値が stack に残ります
  • ジャンプしなかった場合アドレス 6 で設定した true 値を discard して、 false を stack に残します

ひとまずテストは通りました。この方法に関しては特に裏付けはありません。

脚注

  1. 余談ですが let や proc のようなキーワードは Ident として単語化しています。 ↩︎

toyboot4etoyboot4e

Bitwise な VM の夢

スタックの中の 1 変数が 8 bytes 使っている気がしていました。全然そんなことは無いと確認できました。

ローカル変数はぎっしり詰まっていた

void main() {
    char c1 = '0';
    char c2 = '1';
    char c3 = '2';
    char c4 = c1 + c2 + c3;
}

godbolt でアセンブリを確認します。アセンブリは x86-64 で、最適化をオフに (-O0) します:

main:
        push    rbp
        mov     rbp, rsp
        mov     BYTE PTR [rbp-1], 48
        mov     BYTE PTR [rbp-2], 49
        mov     BYTE PTR [rbp-3], 50
        movzx   edx, BYTE PTR [rbp-1]
        movzx   eax, BYTE PTR [rbp-2]
        add     edx, eax
        movzx   eax, BYTE PTR [rbp-3]
        add     eax, edx
        mov     BYTE PTR [rbp-4], al
        nop
        pop     rbp
        ret

c1, c2, c3 が 3 バイトにぎっちり詰まっています。 これを自分の VM で再現するのはわりとしんどい と思いますね……。 1 変数 8 バイト使っちゃおうかなと思います。その程度だから！　僕なんて！　所詮！　その程度だから！！

一時変数にはレジスタを使っており、スタックの使い方を確認できませんでした。

x86-64 の知識が足りない

コンパイラの本を読んだ方がいいなと思います。 compilerbook で『後はコードを読みなさい』となっていましたが、できればエアプで済ませたい……！

  • スタックを使った計算
    char に使うのは 1 バイトか 8 バイトか

  • 関数呼び出し

    • スタックで引数渡し
    • レジスタで引数渡し

  • アラインメント

    • アラインメントのルールを厳密に把握する
    • オフセットも気にする必要はある？
toyboot4etoyboot4e

Stack のバランスを取ってみた

問題点

今までは値を返す (stack に積む) 式と値を返さない式が混在していました:

(let a 10) ;; stack に値を積まない
(+ 1 2)    ;; stack に 3 が残る

このため無を pop したり (panic する), stack にゴミが永遠に残るということがありました。

解決策

すべての式が値を返すように変更しました:

(let a 10) ;; stack に無を積む (Rust の unit に相当する)
(+ 1 2)    ;; stack に 3 が残る

任意の式は stack に 1 つ値を積みます:

  • 単一の式は stack に 1 つ値を積みます
  • 2 つ以上の連続する式は、必ず expr::Block の中に入っています。 expr::Block を評価する際は、最後の式以外が返す値を破棄します

最適化の際は、 push と pop 命令が連続していたら両方とも消去すれば良いです。

最適化すると jump 命令の目標アドレスが変わる件について

強引に対応するか、最適化しなければいいですね。中間表現を 1 つ増やした方がいいなとは思います。

toyboot4etoyboot4e

制御構文 (1): when, unless

実装

ジャンプ命令を使うだけでした。返値は無です。

set 命令も実装してみた

(proc main ()
    (let a 0)
    (when true (set a 10))
    a)
;; => 10

Validation パスを経た IR が欲しくなってきた

コンパイル時にエラー検出用のコードが重複しがちです。

  • 構文エラー
    ( のとじ忘れから operand の欠如など

  • 型のエラー
    ミスマッチや arity チェックなど

  • 文脈のエラー
    未実装ですが、 break や continue が出てくると文脈によっては無効にすべきです。

  • Desugaring
    複数の項を取る演算子などは、 2 項の演算子で表現し直した方が簡単です。

コンパイラ側の都合が見えてきたので、 IDE サポート時の都合にも目を通したいと思います。両方見えてきたら IR を追加します。

toyboot4etoyboot4e

制御構文 (2): cond

cond は基本的に when の列挙です:

(proc main ()
    (cond (false 10)
        ((or false false) 20)
        (true 30))
;; => true

cond 式と cond 文

cond 内の句は網羅的 (comprehensive) でないかもしれません。 (t ..) 句が無い場合は文として処理します。

ELisp の cond は、どのテストも通過しなかった場合 nil を返します。

cond の返値を使わない場合も cond 文として処理するべきです。 cond 文は、それぞれのケースの返値の型が合わなくても許容します。

toyboot4etoyboot4e

cond の見直し

cond ケースの () を削除する案

たとえばこの記事で言及されています:

https://www.reddit.com/r/lisp/comments/dm6ox1/lisps_mistake_cond/

日本語記事でも [] を構文に採用すると良いぞ、と言う話で cond にも触れられていたような……どの記事かな……

フィボナッチ数列で比較すると:

(fn fib (x:i32)
    (cond ((= x 0) 1)
        ((= x 1) 1)
        (t (+ (fib (- x 1)) (fib (- x 2)))))

(fn fib (x:i32)
    (cond (= x 0) 1
        (= x 1) 1
        t (+ (fib (- x 1)) (fib (- x 2))))

fn は純粋な関数、 proc は副作用を含む手続きにしたいです

あるいは複数の式が続く場合:

(cond
    (false (print "a")
          (print "b"))
    (true (print "a")
         (print "b")))

(cond
    false (do (print "a")
               (print "b"))
    true (do (print "a")
              (print "b")))

意外と僕は () を書く方が好みです。

() が無いバージョンを cond2 にしても良いかもしれません。

あるいはケースの区切り文字を作ると:

(cond
    | false (print "a")
          (print "b")
    | true (print "a")
          (print "b"))

これはアリかもしれません。 Lisp はこういう特殊な構文を最小限にした言語ですが、 toylisp は Lisp モドキなので全然良いと思います。

でもまぁ () アリが好みかなぁ………

cond を式に、 when* を文にしてみる案

式／文の解析が面倒です。 cond は常に式 (恒真のテストが無ければエラー) 、 when* は文という形でも良いかもと思います。 cond と cond_ を区別してもいいです。

toyboot4etoyboot4e

比較演算子の実装

分岐やループ条件には比較演算子が必要です。フィボナッチ数列にも分岐が現れます。

実装

AST では通常の関数と組み込み演算子を区別しません。 IR 以降では通常の関数と区別します。

組み込み演算子は通常の関数と異なり generic です (arity が 2 以上の任意の数で、項の型が不特定) 。マクロとして desugaring するか、個別に実装を用意するかはともかく、通常の関数とは扱いを分けておいた方が無難です。

テスト
#[test]
fn comparison() {
    // bool
    test_expr("(= true true)", true);
    test_expr("(= true false)", false);
    test_expr("(= false true)", false);
    test_expr("(= false false)", true);

    test_expr("(!= true true)", !true);
    test_expr("(!= true false)", !false);
    test_expr("(!= false true)", !false);
    test_expr("(!= false false)", !true);

    // i32
    test_expr("(= 0 2)", false);
    test_expr("(= 2 2)", true);

    test_expr("(!= 0 2)", !false);
    test_expr("(!= 2 2)", !true);

    test_expr("(< 2 4)", true);
    test_expr("(< 3 3)", false);
    test_expr("(< 4 2)", false);

    test_expr("(<= 2 4)", true);
    test_expr("(<= 3 3)", true);
    test_expr("(<= 4 2)", false);

    test_expr("(> 2 4)", false);
    test_expr("(> 3 3)", false);
    test_expr("(> 4 2)", true);

    test_expr("(>= 2 4)", false);
    test_expr("(>= 3 3)", true);
    test_expr("(>= 4 2)", true);

    // f32
    test_expr("(= 0.0 2.2)", false);
    test_expr("(= 2.2 2.2)", true);

    test_expr("(!= 0.0 2.2)", !false);
    test_expr("(!= 2.2 2.2)", !true);

    test_expr("(< 2.2 4.4)", true);
    test_expr("(< 3.3 3.3)", false);
    test_expr("(< 4.4 2.2)", false);

    test_expr("(<= 2.2 4.4)", true);
    test_expr("(<= 3.3 3.3)", true);
    test_expr("(<= 4.4 2.2)", false);

    test_expr("(> 2.2 4.4)", false);
    test_expr("(> 3.3 3.3)", false);
    test_expr("(> 4.4 2.2)", true);

    test_expr("(>= 2.2 4.4)", false);
    test_expr("(>= 3.3 3.3)", true);
    test_expr("(>= 4.4 2.2)", true);
}
toyboot4etoyboot4e

制御構文 (3): while

比較演算子ができたのでループも実装できます。

テスト

for 文じみた while を書いてみました:

    test_expr(
        "
(let a 0)
(while (< a 3)
    (set a (+ a 1)))
a",
        3,
    );

Lisp らしからぬ普通の言語になりつつあります。マクロが来てからが本番ですね。

break 実装は IR を増やすまで保留

break をコンパイルするためには、 break に対応するループの終わりを見つけなくてはなりません。もちろん今でも実装できますが、コンパイルに必要な文脈が増える気がします。むしろ break 先を静的に解決した IR を用意したいところです。

loop や break の実装は保留します。ユーザ関数 → 言語サーバ稼働 → コンパイル用 (もしくは解析用) IR 作成 という順番で行こうと 思います。 if なども今は実装しません。

参考: Racket のループ

Scheme 系の言語では、ざっくりと [] とか {} は () と等価らしいです。特殊形式における特殊な () を [] と書いて区別します。

https://beautifulracket.com/explainer/loops.html

そんな Racket のループでは、 2 つイテレータを並べると zip になる (?) みたいです:

(for ([i (list 1 2 3)]
      [j (list 1 2)])
  (println (list i j)))

この書き方は必要無いですが、多重ループを簡単に書く仕組みはあっても良いなと思います。 Haskell のリスト内包表記が良い例です。

ループ中のガード (#:when, #:unless) や #:break といった構文もあるようです。 toylisp では(#:break) または (#:break expr) という形にしようかと思います。参考になりました。

toyboot4etoyboot4e

MIR と dada BIR の関連

Guide to Rustc Development の MIR data types の言葉を知ると、 dada の bir (base IR) が分かってきます。

MIR の語彙及びテキスト表現

MIR ではプログラムを CFG で表現し、分岐や break のジャンプ先が明確になります。また MIR の語彙を使うとプログラムの意味に近付けます。たとえば代入の文法は <Place> = <Rvalue> となり、メモリ位置を表す式のみが左辺に来ます。 Copy / move やライフタイムも明示的になるようです。

  • Basic blocks: CFG (MIR) の構成単位。 bb0, bb1 のように書く
    • statements: basic block 内の末尾以外の文
    • terminators: basic block 末尾の式／文
  • Locals: スタック上の領域 (引数、ローカル変数、一時変数) 。 _1, _2 のように書く。 _0 は返値
  • Places: メモリ位置を表す式
  • Rvalues: 値を生む式
    • Operands: rvalue が取る項、 rvalue の引数 (定数もしくは place)

dada の BIR から例を取り出すと、

#[derive(PartialEq, Eq, Clone, Hash, Debug)]
pub struct BasicBlockData {
    pub statements: Vec<Statement>,
    pub terminator: Terminator,
}

#[derive(PartialEq, Eq, Clone, Hash, Debug)]
pub enum StatementData {
    AssignExpr(TargetPlace, Expr),
    Clear(LocalVariable),
    // ~~~~
}

#[derive(PartialEq, Eq, Clone, Hash, Debug)]
pub enum TargetPlaceData {
    LocalVariable(LocalVariable),
    Dot(Place, Word),
}

……まだ名前解決の途中のような雰囲気もありますが、概ね MIR です。一時変数の自動挿入というのもあるようで、意外とリッチな解析と lowering が行われている気配があります。

toylisp フロントエンドに BIR / MIR は必要か

あった方が良いと思いますが、 rust-analyzer には MIR はありませんから試行錯誤になりそうです。 dada も IDE サポートをそんなに頑張ってくれていないので、コピペプログラマにはなれません。

toyboot4etoyboot4e

関数呼び出し (1)

基礎的な命令が揃ってきたところで、いよいよ関数呼び出しを実装します。

引数の無い関数呼び出し

VM が複数の関数を持てるように拡張します。関数毎にバイトコードを持つことにしました。 VmProc や VmCallFrame といった型を追加します。

(proc f ()
    15)

(proc main ()
    (+ 5 (f)))
;; => 20

引数を持つ関数の呼び出し

コールスタックの扱いを考える必要があります。 Crafting Interpreters では 、 2 つのコールフレームの範囲を引数の部分で重ねているので倣います。また返値はコールフレームを pop した後に改めて push することにします。

(proc f (x)
    (+ x 5))

(proc main ()
    (f 10))
;; => 15

フィボナッチ関数

さてバグが無ければフィボナッチ関数も実行可能です。デバッグのために DebugContext を作ります。式やパタンの ID を再帰的にデータに復元してデバッグ表示できるようになり、取り回しが良くなりました。残ったバグを取り除きます。

いざ実行……！

(proc fib (x)
    (cond ((= x 0) 0)
          ((= x 1) 1)
          (true (+ (fib (- x 1)) (fib (- x 2))))))

(proc main ()
    (fib 10))
;; => 55
現状の bytecode (命令数多いな……)
proc 0:
  0: alloc-frame-8   0
  2: shift-back-8    0
  4: push-const-8    0
  6: call-proc16     1 (u16)
  9: ret

proc 1:
  0: alloc-frame-8   0
  2: shift-back-8    1
  4: push-local-8    0
  6: push-const-8    0
  8: eq-i32
  9: jump-if-not-16  17 (u16)
 12: push-const-8    1
 14: jump-16         55 (u16)
 17: push-local-8    0
 19: push-const-8    2
 21: eq-i32
 22: jump-if-not-16  30 (u16)
 25: push-const-8    3
 27: jump-16         55 (u16)
 30: push-const-8    4
 32: jump-if-not-16  55 (u16)
 35: push-local-8    0
 37: push-const-8    5
 39: sub-i32
 40: call-proc16     1 (u16)
 43: push-local-8    0
 45: push-const-8    6
 47: sub-i32
 48: call-proc16     1 (u16)
 51: add-i32
 52: jump-16         55 (u16)
 55: ret

引数の型

引数の型は推論 [1] させても動くと思いますが、型表記が無ければ構文エラーにしたいと思います。それは次回！

脚注

  1. 単相の型なので、推論と言っても単純な unify です。 ↩︎

toyboot4etoyboot4e

関数の型の記法

どの構文が良いかな？

既存言語

手続き型言語

Rust:

fn fib(x: usize) -> usize {
    match x {
        0 => 0,
        1 => 1,
        _ => fib(x - 1) + fib(x - 2),
    }
}

Odin (参考):

fib :: proc(n: int) -> int {
	switch {
	case n <= 0:
		return 0
	case n == 1:
		return 1
	}
	return fib(n-1) + fib(n-2)
}
Lisp 系の言語

Racket (参考):

(: fib : Number -> Numer)
(define (fib n)
  (cond
    ((= n 0) 0)
    ((= n 1) 1)
    (true (+ (fib (- n 1)) (fib (- n 2))))))

(define (fib [n : Number])
  (cond
    ((= n 0) 0)
    ((= n 1) 1)
    (true (+ (fib (- n 1)) (fib (- n 2))))))

Common Lisp (参考):

(declaim (ftype (function (fixnum) fixnum) fib))
;;                         ^^input ^^output [optional]

(defun fib (n)
  (cond
    ((= n 0) 0)
    ((= n 1) 1)
    (t (+ (fibo (- n 1)) (fibo (- n 2))))))
関数型言語

OCaml はコンパイルできなかったのでスキップします。

Haskell:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

まとめ

  • Rust: 式指向、網羅的パタンマッチ、アロー
  • Odin: 関数の名前を行頭に書く
  • Haskell: 引数に対するパタンマッチ
  • Scheme: (define (f arg1 arg2) body) + 型を表記する行
  • Common Lisp: (defun f (arg1 arg2) body) + 型を表記する行

toylisp の proc を相当特別な特殊形式にすることに抵抗ありません。スペース無しなら name:type の形で型を表記できることにします:

(proc fib (x:i32) -> i32
    (cond ((= x 0) 0)
          ((= x 1) 1)
          (true (+ (fib (- x 1)) (fib (- x 2))))))

あるいは Scheme 系の構文に:

(proc (fib x:i32) -> i32
    (cond ((= x 0) 0)
          ((= x 1) 1)
          (true (+ (fib (- x 1)) (fib (- x 2))))))

まぁ前者かなぁ

toyboot4etoyboot4e

そういえば occur check をしていない

速攻 MinCaml コンパイラ概説 の型推論の項で説明のあった occur check ですが、まだ実施していません。

たとえば、もし（occur checkをしないで）型変数αと関数型int→αをunifyしてしまうと、α = int→αなので、int→int→int→...という無限長の型になってしまいます！

高階の関数を使い始めると occur check 必要になるようです。

toyboot4etoyboot4e

関数呼び出し (2)

引数の型表記を実装しました。以下で x:i32 を x:f32 に書き換えると、型のミスマッチを検出できます:


(proc fib (x:i32)
    (cond ((= x 0) 0)
          ((= x 1) 1)
          (true (+ (fib (- x 1)) (fib (- x 2))))))

(proc main ()
    (fib 10))

1 引数の文法は Pat ":" Type なので、仮にタプルを実装すれば (x, y): (i32, i32) のような型も受け付けることができます。気の早い (気の長い) 話ですが……

toyboot4etoyboot4e

rust-analyzer はいかに診断情報を扱っているか

rust-analyzer の診断情報は基本的にコンパイラの診断情報と完全一致します。これはそもそもコンパイラの出力 (cargo check) を利用しているためです:

https://rust-analyzer.github.io/manual.html#diagnostics

ra はファイル保存時に cargo check を実行します (ra の用語では (Emacs にちなんで？) flycheck という) 。 cargo check はディスクのファイルを読んで実行されますから、ファイルの編集中には診断情報が更新されないという issue が上がっています:

https://github.com/rust-lang/rust-analyzer/issues/3107

一方で fixits (コードの修正候補) を持つような診断情報は、 ra 独自の解析によって得られています。これらの診断情報がどのように使い分けられているのか、それぞれの場面でユーザが目にするのはどちらの診断情報なのか確かめていきたいと思います。

rustc からの診断情報 (flycheck)

たぶんこれ？:

https://docs.rs/cargo_metadata/latest/cargo_metadata/diagnostic/struct.Diagnostic.html

TODO: flycheck のソースをよく読む

ra 独自の診断情報 (ide_diagnostics)

HIR の診断情報は必要最低限のデータです:

hir/diagnostics.rs
#[Debug)]
pub enum AnyDiagnostic {
    // ~~
    TypeMismatch(TypeMisMatch),
    // ~~
}

#[derive(Debug)]
pub struct TypeMismatch {
    // FIXME: add mismatches in patterns as well
    pub expr: InFile<AstPtr<ast::Expr>>,
    pub expected: Type,
    pub actual: Type,
}

ide_diagnostics の診断情報は、ユーザ表示のため fixits や範囲が付いています:

ide_diagnostics/lib.rs
#[derive(Debug)]
pub struct Diagnostic {
    pub code: DiagnosticCode,
    pub message: String,
    pub range: TextRange,
    pub severity: Severity,
    pub unused: bool,
    pub experimental: bool,
    pub fixes: Option<Vec<Assist>>,
}

flycheck, ide_diagnosticsの使い分け (rust_analyzer)

予想: ra 由来の診断情報が rustc 由来の診断情報に完全一致する場合、マージして fixits などの情報を付加する。もしくは診断情報表示は flycheck, その他は ide_diagnostics という 2 つの並行したシステムとして扱い表示する。

TODO

toyboot4etoyboot4e

診断情報の検討

Rust と言えば懇切丁寧なエラー表示で、 Haskell のエラーを見るたびに『もう少し頑張ってくれ！』と嘆くわけですが、 toylisp のエラー表示も Rust に準ずるするものであってほしいです。

描画用クレート

大した行数でもないので自作しようかと考えています。既存のクレートは、

crate line counts ノート
ariadne 1260 shiika でも使用されている
miette 4909 Error トレイトの拡張？も目指す
codespan-reporting 2050 ぱっと見では一番好み
annotate-snippets-rs 1470 rust のリポジトリだけれど放置気味

ざっと見た感想としては、

  • trait 無しにしたい
  • Builder 主体の API が良さそう

rustc の場合

診断情報の構成要素がノートされています:

https://rustc-dev-guide.rust-lang.org/diagnostics.html

Span は lazy に取得する

診断情報を作ったからといって、描画するとは限りません。特に span の取得は計算に必要な依存を増やします。 Span を取得するのは描画の直前が無難そうです。

しかし cargo check するわけでもないので、 toylisp では言語サーバが全てのソースを解析することになると思います。果たしてレジーな計算に意味があるのかは疑問です。

Accumulators (salsa-2022)

salsa DB が診断情報のストレージを作ってくれるので試してみようと思います。ぱっと見 Vec がダブりそうなんですが大丈夫なのか。

描画例 (Rust)

ターミナル上では全情報表示:

言語サーバ上ではメッセージのみ表示 (一覧表示ではサブメッセージも表示):

すべて Ascii 文字で表示しており、滑らかな曲線表現などはありません。その点も好みです。

toyboot4etoyboot4e

診断情報こと始め

随時更新

diagモジュール

眠すぎゆ (23:11)

行表示

眠すぎんぬ (01:17)

  • エラー行を正しく表示:

ひとまず span が正しく機能していたようで良かった。予想された型を表す Note が欲しい。周辺のコードも表示してほしい？　段階を分けて診断情報を作るための API (builder?) が欲しい。

背景色を使って表現するのも面白いかも。ただしターミナルの初期背景色を想定するか、コードの初期背景色を設定する必要がある

診断情報作成の API

仮に作った診断情報の構造体が大きいです:

struct Line
pub struct Line<'a> {
    // [code]<severity>: <msg>
    pub severity: Severity,
    pub msg: &'a str,
    // --> <src_file>
    //            |
    // <ln>:<col> | <line_text>
    //            |    ^^^^ <reason>
    pub src_file: &'a str,
    pub line: usize,
    pub column: usize,
    pub line_text: &'a str,
    pub line_span: Span,
    pub reason: &'a str,
}

API を簡潔にするために trait を足してみました。情報を集約したデータを少数受け取って診断情報を作っています。意外に builder が合わないかも:

pub trait Diagnostic {
    // fn code(&self) -> &str;
    fn severity(&self) -> Severity;
    fn msg(&self) -> &str;
}

フォーマット修正

色や太字の修正を入れると Rust でお馴染みの画面に近づきました。相当映りが良くなりますね。

toyboot4etoyboot4e

Rust の型ミスマッチ診断抜粋

個々の診断 (スクリーンショット)

E0207

引数の型が異なる (ビルトイン演算子)

トレイト実装が無いということに:

E0308

引数の型が異なる (ユーザ定義関数)

元の関数定義の note が出ます:

関数定義や関数呼び出しが複数行に分かれている場合:

`match` アームの型が異なる


ケースが複数行に及ぶ場合:

E0412

型が不明な関数とその呼び出し

呼び出しの方には診断情報が出ませんでした:

ノート

  • 同じエラーコードでも、エラーの詳細に応じてメッセージが異なる
  • 診断ウィンドウ でミスマッチ部分を指す
    • 1 行に複数の指摘が混じる場合がある
    • 複数行に対する指摘の場合もある
  • サブ診断 (note: ..) でなぜその型が予期されるかを示す
  • サブ診断 (help: ..) でコード編集案を示す。 rustc の help は LSP では hint に相当する。
  • 診断情報はダブらせない
    • if ブロックや match アームの型ミスマッチについては、複数のミスマッチがあっても 1 つだけ報告する
    • 型が不明な関数定義があった場合、その呼び出しには診断情報を出さない
  • 診断ウィンドウとサブ診断はいずれも左端に表示する。ただし色の違いによってどのサブ診断がどの診断ウィンドウに属するか判断できる
  • | のインデントは指摘箇所のコード行数による:

表示全体

Item の診断を先に出して、その後 body が続きます。行数が小さい方から順番に表示するというのも考えられそうですが、どうでしょうか。またエラー情報の一覧を見るような TUI があっても良い気はします。

toyboot4etoyboot4e

Shiika 覗き見

ariadne を実用している数少ない言語ということで、 Shiika の表層を覗いてみます。 .sk ファイルを実行すると、 .ll ファイル及び .out ファイルが生成されます。これが噂の LLVM の入出力……？！

診断情報

ariadne の診断情報を自分のターミナルで見るとめちゃめちゃカッコいい:

Unicode の記号で滑らかに線を描いています:

特に左端の点がお気に入りで、明らかに rustc の出力よりも美しく機能的ですね。 Ascii 文字縛りは止めようと思いました 。

所感

診断を含め、フロントエンドはまだまだこれからみたいです。 Help wanted で構文ハイライトが必要そうなので、 tree-sitter のパーサを追加できたら良いかもしれません。

行数カウントを取ると、 Rust と Shiika builtin が両方 15,000 行程度でした。ライブラリの方に力が入っているのは、誰よりも作者が待ち望んでいる言語という感じがしますね。いいなぁ……

toyboot4etoyboot4e

さらに診断情報表示

Rust のエラー表示が分かってきたのでゴリ押しで実装します。ともかくレスポンスが出てくるのは嬉しいですね。

1 行に複数のマーカー

より rustc 風の表示に近づきます:

Unicode 罫線文字 をお試し

角線:

rustc / ariadne の折衷案:

1 つの診断に複数行のマーカー

できました:

マーカーの対象が複数行に渡る場合にも対応したいですが、まだ文字列リテラルはないのです……

コンテキスト表示

型エラーが起きたコードが所属する手続きの名前を表示します:

範囲を明確に

短い範囲も明確に示すことができるようになりました:

でもちょっとキモいね……。

このくらいがまだ無難かな。

toyboot4etoyboot4e

さらに診断情報

すべてのパスで美麗な診断情報を得られるように実装していきます。情報が重複しないように気を付ける必要があるかもしれません。

型解析パス

関数呼び出しの型ミスマッチは以下のように報告されます:

<unknown> とか1 arguments となっているのは修正しなければならないが……

ついにサブウィンドウが登場しました。診断情報のデータ配置を把握したので Builder だってつくれます。型がマッチした引数には下線を引きませんし引用しません。

Item 収集パス (lowering)

Item のエラーは構文エラーですが、『どの関数のエラーなのか』をまとめて表示するため item 収集パスでレポートしたいと思います

上の例は、 rustc だと 3 つの個別エラーになります。その場合エラー毎に修正案 (help) を出せることが利点になりますが、それぞれのエラーがどの関数に所属するものかは伝わりにくくなります。 toylisp の場合、 help は出すつもりが無いのでまとめて表示してみます。

IDE で見る場合も 1 つのエラー表示になり、 help の恩恵も受けられなくなりますが、案外まとまった表示が良いということになるかもしれません。試してみたいと思います。

手続きの名前が抜けている場合は、それだけレポートします:

名前の無い proc は手続きとして認めないため、引数や返値の分析はしません。

同名の関数が複数ある場合を扱います。まずアイテムレベルの構文エラーがある場合『同名の関数が存在するか』はレポートされません。関数の名前が重複する場合は、ファイル冒頭に近い最初の関数定義が正という扱いになり、 rust-analyzer の goto definition でもそこに飛びます。またその関数定義に関数定義に構文エラーが含まれていても、その関数が正の関数という扱いです。

TODO

字句解析パス (lex)

字句解析のエラーは、文字列が閉じていないというのしか思いつきません。

構文解析パス (parse)

構文解析パスでは、引数の型表記が抜けているなど、トークンの並びに関するエラーを検出できます。現状では余計なエラーが大量に出てしまいます:

Crafting Interpreters では ベストエフォートで解析を続けました (動きを見る限り rustc も同様) 。 toylisp では () のバランスが取れていない場合他のエラーを報告しないというのが良い気がします。

Body 収集パス (lowering)

  • 名前解決のエラー

TODO

Validate パス

このパスを実装するのは

Compile パス

Validate パスが全てのエラーを吸収する気がします。

toyboot4etoyboot4e

どこまで作ったっけ……

やはり toylisp こそ本命！

近々やりたいこと

この辺はなんとかなりそうです。手を付けていきますか……！

  • 開発環境改善
    • Bytecode をデータ駆動でテスト可能にする
    • Bytecode のデバッグ表示に関数名などのコメントを含める
  • 機能追加
    • 文字列リテラル
    • print, assert
    • loop, break, return
      • やはり BIR への展開が必要？
    • do
    • for in
  • () の数が合わないときの診断情報表示をマシにしたいが……
  • 言語サーバを再度動くようにする

将来的な

これは手に負えるのか……

  • 言語サーバの各種機能
  • strict, enum
  • match
  • マクロ
  • Generic データ型 or comptime
  • Generic 関数 or comptime
  • クロージャ
  • コルーチン
  • Prelude (Vec, Map ほか)
  • extern
toyboot4etoyboot4e

On Modularity of Lexical Analysis

  • 行単位でパースできるようにする
  • api = pub, pub = pub(crate) にしてファイル内全域から見えるというのは止める
  • export 禁止にする
  • 名前解決の前に構文ベースのマクロを展開する
  • mod foo を止めてファイルシステムをそのまま反映する
  • :: を止めて . を使う。型と値を分けるのは上手く行っていない
  • モジュールの木を作成する以外は全て並列処理にする
  • コンパイラが .api ファイルを出力し、 Git 等で追跡できるようにする
  • モジュールは相互参照でき、ライブラリはできない
  • 可視性はモジュール単位で作るべき。
toyboot4etoyboot4e

Type Checking If Expressions

それはそうだという感じでした。

  • if が式である場合

    • 各 branch の型が一致しなければならない (自動的に upcast しない)
      • return で終わる branch など bottom 型は制約を課さない
    • 各 branch が全ての分岐を網羅しなければならない

  • if が文である場合

    • 上記制約無し

加えて代入先の型が分かっている場合は、 if 式全体の型推論ができて、各 branch の型を unify できると思います。

toyboot4etoyboot4e

Representing Heterogeneous Data

Sum type 的な言語機能の簡単な代替を模索する記事のようです。パタンマッチや destructuring を作ってみたが、実装も構文も複雑になったため他の方法を採用しています。

Variant の作り方は Rust 的ではなく TypeScript 的です？ [1] 。またすべての variant 中のフィールドを union のように扱いつつ、タグで分岐するための構文 if object is Variant then .. も用意しています。

フロー解析 (タグのマッチ後にしか variant のフィールドにアクセスできない) は、 Dart で大変過ぎたため採用しないようです。確かに途中で別の varient を再代入した場合などは、考えるのも面倒くさそうです。。

ただこの方式だと null safety は無いですね。僕としてはフロー解析によってソース位置によって変数の型が変化する……のは大変なので、やはり sum type が良いかなと思っています。パタンマッチの度に新しい変数 (参照) を作るとすれば、解析は比較的簡単になりそうです。十分複雑なようですが……。

脚注

  1. この違いは何ていうんだっけ…… ↩︎

toyboot4etoyboot4e

25. Closures · Crafting Interpreters

Upvalue と flat closure の話とか、メモしていなかったっけ……？

Upvalue とは

すべての関数はクロージャとしてインスタンス化して実行する。クロージャにキャプチャされる変数はスコープよりも長いライフタイムを持ち、 GC によって管理される必要がある。 キャプチャの対象を常にヒープに入れる というもの有効な手だが、 Lox においては one-pass コンパイラであるため Lua 同様に upvalue を用いる。

実行時における upvalue の表現を ObjUpvalue とする。 ObjUpvalue はヒープ上にある共有変数である (GC によって開放される) 。 ObjUpvalue はキャプチャ対象の変数がスタック上にある限りはスタックを指し、スタック上に無い時は自身のフィールドにて所有する。

なおグローバル変数はキャプチャ対象ではない。

コンパイル時の Upvalue への名前解決

Local 変数と同列のデータ型として Upvalue を追加する。クロージャのコンパイル時に、外部スコープ上の変数として名前解決された変数は Upvalue として扱う。

あるキャプチャ対象の変数に対する ObjUpvalue ただ 1 つでなければならない。そこで Upvalue は、真上のスコープ中のスタック上にある <変数または Upvalue> を指すものとする。スタック上の変数を指す Upvalue の作成は、実行時における ObjUpvalue の作成に相当する。 Upvalue を指す Upvalue の作成は、実行時における既存の ObjUpvalue の共有権のコピーに相当する。

実行時に ObjUpvalue の deduplication

これでネストしたクロージャに関しては ObjUpvaue の deduplication に成功したが、同じ階層に複数のクロージャがある場合は、 ObjUpvalue を 2 つ作らないように注意が必要となる:

fn outermost() {
  var x = 10;
  fn a() { x += 10; } // `x` をキャプチャする (新たに `ObjUpvalue` を作成する)
  fn b() { x += 20; } // `x` をキャプチャする (既存の `ObjUpvalue` をコピーする)
  return (a, b)
}

Lox においては、以下の通り動的に解決している。コンパイル時に解決すれば良いと思うが、クロージャの位置関係によって upvalue キャプチャ命令を切り替えるよりもシンプルなのかもしれない。

VM に open upvalue (スタック上の変数を指す upvalue) のリストを持つ。このリストはスタックへの添字 (またはポインタ) でソートされており、最も先頭の upvalue はスタック上で最も高い位置にある。そのため open ObjUpvalue の線形探索の打ち切りができる (し、 2 分探索もできると思う) 。

実行時の ObjUpvalue 作成と close 処理

クロージャの呼び出し時に ObjUpvalue の作成を行う。この際に同じキャプチャ対象の ObjUpvalue を複製しないよう気を付ける。すなわち:

  • Upvalue がスタック上の変数を指す場合
    • VM が持つ ObjUpvalue のリストに対象の変数を指す ObjUpvalue が存在する場合
      それをコピーする
    • VM が持つ ObjUpvalue のリストに対象の変数を指す ObjUpvalue が存在しない場合
      新たに ObjUpvalue を作成する。
  • Upvalue が外側のクロージャにキャプチャされた ObjUpvalue を指す場合
    その ObjUpvalue をコピーする

スコープの終了時には、スタック上のローカル変数を指していた open な ObjUpvalue をクローズし、スタック上の実態を ObjUpvalue のフィールドに移動する。外から見た ObjUpvalue の API は一定であり、常に deref_upvalue 的な関数経由で実体にアクセスする。

The Implementation of Lua 5.0

Flat closure の話が乗っている。

With flat closures,
whenever a function accesses an outer variable that is not local to its enclosing
function, the variable also goes to the closure of the enclosing function. Thus,
when a function is instantiated, all variables that go into its closure are either
in the enclosing function’s stack or in the enclosing function’s closure.

Lua, Lox ではそれぞれのクロージャが ObjUpvalue の配列を持っている。 ObjUpvalue の配列を outermost 関数に集約できないか考えてみたが、クロージャを返す関数もあるので、クロージャ自体が upvalue への共有権を持った standalone な存在でなければならない気がした。

toyboot4etoyboot4e

26. Garbage Collection · Crafting Interpreters

"Mark and sweep" 方式が主流のようです。

Mark

ルート変数から到達可能なオブジェクト (GC 対象) をマークします。

ルート変数をマークする

以下のルート変数を訪問し、 mark フラグをセットした上でスタックに入れます:

  • スタック領域・グローバル領域にあるオブジェクト
  • upvalues
  • コンパイル中の関数オブジェクト

到達可能な変数を調べる

DFS します。

Sweep

全オブジェクトを訪問し、 mark されていなければ到達不能なので解放します。また is_marked 変数を false にリセットします。

Lox においてはすべての Obj の連結リストを作っています。 Rust だったら Vec<Obj> に入れておいて swap_remove していくのが楽そうです。

String テーブルにおいては interning をおこなっているため特別な対応が必要。テーブルは String への弱参照を持ち、 ObjString は強参照を持つ。 sweep 直前に string テーブルの解放処理を挟む。

GC のタイミング

ヒープ領域中のデータサイズが閾値を超えたら実行します。また GC 後に閾値を調整します:

vm.nextCG = vm.bytesAllocated * GC_HEAP_GLOW_FACTOR;

バグ

関数の実行中に都度 GC しなければならない場合がある のが恐ろしいところですね。アロケーションの直前に GC を行うのが最も柔軟ですが、コーナーケースの阿鼻叫喚……！

toylisp においてはホスト言語からの実行がメインなので、関数の実行完了時に GC すれば良い気がしています。でもコルーチンがあると大変そうだな……！

Rust 版では？

ヒープ変数はアリーナに入れると思うので、かなり扱いが変化しそうです。

toyboot4etoyboot4e

19. Strings · Crafting Interpreters

20.5 String Interning

VM に interning 用のハッシュテーブルを追加し、全ての文字列を interning します。 文字列コピーが単なる参照のコピーとなる 他、文字列の比較も O(1) になり、メソッドの名前解決なども高速化されるようです。

静的言語ではコンパイル時に名前解決するため、 実行時に interning する意味は無いのではないか (文字列を共有オブジェクトにするだけで十分なのではないか) という気もします。

ファイル毎に並列でコンパイルする場合、ローカルなコンパイル結果を後から統合して interning する必要があると思います。

文字列リテラル

コンパイル時に interning しておきます。グローバルの関数はルートとしてマークされるため、文字リテラルを含む定数は GC 対象となりません。

あるいは n 番以下の文字列はリテラルであるから解放しないとすれば良い気が。

静的型付け

Lox は動的型付けの言語なので、スタックの中の値はタグ付き共用体として型付けされています。一方 toylisp は静的型付けの言語であるため、スタック領域は単なるバイト列です。そのためスコープ毎に GC の対象となるオブジェクトをメモしておく必要があると思います。

ただし関数の実行状態によって同じスタック領域でも変数の解釈が変わってくるので、それはめんどいなぁ……

全てのスコープの変数にユニークなアドレスを割り当ててしまえば簡単そうですが。

toyboot4etoyboot4e

WIP 文字列実装

既にある程度コンパイラパスが出来上がっているので、機能追加は楽です。

  • パース
  • lowering
  • 演算
  • print
    • 型チェックどうしよう
  • GC
    • mark
    • trace
    • sweep