Zenn
Closed11

combine でハマっているところメモ

Rust
yukiyuki

Rust のパーサーコンビネータのひとつである combine を使っているが、型パズルがたくさん発生してそれなりにハマっている。

combine でハマったときに、あまり資料や、関数を切り分けたり複雑な定義を実装したサンプルコードがないのがネックだなあと思ったので、そうしたサンプルコードを残す意味でメモをとっておく。

yukiyuki

再帰的な呼び出しは通常の関数では難しそう？

下記のようなコードを書いており、ほとんど定義自体は終わっているのだが、Rust 独特の事情でコンパイルエラーになってしまう。

下記のコードは、primary と expression が循環的に再帰参照されるが、これをすると impl Parser<&'str, Output = Expression<'a>> のメモリ上のサイズがコンパイルタイムで決定できなくなる。つまりコンパイルエラーになる。

実装中のコード
use combine::{
    attempt, chainl1, many,
    parser::{
        self,
        char::{alpha_num, digit, spaces, string},
    },
    Parser,
};

use crate::calculator::ast::*;

use super::ast::Program;

fn r#if<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("if").skip(spaces()))
}

fn r#else<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("else").skip(spaces()))
}

fn r#while<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("else").skip(spaces()))
}

fn plus<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("+").skip(spaces()))
}

fn minus<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("-").skip(spaces()))
}

fn aster<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("*").skip(spaces()))
}

fn slash<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("/").skip(spaces()))
}

fn lt<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("<").skip(spaces()))
}

fn lt_eq<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("<=").skip(spaces()))
}

fn gt<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string(">").skip(spaces()))
}

fn gt_eq<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string(">=").skip(spaces()))
}

fn eq_eq<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("==").skip(spaces()))
}

fn not_eq<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("!=").skip(spaces()))
}

fn global<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("global").skip(spaces()))
}

fn define<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("define").skip(spaces()))
}

fn comma<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string(",").skip(spaces()))
}

fn lparen<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("(").skip(spaces()))
}

fn rparen<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string(")").skip(spaces()))
}

fn lbrace<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("{").skip(spaces()))
}

fn rbrace<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("}").skip(spaces()))
}

fn semi_colon<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string(";").skip(spaces()))
}

fn ident<'a>() -> impl Parser<&'a str, Output = String> {
    many(alpha_num()).skip(spaces())
}

fn identifier<'a>() -> impl Parser<&'a str, Output = Expression<'a>> {
    ident().map(|s| symbol(s))
}

fn integer<'a>() -> impl Parser<&'a str, Output = Expression<'a>> {
    many::<String, &'a str, _>(digit())
        .map(|d| crate::calculator::ast::integer(d.parse().unwrap()))
        .skip(spaces())
}

fn primary<'a>() -> impl Parser<&'a str, Output = Expression<'a>> {
    let s1 = attempt(lparen()).then(|_| expression().then(|v| rparen().map(move |_| v.clone())));
    let s2 = s1.or(integer());
    s2
}

fn multitive<'a>() -> impl Parser<&'a str, Output = Expression<'a>> {
    let mul = aster().map(|_| |l: Expression<'a>, r: Expression<'a>| multiply(l, r));
    let div = slash().map(|_| |l: Expression<'a>, r: Expression<'a>| divide(l, r));
    chainl1(primary(), mul).or(chainl1(primary(), div))
}

fn additive<'a>() -> impl Parser<&'a str, Output = Expression<'a>> {
    let add = plus().map(|_| |l: Expression<'a>, r: Expression<'a>| add(l, r));
    let sub = minus().map(|_| |l: Expression<'a>, r: Expression<'a>| subtract(l, r));
    chainl1(multitive(), add).or(chainl1(multitive(), sub))
}

fn comparative<'a>() -> impl Parser<&'a str, Output = Expression<'a>> {
    let lt = attempt(lt()).map(|_| |l: Expression<'a>, r: Expression<'a>| less_than(l, r));
    let gt = attempt(gt()).map(|_| |l: Expression<'a>, r: Expression<'a>| greater_than(l, r));
    let lte =
        attempt(lt_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| less_than_equal(l, r));
    let gte =
        attempt(gt_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| greater_than_equal(l, r));
    let eq = attempt(eq_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| equal_equal(l, r));
    let neq = attempt(not_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| not_equal(l, r));
    chainl1(additive(), lt)
        .or(chainl1(additive(), gt))
        .or(chainl1(additive(), lte))
        .or(chainl1(additive(), gte))
        .or(chainl1(additive(), eq))
        .or(chainl1(additive(), neq))
}

