簡単、高速、安全。Rc / RefCell の威力を知ってほしい。
型
まずは普通に型
enum Ty {
Bool,
Func(RcTy>, RcTy>),
}
Box ではなく Rc を使っています：これから型推論を実装しますが、型
型変数
次に、型変数
enum Var {
Assigned(RcTy>),
Unassigned,
}
最後に、型変数 Ty の列挙子に Var を追加します。
enum Ty {
Bool,
Func(RcTy>, RcTy>),
Var(RefCellVar>),
}
解 Var::Unassigned から Var::Assigned() に書き換える必要があるので、可変性のために RefCell を使っています。
定義は以上です。以下、実装です。
Contains の実装
たとえば
impl Ty {
fn contains(self: &RcTy>, var: &RefCellVar>) -> bool {
todo!()
}
}
self (var (
fn contains(self: &RcTy>, var: &RefCellVar>) -> bool {
match self.as_ref() {
Ty::Bool => false,
Ty::Func(param, ret) => param.contains(var) || ret.contains(var),
Ty::Var(self_var) => todo!(),
}
}
AsRef を使って self.as_ref() と書いていますが、記号が増えるのが嫌じゃなければ別に &**self でいいし、use が増えるのが嫌じゃなければ Deref でもいいです。
残るは self_var、つまり self_var が Var::Assigned()、つまり self_var が Var::Unassigned なら、&RefCell なので、参照のまま ptr::eq に突っ込んでもいいし、RefCell::as_ptr で *mut Var に変換してもよいです。
match self.as_ref() {
Ty::Var(self_var) => match *self_var.borrow() {
Var::Assigned(ref ty) => ty.contains(var),
Var::Unassigned => self_var.as_ptr() == var.as_ptr(),
},
}
従って、contains 全体では以下のようになります。
impl Ty {
fn contains(self: &RcTy>, var: &RefCellVar>) -> bool {
match self.as_ref() {
Ty::Bool => false,
Ty::Func(param, ret) => param.contains(var) || ret.contains(var),
Ty::Var(self_var) => match *self_var.borrow() {
Var::Assigned(ref ty) => ty.contains(var),
Var::Unassigned => self_var.as_ptr() == var.as_ptr(),
},
}
}
}
Unify の実装
いよいよ unify です。2 つの型
fn unify(left: &RcTy>, right: &RcTy>) -> bool {
todo!()
}
まず、Bool 同士の場合、Func 同士の場合について書くと以下のようになります。
fn unify(left: &RcTy>, right: &RcTy>) -> bool {
match (left.as_ref(), right.as_ref()) {
(Ty::Bool, Ty::Bool) => true,
(Ty::Func(left_param, left_ret), Ty::Func(right_param, right_ret)) => {
unify(left_param, right_param) && unify(left_ret, right_ret)
}
(Ty::Var(left_var), Ty::Var(right_var)) => todo!(),
(Ty::Var(left_var), _) => todo!(),
(_, Ty::Var(right_var)) => todo!(),
_ => false,
}
}
次に Var 同士、つまり
(Ty::Var(left_var), Ty::Var(right_var)) => {
if let Var::Assigned(ref left) = *left_var.borrow() {
return unify(left, right)
}
if let Var::Assigned(ref right) = *right_var.borrow() {
return unify(left, right)
}
todo!()
}
あとは、無限再帰する型が生じないように気を付けながら、代入
(Ty::Var(left_var), Ty::Var(right_var)) => {
if left_var.as_ptr() != right_var.as_ptr() {
*left_var.borrow_mut() = Var::Assigned(right.clone());
}
true
}
(Ty::Var(left_var), _) => {
if let Var::Assigned(ref left) = *left_var.borrow() {
unify(left, right)
} else if right.contains(left_var) {
false
} else {
*left_var.borrow_mut() = Var::Assigned(right.clone());
true
}
}
(_, Ty::Var(right_var)) => {
}
if let の右辺で left_var.borrow() を呼んで Ref を得ていますが、パターンマッチが失敗すると、else 節が始まる前に捨てられるようです。でないと、left_var.borrow_mut() でエラーになります。実際、Edition 2024 では動きますが、Edition 2021 に変えると RefCell already borrowed と言われて panic します。
何はともあれ、unify は実装できました。
上の unify は、どんなケースで遅くなるでしょうか。問題は、Var::Unassigned のときに
*left_var.borrow_mut() = Var::Assigned(right.clone());
としている点です。つまり、
これを防ぐには、まだ何も代入されていない各変数
これを Var::Unassigned に持たせます。
enum Var {
Assigned(RcTy>),
Unassigned(u32),
}
そして、Var::Unassigned のときにこの値を比べます。もし
*left_var.borrow_mut() = Var::Assigned(right.clone());
という代入を行っても
*right_var.borrow_mut() = Var::Assigned(left.clone());
にします。もし
*left_var.borrow_mut() = Var::Assigned(right.clone());
*right_var.borrow_mut() = Var::Unassigned();
こうすれば、
変更後の unify はこうなります：
fn unify(left: &RcTy>, right: &RcTy>) -> bool {
match (left.as_ref(), right.as_ref()) {
(Ty::Var(left_var), Ty::Var(right_var)) => {
let left_rank = match *left_var.borrow() {
Var::Assigned(ref left) => return unify(left, right),
Var::Unassigned(left_rank) => left_rank,
};
let right_rank = match *right_var.borrow() {
Var::Assigned(ref right) => return unify(left, right),
Var::Unassigned(right_rank) => right_rank,
};
if left_var.as_ptr() != right_var.as_ptr() {
match left_rank.cmp(&right_rank) {
Ordering::Greater => *right_var.borrow_mut() = Var::Assigned(left.clone()),
Ordering::Less => *left_var.borrow_mut() = Var::Assigned(right.clone()),
Ordering::Equal => {
*left_var.borrow_mut() = Var::Assigned(right.clone());
*right_var.borrow_mut() = Var::Unassigned(right_rank + 1);
}
}
}
true
}
}
}
ここまで難しそうなことをしていましたが、改めて見ると何だかすっきりしています。Rc と RefCell が分かれているおかげで、.borrow() .borrow_mut() を繰り返すこんなコードも綺麗に書けるわけですね。
以上、Rust で型推論を実装する話でした。実用的にはまだ足りない部分も多いですが、面白いな〜と思ってくれたら幸いです。
Views: 0
