Rustを使ってスケーラブルなプログラムを書く方法

この記事はRust Advent Calendar 2021の12/24日の記事です。

仕事ではScalaを使っていますが、趣味のプログラミングではRustで書いたものが増えました。Rustは楽しいですね。

今回は、Rustでオブジェクト指向プログラミングに関数型デザインを導入することで、スケーラブルなプログラムを書く方法(スケーラブル・プログラミング)について書きます。

「スケーラブル・プログラミング」といえばScalaです。Scalaの「スケーラブル」という言葉には「小さいプログラムも大規模なプログラムも同じ概念で記述できるべきである」という、柔軟性や拡張性を重視した設計の意図が込められています。それを実現するために必要なものは、オブジェクト指向と関数型を組み合わせたマルチパラダイムな設計です。

Scalaはマルチパラダイム言語の先駆者(今も先頭を走り続けています)ですが、他の言語にも広がっています。マルチパラダイム言語の成果は、JavaにScalaが持つ言語機能が取り込まれたり、Rustなどのマルチパラダイム言語の台頭、という形で現れていると思います*1。そういう意味では、スケーラブル・プログラミングは他の言語にも適用可能な時代になっていると考えています。

そして、話を元に戻す…。今回の記事では、その「スケーラブル」という概念を、関数型プログラミングのテクニックを使ってRustに取り入れてみたら、どうなるかを簡単に（！？）説明してみたいと思います。簡単にといいつつ、大作になってしまいました…。*2

想定読者

少なくともRustを「完全に理解した*3」方でないと、おすすめできない記事になっています。

ちなみに、Scalaというキーワードは少しでてきますが、Scala自体の説明はありません。

Scalaを理解しないとRustが使えないということではありません。そのあたりは誤解がないように…。

モナドなどの圏論の話もありませんので、安心してください。

という予防線を張っておき、どんどん関数型な世界に入っていく。

Rustは関数型言語かオブジェクト指向言語か

いきなり蛇足…。「Rustは関数型言語なの？オブジェクト指向言語なの？」という疑問を持つ方は少なくないと思います。

Rustは関数型言語か

Rustは、関数型言語ではなく命令型言語だと言う方が多いです。関数型言語の定義はこんなふうに書いてある。

関数型プログラミング言語（英: functional programming language）とは、関数型プログラミングを推奨しているプログラミング言語である[3]。略して関数型言語（英: functional language）ともいう[4]。

関数型プログラミング - Wikipedia

この定義から考えるとRustは「関数型言語である」とは言えないでしょう。とはいえ、関数型プログラミングに関する機能は取り込まれています。関数型言語かどうかはさておき、関数型プログラミングはできます。

関数型言語の機能：イテレータとクロージャ - The Rust Programming Language 日本語版

Rustはオブジェクト指向言語か

これと似たような話で、Rustはオブジェクト指向言語か？という論争もあります。Rustはクラス・継承・例外・nullがないので、Javaのような既存のオブジェクト指向言語とは一線を画しますが、オブジェクト指向プログラミングはできます(個人の考え)。どちらかというと、C言語でのオブジェクト指向プログラミングに使い方が似ています。

• オブジェクト指向言語の特徴 - The Rust Programming Language 日本語版
• Rustがオブジェクト指向型言語ではないのとその理由 - なんか考えてることとか

Rustもマルチパラダイム言語

Rustは、手続き型プログラミング、オブジェクト指向プログラミング、関数型プログラミングをサポートする、マルチパラダイム言語です。

Rustはマルチパラダイムプログラミング言語であり、手続き型プログラミング、オブジェクト指向プログラミング、関数型プログラミングなどの実装手法をサポートしている。基本的な制御構文はC言語に似ているが、その多くが式（expression）であるという点においてはML言語に似ている。コンパイル基盤にMIRとLLVMを用いており[10]、実行時速度性能はC言語と同等程度である[11]。強力な型システムとリソース管理の仕組みにより、メモリ安全性が保証されている。

Rust (プログラミング言語) - Wikipedia

「関数型言語か」「オブジェクト指向言語か」という既存のステレオタイプに当てはめようとしても無理があると思います。「あれか・これか」ではなく「あれも・これも」の視点で使い方を考えると生産的ではないでしょうか。

Scala関数型デザイン＆プログラミング

本題に戻ります。

この記事では、以下の書籍(以下 FP in Scala本)中で紹介されるテクニックを、Rustへ輸入する具体的な方法を書いています。

