引き続き Mogul という名前のλ計算インタプリタを作っていこうと思います。
前回、パーザを書いたのでソースコードから抽象構文木を生成することができるようになりました。さっそく抽象構文木をいじくり回して何かしらの処理を実装したいところですが、今回はその前の下準備です。
ソースコード全体は GitHub に置いておきます。
抽象構文木は読みづらい
当たり前なんですが、素の抽象構文木は読みづらいです。例えば ^f x y.``fyx の抽象構文木はこれ。
Ident "f":^ (Ident "x" :^ (Ident "y" :^ (Var (Ident "f") :$ Var (Ident"y")):$ Var (Ident "x")))
実際、内部的にこのようなデータが扱われているとはいっても、デバッグ時にこれをそのまま読みたくない感じはじますよね。
というわけで前回、パーザを書いて文字列から抽象構文木を作ったので、今回は逆をやりましょう。プリティプリンタで抽象構文木を文字列に変換します。
プリティプリンタの要件
と云ってもそこまで難しいことをするつもりはありません。とにかく 文字列化 ができればいいだけです。
Mogul で扱っているいろいろなデータ型を良い感じに文字列化する pp :: a -> String を実装します。
関数 pp に求められる数少ない要件は以下の通り。
Expr,Funcなど様々なデータ型に対して動くようにする- 文字列化した後、再度 抽象構文木にパースすることが可能な、正しい Mogul コードを生成する
- 余計なスペースを省いてコードの密度を高く保つ
というわけでやっていきましょう。
PPrintable クラス
関数 pp で様々なデータ型を文字列化したいので、型クラス PPrintable を定義して pp をそのクラスのメソッドにします。
class PPrintable a where prepara :: a -> [Token] pp :: a -> String pp = render . prepara
この PPrintable クラス、なんだが Show クラスに似ていますよね。実際、役割はほぼ同じです。
ghci などでカジュアルにデータ型を表示するために show の動作はそのまま残しておきたいので、あえて Show インスタンスの独自定義はせずに別のクラスを用意します。
もう一つの特徴として prepara :: a -> [Token] によって一度データ型をトークンの列に変換している点が挙げられます。
Mogul の Expr 型は二分木に似た構造ですが、それをまず平坦な Token の列に変換します。そうすることで隣のトークンを読んで適切な位置にスペースを挿入することがやりやすくなります。
Token 型の定義はこんな感じ、
data Token = Backquote -- "`" | Lambda -- "^" | Dot -- "." | Equal -- "=" | Symbol Text -- 英小文字1文字からなるシンボル | LargeSymbol Text -- 英数字2文字以上からなるシンボル | EOL -- 行端 deriving (Eq) instance Show Token where show Backquote = "`" show Lambda = "^" show Dot = "." show Equal = "=" show (Symbol s) = unpack s show (LargeSymbol s) = unpack s show EOL = "\n"
さて、 PPrintable クラスのメソッドの中でも pp にはデフォルトの定義があります。
pp = render . prepara
まず prepara :: PPrintable a => a -> [Token] を使ってトークンの列に変換して、その後に render :: [Token] -> String を使って文字列に変換します。
render の実装は以下のとおり、
render :: [Token] -> String render [] = "" render (s@(LargeSymbol _) : ps@(LargeSymbol _ : _)) = show s <> " " <> render ps render (s@(Symbol _) : ps@(LargeSymbol _ : _)) = show s <> " " <> render ps render (p : ps) = show p <> render ps
LargeSymbol と LargeSymbol が並んでいるとき、または Symbol と LargeSymbol が並んでいるときに限り間に1つのスペースを挿入しながら文字列として結合します。
それ以外の場合はただトークンを文字列に変換しながら並べていくだけです。
PPrintable クラスのインスタンス宣言
ではそれぞれのデータ型を PPrintable クラスのインスタンスにしていきます。対象となるのは Ident, Expr, Func, (Ident, Func), Context です。
{-# LANGUAGE FlexibleInstances #-} instance PPrintable Ident where prepara = (:[]) . symbol instance PPrintable Expr where prepara = flatten [] instance PPrintable Func where prepara = prepara . body instance PPrintable (Ident, Func) where prepara (v, f) = symbol v : Equal : prepara f instance PPrintable Context where prepara = Data.Map.foldrWithKey (\v f cont -> prepara (v, f) <> (EOL : cont)) []
PPrintable (Ident, Func) に対するインスタンス宣言をする際には FlexibleInstances 拡張 を有効にする必要があります。
補助関数 symbol, body, flatten の定義は以下の通り、
-- | symbol (Ident "x" ) => Symbol "x" -- | symbol (Ident "FOO") => LargeSymbol "FOO" symbol :: Ident -> Token symbol v@(Ident x) | isUniIdent v = Symbol x | otherwise = LargeSymbol x -- | body (Func [Ident "x", Ident "y"] (Var (Ident "y") :$ Var (Ident "x"))) -- | => Ident "x" :^ Ident "y" :^ Var (Ident "y") :$ Var (Ident "x") body :: Func -> Expr body (Func vs e) = foldr (:^) e vs flatten :: [Token] -> Expr -> [Token] flatten acc (e :$ e') = Backquote : flatten (flatten acc e') e flatten acc (x :^ e) = Lambda : symbol x : Dot : flatten acc e flatten acc (Var x) = symbol x : acc
大きな木構造を平坦なリストに変換するという意味で flatten は特に重要です。第1引数はただのアキュムレータなので余り気にする必要はありません。 flatten [] :: Expr -> [Token] をトークンの列を得る目的で使っています。
Expr 以外のデータ型は再帰も含まないシンプルなものなので、よしなにトークン列に変換してあげれば大丈夫でしょう。
使ってみる
という訳で pp を使っていくつかの式を文字列化してみます。
ghci> let Right e = parse expr "" "^xyz.``xz`yz"
ghci> e
Ident "x" :^ (Ident "y" :^ (Ident "z" :^ (Var (Ident "x") :$ Var (Ident "z")) :$ (Var (Ident "y") :$ Var (Ident "z"))))
ghci> pp e
"^x.^y.^z.``xz`yz"
ghci> Right e = parse expr "" "``x `FOO BAR y"
gchi> e
(Var (Ident "x") :$ (Var (Ident "FOO") :$ Var (Ident "BAR"))) :$ Var (Ident "y")
ghci> pp e
"``x`FOO BARy"
ghci> let Right e = parse def "" "````Jxyzw = ``xy``xwz"
ghci> e
(Ident "J",Func {args = [Ident "x",Ident "y",Ident "z",Ident "w"], bareExpr = (Var (Ident "x") :$ Var (Ident "y")) :$ ((Var (Ident "x") :$ Var (Ident "w")) :$ Var (Ident "z"))})
ghci> pp e
"J=^x.^y.^z.^w.``xy``xwz"
pp のおかげで確実に可読性が向上いていますね。良い感じです。
まとめ
というわけで可読性確保のために、云うほど pretty でもないプリティプリンタを書きました。
次回は Expr 型に ド・ブラン・インデックス の概念を取り入れてみようかと思います。
私からは以上です。
