Help us understand the problem. What is going on with this article?

Erlangにパーザコンビネータで入門してみた

More than 1 year has passed since last update.

概要

最近、とある事情でErlangを学習する必要が出てきました。とりあえずErlangは触ったことほぼなかったのですが、このエントリにあるように、私は(明らかに向いてない場合除いて)パーザコンビネータでHello, Worldするのが習慣なので、Erlangでパーザコンビネータ書いてみました、という話です。

パーザコンビネータって?

凄い雑な言い方をすると、yaccとかJavaCCとかANTLRみたいな、パーザジェネレータみたいなの(わからなかったら検索してください)を、そのプログラミング言語自体で作る枠組みです。yaccは文法を書くための言語が別に用意されていて、その中にC言語のコードを埋め込むために、埋め込んだCコードの誤り検出がしづらいとか補完がほとんど効かないといった弊害がありますが、パーザコンビネータだとJavaならJavaの、ScalaならScalaの補完機能がそのまま使える、とか、型チェックが効く、とか、ビルドプロセスを分割しなくていい、とか、色々ご利益があります。デメリットもありますが、おいときます。

BNFとパーザコンビネータの例

BNFはなんとなくわかっているという前提でいきます。まず、1,5,10,100,1+2,1-2,1*2,1/2,(1+2)+3,...みたいに、括弧で囲まれた数式(演算は四則演算のみ)を表現する文法をBNFで書き下します。曖昧でない文法を書き下すときは何はともあれBNF(ないしそれの変種)を使うのが通例です。

root ::= expression;
expression ::= A;
A ::= M ( "+" M | "-" M)*;
M ::= P ( "*" P | "/" P)*;
P ::= "(" expression ")" | number;
number ::= [0-9]+;

され、これをいったいどうやって構成するのかという問題をおいとけば、とにかくこのBNFにしたがって、手で処理を書けば機械的に四則演算(ただし空白文字なし)が解析できるようになります(色々語弊あり)。

これをScalaで書かれた自作パーザコンビネータライブラリscombで書き直すと次のようになります。

object Calculator extends SCombinator[Int] {
  def root: Parser[Int] = expression
  def expression: Parser[Int] = rule(A)
  def A: Parser[Int] = rule(chainl(M) {
    $("+").map { op => (lhs: Int, rhs: Int) => lhs + rhs } |
    $("-").map { op => (lhs: Int, rhs: Int) => lhs - rhs }
  })
  def M: Parser[Int] = rule(chainl(P) { |
    $("*").map { op => (lhs: Int, rhs: Int) => lhs * rhs } |
    $("/").map { op => (lhs: Int, rhs: Int) => lhs / rhs }
  })
  def P: P[Int] = rule{
    (for {
      _ <- string("("); e <- expression; _ <- string(")")} yield e) 
    | number
  }
  def number: P[Int] = rule(set('0'to'9').+.map{ digits => 
    digits.mkString.toInt}) |
  }
}
  • 解析だけでなく計算するコードも入っている
  • 型を明示している
  • chainlという謎のメソッドがある

ので、多少記述量が増えていることはしかたないとしても、BNFとScalaがわかっていれば似た感覚で、Scala内でScala自信の機能を使って、簡潔に色々な「言語」のパーザを書くことができるのです1。これがパーザコンビネータのメリット(の一つ)です。

ここまでが前説です。ここで、パーザコンビネータの本体部分であるScombinatorは予め(私が)実装したものですが、私はこのScombinatorの中身に相当する部分を、言語の入門時に書くことにしています。これには、単に"Hello, World"を書くのに比べて次のような効能があると思います(個人の感想です)。

  1. 多数の言語機能の組み合わせ方を知らないと書けないので、それだけで言語の様々な機能を学べる
  2. その言語におけるループあるいは末尾再帰の書き方を学べる
  3. その言語における無名関数(あるいはそれに類似したもの)の使い方を学べる
  4. その言語における高階関数の使い方を学べる
  5. その言語におけるタプルあるいはレコード(構造体)のような、複合データの作り方を学べる
  6. その言語における文字列処理について学べる
  7. その言語特有の「クセ」について学べる
  8. 簡単なテストケースの書き方を学べる

