この記事は言語実装Advent Calendar 2020 25日目の記事です。（2022-11-06: 記事の内容を追記していますが、この記事の結論としては「似たようなものは作れるが、完全体にはならない」です）
- 前提知識
- 従来のエミュレーション方法
- Generic Associated Types を用いたエミュレーション（new!）
- Generic Associated Types（GATs）とは何か
- 追記（2022-11-06）
- リポジトリ
- 参考文献
モナドに関する話題が言語実装アドベントカレンダーの範疇に入るのかわかっていませんが*1、プログラミング言語がお好きな方はきっとモナドもお好きだろう…ということで、Rust におけるモナドの扱いについて記事にしたいと思います。
この記事では、Rust を使って
- モナドを実装してみる。
- do 記法を実装してみる。
ところまでやってみました。後半で、GATs と呼ばれる Rust の nightly に入った機能に関して少し細く説明を加えています。
なおこの記事では、モナドとは何かという話はあまり触れていません。
さらに執筆時間*2と記事の都合上、Rust 言語の細かい文法に関する解説もとくに行っていません🙇♀️ 登場してくる文法には、適宜注釈でコメントをできるかぎり付与するようにしましたが、不十分かもしれません。
今回の記事は、ずいぶん前に登壇した内容のアップデートです。この発表以降にさらに Rust の言語機能にアップデートがあり、その内容を使ってモナドを実装してみるという記事です。
Rust でもモナドは実装できるのか？ - Speaker Deck
前提知識
解説を加えてしまうと記事の長さがとても大変なことになってしまうので今回は省かせていただきますが、いくつか詳しく解説された記事があるのでそちらをリンクさせていただきます。
高階カインド型
まず高階カインド型そのものについては、Scala による説明ですが、下記の記事が直感的でわかりやすいです。
また、なぜ高階カインド型が必要とされるのかについては、この記事がわかりやすいです。
モナド
モナドというのはいくつか説明の仕方があるかとは思いますが、
個人的にはこの記事の説明が丁寧でわかりやすいかなと思いました。
従来のエミュレーション方法
従来のやり方では、HKT<T> と呼ばれる高階カインド型を表現するトレイトを用意し、HKT トレイトに関連型を2つ（高階を示すものと、高階の中身の型を示すもの）用意すれば、完全ではないものの近い形でエミュレーションできました。たとえば、従来のやり方ではモナドは下記のようにエミュレーションできます。
trait HKT<T> { type C; type H; } trait Functor<U>: HKT<U> { fn map<F>(self, f: F) -> Self::H where F: Fn(Self::C) -> U; } trait Monad<U>: Functor<U> { fn pure(self, m: U) -> Self::H; fn bind<F>(self, f: F) -> Self::H where F: Fn(Self::C) -> Self::H; }
単純なデータ構造を例にとって、実装をしてみます。たとえば Id モナド*3を実装してみると、
struct Id<T>(T); // 高階カインドに関するエミュレーションをここで行う。 impl<T, U> HKT<U> for Id<T> { type C = T; type H = Id<U>; } // ファンクタを定義する impl<T, U> Functor<U> for Id<T> { fn map<F>(self, f: F) -> Self::H where F: Fn(Self::C) -> U, { Id(f(self.0)) } } // モナドを定義する impl<T, U> Monad<U> for Id<T> { fn pure(self, m: U) -> Id<U> { Id(m) } fn bind<F>(self, f: F) -> Id<U> where F: Fn(T) -> Id<U>, { f(self.0) } }
といった形で、一応型パズルは解け、実際に動かしてみるときちんとそれらしい動きをしていることがわかります。残りは発表資料をご覧ください。
Generic Associated Types を用いたエミュレーション（new!）
ここからが本題です。
Rust nightly 1.50 から入った Generic Associated Types（解説は後ほど）という機能を使うと、従来の HKT トレイトを使う場合と比べ、かなり実装をきれいにすることができます。
1つ1つ型クラスを定義していきます。
型クラスを定義する
Functor を用意する
まずは Functor を用意します。Functor は変換処理の一般化です。
この Functor に Functor の型パラメータとなる A を関連型 *4 でもたせ、高階カインド型そのものを Lifted<B> という形でもたせます。Lifted は Functor を実装してある必要があるという制約も付与しています。ここに後ほど具体的な型が入ってくることになります。
pub trait Functor { type A; type Lifted<B>: Functor; fn map<F, B>(self, f: F) -> Self::Lifted<B> where F: FnMut(Self::A) -> B; }
そして、Lifted<B> の部分に、いわゆる Generic Associated Types（GATs）が使用されています。GATs については後ほど解説します。現在の stable Rust においては、このように Lifted という関連型に型パラメータを付与することはできません。
Pointed を用意する
続いて Pointed を用意します。Pointed は pure 関数の一般化です。この関数は、元の型をモナドの文脈の型に変換する機能を持ちます。
Pointed は Functor のトレイト境界をもちます。実装先が、Functor も実装してある必要があります。
pub trait Pointed: Functor { fn pure(t: Self::A) -> Self::Lifted<Self::A>; }
Applicative を用意する
続いて Applicative を用意します。Applicative は関数適用の一般化です。apply という関数を持ちます。トレイト境界に Pointed を持ちます。
pub trait Applicative: Pointed { fn apply<F, B, C>(self, b: Self::Lifted<B>, f: F) -> Self::Lifted<C> where F: FnMut(Self::A, B) -> C; }
Monad を用意する
最後に Monad を用意します。Monad は手続きの結合の一般化です。bind という関数を持ちます。トレイト境界に Applicative を持ちます。
pub trait Monad: Applicative { fn bind<B, F>(self, f: F) -> Self::Lifted<B> where F: FnMut(Self::A) -> Self::Lifted<B>; }
いくつか型を実装していく
ここまで用意できたところで、実際にいくつか型を実装していきましょう。まずは最も単純な例として、先ほどもご紹介した Id モナドを実装してみます。
pub struct Id<M>(pub M); impl<A> Monad for Id<A> { fn bind<B, F>(self, mut f: F) -> Id<B> where F: FnMut(A) -> Id<B>, { f(self.0) } } impl<A> Pointed for Id<A> { fn pure(t: A) -> Id<A> { Id(t) } } impl<A> Applicative for Id<A> { fn apply<F, B, C>(self, b: Id<B>, mut f: F) -> Id<C> where F: FnMut(A, B) -> C, { Id(f(self.0, b.0)) } } impl<A> Functor for Id<A> { type A = A; type Lifted<B> = Id<B>; fn map<F, B>(self, mut f: F) -> Id<B> where F: FnMut(A) -> B, { Id(f(self.0)) } }
また、Rust にすでに存在する Option や Result も、一応今回用意したモナドにすることができます。*5
まずは Option モナドを用意してみます。
impl<A> Monad for Option<A> { fn bind<B, F>(self, mut f: F) -> Option<B> where F: FnMut(A) -> Option<B>, { self.and_then(f) } } impl<A> Pointed for Option<A> { fn pure(t: A) -> Option<A> { Some(t) } } impl<A> Applicative for Option<A> { fn apply<F, B, C>(self, b: Option<B>, mut f: F) -> Option<C> where F: FnMut(A, B) -> C, { let a = self?; let b = b?; Some(f(a, b)) } } impl<A> Functor for Option<A> { type A = A; type Lifted<B> = Option<B>; fn map<F, B>(self, mut f: F) -> Option<B> where F: FnMut(A) -> B, { self.map(f) } }
また、Result モナドは今回は Ok 側にバイアスをもたせた形で用意してみました。
impl<A, E> Monad for Result<A, E> { fn bind<B, F>(self, f: F) -> Result<B, E> where F: FnMut(A) -> Result<B, E>, { self.and_then(f) } } impl<A, E> Pointed for Result<A, E> { fn pure(t: A) -> Result<A, E> { Ok(t) } } impl<A, E> Applicative for Result<A, E> { fn apply<F, B, C>(self, b: Result<B, E>, mut f: F) -> Result<C, E> where F: FnMut(A, B) -> C, { let a = self?; let b = b?; Ok(f(a, b)) } } impl<A, E> Functor for Result<A, E> { type A = A; type Lifted<B> = Result<B, E>; fn map<F, B>(self, mut f: F) -> Result<B, E> where F: FnMut(A) -> B, { self.map(f) } }
現状実装できないもの
ただし、関数型プログラミングにおいて利用する道具が完全に実装できるというわけではありません。たとえば、
といった内容が、この記事にて報告されていました。
do 記法
Haskell には do 記法、Scala には for-yield と呼ばれる構文があり、これらを用いることで次のように bind（あるいは flatMap）がいくつも重なってしまう現象を回避できたりします。
// Rust による例 Option::pure(...).bind(|o| return_option_function(o).bind(|p| return_option_function(p))
モナドの真骨頂は、こうした do 記法や for-yield などとともに利用するところにあると思うのですが、Rust にはそうした専用の構文はありません。
そこで、Rust のマクロという機能を用いて do 記法を実装しました。do は Rust においては予約語になっており使用できないので、monad-do から取って mdo というマクロを作りました。
macro_rules! mdo { ($i:ident <- $e:expr; $($t:tt)*) => { $e.bind(move |$i| mdo!($($t)*)) }; ($e:expr; $($t:tt)*) => { $e.bind(move |()| mdo!($($t)*)) }; (ret $e:expr) => { $e }; }
少し Rust のマクロに関して補足を入れておくと、
$i, $e, $t: マクロ内における変数。$(...)*の*: 0回以上の繰り返しを意味します。:ident: これはいわゆる識別子がやってくることを示します。:expr: これはいわゆる式がやってくることを示します。:tt: 何か単一のトークン木がやってくることを示します。
内部で軽い構文解析を行い、<- の前後を解析して式なのか識別子なのか、それ以降に続く別のトークン木なのかを見分けます。その後、取り出せた式と識別子を使ってモナドに紐づけて実装されている（はずの） bind を呼び出し、残ったトークン木を更に再帰的に mdo! マクロにかける、ということをしています。また、結果は ret と書いた後ろの式を返します。
これを用いることで、
mdo! {
a <- {何かモナドを作る};
b <- {何かモナドを作る};
ret result(a +b) // 何か結果を返す
}
といった記法が可能になります。
実際 Rust でこれを使用してみると、下記のように記述可能になり、テストを通すことができました。
mod test_do { use crate::data::option::*; use crate::{applicative::Applicative, functor::Functor, functor::Pointed, monad::Monad}; #[test] fn test_do_notation() { let actual = mdo!{ x <- Option::pure(1); y <- Option::pure(2); ret Option::pure(x + y) // Some(3) が返るはず }; assert_eq!(actual, Some(3)); } }
便利ですね。
Generic Associated Types（GATs）とは何か
ここからは言語実装やプログラミング言語全般の話というより Rust 特有の事情の話になってしまい大変恐縮なのですが、GATs が一体何なのか、どういう使い道があるのかについて RFC を読みながら簡単にまとめておきたいと思います。
GATs というのは先ほども軽く触れたとおり、関連型に何かしらの型パラメータ（A や T みたいなもの）をもたせることができる機能です。Rust にいわゆる高階カインド型を導入するための機能です。
Rust の場合は、他の言語でもあるような型パラメータ以外にもライフタイム注釈*7をこの位置に入れることができます。つまり、型パラメータの位置に入るのは A というような型情報と、もうひとつは 'a というライフタイム注釈が来ることになります。GATs はこれら2つを関連型で扱えるようにするための機能です。
下記は RFC から拝借してきたコードですが、ライフタイムに関しては次のような記述が GATs で行えるようになります。これは Rust を書いていると多々直面する内容で、ユーザーが求めていた機能でもありました。
trait StreamingIterator { type Item<'a>; } impl<T> StreamingIterator for StreamIterMut<T> { type Item<'a> = &'a mut [T]; ... }
また、型パラメータを関連型にもたせる側では、たとえば下記のような記述が GATs を用いて行えるようになります。Rust には Rc や Box などのスマートポインタがいくつか存在しますが、これらは型パラメータを引数に取ります。そうしたポインタを関連型の具象実装側を切り替えることで切り替えたい場合に、GATs が役に立ちます。
trait PointerFamily { type Pointer<T>: Deref<Target = T>; fn new<T>(value: T) -> Self::Pointer<T>; } struct ArcFamily; impl PointerFamily for ArcFamily { type Pointer<T> = Arc<T>; fn new<T>(value: T) -> Self::Pointer<T> { Arc::new(value) } } struct RcFamily; impl PointerFamily for RcFamily { type Pointer<T> = Rc<T>; fn new<T>(value: T) -> Self::Pointer<T> { Rc::new(value) } } struct Foo<P: PointerFamily> { bar: P::Pointer<String>, }
RFC によると、GATs が入ったからと言ってモナドを完全に実装できるようになるというわけではないと注意書きがなされています。私がモナドを実装することに関してそこまで深い知識があるわけではないので、一体どういったポイントが足りなくてそうなっているのかは今後の探求の課題だなと思いました。
追記（2022-11-06）
さて、この記事を書いてから2年が経ち、いくつかの検証記事やそもそも GATs が stable になるといったアップデートがありました。この件を少し補足しておきます。
まず結論から行くと、
私がモナドを実装することに関してそこまで深い知識があるわけではないので、一体どういったポイントが足りなくてそうなっているのかは今後の探求の課題だなと思いました。
これに足りない部分を検証している記事があります。
Monad であれば Applicative を Monad から定義できるはずですが、どうやら難しいようです。具体的には map2 の実装時に返しの型を一つに定められなくなる、という問題があるようです。
GATs がいわゆる関連型である都合、型をひとつに同定することが難しく、たとえば、Option 型に対する Monad を実装しているにもかかわらず Result 型を指定できてしまいます。言語機能的に、関連型についた型パラメータがきちんと消費されているかは見ていないようで、これも実装できないポイントの一つです。
impl<A> Monad<A> for Option<A> { type A = A; type This<B> = Result<A, Error>; }
そもそも Applicative を Monad で定義できない問題もありますし、運用に「関連型に必ず正しい型を入れる必要がある」といったような紳士協定を結ぶ必要があるので普段使いは難しそうですね。後者の問題はマクロを使って解決できそうではありますが、試していないのでわかりません。
リポジトリ
まだいろいろ実験中ですが、リポジトリはこちらにあります。
参考文献
- GATs を用いたモナドの実装はこちらの記事で紹介されていた内容を参考に実装しています: Monads and GATs in nightly Rust
- GATs の RFC はこちら: rfcs/1598-generic_associated_types.md at master · rust-lang/rfcs · GitHub
*1:カレンダーに登録してみたものの、プログラミング言語そのものに関わりそうな話題としての持ちネタがこれくらいしかありませんでした🙏
*2:12/24に書き始めたのが間違いだった。もう少し時間を取るべきでしたね。
*3:恒等モナド。単に 1i32 のような値をモナド文脈の中に持ち込める存在です。これを用いるとたとえば、Id(1).map(|i| i + 1) = Id(2) のような計算を行うことができます。
*4:Rust ではトレイト内部に type という他の言語でも見られるような型エイリアスをつけることができます。これは関連型と呼ばれ、Rust を書いていると何度も登場してくる概念になります。高階カインド型のエミュレーションは、この関連型を用いて行うことになります。後ほど解説しますが、現状の stable Rust ではこの関連型に型パラメータを付与することはできません。が、nightly で型パラメータを付与することが可能になり、より関連型の一般化をしやすくなりました。
*5:Rust では実際のところ、これらの型は Iterator として一般化されているのであまりやる意味はないのですが…
*6:ただ、これは直せそうな気がしました。関連型のうちどれを使用すればいいかをきちんと明示的に書いてあげる必要があるかも？
*7:Rust にはダングリングポインタを防止するための仕組みとしてライフタイムという概念が存在します。このライフタイムというのは、ユーザーがライフタイム注釈を個別に指定してライフタイムを明示的に書くこともできるようになっています。ライフタイム注釈というのは 'a というようにシングルクオートで始まる形で、通常の型情報と同じ位置（<> 内）に入れて書きます。
