Arantium Maestum

プログラミング、囲碁、読書の話題

HaskellでLisp to LLVM IRコンパイラ　その５　（ LispValの定義、パーサ作成とSSA中間言語への変換）

Haskell 言語処理系 LLVM

LispValという再帰的なデータ型を定義して、まずコードをそのLispValとしてパースする。流れはインタプリタを作った時とまったく同じ。

インタプリタの場合はそこでevalを適用したが、コンパイラの場合はそこからSSA中間言語に変換を加えていく。

LispVal型

まずデータ型の定義：

data LispVal = Number Integer

instance Show LispVal where show = showLispVal

showLispVal :: LispVal -> String
showLispVal (Number n) = show n

まだ非常に機能が制限されていて数字を（別の行にあるなら複数）扱うだけなので、LispValも数字だけ。

パーサ

Parsecを使ってMonad的にパーサを書く：

readLispVals :: String -> [LispVal]
readLispVals input = 
  case parse parseLispVals "lispval" input of
    Left err -> error $ "Error parsing LispVal: " ++ show err
    Right vals -> vals

parseLispVals :: Parser [LispVal]
parseLispVals = endBy parseLispVal (char '\n')

parseLispVal :: Parser LispVal
parseLispVal = parseNum 

parseNum :: Parser LispVal
parseNum = do
  s <- many1 digit
  return $ Number (read s)

parseNum関数にdo記法中毒が現れてる。書き直したい・・・

LispValからSSA中間言語への変換

前回定義した中間言語への変換。

まずは一つのLispValをSSAデータ型へと変換する関数：

lispValToSSA :: [Integer] -> LispVal -> [SSA]
lispValToSSA is (Number n) = [Alloc s, Store s (show n), Load a s]
  where t = concat $ tail $ concat $ [["_", show i] | i <- is]
        s = 's':t
        a = 'a':t

引数が二つある。変換元のLispValとSSA中間言語で変数名に使うための数字のリストだ。その数字のリストをtという"1_2_3"のような文字列に変換していて、tの先頭にスタック変数を表すsか一時変数を表すaをつけて、Alloc、Store、Loadの命令を作成している（その三つを使ってLLVM IRで数字を表現している）

しかしソースには行ごとにLispValが含まれ得るので、実際には[LispVal] -> [SSA]の関数が必要：

lispValsToSSAs :: [LispVal] -> [SSA]
lispValsToSSAs = concat . reverse . zipWith lispValToSSA [[x] | x <- [1..]] . reverse

一番最後の行のLispValから順に変数名用の数字を振りつつ前述のlispValToSSAを適用し、SSA型のリストのリストを最後にconcatでSSA型のリストにしている。

次回

ようやくLispで書かれた（？）ソースからLLVM IRへの変換パスがすべて定義できた。次回はその変換の流れを見ていきたい。

Haskell私的メモ　Monadをリストで探る１

Haskell

今回はHaskell初心者にとって理解が困難だといわれているMonadの話。

駆け足で頑張って抽象的な概念を理解しようとするのではなく、親しみ深い「リスト型」をモナドとして使ってみることで具体的な感覚を蓄積していこう、という考え。

>>=

前回FunctorとApplicativeを見てきた。Monadの概念として追加されるのは本当はこの関数だけ：

>>= :: (Monad m) => m a -> (a -> m b) -> m b

（returnはpureと同義だから無視）

具体的にリスト型で見てみると

>>= :: [a] -> (a -> [b]) -> [b]

となる。「a型の値のリスト」と「a型の値一つを引数にb型の値のリストを返す関数」を組み合わせて「b型の値のリスト」を返している。

例えばこんなリストと、リストを返す関数があったとして：

xs = [0, 10, 20]
f x = map (+x) [1..3]

>>=の挙動というのは：

xs >>= f 
= [1, 2, 3, 11, 12, 13, 21, 22, 23]
= concat [[1,2,3], [11,12,13], [21,22,23]]
= concat $ pure f <*> xs
= concat $ f <$> xs

と、concatと<$>を合わせたものなことがわかる。「リストのリスト」のようにコンテキストがネストしていくのを、ネストするたびに引き上げて元のコンテキストのままに維持する挙動が追加されているのがApplicativeより強力なところ。

モナド則

Monadには>>=とreturnが満たすべき法則が三つある。

return a >>= g = g a
m >>= return  = m
m >>= (\x -> g x >>= h) = (m >>= g) >>= h

return = pureと考えて、最初の二つはリストに関しては比較的わかりやすい。定義と証明を触ってみる。

まずreturn a >>= g：

return a >>= g 
= pure a >>= g
= [a] >>= g
= concat $ g <$> [a]
= concat [g a]
= g a   -- g はリストを返す関数

次にm >>= return。帰納法で証明できた：

