ユーザー定義のdistfix/mixfix演算子をパースする

プログラミング言語で演算子というと普通は中置演算子(infix)だが、C言語の++のように前置演算子(prefix)や後置演算子(suffix/postfix)もある。

?:のような演算子はどうかというと3項演算子(tertiary operator)と呼ばれる。 この言葉は3という数字に限定されているし、syntacticな特徴―複数要素から成り、間に被演算項が入る―を表現していない。（f(x,y,z)の形でも3項ではある）

もっと一般的にはどういうのかというと、プログラミング言語の世界ではdistfixまたはmixfixというようだ。[^1]

中置演算子もそうだが、distfixを任意の識別子に対して任意の優先度でユーザー定義できるようにしようとすると、パーサーの動作を動的に変更する必要が出てきて結構大変になる。 一方で、それらの演算子をlexicalに区別できるようにして優先度も固定するならば通常のパーサージェネレーターを使って割と簡単に実現できる。

そういう方法がHaskell界で有名なSimon Peyton JonesさんのParsing distfix operators という古いペーパー（以下PJ(1986)と書く）に書いてあったのでそれを参考にOCamlで実装してみた。

字句解析

まずユーザー定義できる前置、中置、後置演算子を字句解析で区別する方法について、PJ(1986)ではそれぞれ後ろ、両端、前にドットをつけるという方式を採用している。

例えばx .plus. yと出てきたら.plus.はユーザー定義の中置演算子と解釈される。また、これはplus x yと同じものとして解析されるので演算子を定義するときは単に plus　という関数を定義すればよい。 こうするとplusという関数をそのままplus x yとして使うこともできるしx .plus. yとして中置演算子として使うこともできる。 ここではドットではなくバッククォートを使うことにした。

LexPeyton.mll
{
    (中略)
    let drop s = let len = String.length s - 1 in String.sub s 1 len
    let chop s = let len = String.length s - 1 in String.sub s 0 len
    let untick s = let len = String.length s - 2 in  String.sub s 1 len
}
(中略)
let l = ['a'-'z' 'A'-'Z' '\192' - '\255'] # ['\215' '\247']    (*  isolatin1 letter *)
let d = ['0'-'9']                (*  digit *)
let i = l | d | ['_' '\'']          (*  identifier character *)

rule token =
    parse
        (中略)
        | '`' i+              { let id = lexeme lexbuf in Postfix (drop id) }
        | '`' i+ '`'          { let id = lexeme lexbuf in Infix (untick id) }
        | l i* '`'            { let id = lexeme lexbuf in Prefix (chop id) }
        | '`'                 { Postfix "" }
        | l i* ('`' i+)* '`'? {let id = lexeme lexbuf in Ident id}

disfixを使わないならば関数名の識別子に特別な考慮は要らないが、distfixは前置、中置、後置演算子の組み合わせで実現されるので、そのような組み合わせを表現できるようになっていなければならない。これはユーザー定義演算子を区別するのにつかった記号（バッククォート）とは別でも構わないと思うが、ここでは同じバッククォートを用いた。

例えばif` x `then` y `else` z `fiのように使われる演算子を関数定義するときはif`then`else`fiという名前を使う。そのため識別子Identにバッククォートを含められるようにした。

構文解析

ocamlyaccファイルは次の通り。

ParPeyton.mly   
%{
(中略)
let rec slide exp word = match exp with
  VarExp(f) -> VarExp(f ^ "`" ^ word)
| AppExp(e, a) -> AppExp(slide e word, a)
| e -> failwith (AbsPeyton.show e ^ " + " ^ word)
(中略)
%}
(中略)
%%
exp : exp0 Eof { $1 }

exp0 : Let Ident Eq exp0 In exp0 { LetExp($2, $4, $6) }
     | If exp0 Then exp0 Else exp0 { IfExp($2, $4, $6) }
     | Fun Ident Eq exp0 { FunExp($2, $4) }
     | exp1 { $1 }

exp1 : exp1 Postfix { AppExp(VarExp($2), $1) }
     | exp2 { $1 }

exp2 : exp2 Infix exp3 { AppExp(AppExp(VarExp($2), $1), $3) }
     | exp3 { $1 }

