Arantium Maestum

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

Haskell

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

LispValという再帰的なデータ型を定義して、まずコードをそのLispValとしてパースする。流れはインタプリタを作った時とまったく同じ。 インタプリタの場合はそこでevalを適用したが、コンパイラの場合はそこからSSA中間言語に変換を加えていく。 LispVal型 …

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

今回はHaskell初心者にとって理解が困難だといわれているMonadの話。 駆け足で頑張って抽象的な概念を理解しようとするのではなく、親しみ深い「リスト型」をモナドとして使ってみることで具体的な感覚を蓄積していこう、という考え。 >>= 前回FunctorとAppl…

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

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

HaskellでLisp to LLVM IRコンパイラ その4 (SSA中間言語)

LLVM IRに落とし込む前のステップとして簡略化した独自のSSA中間言語に変換しておく、という話を前回した。 その中間言語の各行を表現するデータ型がこれ: data SSA = Alloc String | Store String String | Load String String Lispと違ってこの言語は再帰…

HaskellでLisp to LLVM IRコンパイラ その3 LLVM IRへの出力(数字の出力)

前回に続いてLLVM IRで数字を返す方法を考える。 比較的簡単でこのような形になる: %1 = alloca i32 store i32 3, i32* %1 %2 = load i32, i32* %1 スタック上に%1という変数をalloca命令で用意する %1に3という値を代入 %1に含まれている値を一時変数%2に…

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

LLVM IRというのはLLVMコンパイラ・フレームワークが定義・利用する中間言語だ。 https://en.wikipedia.org/wiki/LLVM#Intermediate_representation LLVMフレームワークでは、コンパイラのFront Endはソース言語をこのIRに翻訳することに集中し、Back Endは…

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

とりあえず作り始めた。 github.com 基本戦略としては、まずは数値計算だけのコードをLLVM IRに変換するのを目的に: Lispコード→LispVal型データ構造→SSA IR→LLVM IR の流れでコンパイルしていく。 長期的にはLLVM IR上でLispValを表すStructを作る必要があ…

`foldr`で`dropWhile`と不動点コンビネータ 補足

以下の記事の補足: zehnpaard.hatenablog.com 式をいじっていて気付いたのだが、不動点コンビネータを使った解は: dropWhile p = foldr (const f) undefined (repeat undefined) where f _ [] = [] f g ys@(x:xs) = if p x then g xs else ys に落とし込め…

Haskellで50行以内のミニマルコンパイラ

こんなツイートが流れてきた: A complete #compiler to x86 in one page for my lecture today. pic.twitter.com/PwFl4V5czy— Joe Gibbs Politz (@joepolitz) 2018年4月11日 元となっているのは"An Incremental Approach to Compiler Construction"という論…

`foldr`で`dropWhile`と不動点コンビネータ

前回のブログの問題元は今は亡き?Monad.Reader第6号の"Getting a Fix from the Right Fold"という記事。 私が考えた答えの「失敗例」は出てくるけど、パターンマッチを使わないで遅延評価が無限リストにも効く解は出てこない。 しかし別解は非常にエレガン…

`foldr`を使って`dropWhile`を定義する

Haskellの高階関数のfoldrでdropWhileを定義せよ、という問題を見たのでやってみる。 foldr foldrの定義は以下のとおり: foldr :: (a -> b -> b) -> b -> [a] -> b foldr f e [] = e foldr f e (x:xs) = f x (foldr f e xs) 「わかってるねんで?foldrがred…

HaskellとParsecでLisp REPL その8(変数定義)

今回の変更 github.com 「ユーザによる変数定義」機能を追加する。 これはかなり大きな変更で、変数の内容を保持・評価するために、変更可能な「状態」を導入する必要がある。 Haskellだと状態をStateやSTモナドで管理することも可能(らしい)のだが、基本…

HaskellとParsecでLisp REPL その7(if構文)

今回の変更 github.com 条件分岐のための構文を追加。 (if a b c)という式は、まずaを評価し、もし真ならbを、偽ならcを評価してその結果が値となる。 bとcのどちらかひとつしか評価されないのが重要なので、関数ではなく構文として定義。 実装としてはeval…

HaskellとParsecでLisp REPL その6(数値比較と論理演算)

