プログラミング言語をつくっている

去年の夏頃からプログラミング言語を作っています。

let
  extern print_int : Int -> Unit = "print_int"
  extern newline : Unit -> Unit = "newline"
  fun fib(n : Int) : Int =
    if n <= 1
    then 1
    else fib(n - 1) + fib(n - 2)
  fun fib_loop(n : Int) : Unit =
    let val unused:Int = fib(30)
    in if n <= 0
       then print_int(fib(0));
            newline()
       else print_int(fib(n));
            newline();
            fib_loop(n - 1)
    end
in
  fib_loop(30)
end

こんな感じのllvm irが吐かれて、

; ModuleID = 'examples/fib.mlg'


declare external ccc i8* @GC_malloc(i64)

declare external ccc {} @newline({}, i8*)

declare external ccc {} @print_int(i32, i8*)

define external ccc {} @"fib_loop.4:(Int -> {})"(i32 %n.5, i8* %captures){
; <label>:0:
  %"unused.6:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 30, i8* undef)
  %"$k.16:Bool" = icmp sle i32 %n.5, 0
  %resultptr = alloca {}
  br i1 %"$k.16:Bool", label %then, label %else
then:
  %"$k.19:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 0, i8* undef)
  %"$_.18:{}" = call ccc {} @print_int(i32 %"$k.19:Int", i8* undef)
  %valdec = call ccc {} @newline({} undef, i8* undef)
  store {} %valdec, {}* %resultptr
  br label %end
else:
  %"$k.23:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %n.5, i8* undef)
  %"$_.22:{}" = call ccc {} @print_int(i32 %"$k.23:Int", i8* undef)
  %"$_.24:{}" = call ccc {} @newline({} undef, i8* undef)
  %"$k.26:Int" = sub i32 %n.5, 1
  %valdec1 = call ccc {} @"fib_loop.4:(Int -> {})"(i32 %"$k.26:Int", i8* undef)
  store {} %valdec1, {}* %resultptr
  br label %end
end:
  %valdec2 = load {}, {}* %resultptr
  ret {} %valdec2
}

define external ccc i32 @"fib.2:(Int -> Int)"(i32 %n.3, i8* %captures){
; <label>:0:
  %"$k.7:Bool" = icmp sle i32 %n.3, 1
  %resultptr = alloca i32
  br i1 %"$k.7:Bool", label %then, label %else
then:
  store i32 1, i32* %resultptr
  br label %end
else:
  %"$k.10:Int" = sub i32 %n.3, 1
  %"$k.9:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.10:Int", i8* undef)
  %"$k.13:Int" = sub i32 %n.3, 2
  %"$k.12:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.13:Int", i8* undef)
  %valdec = add i32 %"$k.9:Int", %"$k.12:Int"
  store i32 %valdec, i32* %resultptr
  br label %end
end:
  %valdec1 = load i32, i32* %resultptr
  ret i32 %valdec1
}

define external ccc i32 @main(){
  %main = call ccc {} @"fib_loop.4:(Int -> {})"(i32 30, i8* undef)
  ret i32 0
}

llvmの最適化をかけたりなんだりゴニョゴニョすると実行可能ファイルができます。

詳しくはREADMEを読んで下さい。Githubで公開しています。

github.com

Malgoの話

Malgoはコンパイラの動作について学習するために作っている俺言語です。文法はSMLベース（というか虎本のTigerベース）で、タプルや無名関数リテラルがあります。言語的にはいわゆる単純型付きラムダ計算のシンプルな実装で、多相型もコレクションもまだ無いので自明でないことをするにはちょっとコツが要ります。

Haskellの話

実装にはHaskellを使いました。選考理由は

ASTとか扱うのに代数的データ型があると嬉しい
良い感じのllvm バインディングがある（https://github.com/llvm-hs/llvm-hs）
stackとかでてきて環境構築が楽になった
慣れてる

ぐらいです。OCamlとどっち使うか長いこと悩みましたが、これは個人的には自転車置き場の議論だったのでエイヤッで決めました。

Preludeがつらい問題

Haskellのよく知られた問題としてPreludeが辛いというか惜しいというのがあります。例えば

mapの型がFunctor f => (a -> b) -> f a -> f bではなく(a -> b) -> [a] -> [b]
lookupのようなよくある関数がアドホック多相になっていなくてMap.lookupなどと書かないといけない
デフォルトの文字列型が[Char]

実用上はゴニョれば良いのであんまり問題ないですが、この問題を解決しようと色々なオレオレPrelude*1が作成されていたりします。

malgoの実装では、試しにprotolude*2を使ってみました。これはオレオレPreludeを作るためのライブラリとして作られているようです。 malgoの実装では、protoludeをベースに、プロジェクトに依存しないユーティリティをまとめてLanguage.Malgo.Preludeモジュールを作っています。

例えば、Showのインスタンスをプリティプリンタ代わりのは微妙という話があるのでPrettyPrint型クラスを作ったり、辞書として使える型を表すDict型クラスを作ったりしています。

実装の話

処理の流れとしては

パースする（Lexer.hs, Parser.y）
shadowingなどのアレコレを名前解決して、全識別子に連番を振る（Rename.hs）
型検査を行い、識別子に型情報を付加する（TypeCheck.hs）
K正規化と脱糖衣を行う（KNormal.hs）
もろもろの最適化（まだほとんど未実装）
クロージャ変換（Closure.hs）
LLVM IRの生成（CodeGen.hs）

とかなりシンプルです。

中間表現は

パースでASTとして生成されるSyntax Name（Syntax.hs）
名前解決で生成されるSyntax ID
型検査で生成されるSyntax TypedID
K正規化&脱糖衣で生成されるHIR TypedID（HIR.hs）
クロージャ変換で生成されるMIR TypedID（MIR.hs）

みたいな感じになっています。

今後の話

多相型を実装
リスト、配列などのコレクションを実装
モジュールシステムを実装

などをやっていき〜みたいな感じです。

*1:https://hackage.haskell.org/packages/tag/prelude

*2:https://github.com/sdiehl/protolude

星にゃーんのブログ

ほとんど無害。