exp3 : exp3 Add exp4 { AppExp(AppExp(PrimAdd, $1), $3) }
     | exp3 Sub exp4 { AppExp(AppExp(PrimSub, $1), $3) }
     | exp4 { $1 }

exp4 : exp4 Mul exp5 { AppExp(AppExp(PrimMul, $1), $3) }
     | exp4 Div exp5 { AppExp(AppExp(PrimDiv, $1), $3) }
     | exp5 { $1 }

exp5 : exp5 exp6 { AppExp($1, $2) }
     | exp6 { $1 }

exp6 : Integer { IntExp($1) }
     | Ident { VarExp($1) }
     | distexp Postfix { slide $1 $2 }
     | LParen exp0 RParen { $2 }

distexp : Prefix exp3 { AppExp(VarExp($1), $2) }
        | distexp Infix exp3 { AppExp(slide $1 $2, $3) }
;

後置演算子と中置演算子はそれぞれexp1とexp2に定義されている。これは特筆することはない定義で、semantic actionで関数適用の構文を作るために順序を入れ替えたりするようにしている。

distfixは一番結合度の高いexp6の定義から始まる。これはつまり「distfixとは前置演算子と式で始まり、0組以上の中置演算子と式の後に後置演算子で終わる」という定義である。 解析木としては前置演算子が一番内側、後置演算子が一番外側に来るような形になる。

これを通常の関数適用の構文木にアダプトするために使っているのがslideという関数だ。この関数は後からくっつく方の演算子（中置、後置演算子）を予め適用されている演算子にくっつける働きをする。（なおPJ(1986)の同名関数はSaslという言語で書かれていたのだけど、どうにも型がつけられそうにないような定義になっていてよくわからなかったので適当に改変した）

ソースの全体はGistにアップロードした。

所感

演算子の優先順位には結構微妙なところがある。 たとえばdistexpに含められる式はexp3としているが、これをexp2やexp1にするとshift-reduce conflictが起こる。 もしexp1がdistfixの中に現れることができるとするとたとえばa` 0 `b` 1 `cという文をa`b`c 0 1と解釈するかa`c (b 0 1) = a` (0 `b` 1) `cと解釈するかで多義的になってしまう。

exp2の後置演算式についても同様で、exp2がdistexpに現れてよいとabout` 2 `years `agoは(about` 2 `years) `agoかabout` (2 `years) `agoかの多義になる。 これはまあしょうがないのだが単純な後置演算式の結合度がかなり弱いというのはなんとなく直観に反するかもしれない。

あとこの文法定義ではdisexpは必ず後置演算子で終わらなければならない。exp6にdistexp単独のルールを追加するとshift-reduce conflictが起こる。 これはmultiply` x `by` y + zのような式が(multiply` x `by` y) + zなのかmultiply` x `by` (y + z)なのか(multiply` x) `by` (y + z)なのか((multiply` x) `by` y) + zなのか多義になってしまうためである。

distexpの中に現れてよい式のレベルをもっと下にすると大体の衝突は回避できるけどその代り結局括弧が必要になるし、中置演算子をshiftするかどうかのconflictはそれでも解消されない。 英語の構文を模倣すると後置演算子で終わることになることはまずない（英語には基本的に後置詞というものがないので）のでこれはとても惜しい点だ。 `fiとか`endとか`doneみたいなのを多用するのはあまり簡潔とは言えない。でも括弧をやたらと書くよりはましだろうか。ただし上記の字句解析では単に`を書いた時にも後置演算子になるようにしたのでmultiply` x `by` y `とは書ける。（multiply`by`という関数が対応する）

なお、PJ(1986)ではpartial insantiationというのも提案されていた。これはたとえばif`then`else`fiを定義して、if` `then` 0 `else` 1 `fiという風に一部を埋めない形で使うと関数の部分適用のようになるというものだった。これはなんというか、できても使わないだろうと思ったので上記の文法定義には含めていない。

[^1]: prefix/suffix/infixが明らかに言語学から来ている用語なのに対してdistfix/mixfixはおそらくプログラミング言語の世界で造語されたと思われる。 なおprefix/infix/suffixは言語学ではlexicalなレベルで起こる事象に使うのに対してプログラミング言語の世界では演算子のsyntacticな配置に対して用いられるのでちょっと用法が違う。