僕の考えたさいきょうの抽象構文木データ型

あらすじ

プログラミング言語処理系を作成しようとすると避けては通れないのが、構文木データ型の設計である。
言語処理系では構文解析、アルファ変換、脱糖、正規化など構文木を変換するパスがいくつか存在して、それらの構文ごとにデータ型を設計しなければならない。今回はHaskellの依存型機能を使って、拡張のしやすい構文木データ型の構築方法を示す。

はじめに

今回の記事では単純な型なし関数型言語のインタープリタを実装していく。コード全体はgithubに上げている。
github.com

今回のお題

今回は次のような構文の関数型言語を題材にする。評価戦略は値呼びである。

<expr> ::= <id> | <int_literal> | <bool_literal>
        |  <prefix_op> <expr> 
        |  <expr> <infix_op> <expr>
        | "let" <id> "=" <expr> "in" <expr>
        | "fun" <id> "->" <expr>
        | <expr> <expr>
        | "if" <expr> "then" <expr> "else" <expr>
        | "if" <expr> "then" <expr>
        | <expr> "&&" <expr> | <expr> "||" <expr>
<id> ::= [a-zA-Z][a-zA-Z0-9'_]*
<int_literal> ::= [0-9]+
<bool_iteral> ::= "true" | "false"
<prefix_op> ::= "+" | "-"
<infix_op> ::= "*" | "/" | "+" | "-" | "<" | ">" | "=" | "<>" | "<=" | ">="

素朴な実装

このような構文をHaskellのデータ型で表現する際、最も素朴なのは代数的データ型を用いるものだろう。
例えばこんな感じ。

data Expr = Id Id | IntL Int | BoolL Bool 
          | PrefixOp POp Expr | InfixOp IOp Expr Expr
          | Let Id Expr Expr 
          | Fun Id Expr
          | App Expr Expr
          | IfThenElse Expr Expr Expr
          | IfThen Expr Expr
          | Cond CondOp Expr Expr
data CondOp = And| Or
type Id = String
data POp = Plus | Minus
data IOp = Mul | Div | Add | Sub | ...

ただし、この定義には二つの問題点がある。

どの構文ノードにも共通して存在するデータを埋め込むのが面倒、例えば、構文木ノードにユニークなラベルを貼ったり、ソースコード上での位置を表すデータなどのメタデータを埋め込みたいとき、全てのコンストラクタに書かなければならない。
拡張性に乏しい。例えば"e0 && e1"は"if e0 then e1 else false"の糖衣構文であるので、脱糖後のデータ構造にはそのような構文は許されないが、脱糖後のデータ型でそのことを表現するためにはほぼ同じ代数的データ型を定義する必要がある。コンストラクタの名前を考えるのが面倒だし、名前空間が汚くなる。

僕の考えたさいきょうの抽象構文木データ型

ここで本記事の目的であるデータ型を紹介しよう。
まず、DataKinds拡張を使って構文木のコンストラクタのラベルを表すConstカインドと
そのシングルトン型SConstをGADTとして定義する。

{-# Language DataKinds, GADTs #-}
module Language.ToyML.Syntax.Base where
import Data.Void(Void)
import Data.Kind(Constraint)

data Const = Var | Literal | Infix | Prefix 
           | App | Abs | Let  
           | IfT | IfTE
           | Cond

data SConst (c :: Const) where
    SVar     :: SConst 'Var
    SLiteral :: SConst 'Literal
    SInfix   :: SConst 'Infix
    SPrefix  :: SConst 'Prefix
    SApp     :: SConst 'App
    SAbs     :: SConst 'Abs
    SLet     :: SConst 'Let
    SIfT     :: SConst 'IfT
    SIfTE    :: SConst 'IfTE
    SCond    :: SConst 'Cond

そして構文木のデータ型はこれだ。

data Exp where
    Exp :: WellFormed c Exp arg => SConst c -> arg -> Exp

つまり、構文木はExp op argという二つ組でopはSConst c型、つまりコンストラクタの種類を表している、
一方argの型はこの定義からはわからないが、WellFormed c Exp argという制約がargの型を定めてくれる。
カギはWellFormed c e argという制約にあるわけだが、これはtype familyという仕組みで次のように定義している。

type family WellFormed (c :: Const) e arg :: Constraint where
    WellFormed 'Var e arg     = arg ~ Ident e
    WellFormed 'Literal e arg = arg ~ Literal e
    WellFormed 'Infix e arg   = arg ~ (InfixOp e,e,e)
    WellFormed 'Prefix e arg  = arg ~ (PrefixOp e, e)
    WellFormed 'App e arg     = arg ~ (e,e)
    WellFormed 'Abs e arg     = arg ~ (Ident e, e)
    WellFormed 'Let e arg     = arg ~ (Ident e, e, e)
    WellFormed 'IfT e arg     = arg ~ (e, e)
    WellFormed 'IfTE e arg    = arg ~ (e, e, e)
    WellFormed 'Cond e arg    = arg ~ (CondOp, e, e)

type family Ident e
type family Literal e
type family InfixOp e
type family PrefixOp e

この定義によると、例えばExp SApp argの場合、argは(Exp, Exp)型となり、またExp SVar argの場合はargはIdent Exp型になる。
Ident Exp型がどのような型になるかもtype familyによって定めており、具体的にはStringになるように次のように定めている。

type instance Ident Exp = String
type instance Literal Exp = Lit
type instance InfixOp Exp = Op
type instance PrefixOp Exp = Op
data Lit = CInt Integer | CBool Bool
data Op = Op { headChar :: Char, opName :: String }

この定義に従うと構文解析後のデータとして"正しい"データ構造を表現できている。例えば次のような例があり、間違ったデータ構造はコンパイルエラーとなる。

exp1 :: Exp
exp1 = Exp SVar "x"

exp2 :: Exp
exp2 = Exp SAbs ("x", Exp SApp (Exp SVar "x", Exp SVar "x")) -- fun x -> x x

exp3 :: Op -> Exp
exp3 op = Exp SPrefix (op, Exp SVar "x") 


-- これはコンパイルエラー(前置演算子なのに二つ子のExpを持つため)
-- exp3bug :: Op -> Exp
-- exp3bug op = Exp SPrefix (op, Exp SVar "x", Exp SVar "x")

このパターンで構文木データ型を定義すると共通するデータを埋め込むのも容易である。
例えば、ソースコード上の位置を埋め込みたければ

data Exp where
    Exp :: WellFormed c Exp arg => SConst c -> arg -> SourcePos -> Exp

と変えるだけで良い。

次に拡張も簡単であることを示すために脱糖後のデータ型をこのパターンを用いて定義してみよう。

data Exp where
    Exp :: (WellFormed c Exp arg, Desugared c Exp arg) => 
           SConst c -> arg -> SourcePos -> Exp

type family Desugared (c :: Const) e arg :: Constraint where
    Desugared 'Infix e arg = Impossible 'Infix
    Desugared 'Prefix e arg = Impossible 'Prefix
    Desugared 'IfT e arg = Impossible 'IfT
    Desugared 'Cond e arg = Impossible 'Cond
    Desugared c e arg = ()

これだけである。
先ほど定義したWellFormed c e argという制約に加えて脱糖後にはInfix, Prefix, IfT, Condのコンストラクタが使えないことをDesugared c e argという制約で表現している。
ここでImpossibleという制約があるわけだが、この制約はこのように定義する。

import Data.Void
class Impossible (c :: Const) where
    impossible :: SConst c -> Void

つまりImpossibleは型クラスであり、そのインスタンスは存在しない。したがって、Impossible制約を持つコンストラクタを使うことはできないようになっている。逆にパターンマッチでこのパターンが来たらData.Void.absurd :: Void -> aという最強関数で安全に型を合わせてしまうことができる。

終わりに

今回紹介したパターンを使えばこのように柔軟な型コンストラクタをHaskellでも実装することができる。パターンマッチの部分もなかなか面白いので興味のある人はレポジトリのコードを読んでみてほしい。
github.com