fn expression<'a>() -> impl Parser<&'a str, Output = Expression<'a>> {
    comparative()
}

fn parse<'a>(source: &'a str) -> Program<'a> {
    let parser = expression();
    let parsed = parser.parse(source).unwrap();
    Program::new(Vec::new())
}

これを解決するには、combine の rustdoc の一番最初に書いてあるのだが（私も見逃してた）、parser! マクロを用いる。ドキュメント上のリンクは下記。

https://docs.rs/combine/4.6.2/combine/#examples

ということで実装を開始したが、まず全体的に impl Parser<&'a str, Output = {return_type}> となっていて、これをマクロ内の記法でどう扱ったらよいかわからなかった。なのでまず、 impl Parser<Input, Output = {return_type}> where Input: Stream<Token = char> の形に統一するように修正した。

当初の型でも循環させない限りは特段問題ないのだが、combine の提供するマクロなどの機能やその他サンプルコードを見る限りでも、後者の型に統一しておいたほうがいろいろと都合がよいように思えた。

修正後のコード
use combine::{
    attempt, chainl1, many, many1, parser,
    parser::char::{alpha_num, digit, spaces, string},
    ParseError, Parser, Stream, StreamOnce,
};

use crate::calculator::ast::*;

use super::ast::Program;

fn r#if<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("if").skip(spaces()))
}

fn r#else<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("else").skip(spaces()))
}

fn r#while<'a>() -> impl Parser<&'a str, Output = &'a str> {
    spaces().with(string("else").skip(spaces()))
}

fn plus<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("+").skip(spaces()))
}

fn minus<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("-").skip(spaces()))
}

fn aster<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("*").skip(spaces()))
}

fn slash<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("/").skip(spaces()))
}

fn lt<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("<").skip(spaces()))
}

fn lt_eq<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("<=").skip(spaces()))
}

fn gt<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string(">").skip(spaces()))
}

fn gt_eq<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string(">=").skip(spaces()))
}

fn eq_eq<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("==").skip(spaces()))
}

fn not_eq<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("!=").skip(spaces()))
}

fn global<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("global").skip(spaces()))
}

fn define<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("define").skip(spaces()))
}

fn comma<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string(",").skip(spaces()))
}

fn lparen<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("(").skip(spaces()))
}

fn rparen<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string(")").skip(spaces()))
}

fn lbrace<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("{").skip(spaces()))
}

fn rbrace<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string("}").skip(spaces()))
}

fn semi_colon<'a, Input>() -> impl Parser<Input, Output = &'a str>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    spaces().with(string(";").skip(spaces()))
}

fn ident<'a, Input>() -> impl Parser<Input, Output = String>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    many(alpha_num()).skip(spaces())
}

fn identifier<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    ident().map(|s| symbol(s))
}

fn integer<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    many1(digit())
        .map(|d: String| crate::calculator::ast::integer(d.parse().unwrap()))
        .skip(spaces())
}

fn primary<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    let s1 = attempt(lparen()).then(|_| expression().then(|v| rparen().map(move |_| v.clone())));
    let s2 = s1.or(integer());
    s2
}

fn multitive<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    let mul = aster().map(|_| |l: Expression<'a>, r: Expression<'a>| multiply(l, r));
    let div = slash().map(|_| |l: Expression<'a>, r: Expression<'a>| divide(l, r));
    chainl1(primary(), mul).or(chainl1(primary(), div))
}

fn additive<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    let add = plus().map(|_| |l: Expression<'a>, r: Expression<'a>| add(l, r));
    let sub = minus().map(|_| |l: Expression<'a>, r: Expression<'a>| subtract(l, r));
    chainl1(multitive(), add).or(chainl1(multitive(), sub))
}