慣れればよっぽど変わった言語でなければ長くても3〜4時間で作れる割に、言語入門としては一気に色々学べるのでコストパフォーマンスがいい方法だと考えています。

というわけで、Erlang入門にあたって、Erlangでパーザコンビネータライブラリを書いてみることにしたのでした。めんどくさいので、とりあえず完成版をさらすとこんな感じです。

-module(er_combinator).

%% Macros
-define(rule(Block), (fun(Input) -> (Block)(Input) end)). 



%% API exports
-export([literal/1, s/1, alt/2, seq/2, rep/1, map/2, chainl/2, regex/1]).
-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").
-endif.

%%====================================================================
%% API functions
%%====================================================================

%% string literal in PEG
literal(Prefix) -> 
        fun(Input) ->
                        case string:prefix(Input, Prefix) of
                                nomatch -> {failure, "", Input};
                                Suffix -> {success, Prefix, Suffix}
                        end
        end.

%% regex literal.  Although this is not included in PEG, this is convenient.
regex(Literal) ->
        fun(Input) ->
                        {M, [{BeginIndex, EndIndex}]} = re:run(Input, Literal),
                        case M of
                                match when BeginIndex =:= 0 ->
                                        {success, 
                                         string:slice(Input, 0, EndIndex),
                                         string:slice(Input, EndIndex, string:len(Input))};
                                _ ->
                                        {failure, "", Input}
                        end
        end.

%% Shorthand of literal/1
s(Prefix) -> literal(Prefix).

%% X / Y in PEG
alt(X, Y) -> 
        fun(Input) ->
                        case X(Input) of
                                {failure, _, _} -> Y(Input);
                                Success -> Success
                        end
        end.

%% X Y in PEG
seq(X, Y) ->
        fun(Input) ->
                        case X(Input) of
                                {success, V1, Next1} ->
                                        case Y(Next1) of
                                                {success, V2, Next2} -> 
                                                        {success, {V1, V2}, Next2};
                                                Failure -> Failure
                                        end;
                                Failure -> Failure
                        end
        end.

%% X* in PEG
rep(X) ->
        fun(Input) ->
                        {success, Values, Next} = loop(X, Input, []),
                        {success, Values, Next}
        end.

%% map combinator
map(Parser, F) ->
        fun(Input) ->
                        case Parser(Input) of
                                {success, V, Next} -> {success, F(V), Next};
                                Failure -> Failure
                        end
        end.

%% chainl1 combhinator
chainl(P, Q) ->
        map(
          seq(P, rep(seq(Q, P))),
          fun(Values) ->
                          {X, XS} = Values,
                          lists:foldl(
                            fun(R, A) ->
                                            {F, E} = R,
                                            F(A, E)
                            end,
                            X,
                            XS
                          )
          end
        ).

%%====================================================================
%% Internal functions
loop(Parser, Rest, Results) ->
        case Parser(Rest) of
                {success, V, Next} -> loop(Parser, Next, [V|Results]);
                {failure, _, Next} -> {success, lists:reverse(Results), Next}
        end.

これを使って実際に四則演算の文法を書いたのが以下です。

e() -> ?rule(a()).
a() -> ?rule(
          chainl(
            m(),
            alt(
              map(s("+"), 
                  fun(_) ->
                                  fun (Lhs, Rhs) -> 
                                                  Lhs + Rhs 
                                  end
                  end
                 ),
              map(s("-"), 
                  fun(_) ->
                                  fun (Lhs, Rhs) -> 
                                                  Lhs - Rhs 
                                  end
                  end
                 )
             )
           )
        ).