m >>= return
= m >>= pure
= concat $ pure <$> m

case []
concat $ pure <$> []
= concat []
= []
= m

case (x:xs)
concat $ pure <$> (x:xs)
= concat $ (pure x) : (pure <$> xs)
= concat $ ([x]) : (pure <$> xs)
= [x] ++ concat $ pure <$> xs
= [x] ++ xs    -- Induction
= x:xs
= m

直観的には

  • returnはリストのネストを一つ増やす
  • >>=はリストのネストを一つ減らす
  • だから統合が成り立つ

というイメージ。

最後の法則は結合律に近くて、リストを返す関数の合成について：

m >>= (\x -> g x >>= h) = (m >>= g) >>= h

case [] 左辺
[] >>= (\x -> g x >>= h)
= concat $ (\x -> g x >>= h) <$> []
= concat []
= [] 

case [] 右辺
([] >>= g) >>= h
= concat $ h <$> ([] >>= g)
= concat $ h <$> (concat $ g <$> [])
= concat $ h <$> (concat [])
= concat $ h <$> []
= concat []
= []

case x:xs 左辺
x:xs >>= (\x -> g x >>= h)
= concat $ (\x -> g x >>= h) <$> (x:xs)
= concat $ (g x >>= h) : (\x -> g x >>= h) <$> xs
= (g x >>= h) ++ concat $ (\x -> g x >>= h) <$> xs
= (g x >>= h) ++ concat $ (\x -> g x >>= h) <$> xs
= (g x >>= h) ++ (xs >>= (\x -> g x >>= h))
= (g x >>= h) ++ (xs >>= g) >>= h  -- Induction

case x:xs 右辺
(x:xs >>= g) >>= h
= concat $ h <$> (x:xs >>= g)
= concat $ h <$> (concat $ g <$> x:xs)
= concat $ h <$> (concat $ (g x):(g <$> xs))
= concat $ h <$> ((g x) ++ concat $ g <$> xs)
= concat $ (h <$> g x) ++ h <$> (concat $ g <$> xs)
= (g x >>= h) ++ h <$> (concat $ g <$> xs)
= (g x >>= h) ++ concat (h <$> (concat $ g <$> xs))
= (g x >>= h) ++ concat (h <$> (xs >>= g))
= (g x >>= h) ++ (xs >>= g) >>= h

証明はできたし直観的にもわかるんだけど、やはり>>=を使う形ではなかなか言語化しにくい法則である。

感想

リストがモナドであることは知られているが、「なぜリストがモナドであるとうれしいのか」はあまり知られていない気がする。

今回いろいろさわってみたが、やはり「なぜリストがモナドであるとうれしいのか」はよくわからなかった。そもそも「リストを返す関数を組み合わせて各ステップごとにフラット化していく」ってあまり使う状況が思い浮かばない。

Applicativeなのがうれしいのはわかるのだが・・・

次回はそこを掘り下げつつ、sequenceやmapMなどの補助関数も使ってみたい。

Haskell私的メモ　FunctorとApplicativeをリストで探る

Haskell

「モナドとはなにか」「Applicativeとはなにか」といった抽象的な共通性の探索からはじめると挫折するのが目に見えているので、いったんそういったことは置いておいて、まずはいくつかの具体的なモナドと戯れて個別に挙動を理解していきたい。そういった具体的な理解からだんだん抽象化が自然と見えてくればしめたものである。

ということで、今回は一番お世話になっている「リストモナド」をFunctor、ApplicativeそしてMonadとして使ってみて理解してみたい。（今回はFunctorとApplicative、次回でMonad）

Functorとしてのリスト

HaskellでFunctorとは以下のように定義されている：

class Functor f where
  fmap :: (a -> b) -> f a -> f b

（実際には他にも$>が定義されているが、fmapを使ったデフォルト定義が存在するので割愛）

さらに、暗黙の了解としてfmapが以下の法則を満たすことが求められる：

fmap id = id
fmap a . fmap b = fmap (a . b)

リストはFunctorとして定義されているし、fmap = mapでFunctorの法則を満たしている。

map id [1,2,3]
= [id 1, id 2, id 3]
= [1, 2, 3]
= id [1, 2, 3]

fmap a $ fmap b [1,2,3]
= fmap a [b 1, b 2, b 3]
= [a (b 1), a (b 2), a (b 3)]
= [(a . b) 1, (a . b) 2, (a . b) 3]
= fmap (a . b) [1,2,3]

実はfmapは(<$>)という同義の二項演算子が存在する。これは(+1) <$> [1..5] = [2,3,4,5,6]のように使える。

Applicativeとしてのリスト

ApplicativeというのはFunctorとMonadの中間にある概念で、Haskellに明確に組み込まれるのは他の二つより遅かったらしい。Applicative Functor with Effectsという論文でApplicativeの概念としての有用性が懇切に説かれている。