今回の変更 github.com 前回Bool値を定義できたので、=、/=、<、>などやand/orを実装する。 Functions Functionsモジュールのprimitivesにどんどん追加していく: primitives :: [(String, [LispVal] -> LispVal)] primitives = [ ... ("=", numBoolBinOp (=…

HaskellとParsecでLisp REPL その5(Bool型の追加)

今回の変更点 github.com ブール値の追加。データ型とパーサの拡張のみ。 データ型 data LispVal = Atom String | List [LispVal] | Number Integer | Bool Bool ちゃんとshowできるようにしておく: showVal (Bool True) = "#t" showVal (Bool False) = "#f…

HaskellとParsecでLisp REPL その4(四則演算)

今回の変更点 github.com ついに四則演算の実装。入力をそのまま返すのではなく、入力を評価・変換して出力するようになり、「ちゃんとしたREPL」にちょっと近づく。 データ型とパーサ 今回は変更なし。四則演算ならAtom、List そしてNumber型だけで十分。演…

HaskellとParsecでLisp REPL その3(Number型の追加)

今回の変更点 github.com REPLで数字を入力するとパースエラーになる。Atom、Listに続いてNumberもパースしデータとして扱えるようにしたい。 LispValにNumber型を追加 LispValに新たにNumber型を定義し、Haskellの整数を保持させる: data LispVal = Atom S…

HaskellとParsecでLisp REPL その2(Listも使えるREPL)

LISPとはそもそもLISt Processingの略なので、リストを全く扱えない状態からいち早く脱却したい。 というわけで次はリストの実装。ユーザから(a1 a2 a3)といった文字列を受けとり、List型として表現できるようにする。 gistからちゃんとしたgithub repoに変…

HaskellとParsecでLisp REPL その1(Atomをパースし表示するREPL)

ここ一週間ほどHaskellを試しがてら、以下のチュートリアルをいじっていた: Write Yourself a Scheme in 48 Hours - Wikibooks, open books for an open world まずは全部通しで実装してみて、その後コードをいろいろ書き換えたり。 このチュートリアル、非…

Thinking Functionally with Haskell勉強メモ: 第7章1 メモリ、計算量、`seq`

Thinking Functionally with Haskell全12章の折り返し地点に到達。第7章は最適化に関する話題。 メモリと計算量のトレードオフ Haskellの評価戦略は完全にナイーブではない: sqr (sqr (3+4)) = (sqr (3+4)) * (sqr (3+4)) = ((3+4) * (3+4)) * ((3+4) * …

Thinking Functionally with Haskell勉強メモ: 第6章問題4

Exercise K 第一部 takePrefix pをリストxsに適用すると、xsの頭から連続してpを満たし続ける最も長いセグメントを返す。 takePrefix :: ([a] -> Bool) -> [a] -> [a] takePrefix nondec [1, 3, 7, 6, 8, 9] = [1, 3, 7] -- リストの先頭から上がり続ける最…

Thinking Functionally with Haskell勉強メモ: 第6章問題3

Exercise J Maximum Subsequence Sumが以下のように定義されている: mss :: [Int] -> Int mss = maximum . map sum . subseqs subseqs :: [a] -> [[a]] subseqs [] = [[]] subseqs (x:xs) = xss ++ map (x:) xss where xss = subseqs xs より効率のいい定義…

Thinking Functionally with Haskell勉強メモ: 第6章問題2

Exercise F 第一部 任意の有限リストxsについて、以下の等式が成り立つことを証明せよ: foldl f e xs = foldr (flip f) e (reverse xs) 帰納法で解く。 Case [] 左辺 foldl f e [] = {foldlの定義} e Case [] 右辺 foldr (flip f) e (reverse []) = {revers…

Thinking Functionally with Haskell勉強メモ: 第6章問題1

Exercise A 自然数が以下のとおりに定義されている: mult :: Nat -> Nat -> Nat mult Zero y = Zero mult (Succ x) y = mult x y + y mult (x+y) z = mult x z + mult y zを証明せよ: case 0 左辺 mult (x+0) z = {x+0 = x} mult x z case 0 右辺 mult x z…

Thinking Functionally with Haskell勉強メモ: 第6章4 Maximum Segment Sum

第6章の最後はJohn BentleyのProgramming Pearlsに出てくる「Maximum Segment Sum」を今までのような式変換と証明で解く、という演習。 Maximum Segment Sum問題 あるリスト(は整数)の中にある連続部分の和の最大値を求める関数mssを定義せよ ただし空の…

Thinking Functionally with Haskell勉強メモ: 第6章3 foldlとscanl

foldl関数 foldrに似たfoldl関数を定義したい。挙動は以下のとおり(@は任意の演算子): foldr (@) e [a, b, ... y, z] = (a @ (b @ ... (y @ (z @ e)))) foldl (@) e [a, b, ... y, z] = (( ... ((e @ a) @ b) ... @ y) @ z) lisp系やpythonでいうところの…

Thinking Functionally with Haskell勉強メモ: 第6章2 foldr

foldr関数 sum、concat、filter、mapは似ている。 リストを受け取る 空リストが停止条件 (x:xs)が引数の場合、(mapやfilterの場合は何か関数適用した)xと、xsに対して再帰的処理した結果とを、なんらかの方法で結合する。 そして例えばsum (xs ++ ys) = su…

Thinking Functionally with Haskell勉強メモ: 第6章1 数学的帰納法による証明

第6章は証明について。まずは数学的帰納法による証明を説明し、それを元にfoldl、foldrといった高階関数の性質を証明し、今後は個別の処理について証明するときの論理をfoldlとfoldrの性質を使って簡略化・普遍化する。 今回は数学的帰納法の話。 自然数 数…

Thinking Functionally with Haskell勉強メモ: 第5章問題

Exercise A Matrix Intのすべての要素に1を足す関数: addOneToAll = map (map (+1)) Matrix Intのすべての要素の和: sumAll = sum . sum sum :: Row Int -> Int sum [] = 0 sum x:xs = x + sum xs 二つのMatrix Intの各要素を足す関数: addMatrix :: Mat…

Haskellと圏論ノート:Haskと型と関数と関手

Thinking Functionally with Haskellがすこし進んできたので、ちょっと今まで出てきた概念と関連するところまで圏論について調べてみた。まごうことなき私的勉強メモ。 圏Cは以下の三つの要素をあわせた概念: Object(対象)の集まり Cに含まれる対象間のmo…