molecular coordinates

/var/log/coorde.log

セキュリティ・キャンプ全国大会2019に参加しました

昨日(2019/8/17)までセキュリティ・キャンプ全国大会2019に参加していました。私は集中開発コースの「Y-Ⅱ Cコンパイラを自作してみよう!」ゼミに参加しました。

セキュキャンとは?とか応募用紙*1についてはここに書いてあるよ↓

セキュリティ・キャンプ全国大会2019に参加してきます - molecular coordinates

全体を通してCコンパイラを書いていたんですが、それ以外にも色々あったので時系列で書いていきます*2

1日目 8/13

開会式などの後、LT大会がありました。尖った人たちの尖った話が聞けて楽しかったです。 kintoneを全く見ておらずLT希望を取っていたことに気づかなかったのが悔しいですね...

グループワークがあり、キャンプ終了後に活動する仲間を見つけてグループを組むといった趣旨のものでした。有志4人でチームを組み、プログラミング言語処理系に高度な言語機能を実装するための知見を一般に普及させる取り組みをやろうとなりました。

この日は講義の時間がなかったのでCコンパイラのコードが書けなかったです。正直5日間コードが書けると思っていたので拍子抜けでした(プログラムはちゃんと読もうな) (でもグループワークもLT大会もめちゃー楽しかったのでいい1日でした)

2日目 8/14

初期化子*3を実装しました。初期化子しんどくて、見た目が似ていても{グローバル,ローカル}な{値,配列}でどれも全然違うことをやらねばならんのですよ

でもこの日は一日中コードを書ける日でした。幸せの具現化ですね。

一方で1日が終わるにつれて「これ期間中にセルフホストできないんじゃね?」みたいな焦りがひどく、部屋に帰ってからは暗黙の型変換をガーッと実装していました

3日目 8/15

講義時間中はstructを実装しました。部屋に帰ってからtypedefを実装しました。enumが生えたのもここら辺じゃないかな

期間中のセルフホストを諦めて*4、明日からは別のことをやろうと思っていました。

この日と4日目に"会員企業のお仕事紹介"があったのですが、kintoneを全く見ておらず希望を取っていたことに気づきませんでした。そういうこともあってどこの部屋にいけばいいのかわからずあたふたしてしまった。

4日目 8/16

色々やった。

  • sanitizerを噛ませると発生しなくなる気味の悪いのバグを潰した*5
  • ruiさんに再配置について*6事細かに教えてもらった。今までずっと疑問だった部分が晴れて本当によかった。
  • レジスタ割り当てのバグを取るための方法を考え、作業を始めた。

Yトラック内で発表会がありました。YトラックにはOS開発ゼミとCコンパイラゼミがありますが、そこの全参加者が一人二分で全員話しました。ほんわかした雰囲気で進捗が報告されており楽しかったです。

その後ラストナイトイベントというやつがあり、本を得ました。ありがとうございます。

部屋に帰ってからは発表資料を作ったりレジスタ割り当ての改善を続けたりしていました。

5日目 8/17

荷物をどうにかしなければいけなかったので朝飯が食べられませんでした。そもそも八時起床をやめろ

講義の成果報告のLTをしました。

その後閉会式などがあって終了*7です。

思うこと

いい環境で好きなことをできるのは本当に楽しい

コーディングに集中できる環境(ディスプレイ、水分、お菓子)がありつつ実装で困ったことがあればすぐ講師の方々に相談できる最高の空間がありました。そこで作業している時間がとても楽しかったです、あの環境を用意してくださった運営やチューター、そして講師の方々には心から感謝しています。

また、コンパイラや言語処理系が好きな人たちと話すのは楽しかったしいい刺激になりました。1日目に部屋に帰った時は「おれが見ていた世界は狭かったんだな...」みたいな謎の感情をやっていた

飯の時間に多種多様な分野の人々と話したのも楽しかったです。めっちゃ面白い人だな〜と思って話していた人が、聞けば有名なプロだった、なんてことも

一方で、参加前はセキュリティキャンプについて5日間のコーディング合宿みたいなもんだと思っていたのですが、その認識は間違いでした。書ける期間は実質3日だし、2日目以外は夜に色々と他のイベントがある

なのでもっとコード書きたかったというのはあります*8 いやそれは趣旨と違うやろ せやね

来年以降参加する人へのアドバイスですが、参加前はプログラムとkintoneをよく確認した方がいいです。特にkintone、結構大事なアンケートが来ていたりするので日常的なチェックを忘れずに...

進捗はどうですか

満足したらまた別にブログ書くから待ってね

成果報告時点の進捗はこんな感じ↓

まとめ

五日間ありがとうございました!

*1:そういえばあれ紙じゃないじゃん

*2:語調が統一できなくて、日本語は難しいなと思っている

*3:int a[] = {1, 2, 3}; みたいなやつの右辺っぽい部分

*4:? https://twitter.com/coord_e/status/1161630222422122496

