Haskellで抽象構文木 (AST) にメタデータを付与する

2018-01-03 / [haskell] [ghc] [compiler] [elm] [sml] [standardml] [parsec]

2018-01-04 追記: ここで全部語り尽くされている気がしたので、Labelling AST Nodes with locations なにもこんなブログ読むことはないのかもしれない。

megaparsecを使って構文解析器を書いている。

構文解析やっているとASTにソースファイルの位置情報とかをメタデータとして乗せたくなるが、 どんな感じで実装するのか調べた。

僕自身はどのアプローチをとるのか決まっていない。

問題

やりたいこと

megaparsec, parsecなどのコンビネータライブラリはジェネレータ系のalex + happyと比べると幾分まともなエラーメッセージを吐くようになっている。(alex + happyがえげつないほどterseなだけ)

しかし、構文解析が終わった後のα変換によるshadowingの回避や型推論のフェーズでコンパイラがエラーを見つけた場合に、 そのトークンの位置が保存されていないと、エラーメッセージとして不親切に思う。

なので、ASTに位置 SourcePos のようなものを乗せたい。

解きたいこと

しかし、単純に既存のデータ構造に埋め込むと、値コンストラクタのArityが変わったり、コンストラクタのパターンが増えたりしてせっかく書いたhspecのテストも盛大に直さなければならない。

それは嫌だ。

僕がやりたいのは 「ASTにメタデータとして位置情報を乗せたい」 のであって 「ASTの意味を変えたい」 訳では断じて無い。 僕がやりたいことを簡潔にデータ型として表現したい。

おい、Haskellお前ならできるはずだろ！？

夢を見させてくれよ！

お前そういうの得意だろ！？

アプローチ

少し既存の構文解析器を調べた。

下記の調査をまとめると。

  1. メタデータを保存するための値コンストラクタをASTのブランチとして定義する
  2. メタデータを保存するラッパーを定義する

の2種類のアプローチを観測した。

1. ASTにブランチを追加するパターン

下記の2言語で発見。

dhall-haskell

Note というコンストラクタをメインのASTにブランチとして定義して、s にメタ情報を格納しているらしい。

-- | \> Note s x ~ e| Note s (Expr s a)

s が位置情報を含んでいる模様。

ASTがプログラミング言語の構文を定義するのだとすると、 こういったメタ情報がコンストラクタに表れるのはやはりノイズでしかないので できれば排除したいなーという思い。

SML/NJ

fixitem というデータ型を定義している

type 'a fixitem = {item: 'a, fixity: symbol option, region: region}

この region というのが場所を保存している。

でそれをASTのコンストラクタに埋め込んでいる。

| FlatAppExp of exp fixitem list (\* expressions before fixity parsing \*)

あるいは位置保存用のコンストラクタを各サブツリーのデータ型に定義している。

| MarkExp of exp \* region (\* mark an expression \*) |

この MarkXXX とつくコンストラクタは全て位置情報を確保しておくためだけにある、 メタな何かだ。

式やパターンなどのASTごとにこういった MarkXXX というコンストラクタを定義している。

これはdhallと同じアプローチのようだ。

2. ASTにラッパーをかぶせるパターン

下記の2言語で発見。

ghc

概ね知りたいことがWikiに書いてあった。

The HsSyn types

ghcマジ天使。

  • SrcLoc というのが位置情報を持っている。

  • SrcSpan というのが位置から位置までのブロックを表している

  • Located e で e の実際のブロックを保存する

    -- | We attach SrcSpans to lots of things, so let's have a datatype for it.data GenLocated l e = L l e deriving (…)type Located e = GenLocated SrcSpan e

ghcではなんらかのASTを構築したら、これを Located で包むことによって、 位置情報を付加している。

この場合、ASTそれ自体 (この場合HsSyn) の定義は変わらないので 関心事は上手く分離されているといえる。

elm-compiler

ghcと同様の方式を選んでいるように見える。

これは式のASTの例だが、

-- EXPRESSIONS type Expr def = A.Located (Expr' def) data Expr' def = Literal Literal.Literal ...

Expr' が実際のAST。( def はbinderっぽいので気にしなくてよし)

それに Located というデータをかぶせている。

これは何かというと、

-- ANNOTATION type Located a = Annotated R.Region a

Located はペイロードとして a この場合は Expr' とともに、Region を持つようになっている。

data Region = Region { start :: !Position , end :: !Position } deriving (Eq, Show)

Region がまさしく位置情報。

ghcと同じアプローチを感じる。

(発展的話題) なんか色々言ってる人がおる

おもむろに怪しい道具 Fix を持ち出す海外勢の様子。

How to work with AST with Cofree annotation?

Adding source positions to AST nodes for free

何やってるのかわからない。

どいつもこいつも Fix 大好きだなおい。 本気で言っているのか。

それは本当にお前たちの問題領域を簡潔に保っているのか。

という疑念が晴れない。 というか、ここにわざわざFreeモナドを導入する必要はあるのか。 ぶっちゃけ使いたいだけじゃないのか。

ダークパワーを使いたくない僕としてはまだこのアプローチにだいぶ抵抗感がある。

どうするどうする

どうしよう。

ASTそのものは定義を変えずにいけるghc方式をとるかもしれない。

だいぶ素人なので詳しい人いたらアドバイスください。。。

まとめ

ASTに位置情報を付与したい場合は

  1. メタデータを保存するための値コンストラクタをASTのブランチとして定義する
  2. メタデータを保存するラッパーを定義する

という方法があるらしい。

(その他、識別子から位置情報を引くハッシュテーブルを作るみたいなのもあった気がする)