Hytl開発日誌

todo

syntaxを考える

テスト

残りの型のtypeinferを実装する

エラーしょり

コンパイラ実装

コンパイラにtypeinferを組み込む

デバッグのために任意の場所でEnvを見れるようにできるとかなり楽なんだが..

現状1引数関数定義にしか対応していない

testに落ちているやつを実装する

bugsの修正

ここまでくればfibが実装できる気がする

エラー処理

型シグネチャのパース

型のテスト追加

listのtypeinfer

フラグがあるように見えてしまう

インタプリタのエラー処理

いちいち落とさない

bugs

reduce/reduceがある

いつでもできること

テストケースの追加

リファクタ

repl, typeInfer

35日目

todos

Expを実装

リファクタj

Expの細かいところを修正

型推論器、忘れているので思い出したい

そしてリファ蔵

Exp以外のものを実装

34日目 2020/9/30

ドキュメントに軽くメモった

evalとtype共通のEnvironmentを作った

33日目 2020/9/28

git hooks追加した

type inferのテストケースを追加

32日目 2020/9/18

前回のcommitでテストが落ちるようになってた。

commitする前にテスト走らせたいな..

31日目 2020/8/19

30日目 2020/8/9

VSCodeのHaskellのLanguage Serverが自動でアップグレードしてめちゃくちゃ快適になった

最終的にけっこう妥協した

以下のような関数定義は現時点でサポートしない

code:hytl

f true = .. -- 引数にBool値

f 1 = .. -- 引数に数値

f "hoge" = .. -- 引数に文字列

これは型検査器の仕事かな

視覚的に問題なのか

全然進まないのでいったんevalやる

reduce/reduceのエラーがあるので早めに直さないといけない

やっとconsの関数定義ができるように成った

https://gyazo.com/5014f6a2463826dd3550b2c1681a1bf1

29日目 2020/8/5

evalのテストを書けるとこまで書いた

Testのファイルの分け方がわからない

というよりもmoduleとしてimportするべきなのか、そのへんがわからん

関数適用のリストのparserができない

関数適用のリストのparserとコンフリクトしているのが原因

code:y

28日目 2020/7/19

lexer & parserのテストを修正した

関数の引数に当たる部分のASTを少し拡張した

27日目 2020/7/2

セミコロンをやめた

多分このままだとファイルを読み込んで実行するときにエラーになる

parserのコンフリクトの消し方がわからない..

26日目 2020/6/20

code:hytl

hytl> 1:2:3:[];

関数内で関数を呼び出せなくなっていたので修正した

次は、↓を実行できるようにする

code:hytl

head (x:xs) = x;

LambdaのASTを変えないといけない

引数はStringだけなく色々取りうる

code:hs

f [] = []

f x = [] -- これがString

f (x:xs) = []

parserのstrListとlistのところ、ほとんど同じなんだが、多相っぽくできないのか？

Happyの話

parseまではできるようにしたが、実行はまだできない

25日目 2020/6/11

リストのevalを作ろうとしているがevalの返り値がIntegerじゃ無理じゃん

だからと言ってむやみにStringにはできない

evalの返り値を使って演算をしてる箇所もあるので

EvalでIntegerにする、というよりは簡約する、というイメージで実装すればいけるのかも

表現力の高いExprからより簡素な型EvalExprなどに変換する

とりあえずListをインタプリタに出力するところまでできた

todo

ライフゲームに必要な機能を調べる

24日目 2020/5/21

だいぶ日が空いた。何しよっかなーになっている

リストを追加した

一応trelloは並び順が優先順位にしているつもり

テスト、エラー処理に加えて、ちょっとevalでできることを増やしたい気持ちになってきた

目標3を開始する

リストとその便利関数、テストを作りながらエラー処理を書こう

evalにエラー処理を入れよう

replで変な構文を入力したときに落ちたりしているがそのへんを消す感じにするのか？

23日目 2020/5/12

良い感じのテストのことを考えていたり、理論の本を読んだりしていて全然進んでいない

良い感じのモナド設計論を知りたい

いったん1つ目のテストケースを書いた

次はこれのリファクタと他のテストケースの追加とHspecもうちょい調べる

22日目 2020/5/1

もしかしてStateモナドってreplにしたらリセットされるのか？なんで？？

これをIORef & Readerにするべきかどうかは微妙

そもそもこういうデバッグをreplでするものか感があるので。

なので普通にテストを書けば良いという感じもある

21日目 2020/4/28

TypeInferたぶん実装おかしいんだが、まずReplを動かせるようにしたいな

インタプリタ的に環境を更新しながら型推論をする過程と、

ProgramやStmtをdoInferできる状態にまずしたい