*5:結局初期化忘れ

*6:GOTやPLT、PICとPIEについて

*7:終了

*8:コーディング合宿とか知ってる人いたら教えてください

セキュリティ・キャンプ全国大会2019に参加してきます

明日(2019/8/13)からセキュリティ・キャンプ全国大会2019に参加してきます*1。私は「Y-Ⅱ Cコンパイラを自作してみよう!」ゼミに参加します。

セキュリティ・キャンプ全国大会って何?

セキュリティ・キャンプ全国大会2019は、セキュリティ・キャンプのメインイベントとして実施している合宿形式の勉強会です。 エキスパートによる実践的な講義が受講できます。また、これまでにセキュリティ・キャンプに参加された修了生による学習支援があります。

セキュリティ・キャンプ全国大会2019 ホーム:IPA 独立行政法人 情報処理推進機構

なんでこのコースにしたの

コンパイラが書きたかったので

応募用紙には何を書いたの

[問1] これまでのプログラミング歴(C言語に限りません)について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。

今までやってきたことを羅列しつつ、それぞれの取り組みで特に自分が努力したところ、またその取り組みから何が得られたのかを書くように心がけました。コンパイラに関係ないことも書くには書いた(でも低レイヤ寄りな部分を強調した)。

[問2] コンパイラソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。

字句解析してトークン列ができて、構文解析してASTができて...みたいなことを書きました、各段階の表現が持っている意味がどう変化していくかみたいなのを意識した書き方をしました。

[問3] C言語コンパイラを書く際に、最も難しいポイントはどこだと思いますか?考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。

C言語のディスりが軸になっていた気がする。仕様が複雑だから大変〜みたいな... これはこれまでのプログラミング経験によって結構ばらつきそうだし、(どれだってそうだが)思ってることを書けばいいんじゃないかなあ

[問4] 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。

コンパイラへの熱意をアピールし、キャンプでは今までやったことのない分野に挑戦したいと書いた。

Cコンパイラ

参加が決まった段階から事前学習ということでCコンパイラを書いています。↓こんな感じ

github.com

キャンプ前にセルフホストしてキャンプ中は最適化やるぞ〜とか思ってたらもう前日だよ、助けてくれ*2

目標はセルフホストしつつ、gcc -O1より速い*3コードを吐かせることです

参加者の皆さんへ

名刺が無限にあるからもらってね

5日間よろしくお願いします。

まとめ

*1:"参加しました"エントリのためにこの記事を書いている節、ある

*2:ブログなんか書いてる場合ですか?

*3:"速い"とは................

mlmlの実装について

前記事: 自作OCamlコンパイラでセルフホストした - molecular coordinates

mlmlの制作のまとめとしてここに実装の詳細を記しておきます。

mlmlとは

自作OCamlコンパイラです。詳しくは前記事を参照してください。

全体の構成

以下の図にmlmlの構成を示します。

f:id:coorde:20190523180006p:plain

ファイル名を入力として受け取ります(①)。そのファイルをエントリポイントとしてBundlerが必要なソースを集めて一つのASTに纏め、Analysisに渡します(②)。AnalysisがASTに様々な変形を施し、Codegenに渡します(③)。CodegenはASTからアセンブリを生成し、出力します(④)。

依存関係の解決 (Bundler)

mlml/mlml/bundler at develop · coord-e/mlml · GitHub

まず受け取ったファイルに字句解析・構文解析を済ませます。次に構文解析によって作られたASTに対して依存関係の解析を行い、そのファイルが依存しているモジュールを探します。見つかった依存モジュールに対しても同じように解析を行い、下のようなツリー状のデータ構造*1を構築します。

f:id:coorde:20190523183945p:plain
依存関係ツリー (stdlibは省略)

次に、”自身が依存するモジュールが常に自分の前に存在するように"、このツリーを潰して直線状に並べます。(追記: この操作はトポロジカルソートと呼ぶようです。@syobon_hinataさん、ありがとうございます)

f:id:coorde:20190523184045p:plain
直線状になった依存関係 長っ

最後にこの並びに従ってモジュールを並べてやることで、それぞれのモジュールが必要なモジュールを参照可能な状態になった大きなASTが出来上がります。

めでたしめでたし...という感じですが、これは本来コンパイラがやるものではなくてビルドシステムにやらせるのが賢明だと思います。作ってしまったものはしょうがないんですが

識別子の名前解決 (Analysis)

mlml/resolve.ml at develop · coord-e/mlml · GitHub

今回はコード生成器でモジュールを意識したくなかったので、Analysisで名前解決*2を行ってしまうことにしました。私はこの変換を"Resolve"と呼んでいます。

以下のようなOCamlコードを考えます。

module Module1 = struct
  let f x = Printf.printf "Hello from Module1: %s\n" x
  let g () = f "g"  (* (1) *)
end

module Module2 = struct
  let f x = Printf.printf "Hello from Module2: %s\n" x
