So-net無料ブログ作成
検索選択

初めて再帰モジュールが必要になった話 [OCaml]

入力ストリームの実装から独立したパーサーを定義したい。 そこでまずは入力ストリームのデータ型を定義する。

module type INSTREAM = sig
  type instream
  (* 本当はinstreamに対する色々な操作を含むつもり *)
end

実際の入力元はチャネルだったりメモリ上の文字列だったりする。

module ChanIns = struct
  type instream = in_channel
end

module StringIns = struct
  type instream = string
end

パーサーのシグニチャと実装はこんな感じになる。

module type PARSE = sig
  type instream
  type result
  val parse : instream -> result
end

module Parse(I: INSTREAM): PARSE with type instream = I.instream
  = struct
  type instream = I.instream
  type result = unit
  let parse ins = ()
end

module StringParse = Parse(StringIns)
module ChanParse = Parse(ChanIns)

ここでparse関数の中で、 「ストリームから読み込んだデータをいったん文字列にしてparse関数自身でパースする」 という処理がしたい。 文字列が変数sだとして、その内部のparse関数の呼び出しはどのように書けばよいか。

単にlet rec parse ins = ...としてparse (s : string)では駄目そうだ。 parseの型はinstream -> resultなのだがinstreamI.instreamであって、 stringであるとは限らない。

じゃあ StringParse.parse (s : string) では?というとこれもだめだ。 Parseの実装の中ではまだStringParseは定義されていない。 もちろんStringParseはParseに依存するのでParseより前に移動するわけにもいかない。

ということは…あ、再帰か。 ということで初めて実際に再帰モジュールというものが必要になる場面に出くわしたのだった。

結論から書くと、次のように書くことでコンパイルが通るようになる。

module Parse(I: INSTREAM)(S: PARSE with type instream = StringIns.instream)
  : PARSE with type instream = I.instream
  = struct
  type instream = I.instream
  type result = unit
  let parse ins = (ignore (S.parse ""); ())
end

module rec StringParse : PARSE with type instream = StringIns.instream =
        Parse(StringIns)(StringParse)
module ChanParse = Parse(ChanIns)(StringParse)

ファンクターは新しい引数Sをとる。 Sのモジュール型から、S.instreamはStringIns.instreamであるという想定がおけるので、 問題のparseの呼び出しはこのSに定義されたparseを呼ぶことでよくなる。

S.parseは結果的にはStringParse.parseを呼んでいることにしたい、 つまりS = StringParseであるということにしたいので、 ファンクターを適用するときに第2引数をStringParseにする必要がある。

これはChanParseのときは簡単な話で、普通に適用すればよい。 しかしStringParseを作るときは自分自身を使って自分自身を作るということになる。 これは再帰だ。ということでrecが付く。 再帰モジュール定義の場合はStringParseのモジュール型を明示する必要があるようだ。

後書き

実際にはSMLを書いていてこの問題に遭遇したのでこのように解決することはできませんでしたが、 そういえばOCamlには再帰モジュールって有ったと思い出して問題を翻訳しました。


シェルのコマンド置換の内部でのコメント [sh]

シェルのパーサーを書こうとしていていたのだけどマニュアルから読み取れないところはどうしても動かして実地調査するしかない。 シェルのコマンド置換の内部にコメントを書いて、そのコメントの中にコマンド置換の終端記号が来た場合、終端記号が勝つのかコメントが勝つのかという問題を調べた。

つまりこういうのを試す。