「Rustなんもわからん」もしくは「Rustチョットデキル」の方には考えてみてほしいテーマです。

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

当然、コード例はScalaで説明されているわけですが、それをRustに脳内トランスパイルして学び直しました。

この書籍を参考にして作ったもの

この本の中盤の「Part II 関数型デザインとコンビネータライブラリ」という部分では、「プロパティベースのテスト」と「パーサコンビネータ」の解説があります。それに沿って作ったRustの実装は以下です。ほとんど同じ機能かそれ以上の機能を提供しています。

• GitHub - j5ik2o/prop-check-rs: A Rust crate for property-based testing.
• GitHub - j5ik2o/oni-comb-rs: A Rust crate for LL(k) parser combinators.

今回「パーサコンビネータ」を通して関数型デザインの考え方を紹介したいので「プロパティベースのテスト」は割愛します。

パーサコンビネータ

パーサーとは構文解析器のことです。

パーサーは自前で実装せずにライブラリを使うことが一般的だと思います。そのパーサライブラリには、パーサージェネレータとパーサコンビネータの大まかに二つの種類があります。

パーサージェネレータ

全く実用性はありませんが、過去にJavaで四則演算だけができる言語を作りましたが、JavaCCというパーサージェネレータを使いました。パーサージェネレータはその名の通り、特殊な記法で記述されたルールに基づき、パーサーを生成してくれるツールです。

数値がBigDecimal型な計算式言語を作ってみた - かとじゅんの技術日誌

パーサーコンビネータ

今回は、パーサーをジェネレートする必要のない、パーサコンビネータを紹介します。FP in Scala本によると以下のように説明されています。

パーサーコンビネータライブラリのパーサーは、どこにでもあるファーストクラスの値にすぎません。解析ロジックを再利用するのはいとも簡単なことであり、プログラミング言語以外に外部ツールの類いはいっさい必要ありません。

今回実装したパーサコンビネータでは、空白やタブや改行の連続を解析して破棄するパーサは以下のように簡単に書けます。elm_of(" \t\r\n")は空白やタブや改行の連続を解析するパーサーを返す関数です。of_many0()はそれが0個以上連続することを意味し、discard()は解析に成功すると解析結果を破棄することを意味します。of_many0, discardはパーサーと組み合わせて利用するので、コンビネータ*4と呼ばれます。

fn space<'a>() -> Parser<'a, char, ()> {
  elm_of(" \t\r\n").of_many0().discard()
}

読み込んだ文字や文字列がパターンに合致するかなどの手続きのHowを記述するのではなく、パーサーコンビネータでは、その構文が何か(What)をそのままコードとして表現するスタイルになります*5。

なぜパーサコンビネータライブラリを自作したのか

Starが多いRust製のパーサーライブラリは以下です。

• https://github.com/Geal/nom
• https://github.com/Marwes/combine
• https://github.com/zesterer/chumsky
• https://github.com/J-F-Liu/pom

どれもそれなりに使えます。

nomのインターフェイスは扱いづらい

nomを使ってURIのパーサーを実装しましたが、関数の呼びだしが g→h→f のような解析順であっても、f(h(g()))のような入れ子になります。直感的にコードを記述できないです。

uri-rs/ipv6_address_parsers.rs at main · j5ik2o/uri-rs · GitHub

構文ルールに合わせて、左から順番にコードが読めないのはつらい…。

pub(crate) fn ls32(i: Elms) -> UResult<Elms, String> {
  context(
    "ls32",
    alt((
      map(
        tuple((h16, preceded(complete::char(':'), h16))),
        |(c1, c2)| [c1, c2].join(":"),
      ),
      ipv4_address_parsers::ipv4_address,
    )),
  )(i)
}

pomは書きやすく読み易い

一方でpomは構文ルールをそのままメソッドチェーンで記述できるので、構文ルールどおりに書きやすいし読みやすい*6。pomでは、g() + h() + f() のように直感的に記述できます。

たとえば、CROND文字列の分を解析するパーサーは以下のように定義できます。

これは入力としてu8なのでバイト列を解析するパーサーの例です。pomの方がnomより読みやすいと思います。one_ofは指定した要素のうちいずかにマッチするという意味です。symは単一の要素にマッチするという意味です。

one_of(b"12345")という数値の羅列ではなく、one_of('1', '5')のようにもう少しすっきり書けないのか…というのはありますが、pomより読みいやすいと思います。