end

open Module2 ;;
f "mlml" ;;  (* (2) *)
Module1.g ()

ここではソースコード上で表記されている名前(fModule.gなど)を相対パス、変換後(Resolve後)の名前を絶対パスと呼ぶことにしましょう。

さて、このコード内では二回fという相対パスが使われていますが、その二つは実は違う実体を参照していることがわかります。 参照先が明確になるよう書き換えてみると(1)のfModule1.f、(2)のfModule2.fになります。

このように文脈を考慮して参照先を決定し、絶対パスに書き換える操作をResolveでは行っています。

相対パスは文脈によって参照している実体が変わりますが、絶対パスは文脈に関係なく参照先が定まります。そのため、全ての名前を絶対パスに変換してしまえばコード生成器でモジュールの文脈を意識する必要がありません。

参照だけではなく定義の名前も絶対パスに変換すると、変換後のコードは以下のようになります

(* 擬似コード *)
module Module1 = struct
  let Module1.f x = Printf.printf "Hello from Module1: %s\n" x
  let Module1.g () = Module1.f "g"  (* (1) *)
end

module Module2 = struct
  let Module2.f x = Printf.printf "Hello from Module2: %s\n" x ;;
end

open Module2 ;;
Module2.f "mlml" ;;  (* (2) *)
Module1.g () ;;

全ての名前が絶対パスになったので、もうモジュールに関する文脈(module定義やopenなど)は必要ありません。最終的にはそれらが取り除かれ以下のようになります。

(* 擬似コード *)
let Module1.f x = Printf.printf "Hello from Module1: %s\n" x
let Module1.g () = Module1.f "g"  (* (1) *)
let Module2.f x = Printf.printf "Hello from Module2: %s\n" x ;;

Module2.f "mlml" ;;  (* (2) *)
Module1.g () ;;

これでコード生成器内で名前が扱いやすくなりました。

カリー化

mlmlでは複数の引数を受け取る関数をカリー化しており、全ての関数が一つしか引数を受け取りません。

例えば次のOCamlコードを考えます。

let f x y z = x + y + z in
let g = f 1 2 in
g 3

ここではfx, y, zの三引数を受け取る関数として定義されています。これはmlmlでは糖衣構文で*3、脱糖すると以下のコードになります。

let f x = fun y -> (fun z -> x + y + z) in
let g = (f 1) 2 in
g 3

複数引数を受け取る関数を「一つ引数を受け取り、関数を返す関数」として扱うことで、カリー化が実現できます。また、引数を一つだけ考えればよくなるため、後の変換やコード生成が楽になります。

クロージャ変換 (Analysis)

mlml/closure.ml at develop · coord-e/mlml · GitHub

OCamlでは、関数内部で引数だけではなく外にある名前も参照することができます。以下のOCamlコードを考えます。

let a = 10 ;;
let b = 20 ;;
let f x = x + a + b ;;
f 1

関数f内でabが参照されていますが、それは関数の引数(x)ではありません。ここではabのような変数をキャプチャ変数と呼ぶことにします。また、それとは別に、引数やlet式に束縛されていない変数のことを自由変数と呼びます。例えば定義let f x = x + a + bを単体で見たときの自由変数は{a, b}です。

さて、最終的にアセンブリに出力する際、関数内から関数外の変数を参照することはできません*4。そのため、変換によって関数定義から自由変数を取り除く必要があります。この変換をクロージャ変換と呼びます。基本的なアイデアとしては、関数を関数とキャプチャ変数の組として扱うというものになります。

クロージャ変換についてはMinCamlのページでわかりやすく解説されています。

mlmlのクロージャ変換では関数定義のキャプチャ変数をタプルにまとめ、引数を本来の引数とキャプチャ変数のタプルで受け取るように変形します。そして、関数を実体とキャプチャ変数のタプルとして定義し直します。このタプルをクロージャと呼びます。また、関数適用ではクロージャを関数本体とキャプチャ変数のタプルに分解し、それを引数に渡してやることで意図した動作を実現しています。*5

この通りに変換すると先ほどのコードは以下のようになります。*6

let a = 10 ;;
let b = 20 ;;
let f =
  let f (x, (a, b)) = x + a + b in
  f, (a, b)
;;
let (_f, _fv) = f in _f (1, _fv)

変換後のコードに現れる関数定義(let f (x, (a, b)) = x + a + b)には自由変数がなくなっています。これで関数のコード生成が可能になります。

フォーマット文字列 (Analysis)

mlml/format_string.ml at develop · coord-e/mlml · GitHub

OCamlではPrintfもカリー化されており、以下のような扱いをすることができます。

let printer = Printf.printf "%s %d" in
List.iter (printer "hello") [1; 2; 3]

