TAPLのML実装をRustでやってみるシリーズ「4章 算術式のML実装」

TAPL本(Types And Programming Language、型システム入門)の各章にある「ML実装」の例をRustにポーティングしてみます。

まずは4章の算術式です。書籍でのtype termが保持するinfoは、ソースからパージングするわけではないので略します。いらなそうなletは省きました(OCamlでの必要性は不明)。

#![feature(box_patterns)]
#![feature(box_syntax)]

#[derive(Debug,Clone)]
enum Term {
    True,
    False,
    If(Box<Term>, Box<Term>, Box<Term>),
    Zero,
    Succ(Box<Term>),
    Pred(Box<Term>),
    IsZero(Box<Term>)
}

use Term::*;

fn is_numerical(t: &Term) -> bool {
    match *t {
        Zero => true,
        Succ(box ref t1) => is_numerical(t1),
        _ => false
    }
}

fn is_val(t: &Term) -> bool {
    match *t {
        True => true,
        False => true,
        _ => is_numerical(t)
    }
}

fn eval1(t: Term) -> Term {
    match t {
        Zero => Zero,
        If(box True, box t2, _) => t2,
        If(box False, _, box t3) => t3,
        If(box t1, t2, t3) => If(box eval1(t1), t2, t3),
        Succ(box t1) => Succ(box eval1(t1)),
        Pred(box Zero) => Zero,
        Pred(box Succ(box ref t1)) if is_numerical(t1) => t1.clone(),
        Pred(box t1) => Pred(box eval1(t1)),
        IsZero(box Zero) => True,
        IsZero(box Succ(box ref t1)) if is_numerical(t1) => False,
        IsZero(box t1) => IsZero(box eval1(t1)),
        _ => panic!()
    }
}

fn main() {
    assert_eq!(format!("{:?}", True), "True");
    assert_eq!(is_numerical(&True), false);
    assert_eq!(is_numerical(&Zero), true);
    assert_eq!(is_val(&True), true);
    assert_eq!(is_val(&If(box True,box True,box False)), false);
    assert_eq!(format!("{:?}", eval1(If(box True,box True,box False))), "True");
    assert_eq!(format!("{:?}", eval1(If(box False,box True,box False))), "False");
    assert_eq!(format!("{:?}", eval1(If(box IsZero(box Zero), box True, box False))), "If(True, True, False)");
    assert_eq!(format!("{:?}", eval1(Succ(box Succ(box Zero)))), "Succ(Succ(Zero))");
    assert_eq!(format!("{:?}", eval1(Pred(box Zero))), "Zero");
    assert_eq!(format!("{:?}", eval1(Pred(box Succ(box Zero)))), "Zero");
    assert_eq!(format!("{:?}", eval1(Pred(box Succ(box Zero)))), "Zero");
    assert_eq!(format!("{:?}", eval1(IsZero(box Zero))), "True");
    assert_eq!(format!("{:?}", eval1(IsZero(box Succ(box Zero)))), "False");
    assert_eq!(format!("{:?}", eval1(IsZero(box Pred(box Succ(box Zero))))), "IsZero(Zero)");
}

• boxを除けば、ほぼOCamlと同等。GCの無い言語としては、良い線に行っていると思う。
• 実行メモリモデルがまさにC/C++なので、参照と値、cloneを完璧に適切に使いわける必要がある。OCaml版では全く意識する必要がない点である。この区別をてきとうにやっておけばうまく動く、ということはない。ここがGC言語との違い。
  • もし完璧に適切に使いわけられないならば、それはコンパイルが通らないことを意味する。やりとげてみると、目から鱗の自然な形なのだが、最初わからないとつらい。根性しかない。
  • 今回の場合、match式の背後にある「暗黙の代入」、すなわちマッチ対象から各パターン、ガード、枝の本体に分配されるための代入が、それぞれムーブセマンティクスなのか、ownershipをとらない参照(&mutではない&)なのか、boxなのかrefなのかbox refなのか、そのすべてが正しく的確に指定されている必要がある。matchが展開された結果における暗黙の代入の様子を想像する力が問われる。どっかにドキュメントありますかね…。
  • Rustにおけるデータ管理は、「値」が基本になる、というのはたぶん間違いない。しかし、リアルワールドでは「値だけ」でやっていくことはできない。borrwingとclone()を適宜組合せる必要がある。