fn min_digit<'a>() -> Parser<'a, u8, Expr> {
  (one_of(b"12345") + one_of(b"0123456789")).map(|(e1, e2)| ValueExpr((e1 - 48) * 10 + e2 - 48))
    | (sym(b'0') * one_of(b"0123456789")).map(|e| ValueExpr(e - 48))
    | (one_of(b"0123456789")).map(|e| ValueExpr(e - 48))
}

そして車輪の再発明へ

ツールを作るだけならpomを使えばよかったのですが、以下の理由で自作(車輪の再発明)することにしました。

• 関数型デザインを学ぶため
• pomにない機能を実装するため

作ったものは鬼昆布(oni-comb-rs)

作ったものは鬼昆布(oni-comb-rs)

github.com

鬼昆布は非常に濃いダシがとれる昆布です。生産量が少なく、市場に滅多に出回らない非常に珍しい昆布です。

濃いダシが出るように設計しました(謎

鬼昆布(oni-comb-rs)の使い方

例えば、1+2という文字列*7を解析したい場合は、以下のように記述できます。

elm_digitは0から9までの要素にマッチすると成功するパーサーで、elmは引数の要素にマッチすると成功するパーサーです。

// 入力値
let input = "1+2".chars().collect::<Vec<char>>();

// パーサーの構築
let parser: Parser<char, ((char, char), char)> = elm_digit() + elm('+') + elm_digit();

// 解析の実行
let parse_result: ParseResult<char, ((char, char), char)> = parser.parse(&input);

// 解析結果の取得
let result: ((char, char), char) = parse_result.success().unwrap(); // ((1, +), 2)

パーサーどうしを合成することによって、より複雑な構文を解析するパーサーを構築できます。

charのタプルを返されてもあまり実用的でないので、以下のようにAddExprなどの構造体に変換させることが多いです。

let parser: Parser<char, AddExpr> = (elm_digit() - elm('+') + elm_digit()).map(|(a, b)| AddExpr(a, b));

鬼昆布(oni-comb-rs)を使って何を作ったか

このライブラリを使っていろいろつくりましたが、いくつか紹介します。

URIパーサー

わかりやすい例としてはURIパーサです。今どき、URIパーサーなんて作らないとは思いますが…。気に入ったクレートがなかったのでRFCを参考に実装しました。

oni-comb-rs/uri at main · j5ik2o/oni-comb-rs · GitHub

例えば、URI仕様の一部であるIPv6アドレスのls32は以下のように書けます。

fn ls32<'a>() -> Parser<'a, char, LS32> {
  let p1 = (h16() - elm(':') + h16()).map(|(a, b)| LS32::Ls32(a, b));
  let p2 = ip_v4_address().map(|a| LS32::Ipv4Address(a));
  p1.attempt() | p2
}

h16もパーサーです。Aの次にBというパターンの場合はa + bと記述できます(連言といいます)。a - b + cのように-を使うとbの結果だけ捨てられます。mapは解析に成功した結果が関数へ渡され、解析結果を別の型・値に変換できます。p1.attempt() | p2のattempt()はp1が解析に失敗しても解析を中断しないという意味になります。|は選言といって、AまたはBというパターンの場合で使えます。Parser型はParser<'a, 入力要素型, 解析結果型>です。

JSONパーサー

JSONパーサーは以下に90行足らずで実装できます*8。

oni-comb-rs/json_char.rs at main · j5ik2o/oni-comb-rs · GitHub

配列を解析する処理は以下のように簡潔に記述できます。

valueはJSONに含まれる値(文字列, 数値, 二値, nullなど)を解析するパーサーです。lazyはパーサを返す関数を引数に取り遅延評価します。これはパーサーの初期化処理が循環し、スタックがあふれしてしまうことを回避するための工夫です。of_many0_sepメソッドはselfをデリミタありで0回以上の出現を解析するコンビネータです。この例では、value ,の繰り返しが0回以上という意味になります。解析結果はVec型になります。surroundは引数の順序どおりにパーサーを評価しますが、解析に成功すると第一引数と第三引数のパーサーの結果を捨てます。

fn array<'a>() -> Parser<'a, char, Vec<JsonValue>> {
  let elems = lazy(value).of_many0_sep(space() * elm_ref(',') - space());
  surround(elm_ref('[') - space(), elems, space() * elm_ref(']'))
}

Toys言語

そして、@kmizuさんによる、WEB+DB PRESS vol.125の特集記事のToys言語に興味を持ちました。ちょっとしたミニ・プログラミング言語を作ってみようという企画です。

gihyo.jp

具体的な実装コードはこちら。

GitHub - kmizu/toys: A toy programming language to learn how to design and implement programming languages

Rust版の実装

特集記事の実装はJavaで実装されていましたが、Rustで実装しようと考えました。oni-comb-rsを使って。

詳しく説明しませんが、Rust版の実装コードはこちら。

oni-comb-rs/toys at main · j5ik2o/oni-comb-rs · GitHub

パーサー自体の定義は320行ぐらいでした。実用性は全然ないですが、FizzBuzzを書くことができます。パーサーを実装するよりインタプリタの実装のほうが面白かったです。

fn main() {
  let source = r#"
    fn fizz_buzz(i) {
      if ((i % 3 == 0) && (i % 5 == 0)) {
        println("FizzBuzz");
      } else if (i % 3 == 0) {
        println("Fizz");
      } else if (i % 5 == 0) {
        println("Buzz");
      } else {
        println(i);
      }
    }
    fn main() {
      println("----");
      for (i in 1 to 100) {
        fizz_buzz(i);
      }
      println("----");
    }
    "#;
  let input = source.chars().collect::<Vec<_>>();
  let result = program().parse(&input).to_result().unwrap();
  println!("{:?}", result);
  Interpreter::new().call_main(result);
}

他のRust版の実装

他にもnomやcombineを使った実装があります。ご参考までに。

• https://github.com/pione30/toysrust
  • nomによる実装
• https://github.com/yuk1ty/toy-lang
  • combineによる実装

どうやって設計したか

やっとここからが本題。

代数的設計

今回の実装は、代数的設計というものを重視しています。

FP in Scala本では、代数は以下のように説明されています。

代数とは、一つ以上のデータ型を操作する関数の集まりと、そうした関数の間の関係を指定する一連の法則のことです。

つまり、代数とは関数とその関数を合成する法則のことです。この考え方をうまく使うと、スケーラブルなプログラミングができます。

わかるようなわからないような…コードをみたほうが早いのですね。実装コードの抜粋を説明します。

要素(文字)を解析するパーサー

最初に設計した関数は要素(文字)を解析するパーサーを返すelm_pred_ref関数です*9。パーサーを生成するファクトリです。このtraitは要素を解析するパーサーを返す関数を実装します。数値文字列や小文字を解析するパーサーを返す関数も提供されます。elm_pred_ref関数はfがtrueを返すとき、解析に成功し入力の文字への参照を返すパーサーを返します。

ちなみに、関数名のrefというサフィックスは解析結果への参照を返すパーサと返すという意味で、refがついてない関数を利用すると実体の値を返すので複製(Clone)が生じます。refの付いた関数を使うことで、できるだけCloneを遅延させたり最適化させたりできます。

element_parsers.rs

pub trait ElementParsers: Parsers {
// ...
  fn elm_pred_ref<'a, I, F>(f: F) -> Self::P<'a, I, &'a I>
    where
      F: Fn(&I) -> bool + 'a,
      I: Element + PartialEq + 'a;
// ...
// Self::Pは`Parsers`トレイトで定義されているパーサー型のエイリアス
}

このメソッドは内部のParsersImplに実装されており、外部には同名のelm_pred_pref関数で公開されます。

lib.rs

pub fn elm_pred_ref<'a, I, F>(f: F) -> Parser<'a, I, &'a I>
  where
    F: Fn(&I) -> bool + 'a,
    I: Element + PartialEq + 'a, {
    ParsersImpl::elm_pred_ref(f)
  }

