hs2bf - すっきり甘さ控えめ
今回は、糖衣構文の除去です。
前回の補足として、
サブセットであることの確認として(厳密にはmain::IO()でない時点でアウトですが・・・)
次のコードがそのままGHCで動作することを目標とします。
interpret :: E -> IO () interpret (Input f)=getChar >>= interpret . f interpret (Output x k)=putChar x >> interpret k interpret Halt=return () main=interpret main' main' :: E
GHCで実行できるならば、hs2bfが丁寧なエラーを出す必要はありません。
これでかなり楽できると思います(何重ものエラーチェックやソースコード位置の保持が不要)。
パーサー
まずはほしい構文/機能を決めます。
- x+yとか書きたい(infixオペレータ)
- 1:2:xsとか書きたい(リストの特別表記)
- [1..]と書きたい(enum式)
- class/instanceはとりあえず要らない(でも簡単にできるなら欲しいかも)
- GADTはいらない(面倒そう)
- (あれもこれも)
結局Haskell98からほとんど減っていません。
そこで素直にHackageのhaskell-srcを使うことにします。
順番を考える
とりあえず保留の機能であとで欲しくなりそうなのは
- class
- module
なので、それが後から実装しやすい構造を考える必要があります。
・・・いろいろ試行錯誤した結果こんなかんじになりました。
なんでdesugarを中途半端に分割しているかというと、ASTのトラバーサルのコードを書くのが面倒だからです。
例えば式を表すHsExpは27個のコンストラクタがあってげんなりします。あぁSchemeがなつかしい。
閑話休題。ここからは、ありきたりなmapの実装の変化を順に見ていきましょう。
map :: (a->b) -> [a] -> [b] map f []=[] map f (x:xs)=f x:map f xs
「浅い」desugar
とにかく特殊構文を減らして次のフェーズが短く書けるようにします。
基本的には[x..y]を(enumFromTo x) yに変換するような、非常にローカルで分かりやすい変換(だから「浅い」)を施すのですが、
例外的にガード構文をcaseで置き換えています(ifはcaseにしています)。
実装は
class WeakDesugar a where wds :: a -> a instance WeakDesugar HsModule where ... instance WeakDesugar Hsなんとか where ...
のような感じです。コードだとWeakになっているあたりにadhocさがにじみ出ているようです。
まだ普通に読めるレベルです。
map :: (a->b) -> ([] a) -> ([] b) map f []=[] map f ((:) x xs)=(:) (f x) (map f xs)
「ちょっと深い」desugar
whereをletに置き換えたりします。
実装は同じような感じですが、さっきのフェーズのおかけでかなり短くかけます。
このフェーズの終わりではこんなかんじです。
map #a0 #a1= case #T2 #a0 #a1 of #T2 f [] -> [] #T2 f ((:) x xs) -> (:) (f x) (map f xs)
モジュール統合
とりあえず何も考えずにくっつけておきましょう。
Preludeのようなもの,Integerの内部的実装を含んだライブラリもここで付けます。
CorePへの変換
CorePはHsModuleと構造は似ているのですが大きな違いがあります。
それは1回のcaseで1重のコンストラクタしか外せないことです。
そこでcaseとHsDeclを変換します。
・・・・・・
結構長くなりそうなのでこの辺で今回は終わりにします。