👋

「作ってかんたんAlgebraic Effects」をRustに移植した

2022/12/27に公開

Haskell

Rust

idea

はじめに

Algebraic Effectsについては以下の（素晴らしい）記事（というかPDF）を読んでほしい。

上のPDFではAlgebraic Effectsを備えた言語、λeffがHaskellで実装されている。

ところで、こういうものはただ写経するのではなく、別の言語で写経（というか移植）してみるというのが理解に効果的という話がある（かもしれない）。
そこで勉強のためRustに移植した^[1]。

まだファイルを分割していなかったりエラー処理をまともにしていなかったりする^[2]が、一応オリジナルのリポジトリの例

let double = inst () in let h = handler double (val x -> x) ((x, k) -> k (k x)) in with h handle (perform double 3) + 10

が動いたので一旦の区切りとする（ちなみに上の例を評価すると23になる）。

このHaskell=>Rustでの移植で躓いたり工夫した点を記載する。

モナド

オリジナルの実装ではHaskellらしくモナドがパーサと評価で使われている。

Rustでモナドを実装する手もあるが、それは茨の道である^[3]。

パーサはRustで使われているパーサを普通に使うことにした。これは後述する。

評価に使用するモナドは状態モナドだったため、状態を引き回すことにした。

-- オリジナルの実装
eval :: Term -> Stack -> Stack -> EffectP -> Term
eval t s es = go (t, s, es)
  where
    go mod idx =
      case flip runState idx $ eval1 mod of
        ((v, [], _), _) | valuable v -> v
        (mod', idx') -> go mod' idx'

// 移植版
fn go(m: (Term, Stack, Stack), idx: EffectP) -> Term {
    match eval1((idx, m)) {
        (_, (v, s, _)) if s.is_empty() && valuable(&v) => v,
        (idx, m_) => go(m_, idx),
    }
}

fn eval(t: Term, s: Stack, es: Stack, idx: EffectP) -> Term {
    go((t, s, es), idx)
}

パーサ

オリジナルのHaskell実装ではパーサとしてParsecが使われている。しかしこれが何も分からない。正直今でも雰囲気で読んでいる。

またRustのパーサも選定にかなり時間がかかった。
当初パーサジェネレーターを使おうとして結局パーサコンビネーターのchumsky
https://github.com/zesterer/chumsky

に落ち着いたが、エラー処理に力を入れないならnomでよかったかもしれない。

ライフタイム周り

当初AST用の型で文字列を引数にとる型、例えば

data Term
  = Var String
  | Fun String Term

におけるStringなどはRustでは&strにしていた。

が、このせいでライフタイム周りがすごいことになってしまった。
特に元のHaskell実装に倣ってclosureを多用していたため

を使うなどしていた。

しかしこの方針はパースの際に苦しくなった。
そこでRustでもStringを使うように変更した。

これで困るのは、staticな文字列が（Stringで）作れないという問題である。
これはonce_cell

で実現できた。

static HOLE: Lazy<Term> = Lazy::new(|| {
    Term::Var(Var {
        term: "□".to_string(),
    })
});

おわりに

型付きも実装してみたいですね。

脚注

やり始めて3ヶ月くらいかかった ↩︎
まだfunだけパースしていない ↩︎
状態モナドなら作れそうだがモナディックパーサコンビネーターは・・・ちょっと・・・ ↩︎

はじめに

モナド

パーサ

ライフタイム周り

おわりに

Discussion