使い方は以下のようになります。特に複雑さはないと思います。

let text: &str = "x";
let input: Vec<char> = text.chars().collect::<Vec<_>>();

let parser: Parser<char, &char> = elm_pred_ref(|c| *c == 'x');

let result: ParseResult<char, &char> = parser.parse(&input);

assert!(result.is_success());
assert_eq!(result.success().unwrap(), &input[0]);

文字を解析するだけなら関数より文字自体を指定したほうが楽なので、以下のメソッドも定義します。

element_parsers.rs

pub trait ElementParsers: Parsers {
// ...
  fn elm_ref<'a, I>(element: I) -> Self::P<'a, I, &'a I>
    where
      I: Element + PartialEq + 'a, {
      Self::elm_pred_ref(move |actual| *actual == element)
    }
// ...
}

lib.rs

pub fn elm_ref<'a, I>(element: I) -> Parser<'a, I, &'a I>
where
  I: Element + PartialEq + 'a, {
  ParsersImpl::elm_ref(element)
}

// ...
let parser: Parser<char, &char> = elm_ref('x');
// ...

ちなみに文字と仮定して説明しましたが、要素はI型なので文字(char)以外にバイト(u8)でも扱えます。

orパーサー

代数的設計の真骨頂は、このあたりから垣間見えます。

