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を使うことにします。

順番を考える

とりあえず保留の機能であとで欲しくなりそうなのは

  1. class
  2. 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を変換します。
・・・・・・
結構長くなりそうなのでこの辺で今回は終わりにします。