しかし考えてみると、Printfが受け取る引数の数は第一引数として受け取っているフォーマット文字列に依存します。 例えばPrintf.printf "%s"は文字列を一つ受け取る関数ですが、Printf.printf "%d %s"は数値と文字列を受け取る関数です。 これは一見コンパイラマジックでも使わないと実現不可能なように思われます。しかし、フォーマット文字列を関数に変換することでこれを実現することができます。

mlmlでは、フォーマット文字列は「関数を受け取り、その関数を必要な引数を受け取ってフォーマットした結果に適用する関数」に変換されます。

ややこしいので具体例をみていきましょう。

例えば"%s and %d"は、以下のような関数に変換されます。

fun k -> (fun s -> (fun d -> k (s ^ " and " ^ string_of_int d)))

フォーマット文字列自体に文字列を組み立てる機能を持たせる感じです。

そしてprintfを以下のように定義します。

let printf fmt = fmt (fun x -> print_string x)

こうすることで、

printf "%s and %d"

fun s -> (fun d -> print_string (s ^ " and " ^ string_of_int d))

に簡約できることがわかると思います。結果としてカリー化されたPrintfが実現できています。

値の内部表現 (Codegen)

OCamlには構造比較演算子=があります。これは二つの値が構造的に等しいかどうか判定するものです。

例えば(1, (2, 3)) = (1, (2, 3))trueに評価されます。当たり前のようですが、タプルはポインタとして実装されているので単純なcmpでは実現できません。値を再帰的に比較していく必要があります。

しかし、ただ値二つを渡されてもそれらを再帰的に比較することはできません。なぜならそれが数値なのかポインタなのかもわからない*7(=再帰的に比較すべきなのかどうかわからない)上に、ポインタだとしてデータのサイズがわからないとどこまで比較を進めていいのかわからないからです。

そこで、これらの情報を値に埋め込んでいます。

改めてまとめると、埋め込むべき情報は以下の三つです。

  • 数値なのかポインタなのか?
  • ポインタなら、続くデータのサイズ
  • 文字列なのかどうか (文字列を埋め込むとポインタと解釈されかねないので、例外的に扱い直接比較させる)

なお、mlmlでは簡単のためデータを8バイト単位で扱っています。

数値なのかポインタなのか

ほとんどの場合*8ポインタはアラインされているので下位2~3ビットが0になっています。ということで一つ目の「数値なのかポインタなのか?」については"数値の最下位ビットを必ず1にする"という決まりを作ってしまえばうまく区別できそうです。このアイデアocaml*9の実装から得たもので、これがOCamlの整数が1ビット足りない理由だったりします。*10

これを実現するために、数値は全て左シフトしたのち最下位ビット(以下LSBと呼びます)を立てています。(n*2+1、ここではこの状態をmarkedと呼ぶことにします*11 ) 実際に中身を使うときは右シフトすれば元の値が取り出せます。

f:id:coorde:20190524165142p:plain
marked int

いちいち整数を扱う度にこの変換を噛ませるのは大きなオーバーヘッドになりそうですが、意外とそうでもないのがこの表現の面白いところです。 例えばn+mを考えると、求めるmarkedな値は(n+m)*2+1となります。これは(n+m)*2+1=(n+m)*2+2-1=(n*2+1)+(m*2+1)-1と変形できるので、markedな整数同士の加算はadddecの二命令で実装できるわけです!これと同じように減算や乗算、論理否定なども"値を取り出す→計算する→作り直す"の手順を踏まずに少ない命令数で実装できます。最初に考えた人頭いいなあ。

ということで、値のLSBを見れば数値なのかポインタなのか判別できるようになりました。

ポインタに続くデータのサイズ & 文字列なのかどうか

ポインタが指す先の一つ目のデータにデータサイズを格納しています。

ただ、文字列かどうかも判別しなければいけないのでこのデータサイズ用の領域のLSBをこのフラグに使っています。データサイズ領域のLSBが1なら文字列、0ならそれ以外のデータです。

具体例を見ていきましょう。下の図に(1, (2, 3))をmlmlがどう扱うかを示します。背景の色が黒ならLSB=1、白ならLSB=0であることを表しています。

f:id:coorde:20190524165811p:plain
(1, (2, 3))のメモリ配置イメージ

タプルは文字列ではないので、データサイズ領域のLSBは0になっています。

文字列を含む構造は以下のようになります。文字列の長さをデータサイズ領域の次にmarked intとして格納しています。これは文字列長がO(1)で求められると色々と*12便利だからです。

f:id:coorde:20190524170003p:plain
("hello", "mlml world", 5)のメモリ配置イメージ

構造比較の実装

と、いうような感じで値の種類を実行時に判別しています。

構造比較演算子=ランタイムライブラリで実装されています。基本的には値の種類を見て再帰的に構造を比較していく感じです。

各種データ構造の実装

タプルは先ほどの画像で示した通りデータが並んでいるだけです。

ヴァリアントはインデックス付きのタプルとして実装しました。以下の型tを考えます。

type t =
  | A
  | B of int * int
  | C of t