echo $(echo hello # comment)

echo $(echo hello
# comment)

echo `echo hello # comment`

echo `echo hello
comment`

結果

$ echo $(echo hello # comment)
> )
hello
$ echo $(echo hello
> # comment)
> )
hello
$ echo `echo hello # comment`
hello
$ echo `echo hello
> # comment`
hello

つまりダラーの場合はコメントのほうが勝って、バッククォートの場合はバッククォートのほうが勝つ。 bashでもksh93でもzshでも同様の動き。

めんどくさい… 忘れないようにメモしておく。


ブログをもう1つ始めた

ブログをもう1つ始めました。

wonderful cool something -- http://wcs.hatenablog.com/

使い分けはあまり考えていませんが、向こうではとりあえずProcessingで遊んだことなどを書き記していこうと思います。

SML の long identifier のドットについて [SML]

Standard MLの文法について調べていて気付いたこと。

SMLでは Int.toString みたいなドットで区切られた識別子のことを long identifier というんだけど、これは The Definition of Standard ML では longx ::= x | strid1.・・・.stridn.x というBNFで定義している(2.4 Identifiers)。 また、2.5 Lexical analysis では "Each item of lexical analysis is ... or a long identifier." と書いていて、long identifier が(syntacticなカテゴリではなく)lexicalなitemであるとしている。

そうするとこのドットの前後にホワイトスペースは許容されるのかという疑問が生じてくる。 通常の lexical analysis ではホワイトスペースをトークン中に含まない。とはいえそういうことができないわけではない。 一方でプログラミング言語一般的にはドットの前後で改行できるのが普通だと思う。

各種のSML実装で比較してみると、なんと!許容しないほうが多数派だった。

  • 許容しない: MLton, MLKit, Poly/ML, Moscow ML, Hamlet
  • 許容する: SML/NJ, SML#, Alice ML

検証ソース

$ cat longvid-split.sml
val _ = print (Int
.toString (Array.
maxLen))

実行結果

$ mlton longvid-split.sml
Error: longvid-split.sml 2.1.
  Illegal token.
Error: longvid-split.sml 2.17.
  Illegal token.
Error: longvid-split.sml 1.16.
  Undefined variable Int.
Error: longvid-split.sml 2.2.
  Undefined variable toString.
Error: longvid-split.sml 2.12.
  Undefined variable Array.
Error: longvid-split.sml 3.1.
  Undefined variable maxLen.
compilation aborted: parseAndElaborate reported errors
$ mlkit longvid-split.sml
[reading source file:   longvid-split.sml]
longvid-split.sml, line 2, column 2:
  .toString (Array.
    ^
cannot lex "."
[[ERR in sub process:
  PARSE_ELAB_ERROR]]
Stopping compilation of MLB-file due to error (code 1).
$ polyc longvid-split.sml
Error- in 'longvid-split.sml', line 2.
unknown symbol .t
Error- in 'longvid-split.sml', line 2.
invalid identifer - Array.
Exception- Fail "Static Errors" raised
$ sml
Standard ML of New Jersey v110.76 [built: Tue Oct 22 14:04:11 2013]
- use "longvid-split.sml";
[opening longvid-split.sml]
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[autoloading done]
16777215val it = () : unit
$ mosml -P full
Moscow ML version 2.10
Enter `quit();' to quit.
- use "longvid-split.sml";
[opening file "longvid-split.sml"]
File "longvid-split.sml", line 2, characters 0-1:
! .toString (Array.
! ^
! Lexical error: ill-formed token.
[closing file "longvid-split.sml"]
$ alice
Alice 1.4 ("Kraftwerk 'Equaliser' Album") mastered 2013/11/08
### loaded signature from x-alice:/lib/system/Print
### loaded signature from x-alice:/lib/tools/Inspector
### loaded signature from x-alice:/lib/distribution/Remote
- use "longvid-split.sml";
val it : unit = ()
### evaluating file /home/ether/longvid-split.sml
16777199-
SML# 2.0.0 (2014-04-04 11:47:08 JST) for i686-unknown-linux-gnu with LLVM 3.4
# use "longvid-split.sml";
8388607#
$ ./hamlet
HaMLet 2.0.0 - To Be Or Not To Be Standard ML
[loading standard basis library]
- use "longvid-split.sml";
val it = () : unit
[processing /home/ether/longvid-split.sml]
../longvid-split.sml:2.0-2.1: invalid character `.'

ちなみにこの実験中に MLKit では Array.maxLen が 123456789 と定義されていることにも気づいてしまった。たぶん嘘だと思う。

$ cat longvid.sml
val _ = print (Int.toString (Array.maxLen))
$ mlkit longvid.sml
[wrote X86 code file:   MLB/RI_GC/base-link_objects.s]
[wrote executable file: run]
$ ./run
123456789

Proglr: SML用のGLRパーサージェネレーター [SML]

ちまちま作っていたSML用のパーサージェネレーターが結構形になってきたので紹介します。

https://github.com/tkob/proglr

先日の記事ではML-BNFCという名前で、パーサーはLR(0)の状態だった。当初のもくろみとしては一度SLR(1)にした後でBermudez and Logothetisの方法なるものを使ってLALR(1)にするということを考えていたんだけど、面倒に思えてきたのと、そのわりに得られる結果がLALR(1)で独自性がない気がしたので結局GLRにした。 そうするとこのパーサージェネレーターの独自性はどちらかというとGLRになるのでML-BNFCという名前もやめてML-GLRという名前にした。[追記参照] いまでは文法定義ファイルからSMLソースを生成するようになっていて、文法定義ファイルの解析自体もML-GLR自身が生成したものになっている。

[追記]: ML-GLRっていう名前のパーサージェネレーターが既にあった!http://www.cis.uni-muenchen.de/~leiss/relationaleGrammatik-09-10/ml-glr.pdf

ということでさらに名称変更してProglrという名前にした。 [追記終わり]

ビルド

git clone --recursive https://github.com/tkob/proglr
cd proglr
make -f Makefile.mlton

パターンマッチに関する警告がたくさん出ますが無視してください。 proglrという実行ファイルができます。 なお、MLtonのほかに一応MLKitとPoly/MLでもビルドできるようになっています。[追記]SML#2.0.0でもコンパイルできるようになりました。

使用例

文法定義は次のように書く。BNFCにおおむね似ている。

token Add "+" ;
token Sub "-" ;
token Mul "*" ;
token Div "/" ;
token LParen "(" ;
token RParen ")" ;
token Integer of int;

EAdd. Exp ::= Exp "+" Exp1 ;
_.    Exp ::= Exp1 ;
ESub. Exp ::= Exp "-" Exp1 ;
EMul. Exp1 ::= Exp1 "*" Exp2 ;
EDiv. Exp1 ::= Exp1 "/" Exp2 ;
_.    Exp1 ::= Exp2 ;
EInt. Exp2 ::= Integer ;
_.    Exp2 ::= "(" Exp ")" ;

この文法定義からは次のようなAST型が生成される。

  structure Ast = struct
    datatype exp =
      EAdd of Lex.span * exp * exp
    | ESub of Lex.span * exp * exp
    | EMul of Lex.span * exp * exp
    | EDiv of Lex.span * exp * exp
    | EInt of Lex.span * int
  end

スキャナーの定義はml-ulexを使う。

%defs (
  open Token
  type lex_result = Token.token
  val eof = fn () => Token.EOF
);

%name Lexer;

%let digit = [0-9];
%let space = [ \t\r\n];

<INITIAL> "+" => (Add);
<INITIAL> "-" => (Sub);
<INITIAL> "*" => (Mul);
<INITIAL> "/" => (Div);
<INITIAL> "(" => (LParen);
<INITIAL> ")" => (RParen);
<INITIAL> {digit}+ => (Integer (Option.valOf (Int.fromString (yytext))));
<INITIAL> {space}+ => (continue ());

ドライバとなるプログラムは次のような感じで書く。

structure Parse = ParseFun(Lexer)

open Parse.Ast

fun calc (EAdd (_, e1, e2)) = (calc e1) + (calc e2)
  | calc (ESub (_, e1, e2)) = (calc e1) - (calc e2)
  | calc (EMul  (_, e1, e2)) = (calc e1) * (calc e2)
  | calc (EDiv  (_, e1, e2)) = Int.div (calc e1, calc e2)
  | calc (EInt (_, e)) = e

fun main () =
  let
    val strm = Lexer.streamifyInstream TextIO.stdIn
    val sourcemap = AntlrStreamPos.mkSourcemap ()
    val ast = Parse.parse sourcemap strm
    val result = calc (hd ast)
  in
    print (Int.toString result);
    print "\n"
  end

val _ = main ()

ビルドするときはランタイムとしてsmlnj-libとmllpt-libをリンクする。

(* calc.mlb *)
$(SML_LIB)/basis/basis.mlb
$(SML_LIB)/smlnj-lib/smlnj-lib.mlb
$(SML_LIB)/mllpt-lib/mllpt-lib.mlb

calc-parse.sml
scan.ulex.sml
calc.sml

スキャナーとパーサーを生成するためのMakefile

mlglr: calc-parse.sml scan.ulex.sml
        mlton -output calc calc.mlb

calc-parse.sml: calc.cf
        proglr < calc.cf > calc-parse.sml

scan.ulex.sml: scan.ulex
        ml-ulex scan.ulex

clean:
        rm -f calc calc-parse.sml scan.ulex.sml

実行例

$ ./calc
(1 - 2) + 3 * 4 + 5
16

Generalized LRについて

構文解析について調べたりしながら思ったこと。

BNFCみたいに文法定義からASTのデータ型を自動生成するということを考えると、文法定義自体が「もともと表現したい構造」から離れていないほうがよい。BNFCのターゲットとなるパーサージェネレーターが全部LR系なのはそれなりに理由があることなんだろう。

ところでよく使われているLALR(1)では多義性のない文法に対してもconflictが生じることがあって、そういう場合はやっぱり文法のほうを変えなければならない。どんな文法に対してもきれいなASTデータ型を自動で出したければ理想的にはすべてのCFGを扱えるパーサーが望ましい。しかし文脈自由言語一般を扱えるパーサーはどれも最悪でO(n^3)の実行時間がかかってしまうそうだ。

Generalized LRもCFG一般を取り扱える手法だが、これはLR(0)やLALR(1)などの決定的なLR法に一手間加えて実現できる。普通の決定的なLR法ではconflictは起こってはいけない、あるいは起こったらどちらかを選ぶように決めておく。GLRではconflictが起きたら両方の選択肢をキープして構文解析を続ける。途中で選択肢の1つがエラーで死ぬかもしれないし、最終的に複数残るかもしれない。これは概念的に理解しやすい。

GLRは任意の文法に対してはO(n^(k+1)) (kは文法の最長の右辺)[1]だそうだけど、いま書いたことを考えるとconflictが起きなければO(n)になりそうじゃないか、という気がしてくる。その場合はベースとなるLR(0)やLALR(1)での解析と同じことしか起こっていないことになるわけだから。Wikipedia [2] にもそのようなことが書いてある。

ちょっとだけconflictのある文法はO(n)よりちょっとだけ遅くて、かなりconflictのある文法はかなり遅くなる、ということなら、プログラミング言語の構文解析も全部GLRでよくはないのだろうか。現実のプログラミング言語の文法はおおよそLALR(1)の範囲であるということが経験的にいえるのだし、そのうえでconflictが起こる少量のケースに関して決定的にするのかペナルティを受け入れて残すかの選択肢が設計者に残せるのだとしたら特に悪いことはなさそうだ。

でもプログラミング言語の処理系でGLRを採用して構文解析しているというのはあまり聞いたことがないような…そうだとしたらやっぱり何か使わない理由があるのだろうか。

[1] 文法をチョムスキー標準形にすると右辺は最大2にできるのでO(n^3)になるということだと思う。
[2] http://en.wikipedia.org/wiki/GLR_parser

SML用のLRパーサージェネレーターを作る [SML]

SMLのためのLRパーサージェネレーターを新しく自分で作っている。 まだ限定的なことしかできないしコードが汚い部分も残っているのだけど、公開された場所に置くことがモチベーションになるかもしれないと思ってGithubにアップロードした。

ML-BNFC: BNF Converter for Standard ML

SML処理系のためのパーサージェネレーターは各SML処理系に付属している場合が多いから、 新しくパーサージェネレーターを作るということ―車輪の再発明―を正当化するのはなかなか難しい。 私の場合は、自分で好きなように手を入れられるものが欲しいと思った、という程度ものだ。 でも新しく作るからには既存のものと少しは違う。 とりあえず作るにあたっての方針と、今後の目標を次に記そうと思う。

方針

  • ml-ulexと組み合わせて使える

SML/NJには歴史のあるml-yacc/ml-lexに加えて、ml-lptという言語処理系作成向けのツール群がある。 ml-ulexはml-lptに付属するスキャナージェネレーターである。 これはml-lexに比べると非常に進化していて、どうしてもこれを使いたかった。 もちろんml-lptを使えば使えるのだが、基本的にはml-antlrというLL(k)のパーサージェネレーターと組み合わせるしかなかった。

  • 構文木のデータ型を自動生成する

パーサージェネレーターには普通セマンティックアクションを付与した文法定義を与え、そのセマンティックアクションの中で構文木の生成を行うという形をとることが多い。 多いというか、パーサージェネレーターを使う殆どのケースでまずは構文木を作ると思う。 だとしたらパーサージェネレーターが構文木のデータ型も構文木を構築するコードも自動生成してくれればいい。 以前紹介したBNFCがそのような機能を提供していてとても便利だと思っていたのでそれを取り入れた。 また、ツールの名前もそこからとってML-BNFCとした。

生成されるコードはできるだけ多くのSML処理系で動くようにする。

現状

現時点でコミットしてあるコードはブートストラップしていなくて、文法定義はSMLのデータとして直接与えて一緒にコンパイルするしかない。 ビルドするとmlbnfcというバイナリができ、ファイル名を与えて実行するとパーサーおよび構文木のデータ型のコードを出力する。 このコードはml-ulexで書いたスキャナーを組み合わせて使えるようになっていて、パースすると構文木が作られる。

今後の目標

  • 文法定義を外部ファイルから読み込むようにする
  • 雛形となるようなドライバのコードも自動生成するようにしたい
  • 現在LR(0)の文法しかサポートされていない。いずれLALR(1)まで持っていきたい
  • コードをきれいにする

[追記] この記事の続きはこちら http://rainyday.blog.so-net.ne.jp/2014-06-18


SML処理系で利用可能なSML Basis Libraryを一覧化する [SML]

各SML処理系がSML Basis Libraryをどこまでサポートしているかを比較してみたいことがある。 自分だけかもしれないが、そういう一覧が必要だと思ったので作ることにした。

とはいえ数多いモジュールとそれに属する関数や定数をいちいち手作業で確かめるのは大変なのでスクリプトを書いた。

https://gist.github.com/tkob/11498077

スクリプトに関する覚書

まず、manpages.rbが http://www.standardml.org/Basis/manpages.html から個別のモジュールの解説ページのURLを取得してmanpages.txtに保存する。

次にgethtml.shがwgetを使って個別解説ページをダウンロードし、 module.rbがそれらのページからstructureとそれに属する値を抽出する。 ここでInt{N}とかWord{N}のようなstructureは16,31,32,63,64の値で展開することにした。 (ただし一部の処理系ではもっと細かく用意されている場合がある) この結果がval.txtに保存される。これは「Array.length」のような名前が1行1つの形式である。

こうして得られた名前が処理系でサポートされているかを確認するには、 REPLのある処理系ならばREPLに打ち込んで評価させればよい。 これをそのまま行うためExpectを使ってREPLを制御することにした。 check.tclがそれを行う。 check.tclは処理系ごとに実行し、smlnj.txt, poly.txtなどの名前で結果が保存される。

compare.rbが処理系ごとの結果を列として読み込んで横に並べ変える。(この種の処理をしたくなることは多いのだけどいつもコードをたくさん書いている気がする。何かいい方法はないのだろうか) 最後にperlのワンライナーでMarkdown形式に変換する。

こうして得られたのが次の結果である。

結果

https://gist.github.com/tkob/11498120

MLtonやMLKitのようなREPLのない処理系はいまのところ未対応である。 やるとしたらautoconf系のツールで行われているように短いプログラムをコンパイルさせてコンパイルが通るかどうかを見る方法になるだろう。

またこれは64bit版のUbuntuで得られた結果だが、32bit環境などではInt{N}などのサポート状況は変化するだろう。


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

プログラミング言語で演算子というと普通は中置演算子(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) `agoabout` (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な配置に対して用いられるのでちょっと用法が違う。


JavaでVisitorのメソッドのthrows節になんと書くべきか [Java]

Javaでヘテロなリスト、たとえばIntegerかStringのどちらかが入るリストを作っておきたいとする。 これをちゃんと静的に型付けされるように書くとしたらJavaではVisitorを使うしかない。

interface IntegerOrString {
        void accept(IntegerOrStringVisitor visitor);
}

class I implements IntegerOrString {
    private Integer integer;
    public I(Integer integer) { this.integer = integer; }
    public void accept(IntegerOrStringVisitor visitor) {
        visitor.visitInteger(integer);
    }
}

class S implements IntegerOrString {
    private String string;
    public S(String string) { this.string = string; }
    public void accept(IntegerOrStringVisitor visitor) {
        visitor.visitString(string);
    }
}

interface IntegerOrStringVisitor {
    void visitInteger(Integer integer);
    void visitString(String string);
}

これを使うときはたとえば次のようなコードを書く。

public class Main {
    public static void main(String[] args) {
        List<IntegerOrString> list = new ArrayList<IntegerOrString>();
        list.add(new I(123));
        list.add(new S("hello"));

        for (IntegerOrString e : list) {
            e.accept(new IntegerOrStringVisitor(){
                public void visitInteger(Integer integer) {
                    /* 整数だった時の処理 */
                    System.out.println(integer + 1);
                }
                public void visitString(String string) {
                    /* 文字列だった時の処理 */
                    System.out.println(string.toUpperCase());
                }
            });
        }
    }
}

ここまでは(Javaの冗長さ以外は)なにも問題ないと思う。 ところでこのリストに対して行いたい処理がチェック例外を投げる処理だったらどうするか。 例えば出力先が標準出力でなくてファイルだったらIOExceptionをどうにかしないといけない。

IOExceptionをmainで捕捉することにすると、 コンパイルを通すためにはまず匿名クラスのvisitIntegerとvisitStringにthrows IOExceptionと書かないといけない。

しかし継承・実装元が投げると宣言していないチェック例外を継承・実装先クラスで投げることはできないから、 IntegerOrStringVisitorの同名メソッドでもthrows IOExceptionと書かないといけない。 IとSのacceptメソッドでそれらのメソッドを呼んでいるからそこにもthrows IOException、IとSの実装元であるIntegerOrStringクラスのacceptメソッドも同様にthrows IOExceptionをつける。

だけどこれは明らかにおかしい。IntegerOrStringというデータ型は、そのデータにどのような操作がなされうるかとは独立に定義されるはずだ。 データと操作をデカップリングするためにVisitorパターンを使ったのだから。 「このデータに何かする操作はIOExceptionを投げうる」ということをどうやってあらかじめ知ることができるというのだろうか。 IntegerOrStringVisitorの実装クラスが増えるたびにIntegerOrStringインターフェイスまで立ち戻ってthrows節にチェック例外を追加するのはナンセンスだ。

いくつか案を検討してみよう。

案1 visitメソッドで例外処理させる

visitメソッド内で例外処理させることを要件にすれば最初のシグニチャのままでどうにかなる。でもこれは明らかに強すぎる制約で、現実的ではないと思う。

案2 visitメソッドで実行時例外に変換する

visitメソッド内でIOExceptionなどのチェック例外を適当な実行時例外に変換して投げるようにすれば、やはりシグニチャを変えずに済む。 この案の問題点は例外を捕捉する側で「より小さい例外を捕捉する」という原則に沿った例外処理ができなくなることだ。あるいは悪い言い方をすると元の例外を覆い隠す。 例えばFileNotFoundExceptionとそれ以外のIOExceptionで例外処理を変えたかったとしても、 捕捉側で受け取るのは変換後の例外なのでcatch節を分けることができない。 いや、正確に言うとgetCauseを使えば処理を変えることはできるが、どっちにしても普通の素直なtry/catchではできない。

もう一つはチェック例外を実行時例外に変換するのはJavaコンパイラが提供する安全機構を外すことであってよろしくない、 という思想なりコーディング規約なりがあるということだ。

案3 throws Exceptionと書く

最初からthrows ExceptionにしておけばVisitorがチェック例外を投げたとしてもデータやVisitorインターフェイスに後から手を入れなくても済む。 このやり方は例外変換を伴わないので案2の最初の問題も存在しない。

問題となりうるのはやはり思想・コーディング規約上のものだろう。 このようなやり方に対しては、どこからともなくチェック例外ポリスが現れてthrows Exceptionはだめだけしからんと言って笛を吹かれる可能性が高い。

また、throws Exceptionが意外に感染力が高いというのもすこしがっかりする点だ。 IntegerOrStringVisitorの実装で実際にはチェック例外を投げない処理だった場合、visitメソッドのthrows節を消すことはできるのだが、 これはあまり意味がない。 acceptメソッドが引数にとるのはあくまでもIntegerOrStringVisitorインターフェイスのvisitメソッドなので、acceptメソッドからthrows Exceptionを消すことはできない。 だから結局全体としてはExceptionを投げうるコードとみなさなければならず、acceptを呼んでいるメソッドで捕捉しないならばそのメソッドもthrows Exceptionにしなければならない。こうして誰かがcatch (Exception e)と書くまでthrows Exceptionが伝搬していく。

案4 visitメソッドで専用のチェック例外に変換する

最後の案は案2のバリエーションで、例えば次のようなチェック例外クラスを定義する。

class IntegerOrStringException extends Exception {...}

visitメソッドやacceptメソッドのシグニチャはthrows IntegerOrStringExceptionにして、visitメソッドの中でチェック例外が発生するときはこれを生成して元の例外をcauseにする。

e.accept(new IntegerOrStringVisitor {
    public void visitInteger(I integer) throws IntegerOrStringException {
        try {
            ...
        } catch (IOException e) {
            throw new IntegerOrStringException(e);  
        }
    }
    ...

これは例外の捕捉に関して案2と同じ欠点を持つ。一方でチェック例外を実行時例外にロンダリングするわけではない。 また、案3とは異なりExceptionのサブクラスを投げるに過ぎないので例外ポリスをも満足させる。

この種の設計は一般的には「その抽象化に適した例外を投げる」(Effective Java)という考えから行われることがある。 例えばJNDIの実装がファイルを使うにしてもDBを使うにしてもlookupメソッドがIOExceptionやSQLExceptionを投げるのは実装の詳細を曝しすぎているのでNamingExceptionのサブクラスに変換して投げるべきだ、というように。 しかしVisitorの場合、この考えから案4を支持するのは無理がある。Visitorに実装される処理は「そのデータに対する何らかの処理」というだけだ。 これは何か必然性のある抽象だろうか?Visitorパターンを使わなくてすむ言語なら名前を付ける必要すらなかったものだ。

「インターフェイスを定義するときに、どういう実装になるかあらかじめわからないがthrowsをどうするか」というのはVisitorに限らずインターフェイス一般に生じる問題だ。 一般には「その抽象化に適した例外」を投げることにしているのだと思われるが、 それは結局「そのインターフェイス/パッケージ用に新しくチェック例外を定義してインターフェイスの全部のメソッドにthrowsをつけて回る」ということになっていることが多い。 かくしてJNDIのインターフェイスには全部throws NamingExceptioが、JMSのインターフェイスのすべてのメソッドにはthrows JMSExceptionがついている。 それが本当にいい設計なのかはともかくとして、これらのインターフェイスはある種の具体的な処理(名前解決、メッセージング)と結びついているので 「その抽象化に適した例外」を定義したのだと主張することはできる。しかしVisitorは処理自体を切り離したわけだから、具体性のある処理と結びついていない。 (抽象度が上がるほど「例外が表している内容」は苦し紛れになってくる。 例えばjava.util.concurrent.Future#getはExecutionExceptionというチェック例外を投げるが、これは単に任意の非同期処理の中で投げられる例外をラップしているだけだ)

そうして考えると案4は単にコーディング規約を満足させるためだけに不必要な例外クラスを定義したにすぎないと思う。

結局JavaでVisitorをやる場合はコーディング規約がどうこうといわれようとも案3をとり、throws Exceptioの伝搬を受け入れるのが妥当ではないか、と考えている。 この書き方のコードはチェック例外のないJVM言語で実行時に起こっていることと同じ動作をするものでもある。


この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。