parser1またはparser2の選言を行うパーサーを返すor関数は以下のようにしました。

operator_parsers.rs

pub trait OperatorParsers: Parsers {
// ...
  fn or<'a, I, A>(parser1: Self::P<'a, I, A>, parser2: Self::P<'a, I, A>) -> Self::P<'a, I, A>
    where
      A: Debug + 'a;
// ...
}

これをそのまま使うと以下のようになります。

let p3: Parser<char, &char> = or(p1, p2);
let p6: Parser<char, &char> = or(or(p4, p5), p3);
// ...

読み書きしにくい理由は前述したとおりです。これを以下のように変形します。

let p3: Parser<char, &char> = p1.or(p2);
let p6: Parser<char, &char> = p4.or(p5).or(p3);
// ...

絶対こっちのがほうが読みやすいです。

さらに演算子を再定義して読みやすくします*10。

let p3: Parser<char, &char> = p1 | p2;
let p6: Parser<char, &char> = p4 | p5 | p3;
// ...

第一引数をselfに置き換えたトレイトも提供して内部でOperatorParsers#orを呼ぶようにします。

operator_parser.rs

pub trait OperatorParser<'a>: ParserRunner<'a> {
// ...
  fn or(self, other: Self::P<'a, Self::Input, Self::Output>) -> Self::P<'a, Self::Input, Self::Output>
    where
      Self::Output: Debug + 'a;
// ...

}

さらにRustの演算子再定義の仕組みを使ってOperatorParser#orを呼びようにします。

bitor_impl.rs

impl<'a, I, A> BitOr for Parser<'a, I, A>
where
  A: Debug + 'a,
{
  type Output = Self;

  fn bitor(self, rhs: Parser<'a, I, A>) -> Self::Output {
    self.or(rhs)
  }
}

and_thenパーサー

parser1の次にparser2という解析を行うパーサーも以下のように定義されます。and_then関数はparser1とparser2の解析結果をタプルで返すパーサーが返します。

operator_parsers.rs

pub trait OperatorParsers: Parsers {
// ...
  fn and_then<'a, I, A, B>(parser1: Self::P<'a, I, A>, parser2: Self::P<'a, I, B>) -> Self::P<'a, I, (A, B)>
  where
    A: Clone + Debug + 'a,
    B: Clone + Debug + 'a;
// ...
}

こちらもorのときと同じです。こんなコードを書かされたら混乱するしかありません…。

let p3: Parser<char, (&char, &char)> = and_then(p1, p2);
let p6: Parser<char, ((&char, &char), &char)> = and_then(and_then(p4, p5), p3);
// ...

同様に変形します。

let p3: Parser<char, (&char, &char)> = p1.and_then(p2);
let p6: Parser<char, ((&char, &char), &char)> = p4.and_then(p5).and_then(p3);
// ...

演算子も再定義します。まぁ+がいいのかどうかはさておき。pomは+だったのでそれに倣いました。

let p3: Parser<char, (&char, &char)> = p1 + p2;
let p6: Parser<char, ((&char, &char), &char)> = p4 + p5 + p3;
// ...

operator_parser.rs

pub trait OperatorParser<'a>: ParserRunner<'a> {
// ...
  fn and_then<B>(self, other: Self::P<'a, Self::Input, B>) -> Self::P<'a, Self::Input, (Self::Output, B)>
  where
    Self::Output: Clone + Debug + 'a,
    B: Clone + Debug + 'a;
// ...
}

add_impl.rs

impl<'a, I, A, B> Add<Parser<'a, I, B>> for Parser<'a, I, A>
where
  A: Clone + Debug + 'a,
  B: Clone + Debug + 'a,
{
  type Output = Parser<'a, I, (A, B)>;

  fn add(self, rhs: Parser<'a, I, B>) -> Self::Output {
    self.and_then(rhs)
  }
}

Parser型

パーサーを生成する関数も基本的な例を説明しましたが、そもそもParser型とは何かという話をしていませんでした。パーサーのインスタンスを表すParser型は、簡単に言えばクロージャを内包する型です。

parser

type Parse<'a, I, A> = dyn Fn(&ParseState<'a, I>) -> ParseResult<'a, I, A> + 'a;

pub struct Parser<'a, I, A> {
  pub(crate) method: Rc<Parse<'a, I, A>>,
}

