👋

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

2022/12/26に公開約2,200字

はじめに

Algebraic Effectsについては以下の(素晴らしい)記事(というかPDF)を読んでほしい。
https://nymphium.github.io/2022/09/17/作ってかんたんAlgebraic-Effects.html

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

ところで、こういうものはただ写経するのではなく、別の言語で写経(というか移植)してみるというのが理解に効果的という話がある(かもしれない)。
そこで勉強のためRustに移植した[1]
https://github.com/Catminusminus/lambda-eff

まだファイルを分割していなかったりエラー処理をまともにしていなかったりする[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を多用していたため
https://stackoverflow.com/questions/63843906/why-can-i-not-return-a-reference-from-a-closure

を使うなどしていた。

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

これで困るのは、staticな文字列が(Stringで)作れないという問題である。
これはonce_cell
https://docs.rs/once_cell/latest/once_cell/

で実現できた。

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

おわりに

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

脚注
  1. やり始めて3ヶ月くらいかかった ↩︎

  2. まだfunだけパースしていない ↩︎

  3. 状態モナドなら作れそうだがモナディックパーサコンビネーターは・・・ちょっと・・・ ↩︎

Discussion

ログインするとコメントできます