ヴァリアント定義に現れた順番で各コンストラクタにインデックスを振っていきます。上の例ではA→0、B→1、C→2です。 そしてコンストラクタが受け取る値とコンストラクタのインデックスをタプルにした値に評価されるようにします。

let a = A ;;             (* (0, ()) *)
let b = B (10, 20) ;;    (* (1, (10, 20)) *)
let c = C (B (3, 4)) ;;  (* (2, (1, (3, 4))) *)

こうすることで構造比較はタプルとして比較することができますし、パターンマッチはインデックス同士を比較することで実現できます。

レコードはただのタプルとして実装されています。レコードのフィールドと要素のインデックスがコンパイル時に結びついています。以下のコードを考えます。

let t = { value: int; tuple: (int * int) } ;;
let v = { tuple = (2, 3); value = 1 } in
print_int v.value

ここで、型tvaluetupleの二つのフィールドをもつレコード型です。出現順にフィールドにインデックスをつけていきます。ここではvalue→0、tuple→1です。

そしてレコードの値を生成する時に、フィールドのインデックスに従ってタプルに値を配置します。上のコードでは{ tuple = (2, 3); value = 1 }とフィールドの順番が型定義と異なっていますが、インデックスに従って並べ替えられ、タプル(1, (2, 3))に評価されます。

レコードから値を取り出す時にもフィールドのインデックスを利用します。v.valueではvalueは0番目のフィールドなので、タプルvの0番目の要素を取り出すように評価されます。

このように、複雑に思えるデータ構造も単純化してタプルとして実装することができました。

GC (Codegen)

mlmlにはBoehm GCを使用したGCがついています。Boehm GCmallocGC_mallocに変えるだけでお手軽にGCが使えてしまう*13 、本当に最高な優れものです。GCなしだとセルフホストしようとした時にあっという間にメモリを食いつぶしてしまったので、GCが必須でした。

おわり

ここまで読んでくださりありがとうございました。mlmlの実装で凝ったことしている部分はだいたいこんな感じです。

あまり調べもせず思いついた方法に突っ走ってしまう傾向が強かった気がしています。モジュールの扱いはかなり改善の余地があると感じているので次に似たようなことをするときはもう少しマシな実装になるよう前例を調べてみようと思います。ocamlのモジュールはレコードになっているらしい*14

参考資料

mlmlの制作にあたり、以下の資料を参考にしました。

*1:ツリーというか有向グラフやな

*2:なんて呼べばいいかわからないのでそれっぽい呼び方をしました

*3:現実装、脱糖がパーサ内で行われているんですが、ダサいのでどうにかしたい

*4:グローバルに置いたりスタックを異常な使い方をすれば可能ですが、ややこしいので考えません

*5:日本語にすると全然わからない

*6:実際にはf、fvは適用される式に対してfreshになるように選ばれます

*7:型がない!!

*8:調べてみたら怪しくなってきた 実際mallocが返すポインタは大抵アラインされているんですが、仕様で規定はされていないらしい...??

*9:OCamlという言語ではなく公式のocamlコンパイラを指しています、以下lowercaseの場合コンパイラを指しています

*10:いや、OCamlには型あるやんけって感じなんですがどうもGCに使うらしいです

*11:tagged呼びの方が一般的っぽいのかな

*12:libcの関数にmlmlの文字列を渡すとき、ポインタ計算で文字列長が頻繁に必要になる

*13: libgcにリンクしなければいけない、GC_initが必要な場合があるなどありますが

*14:http://no-maddojp.hatenablog.com/entry/2015/06/06/165620

自作OCamlコンパイラでセルフホストした

f:id:coorde:20190523170507p:plain

概要

ここ最近作っていたOCaml*1コンパイラmlml*2でセルフホストを達成しました。ヤッター

github.com

mlmlには以下に代表されるような、OCamlの基本的な機能が実装されています。

  • 再帰関数
  • ヴァリアント、レコード
  • パターンマッチ
  • カリー化
  • モジュール

また、多少の標準ライブラリも実装されています。

mlmlの特徴

ほぼフルスクラッチ

今回LLVMやパーサジェネレータに頼らないコンパイラづくりを体験するのが目的の一部だったので、結果的にフルスクラッチらしきこと*3になりました。OCamlの標準ライブラリ以外の外部ライブラリを使用しておらず、字句解析器・構文解析器は手書きです。

OCamlで書かれている

f:id:coorde:20190523092317p:plain

セルフホストしたのでそれはそうなんですが、OCamlで書かれています。

また、言語処理系を書く場合ランタイムライブラリはC言語で用意してリンクする場合が多いと思いますが、今回は謎に意地を張ってしまい全てOCaml内で完結させました。これがよかったのかはよくわからないんですが、文字列などのデータ構造を扱うのにコード生成部と共通のコードを使えるので保守性が上がった(気がします)。

x86_64のアセンブリを吐く