m() -> ?rule(
          chainl(
            p(),
            alt(
              map(s("*"), 
                  fun(_) ->
                                  fun (Lhs, Rhs) -> 
                                                  Lhs * Rhs 
                                  end
                  end
                 ),
              map(s("/"), 
                  fun(_) ->
                                  fun (Lhs, Rhs) -> 
                                                  Lhs div Rhs 
                                  end
                  end
                 )
             )
           )
        ).

p() -> ?rule(
          alt(
            map(
              seq(seq(s("("), e()), s(")")),
              fun(Result) ->
                              {{"(", V}, ")"} = Result,
                              V
              end
             ),
            n()
           )
        ).

n() -> map(
         regex("[0-9]+"),
         fun(V1) ->
                         V2 = list_to_integer(V1),
                         V2
         end
        ).

Erlangの文法のせいでscombを使った場合よりも結構冗長になっていますが、何はともあれ実装できました。雑なテストケースは以下です。

-ifdef(TEST).

seq_test() ->
        X = seq(s("a"), s("b")),
        {C, Value, Rest} = X("ab"),
        ?assert(C =:= success),
        ?assert(Value =:= {"a", "b"}),
        ?assert(Rest =:= "")
        .

alt_test() ->
        X = alt(s("a"), s("b")),
        {C, Value, Rest} = X("ab"),
        ?assert(C =:= success),
        ?assert(Value =:= "a"),
        ?assert(Rest =:= "b"),
        {C2, Value2, Rest2} = X("ba"),
        ?assert(C2=:= success),
        ?assert(Value2=:= "b"),
        ?assert(Rest2=:= "a")
        .

rep_test() ->
        X = rep(s("a")),
        {C, Value, Rest} = X("aaa"),
        ?assert(C =:= success),
        ?assert(Value =:= ["a", "a", "a"]),
        ?assert(Rest =:= ""),
        {C2, Value2, Rest2} = X(""),
        ?assert(C2 =:= success),
        ?assert(Value2 =:= []),
        ?assert(Rest2 =:= "")
        .

regex_test() ->
        X = regex("a*"),
        {C, Value, Rest} = X("aaab"),
        ?assert(C =:= success),
        ?assert(Value =:= "aaa"),
        ?assert(Rest =:= "b").

expression_test() ->
        ?assert({success, 1, ""} =:= (e())("1")),
        ?assert({success, 2, ""} =:= (e())("1+1")),
        ?assert({success, 1, ""} =:= (e())("1*1")),
        ?assert({success, 1, ""} =:= (e())("1/1")),
        ?assert({success, 3, ""} =:= (e())("2+1")),
        ?assert({success, 1, ""} =:= (e())("2-1")),
        ?assert({success, 2, ""} =:= (e())("2*1")),
        ?assert({success, 2, ""} =:= (e())("2/1")),
        ?assert({success, 21, ""} =:= (e())("(1+2)*(3+4)")).

simple_test() ->
        seq_test(),
        alt_test(),
        rep_test(),
        regex_test(),
        expression_test().

-endif.

というわけで、Erlang入門の最初の一歩を終えたのでした。感想としては、

  • 式区切りのセパレータである,と節区切りのセパレータである;を使い分けなければいけない点が不便

どの辺が不便かというと、式を行単位で移動するために行単位カット&ペーストしようとすると、ほぼ必ず構文エラーになるので、それを直すための余計な作業が必要になるのです。Erlangに詳しい人にこれを解決する方法を聞いたのですがElixirを使えばと言われました。さすがにElixirは後発言語だけあります。

  • マクロ引数に渡されるプログラムが抽象構文木でなく、トークン列であるために、構文エラーになるマクロを簡単に(意図せず)定義できてしまう