今回はひたすらリストをApplicativeとしていじるだけにとどめておく。

Applicativeは

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

が主な機能となる。（実際には他にも<*と*>があるが・・・）

pure

pureは簡単で、ある値をApplicativeのコンテキストに入れる。

x :: [Int]
x = 5

などとすると当然型が合わずエラーになるが、

x :: [Int]
x = pure 5

とすると5がリストというコンテキストに入る、つまりリストの要素となり、x = [5]となる。

<*>

<*>は同一のコンテキストに入っている関数と引数をつないで、結果を同じコンテキストに入れて返す。ごく簡単な例を挙げると：

[(+1)] <*> [1] = [2]

となる。リストに入った関数をリストに入った引数に適用して、リストに入った結果を返す。

引数部分が増えると：

[(+1)] <*> [1..3] = [2,3,4]

となる。これは

(+1) <$> [1..3] = [2,3,4]

と非常に似ている。pureを使って：

pure (+1) <*> [1..3] = [2,3,4]

とするとさらに似ているかもしれない。しかし、ApplicativeがFunctorより強力な理由として、引数が２以上の関数でも簡単に使えるという点がある。

pure (+) <*> [1..3] <*> [10, 20] = [11, 21, 12, 22, 13, 23]

と、引数リストの直積に関数が適用される。

f a b c = a + b + c
pure f <*> [1..2] <*> [1..3] <*> [5,6] = [7, 8, 8, 9, 9, 10, 8, 9, 9, 10, 10, 11]

と、引数が増えても対応できる。理屈としては、一回<*>が使われるごとに：

pure (+) <*> [1..3] = [(1+), (2+), (3+)]

のようにcurryingが起きている。

pure (+) <*> [1..3] <*> [1..3]より(+) <$> [1..3] <*> [1..3]のほうが短いので、実際には後者を使う方が楽。

個人的には複数リストに対する関数適用だと、直積よりもzipWithの拡張版のような挙動が欲しい気がしている。そっちについてもいろいろ調べていて、その話題についてはまた別の記事で書きたい。

次回の記事ではリストをMonadとしていろいろいじってみる。

HaskellでLisp to LLVM IRコンパイラ　その４　（SSA中間言語）

LLVM Haskell 言語処理系

LLVM IRに落とし込む前のステップとして簡略化した独自のSSA中間言語に変換しておく、という話を前回した。

その中間言語の各行を表現するデータ型がこれ：

data SSA = Alloc String
         | Store String String
         | Load String String

Lispと違ってこの言語は再帰的ではない。つまり、一つの命令のなかに他の命令が含まれることはない。なのでこの中間言語は「命令のリスト」つまり[SSA]型をとる。

出力して確認したりしたいのでShow型クラスのインスタンス化しておく：

instance Show SSA where show = showSSA

showSSA :: SSA -> String
showSSA (Alloc s) = "alloc " ++ s ++ "\n"
showSSA (Store s n) = "store " ++ s ++ " " ++ n ++ "\n"
showSSA (Load a s) = "load " ++ a ++ " " ++ s ++ "\n"

手書きで作ったテストファイルをLLVM IRに変換して結果を見たりしたいのでパーサも用意する：

readSSA :: String -> [SSA]
readSSA input = case parse parseSSAs "ssa" input of
  Left err  -> error $ "SSA parse failed: " ++ show err
  Right ssa -> ssa

REPLだとパースエラーもちゃんと処理してエラー表示してまたIOに戻るが、コンパイラなのでパースエラーがあったら例外投げて停止するだけで楽。この段階で型情報にEitherモナドとかいれなくてすむのはありがたい。

parseSSAs :: Parser [SSA]
parseSSAs = endBy parseSSA (char '\n')

parseSSA :: Parser SSA
parseSSA = parseAlloc 
       <|> parseStore 
       <|> parseLoad

parseAlloc :: Parser SSA
parseAlloc = do 
  try (string "alloc")
  skipMany1 space
  s <- parseVar
  return $ Alloc s

parseStore :: Parser SSA
parseStore = do
  try (string "store")
  skipMany1 space
  s <- parseVar
  skipMany1 space
  n <- parseNum
  return $ Store s n

parseLoad :: Parser SSA
parseLoad = do
  try (string "load")
  skipMany1 space
  a <- parseVar
  skipMany1 space
  s <- parseVar
  return $ Load a s

パーサのコードがけっこう無残なことになってる・・・　あと一項命令、二項命令などを関数化してparseBinary Load "load"のようにして定義した方がきれいかもしれない。パーサのすっきりした記述はまだ習得できてないな。

この中間言語からLLVM IRへの変換は単純：

ssasToLlvm :: [SSA] -> String
ssasToLlvm ssas = start ++ (concat $ map ssaToLlvm  ssas) ++ end