一旦Replで型を表示できるようになった

20日目 2020/4/22

TypeInferのリファクタをした

envとか持ち回っているの嫌なのでStateに閉じ込めた

TypeInferクラスの多相の持ち方をEvalに合わせよう

Stmtなどが実装されていないのでreplがエラーになる

todo

replのところの構文も考え直さないといけない

開いているタブを消化する

19日目 2020/4/20

型推論器を作り始めた

どうやって既存のreplに組み込もうか

OCamlみたいに1行実行する毎に型を表示するとか

コンパイラにも組み込まないと行けない

18日目 2020/4/9

関数定義と関数呼び出しをコンパイルした

案外あっさり出来た

演算子がおかしいのが原因かわからないがfibがparse errorになるようになった😢

やっぱテスト書かないとな..

修正した

現状

if文が正しく動かない。それ以外は一応動いている

なのでfibは動かない

コンパイラを再開するときにすること

関数宣言、関数呼び出しのLLVM上での設計を考え直す

if文を実装する

fibを動かす

コンパイル時計算になっているので、IOをサポートすると動かなくなるはず

これはいつか修正しよう

型システムを実装していこう

一時保留の理由をメモしておく

if文以外のコンパイルが一応動いている状態

Haskellの処理系に頼ることでevalとほぼ同じ実装で動いていた

しかしif文を実装するときに、これではうまく動かないのでは？ってなった

なので、if文を実装する前に、まず関数宣言と関数呼び出しを修正する必要がある

無理やりすすめることはできるが、syntax的に微妙なので型システムを書いたときに大幅な文法の変更が起こりそうな気がした

そのときに修正だるくね？となったので一旦保留して型が出来てから再開しようという気持ちになった

17日目 2020/4/3

ASTを分割して、ExpとStmtとProgramにした

とりあえずセミコロンをサポートした

これによってコンパイラでも改行を扱えるようになった

こういうファイルのコードが動く

code:hytl

x = 3;

x * 3

しかし、セミコロンは個人的にはあまり好きではないので、代わりに改行を扱えるようにしたい

16日目 2020/4/1

AssignとVarをLLVMにコンパイルできるようになった

軽くまとめよう

しかし、改行をサポートしていないので実際に試せていない

code:hs

data GenState = GenState { table :: Map String Operand}

type CodeGen a = IRBuilderT (ModuleBuilderT (State GenState)) a

run :: CodeGen a -> IRBuilderT (ModuleBuilderT Identity) a

run r = undefined

code:hs

compile expr = ppllvm $ evalState

(buildModuleT "main" $ function "main" [] i32 $ \_ -> do

r <- toOperand expr

printf r

ret (int32 0)

)

emptyCodegen

15日目 2020/3/29

llvm-hsをdownloadした

14日目 2020/3/21

CLIを修正した

結局サブコマンドを使うことにした

最初はこんな感じにしたかったが、わからなかった

そもそもこれが、シェル的に正しいものなのかわからないので、サブコマンドを使った

再帰的なsumを実行できるようになった

code:hytl

sum = n => if n == 0 then 0 else n + sum(n-1)

13日目 2020/3/16

四則演算をコンパイルできるようにした

ファイル名の拡張子を変更する

Haskell実装でLLVMを使っているので参考になりそう

ドキュメントやコマンドを少し修正した

TextとString間の変換に手間取った

正解はData.Textのunpack関数を使う

Add, Mul Subなどに修正した

12日目 2020/3/13

どうやらReaderTとIORefを使うと良いみたい

11日目 2020/3/12

ReaderTモナド変換子を導入した

と思ったが、ムリなのでStateモナドにしたが、ムリなのでIORefに戻ってきた

Haskellだとどう書くのかわからんがこういうノリでテストを書きたい

code:ts

const testCases = [

{

eval: 2,

compiled: 2

},

{

eval: 2,

compiled: 2

}

];

testCases.map(t => lexParTest(t)) // lexAndParse(input) === ast

testCases.map(t => evalTest(t)) // eval(ast) === eval

testCases.map(t => compiledTest(t)) // compile(ast) === compiled

単体テストも結合テストもできる

考えられる問題点

どこでテストが死んだのかわかりにくい

10日目 2020/3/8

lookupはkeyが同名の場合は、先頭に近いほうが返される

以下の書き方だとif/then/elseを全て評価してしまうので、再帰ができない

停止しないから

code:hs

eval (If b t e) env = do

cond <- eval b env

thn <- eval t env

els <- eval e env

return $ if cond == 1 then thn else els

なのでこう書き換える(雑)

条件がtrueのときは、then節だけ評価するようにする

code:hs

eval (If b t e) env = do

cond <- eval b env