これはCプリプロセッサが抱える問題と同じです。Cプリプロセッサはこれを利用したある種の裏技が使えるメリットがあったのですが、Erlangのトークン構造だと活用するのは難しそうです。Elixirはこの欠点を改善していて、Lispのように抽象構文木としてマクロ引数を扱っています。さすがにElixirは(以下略

  • パターンマッチは便利

これはパターンマッチのある言語を使った人ならだいたい同意してくれると思いますが、やはりデータ構造に対するパターンマッチがあると便利です。ただし、リストパターンが中途半端にProlog風味なのはどうかと思います。

  • truefalseをタイポすると死ぬ(のがひどい)

Erlangは大文字で始まるのが変数名で、小文字で始まるのがシンボル名なので、truefalseを間違えても文法的には正しいプログラムとして成立してしまいます。ただし、trufalsは真でも偽でもないため、次のような実行時エラーが発生してしまいます。Elixirではシンボルは:で始まるため、このような問題は発生しません。さすがにElixirは(以下略

case 1 < 2 of
  tru -> "1<2";
  fals -> "1>=2"
end.
** exception error: no case clause matching true

これは非常にイケてない仕様です。何故そうしたのか不思議です(Prolog由来の構文をある程度引き継いだという歴史的事情があるのかもしれませんが)。

  • モジュールの関数を全てインポートする方法がないのが不便

これは一長一短ですが、いわゆるJavaのワイルドカードインポートのように、あるモジュールの関数全てをインポートする方法がないらしく、モジュールの関数全てをインポートしたいときにいちいち全て列挙する必要があります。そういう手段を用意することでわかりづらいプログラムが書けてしまうために、絶対悪いとは言い切れませんがやはり不便です。なお、Elixirではあるモジュールの関数全てをインポートするコードが一行で書けます。さすがにElixirは(以下略

  • 文法はとっつきにくいが(比較的)単純

Erlangの文法は正直言って、書いていて構文エラーが発生しやすいイケてない仕様満載だと感じますが、文法自体は「普通」というか、謎のアドホックなルールがさほどないため、トップダウンに規則を把握するのは難しくありませんでした。

この点は、Erlangより文法を大幅に改善したElixirの方が、おそらく文法的には「複雑」(!=難しい)だと思われるところが興味深いです。文法の複雑さと文法の難しさは必ずしも正の相関を持たないものだな、と思いした。

  • = が単なる変数束縛でなく、パターンマッチなのはどうなのか

これはErlangを知らない人にはわかりにくいと思いますが、たとえば、

E = 1

は、変数Eを1に束縛するという形で挙動が決められているわけではなく、パターンEと値1照合するという動作をするようです。

E = 1 (A)
...
E = 2 %% (B)

の(B)において、Eは単にたまたま変数名がかぶってしまっただけなのに、コンパイルエラーになるわけでも再代入になるわけでも(再代入にならないのは理解できる)なく、Eに結び付けられた値である12の照合を実行時に行って単に失敗してしまうのです。=の左辺には複合的なパターンが出現できるため、利点がないわけでもないのですが、せめて、変数名が単独で出現した場合には救済措置がほしかったところです。

なお、Elixirでも=はパターンマッチ演算子なのですが、こういうコードが出てきたらシャドウイングを行うため、同様の問題は回避できています。さすがElixirは後発(以下略

ErlangとElixir

ElixirはErlang VMのバイトコードを吐き出す言語(と処理系)であり、いまや、Erlang以上に(要出典)人気があるようですが、それも納得するくらいにErlangの文法はとっつきづらいと正直思います(上でしつこいくらいに書いたように、ElixirはErlangの文法上の問題点を徹底的に改善したように見えます)。セマンティクス的にはErlangとElixirはかなり近いようなので、どうしてもErlangでなければならない(たとえば既にErlangのコードベースが大量にある場合)ときを除いて、Elixirを使う方が良さそうだという感想を持ちました(この点は、実務でErlang/Elixirを使っている方からは異論があるかもしれません。Erlang/OTPのバージョン互換にまつわる問題や、Erlangの関数をElixirから呼び出すときに何か罠があるかもしれませんし)。

こんな感じで、Erlang(の文法)については随分辛辣な感想になってしまいました。ただ、Erlangについてはあくまでも初心者であるので、事実誤認があれば遠慮なく指摘いただければと思います。


  1. 正確にはPEGがわかっていれば、と書くべきところですが雑な説明なので気にしないことにしてください 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした