Prolog と Erlang で Mixfix パーサを作ってみた

1. はじめに

Mixfix とは演算子順位法を用いてパーサを拡張するための手法です。
Coq や Agda などの言語で Mixfix 演算子を用いることが出来ます。
Mixfix 演算子は単項演算子や２項演算子よりも複雑な演算子を作ることができるため強力です。Mixfix 演算子は便利ですが実装技術を短く表したコードはないわけではないのですが、あっても難しく感じました。そこで Prolog で簡潔なコードを実装しました。その後、Prolog に構文が似ている Erlang に移植しました。

2. 演算子順位法

まずは Mixfix の基本となる演算子順位法のコードを示します。

2.1. Prolog で演算子順位法

% c2.pl
e(P,O)-->[T],t(P,T,O).
t(P,T,O)-->[U],{atom(U),-[L,U,M],P<L},e(M,V),t(P,[U,T,V],O)|{T=O}.
-[2,*,2]. -[1,+,1].
:-initialization((e(0,T,[1,+,2,+,3,*,4,*,5],[]),write(T),nl,halt)).

実行方法と結果:

$ swipl c2.pl
[+,[+,1,2],[*,[*,3,4],5]]
$ gplc c2.pl && ./c2
[+,[+,1,2],[*,[*,3,4],5]]

Prolog の DCG を使うことでより簡潔に記述出来ています。演算子順位の表を -/1 述語として表せているところも大きいです。

2.2. Erlang で演算子順位法

% c2.erl
-export([main/1]).
e(P,[T|I])->r(P,T,I).
r(P,T,[U|I])->
  case lists:search(fun([_,V,_])->V==U;(_)->false end,get(o))of
    {_,[L,_,M]}when P<L->{V,J}=e(M,I),r(P,[U,T,V],J);
    _->{T,[U|I]}
  end;
r(_,T,I)->{T,I}.
main([])->{V,_}=
  put(o,[[2,'*',2],[1,'+',1]]),
  e(0,[1,'*',2,'+',3,'*',4,'*',5]),io:format("~w\n",[V]).

実行方法と結果:

$ escript c2.erl
['+',['*',1,2],['*',['*',3,4],5]]

3. Mixfix

3.1. Prolog の実装

まずは、元の Prolog のコードです。

% c6.pl
e(P,O)-->[U],t(P,U,O).
t(P,T,O)-->{[L|M]^A},{atom(L)->L=T;P<L},f(M,V,[]),{call(A,V,W)},t(P,W,O)
         ; {T=O}.
f([P|N],R,O)-->({number(P),!},e(P,T),{R=[T|I]};[P],{R=I}),f(N,I,O).
f([],I,I)-->!. [let,1,=,0,in,0]^a(let). a(P,T,R):-R=..[P|T].
:-initialization((e(0,T,[let,x,=,let,y,=,2,in,y,in,3],[]),write(T),nl,halt)).

実行方法と結果:

$ swipl c6.pl
let(x,let(y,2,y),3)
$ gplc c6.pl && ./c6
let(x,let(y,2,y),3)

Prolog では単一化やバックトラックを用いて処理をまとめることで非常に短く実装できました。この実装は Mixfix 以上の能力があります。 let rec x = 1 in x のように演算子を連続して記述することも可能です。

3.2. Erlang の実装

次に Erlang のコードです:

% c6.erl
-export([main/1]).
-mode(compile).
e(P,[T|I])->
  case lists:search(fun({[V|_],_})->is_atom(V)and(V==T)end,o())of
    {_,{[_|M],A}}->{W,J}=f(M,I),r(P,A(W),J);
    _->r(P,T,I)
  end.
r(P,T,[U|I])->
  case lists:search(fun({[L,V|_],_})->is_number(L)and(V==U)and(P<L)end,o())of
    {_,{[_,_|M],A}}->{V,J}=f(M,I),r(P,A([T|V]),J);
    _->{T,[U|I]}
  end;