if cond == 1 then eval t env else eval e env

階乗関数が動いた！！

最小の目標を達成した

https://gyazo.com/5913ee1dfc124275fad6b9a82544530e

9日目 2020/3/6

関数呼び出しの括弧などの少しの修正

タスク管理のためにTrelloを作った

軽い気持ちでやっていく

今から追加しようとしているその記号はどの優先順位に置けばよいのか

そのときにどういうコーナーケースを考えればいいのか

left,rightの差など

これで階乗を求める関数のパーツは揃った

しかし、関数の中で関数が呼べない

code:hytl

g = x => x + 1

f = x => g(x)

f(3) // 本来なら4

できない

変数名がかぶっていると無理になる

code:hytl

g = x => x

f = x => g(x)

f(1)

// できるようになった

できる

code:hytl

g = x => x + 1

f = y => g(y)

f(1)

code:hytl

g = x => 1

f = x => g(1)

f(1)

できない

code:hytl

x=1

f=x=>x+1

f(x)

できる

code:hytl

f=x=>x+1

x=1

f(x)

あ、これ、めっちゃシンプルになる

たぶんbindVarsの呼び出し時に名前解決をしないといけない

そもそもbindVarsの実装内容をよく理解していので理解しよう

できるだけわかりやすい形式に書き換えると以下のようになる

code:hs

bindVars bindings envRef = do

env <- readIORef envRef

r2 <- extendEnv bindings env

newIORef r2

where

extendEnv bindings env = do

r <- (mapM addBinding bindings)

return $ env ++ r

addBinding :: (String, Exp) -> IO (String, IORef Exp)

addBinding (var, value) = do

ref <- newIORef value

return (var, ref)

liftMを理解するために、モナド変換子を一からやりたくなるが、長いのでいったんこの目的を果たすことに集中する

8日目 2020/2/18

関数呼び出しのparserとevalの実装をした

現状の関数定義でできないところ

関数1の中で、外部で定義した関数2、を呼べない

複数の引数を取ることができない

evalとreplをローカル関数で定義し直した

7日目 2020/2/16

Evalが動いた

変数代入、呼び出し、関数定義

IORefの理解→最小のevalの構成→replの修正

の順番でやったらできた

今まではこれらを一緒にやろうとして躓いていた

evalの理想値を定める

code:eval

input -> output

0 -> 0

1+1 -> 2

x=9 -> 9? x=9?

x -> 9

f = x => x + 1 -> -1?

f 3 -> 4

簡約しきってから保存するものでは？

ASTのまま辞書に登録するの不自然な気がする

呼び出すごとに計算しないといけなく成るよ

関数ならこっちのほうが自然だったりする？

6日目 2020/2/12

CLIのoptionを直した

Replリファクタをした

そうか、ASTを作ること、と、Evalを作ること、は完全に分離した作業なのか

なのでEvalの最初の一歩で苦しんでいるが、いったんここは置いておいてASTだけを作っていくのも手としてはあり

Evalの返り値の型がIntなのはたぶんよくない。

しかもここの型が変わればRepl.hsの中の関数の型もリファクタも免れない

LambdaのASTを定義してASTを出せるようになった

code:hytl

// 元のイメージ

// 理想

// 現状

Lambda String Exp

後で直す

https://gyazo.com/88a993512d7a67a00d648d98aca22ce1

https://gyazo.com/f968de3850dcd1d33aa320aaba3fc8af

5日目 2020/2/7

READMEを更新した

replの使い方

start用のスクリプトを用意した

が、ループしないのと、cliのoption無しがきいてないっぽい

ので直す

あと、変数代入のコードがまだ

4日目 2020/1/19

REPLを作った

オプションでASTを表示するモードと、評価値を表示するモードを切り替えたい

https://gyazo.com/48de8000b1a4445aaaec24ff79ad3ce8

3日目 2020/1/18

何のためにIORefやSTRefを使う必要があるのかわからなくなったが、

たぶん

2日目 2020/1/14

優先順位とかカッコとか、地味に面倒なのでいったんあとまわしでもいいかな

とりあえず関数を作るところまでやってから整備していきたい

というか、変数も今すぐに必要なわけでもないので先に関数をやるか

これを動かせるようにする

code:hytl

add x y = x + y

ASTの定義に迷ったらLispとか見たら耐える、というのありそう

よくわからんのでまずは引数は一つ固定で作る

関数定義と関数呼び出しのparserまで作った

型がすごい雑なので修正しないといけない

これが果たしてHaskellらしいやりかたなのかは疑問なので書き直すかもしれない

1日目 2020/1/13

Haskellのモジュールシステムに少しハマった

乗算、除算と、取り急ぎのevalを作った