toylisp devlog 3 (1, 2)

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

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

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

関数 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 関数) を追加してみたいと思います。 + や - をオーバーロードしてほしい！

脚注

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

パス	変換	書き換え
`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` とバイト列間の変換を追加しました

パス	変換	書き換え
`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 命令を追加しました

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

toylisp devlog 3 (1, 2)

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

MinCaml の型推論

構文

型変数の扱い方

型推論のやり方

感想

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

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

true, false リテラルの追加

and, or の追加

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

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

Lisp には論理演算子が無いのかもしれない

Bitwise な VM の夢

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

x86-64 の知識が足りない

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

問題点

解決策

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

制御構文 (1): when, unless

実装

set 命令も実装してみた

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

制御構文 (2): cond

cond 式と cond 文

cond の見直し

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

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

比較演算子の実装

実装

制御構文 (3): while

テスト

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

参考: Racket のループ

MIR と dada BIR の関連

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

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

関数呼び出し (1)

引数の無い関数呼び出し

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

フィボナッチ関数

引数の型

関数の型の記法

既存言語

まとめ

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

関数呼び出し (2)

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

rustc からの診断情報 (flycheck)

ra 独自の診断情報 (ide_diagnostics)

flycheck, ide_diagnosticsの使い分け (rust_analyzer)

診断情報の検討

描画用クレート

rustc の場合

Span は lazy に取得する

Accumulators (salsa-2022)

描画例 (Rust)

診断情報こと始め

diagモジュール

行表示

診断情報作成の API

フォーマット修正

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

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

ノート

表示全体

Shiika 覗き見

診断情報

所感

さらに診断情報表示

1 行に複数のマーカー

Unicode 罫線文字 をお試し

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

コンテキスト表示

範囲を明確に

さらに診断情報

型解析パス

Item 収集パス (lowering)

`true`, `false` リテラルの追加

`and`, `or` の追加

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

制御構文 (1): `when`, `unless`

`set` 命令も実装してみた

制御構文 (2): `cond`

`cond` 式と `cond` 文

`cond` の見直し

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

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

制御構文 (3): `while`

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

rustc からの診断情報 (`flycheck`)

ra 独自の診断情報 (`ide_diagnostics`)

`flycheck`, `ide_diagnostics`の使い分け (`rust_analyzer`)

`Span` は lazy に取得する

Accumulators (`salsa-2022`)

`diag`モジュール

Unicode 罫線文字をお試し

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

実行時に `ObjUpvalue` の deduplication

実行時の `ObjUpvalue` 作成と close 処理