Haskell+LLVM構成で作る自作コンパイラ

Haskellのパーサコンビネータmegaparsecと、コンパイラ基盤であるLLVMを使って、コンパイラを作ってみます。モチベーションとしてはコンパイラはC/C++を使って作るのが定番ですが、型の恩恵を受けながら開発したいなあということでHaskellでも作れないか調べてみました。

コンパイラ作成の流れ

1. パーサコンビネータのMegaparsecで四則演算のパーサを作成します。
2. LLVM IR構築のライブラリであるllvm-hs-pureでLLVM IRのコードへ変換するコンパイラを作成します。
3. 簡単な式をコンパイルしてLLVMのインタープリタlliで実行します。
4. LLVMのコンパイラllcでアセンブラを生成してgccでバイナリまで生成します。

環境

あらかじめ以下をインストールしておいてください。

• stack 1.9.3
• Haskell 8.6.5
• LLVM 9.0.0

コマンドラインで以下を実行できればOKです。

$ stack --version
1.9.3 x86_64
$ lli --version
LLVM (http://llvm.org/):
  LLVM version 9.0.0
  Optimized build.
  Default target: x86_64-apple-darwin18.7.0
  Host CPU: skylake

プロジェクトの作成

まずは新規プロジェクトを作成していきます。

$ stack init simple-calc
$ cd simple-calc

依存パッケージの追加

プロジェクトを作成したらプロジェクト直下に以下の2つのファイルたありますので、書き換えて依存ライブラリをインストールしてください。

stack.yaml

# 以下、追記
extra-deps:
  - text-1.2.3.1
  - filepath-1.4.2.1
  - megaparsec-8.0.0
  - llvm-hs-pure-9.0.0
  - llvm-hs-pretty-0.6.2.0

package.yaml

dependencies:
  - base >= 4.7 && < 5
  # 以下、追加
  - text == 1.2.3.1
  - filepath == 1.4.2.1
  - megaparsec == 8.0.0
  - llvm-hs-pure == 9.0.0
  - llvm-hs-pretty == 0.6.2.0

$ stack install

これで準備が整いました。
このあとの5つのソースコードを作成します。

• src/AST.hs
• src/Parser.hs
• src/Interpreter.hs
• src/Compiler.hs
• app/SCC.hs

また、replで書いてあるコード対話環境での実行を表しています。
stack ghciで対話環境を始めてください。
ソースコードの変更を反映する場合は:reloadで、対話環境を終了するときは:qでできます。

repl

$ stack ghci
> :reload
> :q

パーサを作る

早速パーサを作っていきます。

1. BNFの定義
2. ASTの実装
3. パーサの実装
4. 対話環境でテスト
5. 簡易インタープリタの作成

の順番で進めます。

BNFの定義

まずはBNFを定義していきます。
今回作るコンパイラはただの四則演算の式だけを受け付けます。
なので下のような簡単なBNFを考えます。
"1"で囲まれた文字が終端記号で、<Expr>が非終端記号です。
その他の部分は正規表現的に表現しています。
（ちなみにこの定義だと右再帰ですね。右から演算が進みます）

<Expr> := <Term> | <Term> <ExprOp> <Expr>
<Term> := <Number> | <Number> <Number>
<Number> := ("1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|"0")+
<ExprOp> := "+"|"-"
<TermOp> := "*"|"/"

ASTの実装

抽象構文木をHaskellのデータで定義すると以下のようになります。
基本的にそのままです。

src/AST.hs

module AST where

data Expr
  = Expr Term ExprOp Expr
  | ExprTerm Term
  deriving (Show)
data Term
  = Term Number TermOp Term
  | TermNumber Number
  deriving (Show)
data Number = Number Integer deriving (Show)

data ExprOp = Add | Sub deriving (Show)
data TermOp = Mul | Div deriving (Show)

パーサの実装

パーサを1から作るのは大変な作業なのでパーサライブラリの力を借りることにします。
Haskellのパーサジェネレータやパーサコンビネータにはいくつかライブラリがあり、もっとも有名なものがParsecです。ParsecはAltJSの一つであるPureScriptのトランスパイラ実装でも使われているライブラリです。

ですがParsecは現在はメンテナンスモードらしく積極的な開発はされていないとのことです。
そこでParsecよりアクティブなMegaparsecを利用したいと思います。
(参考: Megaparsec vs Parsec)

Megaparsecはパーサコンビネータと言って、小さいパーサを組み合わせてより大きいパーサを作るという方式を採用しています。小さいパーサを作りながら進めていきます。
チュートリアルはこちらがわかりやすいです。もし全くPasecのようなパーサコンビネータを触ったことがない場合はこちらを先に一読することをオススメします。

Numberのパーサ

まず、Numberのパーサを作ります。1や100を受理するパーサです。すでにMegaparsecが整数のパーサdecimalを作成してくれているので、それにNumberを被せて返却するパーサを作ります。decimalは負の値は受理しません。

num :: Parser Number
num = Number <$> decimal

Termのパーサ

Termのパーサを作ります。1*2や3/4を受理するパーサです。

先に演算子のみのパーサを作ります。

termOp :: Parser TermOp
termOp = choice
  [ Mul <$ char '*'
  , Div <$ char '/'
  ]

termOpは演算子はそれぞれ*ならMul、/ならDivを返します。choiceは[A, B, ...]の配列の中身を先頭から試し該当するものを選択してくれる関数です。

次にTermのパーサを作ります。

term :: Parser Term
term 
  = try (Term <$> num <*> termOp <*> term) 
  <|> TermNumber <$> num

termはいま作ったパーサをアプリカティブスタイルで適用しているものになります。
A <|> BはAまたはBのコードになることを意味します。ところがAで1文字以上読み進めて（消費して）から失敗するとBを実行する前にエラーでパースに失敗するというハマりポイントがあります¹。try(A)で囲むとAで失敗した場合にBが実行されるようになります。

Exprのパーサ

Exprのパーサを作ります。1+2や1-2を受理するパーサです。exprとexprOpの実装はtermとtermOpと同じですね。

exprOp :: Parser ExprOp
exprOp = choice
  [ Add <$ char '+'
  , Sub <$ char '-'
  ]

expr :: Parser Expr
expr 
  = try (Expr <$> term <*> exprOp <*> expr) 
  <|> ExprTerm <$> term

パーサの仕上げ

最後に一工夫必要です。

exprは文字列の先頭から正しい受理できるところまでしか読み取りを行ってくれません。
最後まで読み取ってくれるようにEOFまで消費するprogを実装します。

prog :: Parser Expr
prog = expr <* eof

それからコメントや空白をスキップするようにしましょう。

scn :: Parser ()
scn = L.space
  space1
  (L.skipLineComment "//")
  (L.skipBlockComment "/*" "*/")

これをトークンごとにlexemeで囲ってあげるとトークンの後ろの空白を消費してくれます。

num :: Parser Number
num = L.lexeme scn $ Number <$> L.decimal

トークンごとにつけても先頭の空白はスキップしてくれないので、以下のようにつけてあげるのも忘れないようにします。

prog :: Parser Expr
prog = scn *> expr <* eof

完成したパーサ

完成したパーサの全体は以下の通りです。

src/Parser.hs

{-# LANGUAGE OverloadedStrings #-}

module Parser where

import Data.Text
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L
import AST

type Parser = Parsec Void Text

prog :: Parser Expr
prog = scn *> expr <* eof

expr :: Parser Expr
expr
  = try (Expr <$> term <*> exprOp <*> expr)
  <|> ExprTerm <$> term

term :: Parser Term
term
  = try (Term <$> num <*> termOp <*> term)
  <|> TermNumber <$> num

num :: Parser Number
num = L.lexeme scn $ Number <$> L.decimal

exprOp :: Parser ExprOp
exprOp = L.lexeme scn $ choice
  [ Add <$ char '+'
  , Sub <$ char '-'
  ]

termOp :: Parser TermOp
termOp = L.lexeme scn $ choice
  [ Mul <$ char '*'
  , Div <$ char '/'
  ]

scn :: Parser ()
scn = L.space
  space1
  (L.skipLineComment "//")
  (L.skipBlockComment "/*" "*/")

試しに実行

対話環境で試してみましょう。

repl

$ stack ghci
> import Text.Megaparsec (parseTest)
> parseTest expr "1"

<interactive>:2:16: error:
    • Couldn't match expected type ‘Data.Text.Internal.Text’
                  with actual type ‘[Char]’
    • In the second argument of ‘parseTest’, namely ‘"1"’
      In the expression: parseTest expr "1"
      In an equation for ‘it’: it = parseTest expr "1"

おっと。パーサはStringではなくTextで定義したんでしたね。
pack :: String -> TextでText型に変換

repl

> import Data.Text (pack)
> parseTest expr (pack "1")
ExprTerm (TermNumber (Number 1))
> parseTest expr $ pack "1*2"
ExprTerm (Term (Number 1) Mul (TermNumber (Number 2)))
> parseTest expr $ pack "1*3+2/4"
Expr (Term (Number 1) Mul (TermNumber (Number 3))) Add (ExprTerm (Term (Number 2) Div (TermNumber (Number 4))))

少し読みづらいですがうまくパースできていそうですね。

簡易インタープリタを実装

ASTができたのでこれをLLVM IRに変換すればコンパイラができますね。
ですが、ここで少し寄り道して実際に計算ができることを確認するためにインタープリタを作ってみましょう。
interpreterの型は単純で式を受け取って数値に変換Expr -> Integerするものとしましょう。
今回のExprとTermとNumはすべてIntegerにできますから評価できるという意味でEvaluableクラスに属させることにしましょう。Evaluableクラスはeval :: a -> Integer関数のみを定義します。

src/Interpreter.hs

module Interpreter (interprete) where

import AST

interprete :: Expr -> Integer
interprete = eval

class Eval a where
  eval :: a -> Integer

instance Eval Expr where
  eval (ExprTerm t) = eval t
  eval (Expr t Add e) = (eval t) + (eval e)
  eval (Expr t Sub e) = (eval t) - (eval e)

instance Eval Term where
  eval (TermNumber n) = eval n
  eval (Term n Mul t) = (eval n) * (eval t)
  eval (Term n Div t) = (eval n) `div` (eval t)

instance Eval Number where
  eval (Number n) = n

> interprete <$> parse prog "" (pack "1*3+2/4")
Right 3

コンパイラを作る

llvm-hs-pureというライブラリを使うとLLVM IRのASTを簡単に構築することができます。
ちなみにllvm-hs-pureはLLVMのC++をラップしたFFIではなく、llvmがインストールされていなくとも利用できます。FFIのllvm-hsというライブラリもあります。ですが、llvmをソースからビルドしないとうまく使えないなどやや環境構築が大変です。

どのようなコンパイラを作るかというと四則演算のASTをLLVM IRのAST(Module)に変換するというものを考えます。LLVMのASTを作ると簡単に具象構文に直すことができます。なのでAST（四則演算）をAST（LLVM IR）に変換するデータ変換器をつくるようなイメージです。

LLVMのモジュールは関数やオペランドなどから構成されますが、今回は単純な式だけを扱うので、ExprをOperandに変換していくということを考えていきましょう。
まずはLLVMのオペランドOperandにできるという型クラスを作成します。

class LLVMOperand a where
  toOperand :: a -> LLVMBuilder Operand

Expr、Term、NumberのそれぞれはLLVMOperandの型クラスのインスタンスにしてみます。

Numberのコンパイル

まずはNumberです。

instance LLVMOperand AST.Number where
  toOperand (AST.Number n) = return (int32 n)

int32 :: Integer -> Operandで単純にIntegerをOperandに変換してくれるという関数です。

その他の単純なオペランドへの変換はLLVM.IRBuilder.Constantで定義されています。

Termのコンパイル

次にTermのインスタンスを定義してみます。

instance LLVMOperand AST.Term where
  toOperand (AST.TermNumber n) = toOperand n
  toOperand (AST.Term n AST.Mul t) = mdo
    n' <- toOperand n -- Operandに変換する
    t' <- toOperand t
    mul n' t' -- mul命令を適用する。適用した結果はOperandを返す。 
  toOperand (AST.Term n AST.Div t) = mdo
    n' <- toOperand n
    t' <- toOperand t
    sdiv n' t' -- 整数の商を返す。

それぞれtoOperandしてからmulやsdivといった命令に適用しています。これで再帰的にOperandに変換していくことができます。
命令mulやsdivはMonadIRBuilder m => Operand -> Operand -> m Operandのような型となっています。

Exprのコンパイル

最後にExprのインスタンスを定義します。

instance LLVMOperand AST.Expr where
  toOperand (AST.ExprTerm e) = toOperand e
  toOperand (AST.Expr t AST.Add e) = mdo
    t' <- toOperand t
    e' <- toOperand e
    add t' e'
  toOperand (AST.Expr t AST.Sub e) = mdo
    t' <- toOperand t
    e' <- toOperand e
    sub t' e'

これはTermと同じですね。

計算結果の表示

計算結果を標準出力に表示する部分について考えます。
printfを使うことにしましょう。

まずはprintf関数を使うことを宣言します。

printf <- externVarArgs "printf" [ptr i8] i32

externVarArgsは可変長引数である外部変数の定義です。引数が固定の場合はexternを使います。
これはコンパイルされると以下のようなコードになります。

declare external ccc i32 @printf(i8*, ...)

printfをリンカが解決してくれます。

それからprintfを呼び出して使うための処理を行います。ちなみにC言語で書くと次のようなコードを書きたいということになります。

int r = 1 + 1;
printf("%d\n", r);

まずは"%d\n"を作ってみます。LLVM IRはやはり低レベルなので文字列を作るのも大変なのですが、これにはglobalStringPtrというぴったりの関数がありました。globalStringPtrの説明には次のように書いてあります。

Creates a series of instructions to generate a pointer to a string constant. Useful for making format strings to pass to printf, for example

直訳すると「文字列定数のポインタを作るための一連の命令を作ります。例えば、printfに渡すフォーマット文字列を作るのに便利です。」というような感じになりますね。

form <- globalStringPtr "%d\n" "putNumForm"

それから関数を呼び出す必要がありますね。関数呼び出しは文字通りcall関数を使います。

call :: MonadIRBuilder m 
  => Operand -- 関数
  -> [(Operand, [ParameterAttribute])] -- 指定した関数に対する引数
  -> m Operand -- 指定した関数の戻り値

基本的には直感的なシグネチャですね。
ParameterAttributeは引数に関する追加情報を与えることができるようです。
パッとみる感じでは厳密な制約を指示するための属性のようです。ここでは何も与えないことにしようと思います。

call printf [(form, []), (r, [])]

いい感じですが、型が合いません。
formはConstant型です。Operand型でなくてはなりません。
実は私はこれにだいぶハマってしましました。なんとかリファレンスを漁ってみるとOperandのコンストラクタにConstantOperandがありました。ConstantはそのままOperandにできるんですね。

call printf [(ConstantOperand form, []), (r, [])]

これで呼び出しOKです。

main関数の構築

ということで最後にmain関数を作ります。

compile :: AST.Expr -> Text
compile expr = ppllvm $ buildModule "main" $ mdo
  form <- globalStringPtr "%d\n" "putNumForm"
  printf <- externVarArgs "printf" [ptr i8] i32
  function "main" [] i32 $ \[] -> mdo
    entry <- block `named` "entry"; mdo
      r <- toOperand expr
      call printf [(ConstantOperand form, []), (r, [])]
      ret (int32 0)

完成したコンパイラ

src/Compiler.hs

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RecursiveDo #-}

module Compiler where

import Data.Text.Internal.Lazy
import Data.Functor.Identity

import LLVM.Pretty
import LLVM.AST hiding (function, value)
import LLVM.AST.Type as AST

import LLVM.IRBuilder.Module
import LLVM.IRBuilder.Monad
import LLVM.IRBuilder.Instruction
import LLVM.IRBuilder.Constant

import qualified AST

type LLVMBuilder = IRBuilderT (ModuleBuilderT Identity)

compile :: AST.Expr -> Text
compile expr = ppllvm $ buildModule "main" $ mdo
  form <- globalStringPtr "%d\n" "putNumForm"
  printf <- externVarArgs "printf" [ptr i8] i32
  function "main" [] i32 $ \[] -> mdo
    entry <- block `named` "entry"; mdo
      r <- toOperand expr
      call printf [(ConstantOperand form, []), (r, [])]
      ret (int32 0)

class LLVMOperand a where
  toOperand :: a -> LLVMBuilder Operand

instance LLVMOperand AST.Expr where
  toOperand (AST.ExprTerm e) = toOperand e
  toOperand (AST.Expr t AST.Add e) = mdo
    t' <- toOperand t
    e' <- toOperand e
    add t' e'
  toOperand (AST.Expr t AST.Sub e) = mdo
    t' <- toOperand t
    e' <- toOperand e
    sub t' e'

instance LLVMOperand AST.Term where
  toOperand (AST.TermNumber n) = toOperand n
  toOperand (AST.Term n AST.Mul t) = mdo
    n' <- toOperand n
    t' <- toOperand t
    mul n' t'
  toOperand (AST.Term n AST.Div t) = mdo
    n' <- toOperand n
    t' <- toOperand t
    sdiv n' t'

instance LLVMOperand AST.Number where
  toOperand (AST.Number n) = return (int32 n)

コンパイラのエントリポイント

最後にコマンドラインからコンパイラを呼べるようmainを定義します。
ちなみにソースファイルの拡張子は.scにしましょう。(simple-calcなので)

app/SCC.hs

module SCC where

import System.Environment (getArgs)
import System.FilePath.Posix (replaceExtension)
import qualified Data.Text.IO as T
import qualified Data.Text.Lazy.IO as LT
import Text.Megaparsec (parse)
import Text.Megaparsec.Error (errorBundlePretty)
import Compiler
import Parser

main :: IO ()
main = do
  args <- getArgs
  let srcPath = args !! 0
  let distPath = replaceExtension srcPath ".ll"
  src <- T.readFile srcPath
  let result = parse prog "example" src
  case result of
    Right ast -> LT.writeFile distPath (compile ast)
    Left e -> putStrLn $ errorBundlePretty e

これで完成で実装は完了です！

コンパイラのテスト

コンパイラのコンパイル

ではコンパイラをコンパイルしましょう。

$ stack build

四則演算のソースファイルの作成

さて、ソースファイルを作成します。

$ mkdir example
$ echo "1+2*3" >> example/ex.sc
$ cat example/ex.sc
1+2*3

LLVM IRへコンパイル

LLVM IRにコンパイルしてみましょう。

$ stack runghc app/SCC.hs example/ex.sc

このようにするとex.llファイルが出力されています。

$ cat example/ex.ll

ちゃんとコンパイルできていますね。

example.ll

; ModuleID = 'main'

@putNumForm =  unnamed_addr  constant [4 x i8] c"%d\0a\00"
declare external ccc i32 @printf(i8*, ...)    

define external ccc i32 @main() {
  entry_0:
    %0 = mul i32 2, 3 
    %1 = add i32 1, %0 
    %2 = call ccc  i32 (i8*, ...) @printf(i8*  getelementptr inbounds ([4 x i8], [4 x i8]* @putNumForm, i32 0, i32 0), i32  %1)  
    ret i32 0 
}

いったんバイナリを作る前にlliコマンドで試してみましょう。

$ lli example/ex.ll
7

おお！うまくいきました。

llcとgccでバイナリの生成

$ llc example/ex.ll
$ gcc example/ex.s -o example/ex

これでバイナリexample/exができました。
実行してみます。

$ ./example/ex
7

ちゃんと実行できてますね！
お疲れ様でした。

まとめ

HaskellとLLVMを使っている資料が少なくとても苦労しました。ですが、ここまで分かれば本格的なコンパイラもしっかり作れそうですね。調べてみた結果、（特に環境構築関連でハマると予想してましたが）思ったよりも割とすんなり動きましたし自分の中ではいい選択肢になりました。

1. @as_capabl さんご指摘ありがとうございます。詳細はこちらを確認ください。 ↩