ssaToLlvm :: SSA -> String
ssaToLlvm (Alloc s) = "%" ++ s ++ " = alloca i32" ++ "\n"
ssaToLlvm (Store s n) = "store i32 " ++ n ++ ", i32* %" ++ s ++ "\n"
ssaToLlvm (Load a s) = "%" ++ a ++ " = load i32, i32* %" ++ s ++ "\n"

愚直に文字列を吐き出すだけ。しかし文字列作成のコードも無残なことになっている・・・　printf使うか。

次はこの中間言語を、ソースをパースして作ったLispValデータ構造からどう作成するか、の話。

HaskellでLisp to LLVM IRコンパイラ　その３　LLVM IRへの出力（数字の出力）

Haskell LLVM 言語処理系

前回に続いてLLVM IRで数字を返す方法を考える。

比較的簡単でこのような形になる：

%1 = alloca i32
store i32 3, i32* %1
%2 = load i32, i32* %1
  • スタック上に%1という変数をalloca命令で用意する
  • %1に3という値を代入
  • %1に含まれている値を一時変数%2に代入

という流れだ。基本的にスタック上の変数の値は直接関数に渡したり返したりすることはできず、いったん一時変数に代入してから一時変数を引数・戻り値として使う。ちなみに一度代入された一時変数は（ジャンプによってループしない限り）二度と代入されることがない、というのがStatic Single Assignmentの特徴。

LLVM IRで数字を表現するには、スタック変数、一時変数の名前がユニークであることを保証した上で上記の三つのコードを吐き出せばいいということになる。

必要のない部分は全部削除したとはいえ、上記のLLVM表現はまだすこし読みにくいので：

[Alloca "s1", Store "s1" 3, Load "a1" "s1"]

といったSSAデータ型を中間言語として定義して、それを機械的にLLVM IRに変換していくことにする。

次回はこの独自のSSA中間言語の話。

HaskellでLisp to LLVM IRコンパイラ　その２　LLVM IRへの出力（簡単なテンプレート）

Haskell 言語処理系 LLVM

LLVM IRというのはLLVMコンパイラ・フレームワークが定義・利用する中間言語だ。

https://en.wikipedia.org/wiki/LLVM#Intermediate_representation

LLVMフレームワークでは、コンパイラのFront Endはソース言語をこのIRに翻訳することに集中し、Back EndはこのIRを（IR上で）最適化していってからターゲット・アーキテクチャのアセンブリ言語に翻訳する。

なので今回は「Lispフロントエンドを書く」ということになる。

LLVM IRの枠組み

こんなC言語のコードを書いてみる：

#include <stdio.h>

int lispfn() {
    int a = 42;
    return a;
}

int main() {
    printf("%d\n", lispfn());
    return 0;
}

lispfn.cというファイルに保存して、clang -cc1 -O0 -emit-llvm lispfn.cでコンパイルしてみると、以下のlispfn.llファイルが生成される：

@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00"

define i32 @lispfn() {
  %a = alloca i32
  store i32 42, i32* %a
  %1 = load i32, i32* %a
  ret i32 %1
}

define i32 @main() {
  %call = call i32 @lispfn()
  %call1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i32 %call)
  ret i32 0
}

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

いや、嘘だ。もっといろいろとタグ情報などがついたファイルが作成される。実行に必要のない部分は全部削除して読みやすくしたのが上記のコードだ。このままでもlli lispfn.llでちゃんとJITコンパイルされて42と出力される。

このコードをテンプレートとして使って：

@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00"

define i32 @lispfn() {
  ; ここにコンパイルした結果のLLVM IRコマンドを出力
  %a1 = ; 最終的な結果を代入
  ret i32 %a1
}

define i32 @main() {
  %call = call i32 @lispfn()
  %call1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i32 %call)
  ret i32 0
}

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

という形で最終出力の.llファイルを作成することにする。

HaskellでLisp to LLVM IRコンパイラ　その１

Haskell 言語処理系

とりあえず作り始めた。

github.com

基本戦略としては、まずは数値計算だけのコードをLLVM IRに変換するのを目的に：

Lispコード→LispVal型データ構造→SSA IR→LLVM IR

の流れでコンパイルしていく。

長期的にはLLVM IR上でLispValを表すStructを作る必要があるのかなーと漠然と考えているが、まだ先のことである。

かなり長い間、LLVM IRとにらめっこしていて「どうしたらASTからLLVMに変換できるだろう」と悩んでいたのだが、中間言語を間にかませると変換がわかりやすくなった。純粋な形でのAST→SSAの変換と、SSAをLLVM IRに特殊化させる変換をわけて考えるのがポイント。

REPLと違ってチュートリアルを再構築するわけではないので色々と手探りになるがかなり楽しみ。