Parse型はクロージャ型のエイリアスで、引数に解析中の状態を表すParseState型ととり、戻り値は解析結果を表すParseResult型です。Parser型はそれを内部に保持しますが、Rc型でラップします。こうすることで、Parser 型のインスタンスがCloneされても同一インスタンスを参照できます。

これをどう実行するかというと、以下のような実装になります。parseもしくはrunメソッドを呼びだすと解析処理を行い解析結果を返します。クロージャ型はFn型なので何度でも解析を実行できる必要があります。なので、クロージャ本体の処理でも所有権を一度消費して2回以上実行できない実装はコンパイルエラーになるので注意が必要です。

parser_runner.rs

impl<'a, I, A> ParserRunner<'a> for Parser<'a, I, A> {
  type Input = I;
  type Output = A;
  type P<'m, X, Y>
  where
    X: 'm,
  = Parser<'m, X, Y>;

  fn parse(&self, input: &'a [Self::Input]) -> ParseResult<'a, Self::Input, Self::Output> {
    let parse_state = ParseState::new(input, 0);
    self.run(&parse_state)
  }

  fn run(&self, param: &ParseState<'a, Self::Input>) -> ParseResult<'a, Self::Input, Self::Output> {
    (self.method)(param)
  }
}

elm_pred_ref, or, and_thenの実装

elm_pred_ref, or, and_thenの具体的な実装をみていきましょう。

elm_pred_refの実装

elm_pred_refの実装は以下です。

入力値はparse_state.input()で配意として取得できます。このパーサーでは配列の先頭から1要素への参照を取得しfに渡します。trueの場合はその参照を含むParseResultを成功として返し、falseの場合はParseResultを失敗として返します。

element_parsers_impl.rs

impl ElementParsers for ParsersImpl {

  fn elm_pred_ref<'a, I, F>(f: F) -> Self::P<'a, I, &'a I>
  where
    F: Fn(&I) -> bool + 'a,
    I: Element + PartialEq + 'a, {
    Parser::new(move |parse_state| {
      let input = parse_state.input();
      if let Some(actual) = input.get(0) {
        if f(actual) {
          return ParseResult::successful(actual, 1);
        }
      }
      let offset = parse_state.next_offset();
      let msg = format!("offset: {}", offset);
      let ps = parse_state.add_offset(1);
      let pe = ParseError::of_mismatch(input, ps.next_offset(), 1, msg);
      ParseResult::failed_with_uncommitted(pe)
    })
  }

}

elm_pred_refは他の要素を解析するパーサーの基盤的実装になっています。elm_pred_refさえ実装すれば他のバリエーションの実装が導出されるような設計になっています。

  fn elm_digit_ref<'a, I>() -> Self::P<'a, I, &'a I>
  where
    I: Element + PartialEq + 'a, {
    Self::elm_pred_ref(Element::is_ascii_digit)
  }

orの実装

orの実装は以下です。

まずparser1を評価します。その結果が失敗ならparser2を評価しその解析結果を返し、そうでないならparser1の解析結果を返します。

operator_parsers_impl

 fn or<'a, I, A>(parser1: Self::P<'a, I, A>, parser2: Self::P<'a, I, A>) -> Self::P<'a, I, A>
  where
    A: 'a, {
    Parser::new(move |parse_state| {
      let result = parser1.run(parse_state);
      if let Some(committed_status) = result.committed_status() {
        if committed_status.is_uncommitted() {
          return parser2.run(parse_state);
        }
      }
      result
    })
  }

※コミットするかしないかは、p1 | p2 | p3のような複数の選択肢あるときのバックトラックと関係がありますが、本題ではないので説明は割愛します。FP in Scala本に簡単な説明があるので読んでみるとよいかもしません。

and_thenの実装

and_thenは以下のように実装されます。

operator_parsers_impl

  fn and_then<'a, I, A, B>(parser1: Self::P<'a, I, A>, parser2: Self::P<'a, I, B>) -> Self::P<'a, I, (A, B)>
  where
    A: Clone + 'a,
    B: Clone + 'a, {
    Self::flat_map(parser1, move |a| Self::map(parser2.clone(), move |b| (a.clone(), b)))
  }

二つのパーサーの処理結果をタプルで返すパーサーを作って返しているだけですが、Self::flat_map, Self::mapについて詳しく解説します。

flat_map, map, successful, failed の実装

ParsersImpl#flat_map