fn comparative<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    let lt = attempt(lt()).map(|_| |l: Expression<'a>, r: Expression<'a>| less_than(l, r));
    let gt = attempt(gt()).map(|_| |l: Expression<'a>, r: Expression<'a>| greater_than(l, r));
    let lte =
        attempt(lt_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| less_than_equal(l, r));
    let gte =
        attempt(gt_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| greater_than_equal(l, r));
    let eq = attempt(eq_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| equal_equal(l, r));
    let neq = attempt(not_eq()).map(|_| |l: Expression<'a>, r: Expression<'a>| not_equal(l, r));
    chainl1(additive(), lt)
        .or(chainl1(additive(), gt))
        .or(chainl1(additive(), lte))
        .or(chainl1(additive(), gte))
        .or(chainl1(additive(), eq))
        .or(chainl1(additive(), neq))
}

fn expression_<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    comparative()
}

これを修正した後に、parser! マクロを使用して、再帰の起点となる関数をマクロによって生成させるようにする。

`parser!` マクロ
// 元の関数の末尾にアンダースコアを付与
fn expression_<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    comparative()
}

// 元の関数を、parser マクロ用にラップした関数の中で呼び出しするようにする
parser! {
    fn expression['a, Input]()(Input) -> Expression<'a> where [ Input: Stream<Token = char> ] {
        expression_()
    }
}

マクロの記法についてはドキュメントにある程度書いてある他、コンパイルエラーでもそれなりに詳しく教えてくれるので参考にできる。

ポイントは、ライフタイム指定やジェネリクスの型は [] で囲っていることと、関数の戻りの型の部分に input -> output の順に型の情報を書いていることだと思う。

最後にこれらの実装は、combine のベンチマーキングに使用されていた json パーサーを参考に用意した。examples に入れておいてほしいかも……。

https://github.com/Marwes/combine/blob/master/benches/json.rs#L167

yukiyuki

ちなみにコンパイルエラーで「Opaque Type」というメッセージがたくさん出てきて、あれ、Rust にその型あったかなと思って、コンパイルエラーについてたドキュメント見てみたら chalk での用語らしい。

https://rust-lang.github.io/chalk/book/clauses/opaque_types.html

Opaque Type というのはコンピュータサイエンスでたまに出てくる用語で、a data type whose concrete data structure is not defined in an interface とのこと。ただ、Rust においては impl Trait が隠す具体的な型を意味するようだ。

https://en.wikipedia.org/wiki/Opaque_data_type

yukiyuki

いわゆる Binary Operator を実装する方法

chainl1 と、map の特殊な記法を使うことで実現できる。chainl1 の rustdoc にたどり着くまで全然やり方がわからなくて苦戦した。たとえば、足し算の定義は次のように記述できる。もしかすると、こんなことをしなくてもやれる可能性はある。

plus, multitive 関数は、先ほど掲載したコードの定義をそのまま流用している。

map 関数に2つクロージャをつけているようにみえるのだが、こういう記法があるのを初めて知った。というより、これは何？？

let add = plus().map(|_| |l: Expression<'a>, r: Expression<'a>| add(l, r));
chainl1(multitive(), add)
yukiyuki

省略できる記法

下記はコンパイルが通る。

fn additive<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    let add = plus().map(|_| |l: Expression<'a>, r: Expression<'a>| add(l, r));
    let sub = minus().map(|_| |l: Expression<'a>, r: Expression<'a>| subtract(l, r));
    chainl1(multitive(), add).or(chainl1(multitive(), sub))
}

クロージャー内については、引数の個数と型が一致していると、実引数の代入の記法をカットできる。つまり、下記のように書き直すことができる。これもコンパイルが通る。若干黒魔術っぽく、知っていないとわからない。実際 _ で消されている部分の一時変数の型は &str とかなので…。

fn additive<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    let add = plus().map(|_| add);
    let sub = minus().map(|_| subtract);
    chainl1(multitive(), add).or(chainl1(multitive(), sub))
}
yukiyuki

chainl1 を or でつなげない

お手本にしているコードを参考に同様のコードを生成させようと思ったが、下記コードは作れないらしい。コンパイルエラー。

let add = plus().map(|_| multiply);
let sub = minus().map(|_| divide);
chainl1(multitive(), add.or(sub))

なので、次のようにしていたのだが、今度は - 側が認識されない。↑の記法が仮にコンパイルをパスするとしたら完全に等価だと思ったが、どうやらそうではないらしい。

