【日記】ElmでElmのコンパイラを作る
🤨🤔😑😨😱ElmでElmのコンパイラを作りたい。以下がリポジトリ。
多分一生完成しないけど…
🤨🤔😑😨😱Cコンパイラ自作をやってて、自分でも言語作りたくなった。
Number型とか実装できないだろうし、完全にElmと同じものは作れないと思う。Cコンパイラ作って実力がついたことを確認するために、できるところまでやってみる。
🤨🤔😑😨😱10/17
構文解析まではelm-syntaxを使う方針に変更した。
このライブラリはほぼelm/parserのみに依存している。またelm-reviewの人が現在も開発している。ありがたく使わせてもらう。
🤨🤔😑😨😱パーサーはこれだけで実装完了。
import Elm.Parser exposing (parseToFile)
import Elm.Syntax.File exposing (File)
import Parser exposing (DeadEnd)
parse : String -> Result (List DeadEnd) File
parse inputs =
parseToFile (String.trim inputs)
Fileは一つのElmソースファイルを抽象構文木に変換したデータ型。抽象構文木のデータ構造を考えなくていいの楽だ。
🤨🤔😑😨😱elm-syntaxのおかげで四則演算と括弧と比較演算までは難なく完了した。
コード生成機の型は以下のようにした。
generate : File -> Result (List DeadEnd) String
Result型でコード生成の失敗を拾うようにした。これでコードは複雑になったが、デバッグは簡単になった。この選択が今後どうなるか。
🤨🤔😑😨😱If文を作っている途中で型推論が必要なことがわかった。If cond then elseでcondがBool型であることと、thenとelseが同じ型であることを判定しなきゃならない。なので、抽象構文木を直接コードに変換するのは無理そう。
🤨🤔😑😨😱10/18
Cコンパイラ自作入門だけの知識では、関数型言語の実装は難しいと判断。MinOcamlも参考にする。
🤨🤔😑😨😱MinCamlは以下の順番でコンパイルするらしい。
- 字句解析：ソースコードを単語(トークン)に分割するプロセス。
- 構文解析：単語(トークン)を組み合わせて構文木や抽象構文木を生成するプロセス。
- 型推論：プログラムのコードを解析し、変数や式の型を推定するプロセス。
- K正規化：プログラムをより単純化・一様化した形（K正規形）に変換するプロセス。
- α変換：プログラムの変数名を一貫性を保ちながら変更するプロセス。
- β簡約：ラムダ計算（関数計算）の一部で、関数適用の部分を実際の引数で置き換えるプロセス。
- ネストしたletの簡約：ネストした（入れ子になった）let式をフラットな形に変換するプロセス。
- インライン展開：関数呼び出しをその関数内部のコードに置き換えて、プログラムの実行速度を向上させる最適化手法。
- 定数畳み込み：コンパイル時に計算可能な式をその結果の値に置き換える最適化手法。
- 不要定義削除：使用されていない定義や変数をプログラムから削除する最適化手法。
- クロージャ変換：自由変数を持つ関数（クロージャ）を、自由変数を引数とする関数に変換するプロセス。
- 仮想マシンコード生成：高レベルなプログラムを低レベルの仮想マシンコードに変換するプロセス。
- 13 bit即値最適化：計算機の即値命令を最大限に利用することでプログラムの実行速度を向上させる最適化手法。
- レジスタ割り当て：プログラムの変数を計算機のレジスタに割り当てるプロセス。
- アセンブリ生成：低レベルな仮想マシンコードを更に低レベルなアセンブリ言語に変換するプロセス。
🤨🤔😑😨😱以下だけ実装できれば最低限動く気がする。
- 字句解析
- 構文解析
- 型推論
- α変換
- クロージャ変換
- アセンブリ生成
字句解析と構文解析はelm-syntaxがやってくれた。
型推論は勉強する。
α変換は深さ優先探索して全てのノードに番号割り当てるだけな気がする。
クロージャ変換はなくてもバグるだけで動く気がする。
アセンブリ生成はCコンパイラ自作入門でやってるから大丈夫な気がする。
🤨🤔😑😨😱型推論に関係ありそうな記事
二番目の記事にMinCamlは単相型？なので簡単と書いてある。
Elmはパラメトリック多相をサポートしているのでMinCamlをパクれるかはわからない。
🤨🤔😑😨😱MinCamlをHaskelで実装した記事。
以下だけ実装したと書いてある。
パース
アルファ変換
型推論
クロージャ変換
コード生成
私の直感は正しかった。
🤨🤔😑😨😱Elm in Elmなるプロジェクトを見つけてしまった。
Elm in Elm自体はElm-Syntaxに依存してないみたい。
ただ、このプロジェクトの創設者がElm-SyntaxのASTに型付けを実装してるっぽい。
さすがにARM64のアセンブリに変換は実装してないみたいなので、一応私の取り組みに新規性はある。
🤨🤔😑😨😱色々調べた結果、型推論とは以下の二つを実装することらしい。
- ASTが問題なく型付できるか検査するプロセス
- ASTを型付きASTに変換するプロセス
型付きASTはASTとは別にデータ型を定義しないといけないのかな。その辺がまだわかってない。
🤨🤔😑😨😱なんかパラメトリック多相型を型推論するためには、難しいアルゴリズム使わなきゃいけないみたいだなぁ。とりあえず単相型で突き進むか。
🤨🤔😑😨😱10/20
elm-syntax-type-inferenceをクローンしてきて読んだ。
elm-syntaxのASTのNodeをNodeV2置き換えて型付けASTに変換するコードっぽい。
🤨🤔😑😨😱Elmのコンパイラも少し見た。
Elmは上記の部分でJavaScriptを生成してる。
🤨🤔😑😨😱型を追加した。（コードは整理必要。）
当分は以下の方針とする。
Elm-SyntaxでASTを取得。
ASTを型付けASTに変換。
型付けASTをアセンブリに変換。
🤨🤔😑😨😱elm-syntax-type-inferenceは少しコード読んでみたけど、まだ完成してない？みたいなので今回は不採用。
私の型付けは、Elm-SyntaxのNodeにtype_という項目を作ってそこに型を詰めてく方針とする。
🤨🤔😑😨😱あと、やっぱりElmでコード書くのは気持ちいいなぁ
型が合えばバグらないし、モナドとかわけわからん話を考えなくてもいい。
欠点は、github copilotのコードの精度が悪いことぐらいか。
🤨🤔😑😨😱10/21
If文を追加した
main = if 1 == 1 then 1 else 2
これが計算できる。
🤨🤔😑😨😱こんな感じの型検証もできる。
4: main = if 1 == 2 then 1 != 2 else 2
^
Problem "Type: Unsupported expression"
素晴らしい
🤨🤔😑😨😱以下のように実装しており、ifにラベル付けができてない。そのため、入れ子のIF文を処理できない。
[ cond
, " cbz x0, else"
, then__
, " b end"
, "else:"
, else__
, "end:"
]
|> String.join "\n"
Cとは違ってグローバル変数が使えないから、ラベルづけは深さ優先探索とかしてやらないといけない。
型推論のタイミングでまとめてやってしまうか。別にアルファ変換を作成するか。は選択できる気がする。
🤨🤔😑😨😱chibiccの場合は関数の引数とローカル変数は一緒にしてlvarに格納し、gen_codeの最初のassign_lvar_offsetsで番号をつけている。
elmの場合はletで定義したものと関数の引数がローカル変数になる。それ以外はgvar扱いになる。
当然letや関数引数に関数がありうるのでC言語とは違う。
🤨🤔😑😨😱MinCamlのアルファ変換は変数に対してgenidで名前付けしている。
let counter = ref 0
let genid s =
incr counter;
Printf.sprintf "%s.%d" s !counter
ocamlはグローバル変数に状態を撒き散らす事ができる言語らしい…
If文に対してラベルづけはしていない。
🤨🤔😑😨😱Elmでnumberのタプルを作るとnumber1やnumber2が現れる。なんで番号がついてるのかわからない。
> (1, 2, 3)
(1,2,3) : ( number, number1, number2 )
> ('1', '2')
('1','2') : ( Char, Char )
調べて記事を書いた。
🤨🤔😑😨😱関数を実装する際に、ローカル変数の情報をNodeに付与しないといけないので、ASTから型付けASTに変換する際にラベル付けも実施するように設計しようと思う。
🤨🤔😑😨😱10/22
無駄な処理があったのでリファクタリングした。
コードが綺麗になったのでラベル付けを実装している。
do文がないからandThenで状態を渡して回るはめになってる。相当コードが読みにくい。
別に型クラスがなくてもandThenをdo文と糖衣構文は作れる気がするけどなぁ
なんでdo文を作らなかったのだろう。
🤨🤔😑😨😱10/23
Let式内でどんな順番でも宣言できるようにするのは結構難しいかも
例えばElmだと以下のコードは変数が循環しているのでコンパイルできないと怒られる。
main = let
a = b
b = a
in
a + b
Elmはコンパイラーで循環を検知しているみたい。
🤨🤔😑😨😱再帰関数書く場合は、普通に書くと循環定義をする。
それは、循環の間にラムダが一つでも入っていればエラーにしないように作ってるみたい。
参考: https://github.com/elm/compiler/blob/master/hints/bad-recursion.md#understanding-bad-recursion
例えば以下みたいな例はコンパイルできるけど、実行時エラーになるとか書いてある。
x =
(\_ -> x) () + 1
（これを試したけど、普通にコンパイルエラーになった。このパターンだけマジックでエラーにしてるんだと思う。）
🤨🤔😑😨😱以下の例はコンパイル通るけど、実行時エラーになった。
g : Int -> Int
g x =
(\_ -> g x) () + 1
a : Int
a =
g 0
10/24
変数宣言の宣言について依存関係をグラフにしてトポロジカルソートして、どの順番で評価するのか計算する必要がある。
例えば下のような処理についてa -> b -> cの順番に評価する必要がある。
module Main exposing (main)
main = let
c = 3 + b
b = 2 + a
a = 1
in
a + b + c
11/3
2日頑張ったが、オフセットの計算と変数の依存関係を同時に実装することができない。これむずい。