Rust で型推論を高速かつ安全に実装

CRANK

簡単、高速、安全。Rc / RefCell の威力を知ってほしい。データ型の定義型まずは普通に型 を定義します。たとえば、ブーリアン型 と関数型 だけの型システムなら、以下のようになります。enum Ty { Bool, Func(Rc<Ty>, Rc<Ty>), } Box ではなく Rc を使っています：これから型推論を実装しますが、型 を型変数 に代入するとき、参照カウントをインクリメントするだけで を clone できます。型変数次に、型変数 をこれにくわえます。型変数は「まだ何も代入されていない」or「型 が代入されている」のどちらかなので、これをそのまま enum で表します。enum Var { Assigned(Rc<Ty>), Unassigned, } 最後に、型変数 を元の型 と同列に扱うため、Ty の列挙子に Var を追加します。enum Ty { Bool, Func(Rc<Ty>, Rc<Ty>), Var(RefCell<Var>), } 解 が得られたら、 を Var::Unassigned から Var::Assigned() に書き換える必要があるので、可変性のために RefCell を使っています。定義は以上です。以下、実装です。型推論Contains の実装たとえば のとき、 の解を としてしまうと、 が無限再帰する型になってしまいます。これを防ぐために、 が内部…