let add = plus().map(|_| multiply);
let sub = minus().map(|_| divide);
chainl1(multitive(), add).or(chainl1(multitive(), sub))
    
// 下記のテストは FAIL する
    #[test]
    fn test_sub() {
        let mut parser = additive();
        let actual = parser.parse("2 - 1");
        assert_eq!((subtract(integer(2), integer(1)), ""), actual.unwrap());
    }

正直挙動的にはなんでやねんという感が拭えないが、別の方法を取る必要がある。

発想を変えて実装する必要があると思ったので、まず or がきちんと関数として生えてくる限界点を探す。すると、普通にトークンをパースする箇所であれば関数が生えてくることがわかる。

// これは通る。それぞれの関数の定義はこのスクラップの冒頭にあるので参照のこと。
plus().or(minus())

こう組むと、"+" または "-" のときだけこのパーサーは値を受理するので、あとは両者のケースを抽出して map を書き直すと考えられる。具体的には下記のように書ける。 +, - 以外のケースは一切受理されないので、unreachable で構わない。（Rust の unreachable はコンパイラにここには絶対に来ないというケースを伝えることができ、結果処理ステップ数の削減にもつながる）

    let op = plus().or(minus()).map(|s| match s {
        "+" => |l: Expression<'a>, r: Expression<'a>| add(l, r),
        "-" => |l: Expression<'a>, r: Expression<'a>| subtract(l, r),
        _ => unreachable!(),
    });

最後に op を chainl1 に突っ込むと完成する。全体像は下記のようになる。

fn additive<'a, Input>() -> impl Parser<Input, Output = Expression<'a>>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    let op = plus().or(minus()).map(|s| match s {
        "+" => |l: Expression<'a>, r: Expression<'a>| add(l, r),
        "-" => |l: Expression<'a>, r: Expression<'a>| subtract(l, r),
        _ => unreachable!(),
    });
    chainl1(multitive(), op)
}

テストもこれで通るようになった。

satisfy_map を使える説

試してみたのだが、今回返す内容が高階関数なために少し厳しそうだった。後ほどもう少し真面目にたｍしてみようとは思っているので、できたらまた追記する。

yukiyuki

ここまで Expression でがんばってきたのに、sep_by で苦戦する

（このタイミングで、ライフタイム調整の関係でライフタイムパラメータを一部消す作業をしています）

いよいよ関数呼び出し部分の実装に入ってきたが、関数の引数解析の部分で少し苦戦している。combine に特殊なメソッドが生えていて、スッキリ解決可能だったら知りたいが、現状木構造をリスト構造に変換するというような作業が必要になる気がしている。

やりたい部分を抜き出すと下記のようになる。

sep_by(expression(), comma())

だが、sep_by は Extend トレイトを要求する。入れられたパーサーを中で解析し、セパレータ単位で新しいコレクションに詰め直すという作業をするからだと思う。ただ、この時点で expression パーサーの返す Expression 型はマトリョーシカ的な入れ子になっていて、単一の型として表現されている。ここで食い違いが起きていて、このままだとコンパイルが通らない。

なお、この sep_by はパラメータの取り出しに使用されるので、最終的にはパラメータの Expression を含むリストを返せればよい。所有権などを考慮しない雑なコードを書くと、次のようになる。

ident.then(|name: &'a str| between(lparen(), rparen(), sep_by(expression().extract_params(), comma())).map(|params: Vec<Expression<'a>>| call(name, params)))

仕方がないので、次のような実装を生やそうとしている。

  1. extract_params 関数を Expression に用意する。
  2. 複数リストを内包できる Expressions 型を用意する。
  3. Extend トレイトを Expressions 型に対して実装する。
  4. sep_by の部分の呼び出しの方法を変える。

1. extract_params 関数を Expression に用意する。

この関数は要するに、木構造になっている Expression をリスト構造に変換する作業を行う。

今回はパラメータの取り出しだけできればよいので、パラメータとして判定可能な IntegerLiteral または Identifier に到達したときにベクタに値を詰めて処理を終えるような再帰処理を書く。それ以外のケースではまた関数を再帰させて、どんどん木を探索していくイメージ。

最終的なベクタの結果は Expression 型に詰められて返される。

#[derive(PartialEq, Clone, Debug)]
pub enum Expression {
    IntegerLiteral(i32),
    Identifier(String),
    // その他多数の AST
}