GAS*4に流すことを想定している、x86_64 glibcの環境向けのアセンブリを吐きます。

今までLLVM IRを出力するコンパイラしか作ったことがなかったので、x86もやってみようと今回チャレンジしてみました。

duneの真似をするバンドラーがくっついている

mlmlではduneをビルドシステムとして使っています。そのため気軽にソースを複数のファイル・ディレクトリに分割して開発できました。

しかしセルフホストするときに自分自身が複数のファイルに分割されていると、それらをまとめる部分も作らなければいけません。 ということで、mlmlにはduneの動作をシミュレートするバンドラーがくっついています。内部ではファイル間の依存関係を解決する部分まで書く羽目になりました。これはかなり沼で*5、セルフホストをやる上では設計ミスだったなと思っています。カッコつけずに少ないファイルで作ればよかった。

作り始めたきっかけ

なんとなくOCamlを書けるようになろうと思ったので、公式のチュートリアルをやりました。4月の初め頃のことです。

それが一通り終わったのでコンパイラを作ることにしました。

コンパイラならなんでも良かったんですが、@ushitora_anqouさんの記事"はりぼて自作OCamlコンパイラAQamlでセルフホストしてみた | カオスの坩堝"を読んでセルフホストは楽しそうだなー思い、OCamlコンパイラを作ることに決めました。

その後はハッシュタグ#mlml_compilerに進捗を投稿しつつ制作を続け、開始からだいたい50日でセルフホストに至りました。二ヶ月ですね*6

実装の方針

完璧なOCamlコンパイラを作ろうとしたらいつまでたっても終わらないので、制作を始めるときにいくつか制限を決めました。

出力コードの効率は気にしない

x86_64を直接扱うコンパイラを書くのは初めてなので、まずは効率を気にせず確実に動くコードを吐かせることを優先してコードを書いていくことにしました。

型システムは作らない

これなんですが、作り始めた当時「型システムは実行時エラーを静的に検出するためのものなのに僕は型情報に依存したコード生成をやっている*7!型がなくてもコード生成ができるべきだ」という考えがあったことに起因します。(あとで知ったんですがこの考えは正しいわけではなく、OCaml含む大抵の言語は型情報が項に内因的に含まれています*8。よってコード生成で型情報を利用するのは当然のことです)

結果、型なしでOCamlを実装することになりました。意外にも大体の機能が型推論なしで実装できたんですが、使い勝手が悪かったり一部妥協があったりします。*9

テストイメージ内以外での動作は考えない

出力の可搬性を重視したいならLLVM IRを吐けばいい話なので、"動く環境が存在する"ことを重視することにしました。開発用のDockerイメージを用意し、その内部でテストなどを走らせました。

Dockerコンテナ内でワークフローを回せるようになっているので、macOSWindowsでも開発が行えるようになっています(きっと)

内部構成

技術的な詳細は別記事にまとめたので、ここでは処理の流れを描いた図を示すだけに留めます。

f:id:coorde:20190523171056p:plain
なんとなくデータの流れを描いた図

クロージャ変換やα変換、ヴァリアント/レコード/パターンマッチを実装する体験ができたのは良かったです。作る前はどうやってやるのか見当もつかなかったので...

セルフホストについて

mlmlでは

ことを検証し、セルフホストできたという結論に達しました。*10

セルフホスト用スクリプトを書いたので、誰でも試すことができます。cloneしたディレクトリで以下のコマンドを実行します*11(完了まで一日ぐらいかかります)

./dev/exec.sh ./dev/self_host.sh

ちなみに"セルフホスト"の定義についてTwitterでアンケートをとったら以下のようになりました。

「自分自身をコンパイルできる」派が優勢のようです。僕は「第一世代と第二世代の出力が一致する」派です。真相はいかに

感想

前方参照がないことのキツさ*12やヴァリアント・レコードの実装の簡単さ*13といったことを身をもって感じられたのが一番の収穫だと思っています。

OCamlへの理解は深まったかというとそうでもなくて、オブジェクト指向やGADT、ファンクタなどに触れていない。これは残念です。(セルフホストがしたかったのでしょうがないが)

あとは地味に再帰ガリガリ書く関数型プログラミングをやるのは今回が初だったりするので、慣れることができてよかったなと思っています 再帰にかなり苦手意識があったので...

今後の展望

TaPLを読み進めたりSoftware Foundationsを進めたりしたいのでしばらくはmlmlから離れるつもりです。しかし、例外の実装には興味があるのでいずれmlmlに追加したいなと思っています。

次回に続く

読んでいただきありがとうございました。

次は役に立つことを書くぞ!! (技術的な詳細を書いていこうと思います)

追記: 実装の詳細について書きました。

coordination.hatenablog.com

*1:とある関数型プログラミング言語 http://ocaml.org/

*2:開始当初は"モルモル"と読むつもりだったが実際そう読んだことはない