flat_mapはパーサーどうしの計算を結合するために使われるコンビネータです*11。そのflat_mapではparser.run(&parse_state)によってパーサーの評価を行います。その結果が成功ならクロージャfに結果を渡し、fが返すパーサーを実行し、その結果が失敗なら何もせずに失敗を返します。いずれの結果であっても、パーサー型が返ります。

このコンビネータは、あるパーサーの解析結果を、別のパーサーの解析へ繋ぐ場合に使えます。flat_mapは代数的設計の中核を担うコンビネータです。 言いたいことの9割はこれです。

parsers_impl.rs

fn flat_map<'a, I, A, B, F>(parser: Self::P<'a, I, A>, f: F) -> Self::P<'a, I, B>
  where
    F: Fn(A) -> Self::P<'a, I, B> + 'a,
    A: 'a,
    B: 'a, {
    Parser::new(move |parse_state| match parser.run(&parse_state) {
      ParseResult::Success { value: a, length: n } => {
        let ps = parse_state.add_offset(n);
        f(a).run(&ps).with_committed_fallback(n != 0).with_add_length(n)
      }
      ParseResult::Failure {
        error,
        committed_status: is_committed,
      } => ParseResult::failed(error, is_committed),
    })
  }

このコンビネータも、parser1.flat_map(|result| ...)のように記述できます。

ParsersImpl#map

mapはパーサーが解析した成功の結果を別の値に変換するコンビネータです。mapはflat_mapとsuccessfulを使って導出できます。successfulは指定した値を返すパーサーを返す関数です。

parsers_impl.rs

  fn map<'a, I, A, B, F>(parser: Self::P<'a, I, A>, f: F) -> Self::P<'a, I, B>
  where
    F: Fn(A) -> B + 'a,
    A: 'a,
    B: Clone + 'a, {
    Self::flat_map(parser, move |e| Self::successful(f(e)))
  }
}

このコンビネータも、parser1.map(|result| ...)のように記述できます。

ParsersImpl#successful

ParsersImpl#mapで利用した、ParsersImpl#successfulは、指定された値を返すパーサーを生成します。このパーサーはどんな入力であっても必ず成功するパーサーです。

parsers_impl.rs

  fn successful<'a, I, A>(value: A) -> Self::P<'a, I, A>
  where
    A: Clone + 'a, {
    Parser::new(move |_| ParseResult::successful(value.clone(), 0))
  }

ParsersImpl#failed

ParsersImpl#successfulより出番は少ないかもしれませんが、ParsersImpl#failedは指定されたエラーを返すパーサーを生成します。このパーサーはどんな入力であっても必ず失敗するパーサーです。

parsers_impl.rs

  fn failed<'a, I, A>(value: ParseError<'a, I>, committed: CommittedStatus) -> Self::P<'a, I, A>
  where
    I: Clone + 'a,
    A: 'a, {
    Parser::new(move |_| ParseResult::failed(value.clone(), committed.clone()))
  }

SkipParsers#skip_left, skip_right, surround

実は、基本的なパーサーの合成は 前述のコンビネータがあれば実現できます。

たとえば、p1 + p2のようにand_thenで繋がった二つのパーサーのうち、いずれかのパーサーの解析結果を捨てる実装は以下のようになります。skip_leftは左のパーサーの解析結果を破棄し、skip_rightは右のパーサーの解析結果を破棄します。and_thenはタプルで解析結果を返しますが、skip_left, skip_rightでは単一の解析結果を返します。さらに、p1 + p2 + p3でp2の結果だけを返すパーサーはsurroundです。skip_left, skip_rightの二つのコンビネータを使って簡単に実装できます。

skip_parsers.rs

  fn skip_left<'a, I, A, B>(pa: Self::P<'a, I, A>, pb: Self::P<'a, I, B>) -> Self::P<'a, I, B>
  where
    A: Clone + Debug + 'a,
    B: Clone + Debug + 'a, {
    Self::map(Self::and_then(pa, pb), |(_, b)| b)
  }

  fn skip_right<'a, I, A, B>(pa: Self::P<'a, I, A>, pb: Self::P<'a, I, B>) -> Self::P<'a, I, A>
  where
    A: Clone + Debug + 'a,
    B: Clone + Debug + 'a, {
    Self::map(Self::and_then(pa, pb), |(a, _)| a)
  }

  fn surround<'a, I, A, B, C>(
    left_parser: Self::P<'a, I, A>,
    parser: Self::P<'a, I, B>,
    right_parser: Self::P<'a, I, C>,
  ) -> Self::P<'a, I, B>
  where
    A: Clone + Debug + 'a,
    B: Clone + Debug + 'a,
    C: Clone + Debug + 'a, {
    Self::skip_left(left_parser, Self::skip_right(parser, right_parser))
  }