impl Expression {
    pub fn extract_params(self) -> Expressions {
        fn create_vec(expr: Expression, exprs: &mut Vec<Expression>) {
            match expr {
                e @ (Expression::IntegerLiteral(_) | Expression::Identifier(_)) => exprs.push(e),
                _ => create_vec(expr, exprs),
            }
        }
        let mut exprs = Vec::new();
        create_vec(self, &mut exprs);
        Expressions(exprs)
    }
}

2. 複数リストを内包できる Expressions 型を用意する。

New Type を用意する。

pub struct Expressions<'a>(Vec<Expression<'a>>);

3. Extend トレイトを Expressions 型に対して実装する。

Extend トレイトを実装する。ここはそこまで難しくなく、受け取ったイテレータを自身の保有するベクタに追加するだけ。

impl<'a> Extend<Expression> for Expressions {
    fn extend<T: IntoIterator<Item = Expression>>(&mut self, iter: T) {
        for elem in iter {
            self.0.push(elem);
        }
    }
}

impl Extend<Expressions> for Expressions {
    fn extend<T: IntoIterator<Item = Expressions>>(&mut self, iter: T) {
        for elem in iter {
            self.0.extend(elem.0)
        }
    }
}

最終的な関数呼び出し部分のパーサーは下記のようになった。

fn function_call<Input>() -> impl Parser<Input, Output = Expression>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    ident().then(|name| {
        between(
            lparen(),
            rparen(),
            sep_by(expression().map(|expr| expr.extract_params()), comma()),
        )
        .map(move |exprs: Expressions| call(name.clone(), exprs.0))
    })
}

// 下記のテストが通るようになった
    #[test]
    fn test_comma() {
        let mut parser = super::function_call();
        let actual = parser.parse("add_triple(1, 2, 3)");
        println!("{:?}", actual.unwrap());
    }
yukiyuki

一旦なんとか実装しきれた。attempt をつけ忘れて若干バグが出ていた箇所があったので、それを直したりしたら、階乗の計算は通るようになった。

通った時点でのコミット。
https://github.com/yuk1ty/toy-lang/blob/8216f3378adfab413ec3e0a879efef8406d221a5/src/parser.rs

combine、私の実装が悪い可能性はあるんだけど、クロージャーが重なったときのムーブの解決が面倒だった。元の実装が Java のラムダをかなり重ねる実装だったから合わせてたんだけど、そうするとクロージャーが何層にも重なってテクニカルな解決方法を使わざるを得なかったりと大変だった。

回避方法としては、まず元の実装でラムダ式の一時的な引数を使わない map とかは可能な限り with/skip などのクロージャを受け取らないコンビネータを使用するように調整することかなと思った。

yukiyuki

きれいに実装し直せたので自慢したい実装

Java だと致し方ないんだけど、下記はコールバックがたくさん発生していて若干地獄感がある。

https://github.com/kmizu/toys/blob/50204616f8f14301f66bbb4e8c7b2afb394a9bc9/src/main/java/com/github/kmizu/toys/Parsers.java#L75

    public static Parser<Character, Ast.GlobalVariableDefinition> globalVariableDefinition() {
        var defGlobal = GLOBAL.then(IDENT);
        var defInitializer = EQ.then(expression());
        return defGlobal.bind(name ->
                defInitializer.bind(expression ->
                        SEMI_COLON.map(_1 -> new Ast.GlobalVariableDefinition(name, expression))));
    }

combine ではこれをフラットに実装できる。実質2重のコールバックで済んでいる。もしかすると Java 側も普通に then と skip だけである程度きれいに済ませられる可能性はある。

fn global_variable_definition<Input>() -> impl Parser<Input, Output = TopLevel>
where
    Input: Stream<Token = char>,
    <Input as StreamOnce>::Error: ParseError<
        <Input as StreamOnce>::Token,
        <Input as StreamOnce>::Range,
        <Input as StreamOnce>::Position,
    >,
{
    global().with(ident()).then(|name| {
        eq().with(expression())
            .skip(semi_colon())
            .map(move |expression| global_definition(&name, expression))
    })
}
yukiyuki

ほぼ解決できたかも。ということで、クローズ。

このスクラップは2021/11/10にクローズされました