*3:ビビリなので自信がない 「フルスクラッチ」ってなんだ?

*4:というか面倒なのでgccに流すわけだが

*5:しかもSys.readdirを実装しなきゃいけない!!

*6: ゴールデンウィーク中に終わらせるつもりだったんですが全然終わらなかった(それはそう)

*7:expressiとかでやってた

*8:型付けできない項はinvalidである、Curry-style typingとも

*9:例えばフォーマット文字列と通常の文字列を使われ方によって切り替えることができないので、Printf.printf "Hello"は実行時エラーになります

*10:テストケースを第一世代に流すスクリプトをいずれ書くかもしれない

*11:dockerが必要です

*12:let rec ... and ...が本当につらい 特にコンパイラを書く人にとって...

*13:やってみると大抵のものはタプルだった

Raspberry Piのセットアップ時にやっておくと後々嬉しいこと

独断と偏見しかない (なぜか下書きに埋もれていたので投稿)

USBテザリングができるようにする

皆さんご存知の通りRPiのWifiは弱い 外出先の大事なデモの直前にWifiに繋がらないみたいな手遅れにならんように、USBでiPhoneと繋げばすぐネットワークに繋がってsshできるような準備をしておきましょう

sudo apt install ipheth-utils

参考: Raspberry Pi 2/3/Zero でiPhoneのUSBテザリングを使う - Qiita

Android? 知らないですね...

C++17対応コンパイラを入れる

人権を導入します

公式でバイナリがある*1clangを入れていきましょう

wget http://releases.llvm.org/7.0.0/clang+llvm-7.0.0-armv7a-linux-gnueabihf.tar.xz

参考:

まとめ

*1:嬉しい

C++17と標準ライブラリ: C++17を使うときに気をつけたいこと

この記事では、現在(2019/1/19)新規プロジェクトでC++17を気軽に使い始めて困らないかということを、主に標準ライブラリに焦点を当てて考察する。

C++17は2017年に標準規格化されたC++バージョンだ。C++14、C++11と比べるととても使いやすくなっているので自分も使っていきたいと思うし、広く普及して欲しいと思っている。

しかし結論から言うと、まだC++17(の標準ライブラリ)は軽い気持ちで使い始められるものではないように感じた。

C++17に対応した標準ライブラリは、多くの安定版ディストリビューションでまだ使用可能ではないからだ。

※頑張って正確性に気を使っていますが、事実でない部分などありましたら教えてください。申し訳ない。

C++を構成する要素

一口にC++と言ってもそう単純ではなくて、以下の3つの要素の組み合わせを私たちは普段"C++"と呼んでいる。

3つ要素があるということはそれぞれにバージョンがあるわけで、C++17だったら"C++17のプリプロセッサ"、"C++17のコア言語"、"C++17の標準ライブラリ"がある。

例えば

  • __has_includeディレクティブ: "C++17で入ったプリプロセッサの機能"
  • 構造化束縛: "C++17で入ったコア言語機能"
  • <filesystem>: "C++17で入った標準ライブラリ"

となる。

さて、今回問題になるのはこの3つのうちの標準ライブラリである。(前者2つはコンパイラが対応していればいい、という単純な話なので)

C++の標準ライブラリ

これはコンパイラとは独立したもので*1、様々な実装が出回っている。

ここでは代表的なものとして以下の2つを題材にする*2:

  • libstdc++: gccと一緒に開発されている標準ライブラリ。普通はこれが入っている
  • libc++: LLVMが作っている標準ライブラリ。規格準拠が早いようだ

C++17の代表的な新機能について、それぞれの実装がC++17に対応したバージョンを以下に示す:

  <variant> <any> <optional> <filesystem> <string_view> Parallelism TS <type_traits>_v
libstdc++ 7.1 7.1 7.1 8.1 7.1 No 7.1
libc++ 4.0 4.0※ 4.0※ 7.0 4.0※ No 7.0

公式ページではP0220R1はIn progressになっている(2019/1/19)が、どうやら4.0のあたりでこの3つは入っているらしい

なおこれは2019/1/19時点の情報であり、最新の情報は以下の一次ソースで確認して欲しい:

一般的な環境

次に一般的に使われている環境*3で、どのバージョンの標準ライブラリが使える*4かを以下に示す。

  Ubuntu Bionic Debian Stretch Fedora 29 CentOS 7
libstdc++ 6.4 6.3 8.2 4.8.5
libc++ 6.0 3.5 7.0 No

と、いうことで、C++17標準ライブラリを使用したソースは、ほとんどの環境でコンパイルできないのである。

LLVM公式のリポジトリを使えばUbuntu/Debianでは最新のlibc++が手に入るので*5、これを使えば救いがあるように見える。

しかし、libc++コンパイルされたオブジェクトには、libstdc++コンパイルされたライブラリをリンクできない。一般的にバイナリで配布されているライブラリはlibstdc++でコンパイルされているため*6、libc++でうまくいくと有頂天になっている矢先、下のようなエラーで詰む。