r(_,T,I)->{T,I}.
f([P|N],S)when is_number(P)->{T,S1}=e(P,S),{T1,S2}=f(N,S1),{[T|T1],S2};
f([P|N],[P|S])->{T1,S1}=f(N,S),{T1,S1};f([],S)->{[],S}.
a(O)->fun(L)->list_to_tuple([O|L])end.
o()->[
  {['-',3],a(sub)},
  {[2,'*',2],a(mul)},
  {[1,'+',1],a(add)},
  {['let',3,'=',0,in,0],a('let')},
  {['if',0,'then',0,'else',0],a('if')}
].
main([])->{V,_}=e(0,['let',x,'=','-',1,'*',2,'+',3,'*',4,in,x,'+',3]),
  io:format("~w\n",[V]).

実行方法と結果:

$ escript c6.erl
{'let',x,{add,{mul,{sub,1},2},{mul,3,4}},{add,x,3}}

4. Prolog ユーザー視点でみた Erlang

「Erlang は Prolog に似ている文法が嫌だ。」という話はよく聞くわけですが、Prolog ユーザー視点で見るとまた違った見え方がします。
たとえば、変数は Prolog の変数と同様に大文字で書くことになるので Prolog からの移植は楽です。
パターンマッチは let バインド ではなく Prolog の単一化のイメージで使うことができるので便利です。
atom も Prolog に近いのでわざわざクォートする事なく使うことが出来たり出来なかったりします。(と思って、if then else を実装したらキーワードだったので駄目だったorz... ので let in を作りました。)
Erlang は if then else let などがキーワードなので '' でくくる必要があります。
リストの記法も Prolog にそっくりです。 io:format の関数も似ています。 関数のアリティも考え方は似ています。ドットで終わる構文もそっくりです。コメントが % で始まるところも似ています。

Prolog は単一化変数やバックトラックなどがあるため関数型言語のほうが最適化はしやすいでしょう。とはいえ Prolog も再帰を当たり前に使う言語なので十分最適化された処理系では末尾再帰最適化も行われ実験をするには十分高速に動作します。

Erlang の文法はとっつきにくさがあるでしょうが Prolog との距離が一歩近づく良い機会であるともいえます。毒を喰らわば皿までです。 Erlang を使ったらついでに Prolog も触ってみてはどうでしょうか？

5. まとめ

Mixfix 構文解析のアルゴリズムを Prolog で簡潔に示しました。また Erlang でも実装しました。Prolog のコードは Erlang のコードより簡潔でした。 しかし多くのプログラマにとっては Erlang のほうが簡単に読むことができるでしょう。

参考文献

JavaScript による実装

CGOL の論文

Prolog の論文

付録 A. c6.ml

(* c6.pl *)
type t = I of int | X of string | R of t * t list
let rec show = function
  | I i -> Printf.sprintf "%d" i
  | X x -> x
  | R(x,l) -> show x ^ "(" ^ String.concat "," (List.map show l) ^ ")"
let a x xs = R(X x,xs)
let o=ref[
  [I 2;X"&";I 2],a"And";
  [I 1;X"?";I 0;X":";I 0],a"Cond";
  [X"if";I 0;X"then";I 0;X"else";I 0],a"If";
]
let rec e p = function
  | x::i ->
    begin try match List.find(function X v::_,_ -> x=X v| _ -> false) !o with
    | _::m,a -> let v,i = f(m, i) in r p (a v) i
    | _ -> raise Not_found
    with _ -> r p x i
    end
  | _ -> raise Not_found
and r p t i =
  try match i with
    | X u::i ->
      begin match List.find (function _::X v::_,_ ->u=v | _ -> false) !o with
      | I l::_::m,a when p < l-> let v,i = f(m, i) in r p (a (t::v)) i
      | _ -> raise Not_found
      end
    | _ -> raise Not_found
  with _ -> t,i
and f = function
  | [],s -> [],s
  | I p::n,s -> let t,s = e p s in let t1,s = f(n,s) in t::t1,s
  | p::n,t::s when p=t -> let t1,s = f(n,s) in t1,s
  | _ -> raise Not_found
let () =
  let r,_= e 0[X"if";X"a";X"&";I 2;X"?";I 3;X":";I 4;X"then";I 1;X"else";I 3] in
  Printf.printf "%s\n" @@ show r