or, and_then同様にskip_left, skip_righは演算子を再定義しているので、surround(p1, p2, p3)相当のことはp1 * p2 - p3と記述できます。

mul_parser_impl.rs

impl<'a, I, A, B> Mul<Parser<'a, I, B>> for Parser<'a, I, A>
where
  A: Clone + Debug + 'a,
  B: Clone + Debug + 'a,
{
  type Output = Parser<'a, I, B>;

  fn mul(self, rhs: Parser<'a, I, B>) -> Self::Output {
    self.skip_left(rhs)
  }
}

sub_parser_impl.rs

impl<'a, I, A, B> Sub<Parser<'a, I, B>> for Parser<'a, I, A>
where
  A: Clone + Debug + 'a,
  B: Clone + Debug + 'a,
{
  type Output = Self;

  fn sub(self, rhs: Parser<'a, I, B>) -> Self::Output {
    self.skip_right(rhs)
  }
}

URIのパスを解析するパーサー

実装例としてURIのパスを解析するパーサーを紹介します。

URIのパスはほぼBNFに似た形でコードが書けます*12。

//  path          = path-abempty    ; begins with "/" or is empty
//                / path-absolute   ; begins with "/" but not "//"
//                / path-noscheme   ; begins with a non-colon segment
//                / path-rootless   ; begins with a segment
//                / path-empty      ; zero characters
pub fn path<'a>() -> Parser<'a, char, Option<Path>> {
  (path_rootless().attempt() | path_abempty(true).attempt() | path_absolute().attempt() | path_noscheme())
    .opt()
    .name("path")
}

このパーサーを構成するpath_abemptyも内部実装はファクトリやコンビネータを組み合わせます。

//  path-abempty  = *( "/" segment )
pub fn path_abempty<'a>(required: bool) -> Parser<'a, char, Path> {
  let n = if required { 1 } else { 0 };
  ((elm('/') + segment()).collect())
    .map(String::from_iter)
    .repeat(n..)
    .map(|e| Path::of_abempty_from_strings(&e))
    .name("path-abempty")
}

(elm('/') + segment()).collect()は、collect()はマッチすると入力の文字列への参照(&str)をそのまま返します。ゼロコピーの解析処理を記述できます。&strままだと扱いづらいので.map(String::from_iter)でStringに変換します。このパターンは複数回出現する想定なので、続くrepeat(n..)でコレクションに変換します。

まとめ

Parser型の設計は、まさに「小さいプログラムも大規模なプログラムも同じ概念で記述できるべきである」を表現しています。一つのことをうまくやる小さなパーサーどうしをコンビネータを使って合成することで、より複雑な問題を解決するパーサーを簡単に実装できる。これが代数的設計によってスケーラブルなプログラミングを実現する方法です。

最後に、FP in Scala本以外で代数的設計を学べる本を以下に紹介しておきます。

Functional and Reactive Domain Modeling

長々とお付き合いいただきありがとうございました。flat_mapは偉大！

*1:というか、オブジェクト指向言語や関数型言語の境界線が溶け込んで曖昧になってきているように思えます

*2:丁寧に書くと大作になる。ボリュームが多いと読者は意図をくみとるのに失敗する確率が高くなる、ので難しい…。

*3:このネットスラングを知らない方はこちらをご覧ください→https://togetter.com/li/1783989

*4:高階関数のことです

*5:さらにパーサーはパーサーを組み合わせることで実装可能なので下位層のWhatは上位層のHowになっていきます。下位層には、手続き型のコードはつきものですが、こういった全体の構造からみると一部になります。

*6:実はScala Parser Combinatorsも同じようなインターフェイスになっています。

*7:空白の読み飛ばしをしないと実用的ではないですがここでは割愛

*8:ちなみにこの程度ならpomでも同様に実装できます

*9:文字をわざわざ要素と抽象的な書き方をしたのは、このパーサーが文字以外も解析できるような設計になっているからです。ある規則に沿ったバイト列上の要素であっても解析できます

*10:演算子の再定義がScalaほど柔軟ではないので限界がありますが…

*11:モナドの説明はしません…

*12:RFCの構文規則は結構あいまいに書かれているし、BNFよりPEGに書き直してから実装したほうがいいかもしれません