../lib/libflom.so: undefined reference to `google::protobuf::util::MessageToJsonString(google::protobuf::Message const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >*, google::protobuf::util::JsonPrintOptions const&)'
../lib/libflom.so: undefined reference to `google::protobuf::Message::ParseFromIstream(std::__1::basic_istream<char, std::__1::char_traits<char> >*)'
../lib/libflom.so: undefined reference to `google::protobuf::util::MessageToJsonString(google::protobuf::Message const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >*, google::protobuf::util::JsonPrintOptions const&)'

これはlibstdc++でコンパイルされたprotobufを、libc++でコンパイルされたライブラリにリンクしようとした時に出たエラーの一部です。きつい。*7

バイナリ配布なら問題ないのでは?

「ユーザーがビルドする」というシチュエーションがないと断言できる場合。

これは問題なさそうだが、<filesystem>などは実行時にlibstdc++/libc++の共有ライブラリが必要なのでやはり慎重にならなければならない。

あんまり調べてないけど、他にも実行時に共有ライブラリが必要な機能はあると思う。

結論

C++17(の標準ライブラリ)を使い始めるときはビルドする環境や外部ライブラリをリンクするかなどをよく考えて、慎重になった方が良さそう

特に<optional>なんかは手軽さから一度使い始めるとかなり依存してしまいがち(私は)なので、突然「ラズパイでビルドするぞ!」などとなった時やXenialまでしか使えないCIなどで詰む

おまけ

主要ディストリのC++17標準ライブラリ対応状況(コンパイル可能: Y, コンパイル不可能: N)

libstdc++ Ubuntu Bionic Debian Stretch Fedora 29 CentOS 7
<variant> N N Y N
<any> N N Y N
<optional> N N Y N
<filesystem> N N Y N
<string_view> N N Y N
Parallelism TS N N N N
<type_traits>_v N N Y N
libc++ Ubuntu Bionic Debian Stretch Fedora 29 CentOS 7
<variant> Y N※ Y N
<any> Y N※ Y N
<optional> Y N※ Y N
<filesystem> N※ N※ Y N
<string_view> Y N※ Y N
Parallelism TS N N N N
<type_traits>_v Y N※ Y N

https://apt.llvm.org/から最新のlibc++を入手すれば使えるようになるでしょう(それはそう)

Fedora最強かよ。

 

2019/1/19更新: タイトルと冒頭をより意図が伝わるように修正、libc++の表を一部修正

 

*1:なのでgccでlibc++を使うだとか、clangでlibstdc++を使うことももちろんできる

*2: これ以外だとiccやMSVCにくっついてるものがそれぞれあると思う(名前を知らない)

*3:ディストリの選出は適当です

*4:ビルドすることなく標準のパッケージマネージャーでインストールできる

*5:親切にもLLVMはJessie/Trustyにまでリポジトリを用意してくれている

*6:要出典

*7:何がきついって、初見ではこれprotobuf側で何かシンボルが抜けていると思うじゃん...

【適当】モチベーションを維持しながら開発する方法

注: このブログでは内容の正しさを検証する気がないので真に受けると後悔するかもしれません

エモくなったのでCIが頑張ってる間に書く

今回1週間ぐらいCIが通らなくて病んでしまったので(なんてか弱い心!)、そこからちょっと教訓じみたものを捻り出しました

それは何かというと: (自分からの距離)x(1サイクルにかかる時間)が大きい環境で試行錯誤をしない

※主観しかないので、任意の文の先頭に"coordeの場合は"をつけていただければ幸いです。

自分からの距離 is

コードが走る場所と自分の、心理的な距離

イメージとしては ローカル<コンテナ内<リモート<CIになる

このパラメータは、

  • シェルが使いたいときに使えるか
  • こちらからの操作に対するレスポンスが早いか
  • ファイルシステムにアクセスできるか
  • 物理的な距離
  • など

で評価される気がします。知らんけど。

1サイクルにかかる時間 is

結果が得られて、次の行動を決定するまでにかかる時間。多分。

ビルドするのに時間がかかるプロジェクトならこれが大きくなるし、Dockerイメージのビルドとかもでかい。

これが大きくなる最悪のパターンとしては機械学習がある(と思う)。

(自分からの距離)x(1サイクルにかかる時間)が大きいこと is

CIで機械学習するとか、CIで大きなプロジェクトをビルドするとか

どうやって小さくするのか

まあCIでビルドするな!なんて無理な話なので、近くの環境でうまくいくことを保証してから遠くに持っていけばいいと思う、するとCIで試行錯誤する範囲が小さくなるので...

なので僕の場合はDockerイメージに固めて、ローカルでうまくいったDockerfileをCIに使わせることで心の健康を取り戻しました。やったね。

まとめ

ブログではなるべく敬語ではなく普通に書こうと思っていたんだけど、難しい...やめるか