Hash λ Bye

https://utky.github.io/ に移行したので今後こちらに記事は追加されません

SMLの関数適用を構文解析する時の問題

StandardML SML Haskell compiler

まだ構文解析器で苦労している。 今回も詰まっているのは構文のconflict。

問題

これが関数適用

app : exp exp

これが二項演算子適用

infixapp : exp vid exp

この時に入力を

x y z

とすると２つの解釈ができてしまうことになる。

((x y) z)

とするネストした関数適用なのか

x y z

とする二項演算子の適用なのかParserが判断つけられない。

前者ならreduceするが後者ならshiftする。 なのでこれはshift/reduce conflictが起きていると言える。 happyはデフォルトでshiftするので二項演算子として解釈される。

これを解消したい。

解決

sml-njやmltonのgrmファイルの定義を覗いたところ

FlatAppExp : exp list

のようなデータコンストラクタを使ってとりあえずシンボルのリストとしていったん読み込んでしまうらしい。 なぜ関数適用と二項演算子適用は全然違う構造にも関わらず峻別せずに扱うのだろうと疑問に思った。

なぜだろう

SMLではfixityを自分で定義して二項演算子を作れる。

左結合か右結合かをどこかのテーブルに保存しておくことになる。(おそらくEnv的なもの？まだそのあたり解らない) こういう動的にassociativityが定義される二項演算子はパーサジェネレータでは扱えないっぽい。

なので一度解析しきってから、後でsanityチェックして弾くっぽい。

解析の途中でこのfixityのテーブルを更新しながら進めば別に解析の完了を待たなくてもいいじゃんとも思った。 けれど、それだとfixityの定義が必ず演算子の使用よりも前に定義済みである必要がある。 それは不便だろう。

ということでFlatなんたらという構造を導入してなんとか解決はできた。

追記

http://dev.stephendiehl.com/fun/008_extended_parser.html

ここを見るとinfix operatorを動的に定義していく方法が提示されているが、やはりparsecだな。ghcはどうやっているのか見てみる必要ありかな。。。

納得いってない

悪手かなと思うのは、こうした構文解析上の問題のために抽象的なデータ構造にコンストラクタを追加しなければならないという点。 せっかくきれいにsyntax objectを定義できたのにノイズが入ってしまうみたいでイマイチだなと思う。

これだと

1 + 2 + 3

みたいな入力は

[ "1", "+", "2", "+", "3" ]

のようにreduceされる。

parsecならこれをexpression builder的なAPIでうまく木構造に変換できるのだが。。。 まあ、部分的にparsec使うのはありかもしれない。

これから

あとはモジュール系の構文解析が作れればとりあえず構文解析のステージは終わりだろう。 と、言いたいところだがshift/reduceやreduce/reduceのconflictがわんさか残っている。

どうしよう。。。問題ないならこのまま進めてしまいたい。 正直conflictの解消法は未だにわかってない。

あとまだわかってないこと。

  • 構文解析終わった後のsyntax objectに位置情報を顕に保存していないけれどtype checkエラーの時に位置情報含めてレポートできるのか？
  • そもそもエラーレポートがすごくわかりにくい。後で苦労するので早めにverboseなレポート出せるようにしたい。

やりながら良かったと思うこと。

  • haskellのhappy使ってるけどmlyaccやyaccととても似ているため他のツールチェイン使った時もこのノウハウは活きるだろう
  • テストはこまめに書いているので「ここまでは動く」という証左が得られる安心感はやっぱり良い。プログラマとしてこの感覚は大事にしたい。

その他近況メモ(ぼやき)

カーネル

詳解Linuxカーネル読んでる。 メモリアドレッシングからいきなりハードル高い。

特にページングテーブルの初期化のところとか全然解らない。

Clojure

Scala勉強しなきゃ、からマッハで脱線してClojureの情報ばかり漁っている。

どっかの記事で「Clojureは大規模プロジェクトになるとメンテナンスが難しくなってきてスケールしない」みたいなこと言ってた。 そうだろうなと思う。 リファクタリングはそれほど気軽にできないだろう。

specが出てきてチェック機構は揃ってきているけれど、 それでもやはり「実行しないと結果が解らない」という制約は残る。

REPLで探索しながら直すべきところは見つけられるよ、という意見もあるかもしれないけれど リファクタリングの過程で影響のあるところ全部を検査する仕組みはやっぱり無いではなかろうか。 というかリファクタリングして壊れたところを機械的に見つける手段が無い、と言うべきか。

Clojureもそうだけど、RubyやPythonやJS使っている人たちどうしているのだろう。素朴に疑問。

とかぐだぐだ言いながらもなんかClojure好きなので勉強を続けてしまう。