molecular coordinates

/var/log/coord_e.log

型クラスのご紹介

この記事は型 Advent Calendar 2019の23日目です。

おはようございます!!!coord_eです、よろしくどうぞ。

はじめに

この記事ではOCamlみたいなML系言語が登場します。関数型プログラミング言語と呼ばれる何かしらに触れたことがある人ならお気持ちで読み取れると思います。そうでない人はこちらからOCamlに入門してみると楽しいと思います。楽しいと思いますって何ですか...

また、私は正直なところこの記事を書くにあたって関連する十分な量の文献を読みこむことができたわけではなく、誤りが存在することは容易に想像できます。誤字や誤謬を発見された方は@coord_eまでご連絡ください。

概要

型クラス (type class)はWadlerによって[1]で提案された言語機能だ。本記事では型クラスを導入する動機をオーバーローディングの観点から紹介した後、Wadlerの型クラスを発展させたJonesのconstructor class[2]をベースにした本記事独自の体系の形式化を試みる。

型クラスの紹介

オーバーロードの必要性 *1

int型の値が二つあって、等しいのか調べたいですね。コードを書きます

let rec eq_int a b =
  match a, b with
  | 0, 0 -> true
  | _, 0 -> false
  | 0, _ -> false
  | n, m -> eq_int (n - 1) (m - 1)

なるほど*2。じゃあstring*3標準ライブラリにいい関数があったので借りてくる。

let eq_string = String.equal

いいね。使ってみる。*4

# eq_int 1 2 ;;
- : bool = false
# eq_string "abc" "abc" ;;
- : bool = true

正しい感じがする。ところでOCamlには=という演算子があって...同じ型であればこの演算子を使って値の比較ができる:

# (=) ;;
- : 'a -> 'a -> bool = <fun>
# 1 = 2 ;;
- : bool = false
# "abc" = "abc" ;;
- : bool = true

お〜すごい。ところで文字列と数値は内部表現がかなり違いそうな気がしますが...

前の記事でちょっと書いた話と関連するんですがOCamlはランタイムの値にメタな情報を埋め込んで、それを見ながら=の実装内で実行時に分岐して比較しています。

でもちょっと待って、1 = 1ではintの値に適用しているんだからeq_intを、"abc" = "abc"ではstringの値に適用しているんだからeq_stringを呼べばいいってことはコンパイル時に分かるのでは?整数含む全オブジェクトに共通の内部表現を持たせるのはなかなか厳しいものがあるので*5コンパイル時に呼び分けることができたらかなり嬉しいですね。

おっとそれだけではない!!'a -> 'a -> boolというハイパワーな型を持っているので、例えば関数同士の比較といった``ない''操作*6も型チェックを通ってしまう。

# eq_int = eq_int ;;  (* runtime error *)
Exception: Invalid_argument "compare: function value".

おぅ...これはしんどいわね。

別の例を見てみます。OCamlでも+は見た目に違わず、加算の演算子です。使ってみましょう:

# 1 + 2 ;;
- : int = 3
# 1.1 + 1.2 ;;
Error: This expression has type float but an expression was expected of type
         int

なんか言ってますね。型を見てみます

# (+) ;;
- : int -> int -> int = <fun>

なるほど+intにしか使えないらしい。じゃあfloatはどうすれば...+.があります

# (+.) ;;
- : float -> float -> float = <fun>
# 1.1 +. 1.2 ;;
- : float = 2.3

おお〜よかったですね。なんで使う型ごとに演算子を変えなきゃいけないんですか?(逆ギレ)

この時点でわかったしんどさをまとめてみます。=+の例に共通していたのは、「同じ記号に型によって違う意味を持たせたい」という点でした。その上で:

  • 型ごとに別名を作りたくない
    • +.のようにユーザーに呼び分けを要求したくない
  • 取れる型を、意味が存在する型のみに制限したい
    • (=) :: ('a -> 'a) -> ('a -> 'a) -> bool は許容したくない
    • (+) :: bool -> bool -> bool も許容したくない

ここで登場するのが、一般にオーバーロード (overloading)と呼ばれる機能です。直感的な説明としては同じ名前に対して複数の意味を与えられる言語機能になります。下にC++での例を示します*7

int add(int a, int b) {
    return add_int(a, b);
}

float add(float a, float b) {
    return add_float(a, b);
}

ここで、addには二つの実装があり、引数がintfloatかによって呼び分けることができます。=についても同様で、実際にC++の標準ライブラリではoperator==が比較関数として様々な型にオーバーロードされています。

なお、今後の記事中で二項演算子(+とか)は二引数関数として扱います。すなわち a + b(+) a bとしてパースされるイメージです。

多相性について

さて話は変わりますが、多相性 (polymorphism) について、お話しします。直観的には多相性は同じ値に複数の型をつけることが可能になる型システムの機能のことを言います。とある世界線ではジェネリクスと呼ばれたりします。なお複数の型が付くとはいえ候補が無限にある必要はない点に注意してください。 多相性には大きく分けて二種類あって、

  • パラメトリック多相 (parametric polymorphism) 一つの名前に複数の型が付く。付く型によらず同一のオブジェクトを示す。
  • アドホック多相 (ad-hoc polymorphism) 一つの名前が複数の型を持つ。付く型によって異なるオブジェクトを示す。

があります。パラメトリック多相のわかりやすい例としてはリストの長さを返す関数len :: 'a list -> intがあります。これは任意の'aについて'a list型のリストの長さを求める一つの関数です。アドホック多相は先ほど紹介したオーバーロードですね。何もかもがパラメトリック多相で済めばいいんですがそんなことはなく、特にプリミティヴなオブジェクトに対する操作にアドホック多相が要請されることはよくあります。

型クラスあらわる

ではオーバーロードによるアドホック多相が先ほどの問題の解決策だとわかったところで、実際に実装することを考えてみましょう。先ほどの例で、='a -> 'a -> boolでは弱すぎることがわかりました。+ではその問題がよりはっきりしていて、'a -> 'a -> 'a'ではたまったもんじゃない。じゃあ、名前に対して取れる型の集合を与えてあげてはどうだろう?int, float, bool、そして関数型しかないと仮定すると、こう:

(=) :: { int -> int -> bool, float -> float -> bool, bool -> bool -> bool }
(+) :: { int -> int -> int, float -> float -> float }

オ〜良さそうだ。こういうやつを交差型と呼ぶが、しかしfetburnerさんの15日目の記事

無制限に交差型を入れてしまうと型推論が決定不能になってしまいます

とあるように、何も考えずに交差型を導入するわけにもいきません。

そこで型クラス (type class) だ。Kaesが[3]parametric overloadingと呼んだこの言語機能は、先ほどの完全なオーバーロードに制限を加え、オーバーロードされた名前が取りうる型を制限された型スキームの形で表現する。

(=) :: ∀'a. Eq 'a => 'a -> 'a -> bool
(+) :: ∀'a. Num 'a => 'a -> 'a -> 'a

無限に存在する型の集合に対して有限な表現が与えられている!いいじゃないですか、これを使えばオーバーロード解決ができるかはインスタンスかどうかを見ればいいので一発で判定できます。

さて、型クラスには次のような特徴がある[4]:

  • 多相性: 関数につく型が一つに制限されない
  • オーバーロード: 実装がつく型によって決定する
  • 拡張可能: 定義を追加できる

多相性とオーバーロードについてはこれまで話した通り。"拡張可能性"は、あるクラスのインスタンスを、クラス側の再コンパイルなしに後から追加できる特徴をいい、これはthe expression problemの一つの解決策となりうる。

高階型を含むシステムでの型クラス

話は変わるがmap関数を知っていますか?僕は知っています:

List.map :: ('a -> 'b) -> 'a list -> 'b list

さて、'a optionにもmapは定義されている。

Option.map :: ('a -> 'b) -> 'a option -> 'b option

え〜、listoptionFunctorと呼ばれる共通の構造を持っており、Functorに対する操作としてmapは抽象化することができる。なら、mapオーバーロードできまいか。

map :: ∀'a 'b 'f. Functor 'f => ('a -> 'b) -> 'a 'f -> 'b 'f

ムッ、Functorになっている'fは型ではなく型コンストラクタだ。型コンストラクタのような、型を受けとって型を返すようなものを高階型(higher order types)と呼んだりするが、これの上の型クラスも許すことができたら嬉しいです。この記事では型の概念を拡張し、こういったクラスも許容する体系を扱います。型クラスと高階型を組み合わせた体系はconstructor classという名前で[2]で提示されました。

高階型に対する型クラスがあると様々な抽象を表現することができて、例えば先ほどのFunctorの他にもMonadというのがあります。Monadは手続きを抽象化した構造で、Haskellにような純粋関数型のプログラミング言語で手続きを構造として扱う上で欠かせないものとなっています。[2]モナドを紹介している節があるのでそれを見るとよく解ると思います。

型クラスを含む型システム

では先ほどふわふわとお話しした型クラスを形式化していきましょう!

記法

構文の定義には BNF記法 (Backus-Naur Notation)を使用する。ただしBNFにおけるリテラルには \texttt{monospaced}の書体を使用する。メタ変数 xが集合 Sの上を動くことを x ::\in Sと表記する。列 x_1, \ldots x_n (n \ge 0)について、 n = 0のときは空の列とする。また、メタ変数 x の0個以上の列 x_1...x_n (n \ge 0) \overline{x}と表記し、列 \overline{x}に含まれる要素を元とする集合を [\overline{x}]と表記する。

二項関係 R \subseteq S \times T S,  Tの元 s \in S,  t \in Tについて、 R \cup{{(s, t)}} R [ s \mapsto t]と表記する。また (s, t) \in R R(s) = tと表記する。

その他、集合や関係に関して標準的な記法を用いる。また今後も定義を述べた後にそれに関係する略記や記法を導入することがあり、それについてはその都度記載する。

形式化

class, instance宣言を式中で陽に扱う、高階型クラスの体系を考える。推論規則は[2][5]をベースにしている。[5]の形式化とは、class/instanceが式である、型変数のカインドを明示している、の二点で異なっている。

型は[2]の定義をそのまま使う。 \chiは型コンストラクタ名で、intMaybeとかそういうのです。

f:id:coorde:20191224003647p:plain

え〜  c^\kappa が我々が普段呼ぶところの型なんですが、ここでは[2]に倣って型コンストラクと呼ぶことにします。待って、型に乗っている  \kappa*8…これは型の (kind) です。種とは何かの説明はここではしませんが、直感的な説明としては「型の型」です。[6]の29章に詳しく書いてあると思います。さて、種を以下のように定義します:

f:id:coorde:20191224003703p:plain

 c^* を特に (type) と呼びます*9 c^\kappaは種  \kappa を持つ型コンストラクタ、 \alpha^{* \rightarrow *} は型を取って型を返す型コンストラクタ変数、といった具合です。型の定義に内因的に種が含まれている点に注意してください。なお、今後 \chi^* \alpha^*をそれぞれ単に \chi,  \alphaと表記することがあります。また \rightarrow^{* \rightarrow * \rightarrow *} \, c_1^* \, c_2^* c^*_1 \rightarrow c^*_2と表記します。さらに型 \tau中の型変数 \alpha^{\kappa_1}_1, \ldots \alpha^{\kappa_n}_nをそれぞれ c^{\kappa_1}_1, \ldots c^{\kappa_n}_nで置き換えた型を [\alpha^{\kappa_1}_1/c^{\kappa_1}_1, \ldots \alpha^{\kappa_n}_n/c^{\kappa_n}_n]\tauと表記します。また  \tauの代わりに型を部分に含む別の要素を置く場合があるが、その場合は部分の型に同様に代入したものを表記している(ただし型スキームに対しては定義しない.)*10

次に型にまつわる様々を定義していきます。

f:id:coorde:20191224003712p:plain

 \phiクラス名 \theta述語 (predicate)であり、述語 \phi \; c^{\kappa_1}_1 \ldots c^{\kappa_n}_n c^{\kappa_1}_1 \ldots c^{\kappa_n}_nとクラス \phi との関連を表しています。

f:id:coorde:20191224003722p:plain

それぞれ型、修飾型 (qualified type)、型スキーム (type scheme)です。型スキームで全称量化されている型コンストラクタ変数  \alpha^\kappa *だけでなく任意のカインドを取ることができる点に注意してください。なお、 \overline{\theta} \Rightarrow \tau \overline{\theta}の部分のことを指してコンテキスト (context)と呼びます。

f:id:coorde:20191224002348p:plain

さて、下に今回の言語の文法*11を示します。なお、 l1, "string"みたいなリテラルの上を動く文字として使用しています。

f:id:coorde:20191224003731p:plain

ここに推論規則を当てていきます。ただし:

  •  L \subseteq \textbf{Literal} \times \textbf{Type}にはリテラルとそれに対応する型が入っています。例えば L(42) = \texttt{int}です。
  •  A\subseteq \textbf{Variable} \times \textbf{TypeScheme}型環境 (type environment)で、変数と対応する型スキームが入っています。 Aは型付けが進むに従って変更されていきます。
  •  P \subseteq \textbf{Predicate}は述語の集合です。後に述べる型付け関係に用いられているとき、これを前提(premise)と呼ぶことにします。前提はコンテキストの置き場で、直感的には述語を除去するときに使えるの前提条件です。実際に Pの上で除去できるコンテキストは消せると行った操作があります( \text{ELIM})。
  •  E \subseteq \textbf{Context} \times \textbf{Context}classinstanceによって定まる、コンテキストの包含を表す二項関係です。この E のもと、 P \Vdash_E P' Pの時 P'が実際に除去可能 (直観的には Pならば P') だということを表す二項関係 \Vdash_Eを定義します。

f:id:coorde:20191224002501p:plain

これらを用いて型付け規則を定義します。型付け関係は E \mid P \mid A \vdash e : \sigmaの形をしており、「 E,  P,  Aのもとで式 e は型スキーム \sigmaが付く」と読みます。下に具体的な型付け規則を示します。なお、規則中で、 \forall \alpha^\kappa_1, \ldots \alpha^\kappa_n. P_1 \rightarrowtail P_2 \{\left([\alpha^{\kappa_1}_1/c^{\kappa_1}_1, \ldots \alpha^{\kappa_n}_n/c^{\kappa_n}_n]P_1, [\alpha^{\kappa_1}_1/c^{\kappa_1}_1, \ldots \alpha^{\kappa_n}_n/c^{\kappa_n}_n]P_2\right) \mid c^{\kappa_1}_1 \in C^{\kappa_1}_1, \ldots c^{\kappa_n}_n \in C^{\kappa_n}_n\}の略記として、また E [\forall \overline{\alpha^\kappa}. P_1 \rightarrowtail P_2]を E \cup{\left(\forall \overline{\alpha^\kappa}. P_1 \rightarrowtail P_2\right)}の略記として用いています。

f:id:coorde:20191224002601p:plain

 \textit{CLASS} \textit{INSTANCE} 以外はほとんど[2]からの引用です*12。 一方でclassinstanceについては[2]の中で

The precise definition of entailment is determined by the class and instance declarations that appear in a given program.

としか言及されていないので*13 \textit{CLASS} \textit{INSTANCE} 、あと \Vdash_Eあたりを自分で考えました (👈大丈夫か?)

推論例

この推論規則の適用の様子をいくつか紹介します。まずは一応おさらいとして普通のHMの範囲で型付けの様子を見てみよう:

let id = \x. x in
(id id) 1

f:id:coorde:20191224005303p:plain

ウォウ〜。デカいがまあこんな感じ*14 \textit{GEN} で束縛前に型スキームにしてやることで、使うときに  \textit{INST} で好きな型にインスタンス化してやることができる。よかったね

じゃあ次は型クラスを使った式の推論を見てみる。

class Eq a^* where eq :: a -> a -> bool in
instance Eq int where eq = eqInt in
eq 1 2

f:id:coorde:20191224005246p:plain

 ELIM Eq \; \texttt{int}がしっかり葬り去られているのが見えると思います。

ここからコンテキスト付きのインスタンスとかsuperclassとかを含んだ例についても推論例を示したほうがいいと思うんですが2つ書いてみてあまりにも面倒だったのでやめます。各自、紙と鉛筆でお試しください。

型クラスの実装 (未完)

実装は間に合いませんでした!!!が主要なアルゴリズムは実装されていて、あとはハンドラを書いていく感じですね。extensible effects最高!!一番好きなAn Alternative to Monad Transformersです

実装が完成したらアルゴリズムと実装について記事を書きます...いち早く知りたい人は[1][7]、そして[8]をチェック...!

おわりに

本記事ではWadlerによって提示された言語機能である型クラスについて、高階型を含む体系での応用にも触れつつ紹介した。また、型クラスを含む型システムの推論規則を紹介した。

参考文献

  • [1] Wadler, Philip, and Stephen Blott. "How to make ad-hoc polymorphism less ad hoc." Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, 1989.
  • [2] Jones, Mark P. "A system of constructor classes: overloading and implicit higher-order polymorphism." Journal of functional programming 5.1 (1995): 1-35.
  • [3] Kaes, Stefan. "Parametric overloading in polymorphic programming languages." European Symposium on Programming. Springer, Berlin, Heidelberg, 1988.
  • [4] Peterson, John, and Mark Jones. "Implementing type classes." ACM SIGPLAN Notices. Vol. 28. No. 6. ACM, 1993.
  • [5] Hall, Cordelia V., et al. "Type classes in Haskell." ACM Transactions on Programming Languages and Systems (TOPLAS) 18.2 (1996): 109-138.
  • [6] Pierce, Benjamin C. 型システム入門 プログラミング言語と型の理論. 株式会社 オーム社, 2013.
  • [7] Jones, Mark P. "Typing haskell in haskell." Haskell workshop. Vol. 7. 1999.
  • [8] Demystifying Type Classes - http://okmij.org/ftp/Computation/typeclass.html

*1:OCamlをdisるみたいな構図になっていて本当に申し訳ない、OCamlでもファンクタを使えば似たようなことはできると思うのでOCamlのことは嫌いにならないでください、お願いしましたよ。

*2:負の数のこと忘れてたけど面倒だからこれでええか?いいよ

*3:構造的等値の話しかしない

*4: #はsuperuserとは全く関係なくてocamlのトップレベルに打ってねって意味なのでsuperuserで実行したことによるいかなる事態についても責任は負えません

*5:しんどかった.

*6:や、∀a. f a = g a ↔ f = g なのかもしれませんがそんなことを決定する能力は一般的なプログラミング言語に備わっていないので...

*7:実はこれのせいでfloatで呼び出そうとするとambigousって怒られるんだが本質とは関係ないので無視してくれよな...

*8:型になんか乗っていますが、 c^\kappaは単にメタ変数として扱います

*9:[6]曰く真の型

*10:このあたり雑で申し訳ない...+型スキームは少なくともそうじゃないので

*11:superclassの表記が左矢印なのはPureScriptの真似

*12:表記を変えたぐらい

*13:[2]ではclassとinstanceはグローバルに宣言されることになっているので、式について議論する分にはこれで十分だったんじゃないかな

*14:居ない環境は省略している

cccコンパイラのバックエンド

この記事は言語実装 Advent Calendar 2019の23日目です。

おはようございます!!!coord_eです、よろしくどうぞ。

はじめに

実は、この記事の大半の文章は以前に別の目的で執筆したものです。 そういえばcccについて記事を書いていないな、ということで、少し内容を変更しつつ体裁を整えて公開することにしました。 なお、ブログやスライドなどで散々「セルフホストする」「gcc -O1に勝つ」と豪語しておりましたが、そのどちらも達成できていません。残念。

この記事にはPDF版があります。以下のリンクからダウンロードできます。

元が \LaTeXなので多分PDFの方が読みやすいです。基本的にはPDFとはてなブログの内容は同一ですが、長いアルゴリズムなどは省略してPDFにのみ載せていることがあります*1。また、内容が同じ二つの文書を同時にup-to-dateに保つのは大変そうなので、何か変更する必要が生じたときは僕のやる気によってはPDF版のみ更新してはてなブログの内容が古くなる可能性があります。

この記事の \LaTeXソースはGitHubに公開しています。 また、誤字や誤謬を発見された方は@coord_eまでご連絡いただくかリポジトリにIssueやPull Requestを送ってくださると幸いです。

概要

cccは、自分がセキュリティ・キャンプ2019に参加した際に開発したコンパイラだ。 C11のサブセットをコンパイルする事ができ、暗黙の型変換や初期化子、宣言子に代表される複雑な言語機能を規格に忠実に実装している。 さて、cccは効率の良いコードに効率よくコンパイルすることをテーマに開発を行った。 そのテーマのもと、出力コードの効率を高めるためにcccに実装した技術についてこの記事では説明する。 最後にベンチマークの結果を示し、実装の効果を確かめる。

cccコンパイラの構成

cccコンパイラはCのソースコードを受け取りアセンブリのコードを出力する。cccではワンパスでは行えないと思われる変形や最適化を用いているため、コンパイルの段階に応じて複数の中間表現を用いている。

一つ目の中間表現が抽象構文木(Abstract Syntax Tree, AST)だ。これは構文解析の結果を木構造で表現したもので、この上で意味解析が行われる。 もう一つの中間表現はIRと名付けた*2。これはASTよりもアセンブリに近い構造を持っており、この上で最適化やレジスタ割り当てが行われる。IRについては次節で詳しく説明している。

f:id:coorde:20191211223754p:plain
図1: cccコンパイラ全体の構成

図1はコンパイラ全体の構成を表している。cccコンパイラの内部パスはソースコードからASTを扱うフロントエンド(front end)と、IRを扱うバックエンド(back end)に概念上分類することができる。 フロントエンドではソースコードに対して字句解析と構文解析を行ってASTを生成し、ASTの上で意味解析を行ったのちIRを生成する。バックエンドは生成されたIRの上でコード変形や最適化を行い、最終的に一般的なアセンブラで処理可能な形式のx86_64アセンブリを生成する。

なお、バックエンドは今日ではLLVMに代表されるようなコンパイラ基盤で置き換える事ができる。 しかしcccでは低レイヤ・オタク特有のいわゆる“一から作りたい欲求”に身を任せ、バックエンドを既存のフレームワークを使用せずに自作している。 この記事では主にcccコンパイラのバックエンドに焦点を絞って説明する。

この記事では構文解析に代表されるようなフロントエンドについては説明しない。理論的な側面については[1]が詳しい。また、フロントエンドに限らないが、実装から入る場合は[2]が非常に良いオンラインブックであるとして有名だ。

IR

IRは出力先のネイティブコードに近い構造を持つように設計した。IR内では関数が単位となっており*3、これを関数IRと呼ぶことにする。IRに対する操作も基本的に関数IR単位で行われる。 関数IRはメタデータを除けばIR命令(IR instruction)の列である。IR命令は命令の種類であるオペコード(opcode)*4と命令の引数であるオペランド(operand)で構成されている。また、cccのIR命令列は基本ブロック(basic block)に分割されており、各基本ブロックは後続節(predecessors)と先行節(successors)の情報を保持している。 これらの情報から基本ブロックは制御フローグラフ(Control Flow Graph, CFG)を構成する(図2)。

IR命令はレジスタオペランドにとる。cccのIR上のレジスタには以下の3つの種類がある。

IRを表す図中では、n番目の仮想レジスタvn、n番目の物理レジスタrnrnに割り当てられるm番目の固定レジスタf(vm:rn)と表記する。

さて、IR命令の命令セットを表1に示す。 なお、今後の表やアルゴリズムでは命令の出力オペランド rd、n番目の入力オペランド ra[n]と表記する。*5

表には記載がないが、これらの他にBIN_IMMといった片方のオペランドに定数をとる命令やBR_CMPといった複合命令が実装されている。これらは主にレジスタ上のデータの流れを用いた最適化であるデータフロー最適化で効率的なアセンブリを出力するために用いている。

IRはASTから生成され、IRの上で最適化やレジスタ割り当てが行われたのちにコード生成パスでx86_64のアセンブリに変換される。

f:id:coorde:20191211223835p:plain
図2: cccが出力するIR (CFG) の例

f:id:coorde:20191211223855p:plain
表1: cccのIR命令セット (一部)

ターゲット固有IRへの変換

アーキテクチャやABI(ここでは二つをまとめてターゲットと呼ぶ)によっては、命令がある決まったレジスタを使用することがある。 例えばx86_64アーキテクチャにおいて除算命令divは被除数をraxにとり、商をraxに格納する。 またSystem V ABIにおいてcall命令はrdi, rsi, rdx, rcx, r8, r9に引数をとり戻り値をraxを格納する。 こういった特別に扱われるレジスタをここでは特殊レジスタと呼ぶことにする。 また、x86_64ではadd, subなどのいくつかの命令において演算の左辺と演算結果が同じレジスタでなければならないという制約がある。

一方で、cccのIRでは表1からわかる通りオペランドレジスタに特に制限を設けていない。 そのため、単純な実装ではコード生成時に適切にmov命令を挿入して決まったレジスタを使うようにすることになる。 しかし、この方法では特殊レジスタを汎用的に使うことができず、レジスタ割り当てに使えるレジスタの数が制限されてしまう。 また、一つのIR命令に対応するアセンブリ命令が多くなってしまうと最適化の効果が制限されてしまうことも予想された。

そこで、cccではレジスタ割り当て前にIR上でターゲット特有の変換を行うことでこれらの問題を解決している。 図1では「Target Conversion」と表記している。 これはIR上で固定レジスタへのMOV命令を生成することでコード生成時に正しいレジスタが使用されていることを保証しながらIR上で特殊レジスタの使用を表現するものだ。 こうすることでレジスタ割り当ての時点で特殊レジスタの使用が把握できるため、特殊レジスタが使われていない部分では通常のレジスタとして割り当てに使用できるようになる。 図3にこの変換の例を示す。関数呼び出しや除算が固定レジスタを使うように変換されているのが見て取れる。

f:id:coorde:20191211223918p:plain
図3: ターゲット固有IRへの変換前後のIRの変化例

最適化

効率の良いコードを出力するため、最適化を行う。 cccではデッドコード削除やコピー伝播に代表されるデータフロー最適化やAST上の定数畳み込みなどを実装しているが、ここではそれらについては説明しない。 特にデータフロー最適化について、技術書展8にOtakuAssemblyで記事を出す予定なので、ぜひそちらを楽しみにしていてください。

さて、ここではLOAD/STORE以外の操作を受けていないスタック上の領域をレジスタで置き換える最適化について説明する。 この最適化パスをmem2regと名付けた*6。 mem2regで使用および実装したアルゴリズムアルゴリズム1に示す。

f:id:coorde:20191211223942p:plain
アルゴリズム1

ここではアドレスとして用いられているレジスタアドレスレジスタ(address register)と呼ぶ。 LOAD/STORE命令のアドレスの位置にあるオペランドとして使われているレジスタがアドレスレジスタである。

CollectUses(アルゴリズム2)でアドレスレジスタのうち、置き換え可能なものを求める。 ここではアドレスレジスタcandidatesに集めながら、LOAD/STORE以外の操作を受けているレジスタexcludedに集めている。 また、STACK_ADDR命令で代入されているレジスタを個別にin_stackに集めている。

さて、置き換え可能なアドレスレジスタは、以下の3条件を満たしているものである。

  1. スタックのアドレスを保持している
  2. LOAD/STORE以外の操作を受けていない
  3. 置き換え不可能なアドレスレジスタと同じスタック位置を共有していない

1., 2.を満たすアドレスレジスタの集合は、 (\texttt{candidates} - \texttt{excluded}) \cap {\texttt{in_stack}}で求められる*7。 そして3.を満たさないものを除外するために、置き換え不可能なアドレスレジスタのスタック位置の集合を求め、そのあとにそれを共有しているものを除外するというナイーブな方法をとった。

そして、置き換え可能なアドレスレジスタが求められたのち、ReplaceInstructions(アルゴリズム3、PDF版に掲載)で命令をレジスタを使うように書き換えている。

f:id:coorde:20191211225905p:plain
アルゴリズム2

図4にこの最適化による変形の例を示す。一部のスタックに対する操作がレジスタに置き換わっていることが見て取れる。 この最適化による出力コードの効率の変化についてはこの記事の後半で検討する。

f:id:coorde:20191211224017p:plain
図4: mem2reg最適化前後のIRの変化例

レジスタ割り当て

cccでは出力の実行効率を意識し、入力をレジスタマシンにコンパイルする。 そのために、レジスタ割り当て(register allocation)を行う。一般的なプロセッサにおいてレジスタは有限だ。例えばx86_64においては16本、そのうち汎用的に使えるのは14本しかない。 すなわち、全ての値をレジスタに保存しておくことはできない。値を保存するレジスタが足りなくなった時に、レジスタの代わりにスタックの領域を使う。これをspillと呼ぶ。 spillされたレジスタは使用時にスタックから読み込まれ、値の変更時にスタックに書き戻される。 レジスタへのアクセスはメモリへのアクセスと比べて非常に高速であるため、頻繁にアクセスされる値をレジスタに、そうでない値をメモリに配置することが出力コードの効率向上に繋がる。

一方で最適なレジスタの割り当てを求める問題はNP完全であることが知られている。そこで、コンパイル時間と実行時の効率のバランスが取れたアルゴリズムが考案されてきた。 そのよく知られた例の一つが、レジスタ割り当てをグラフ彩色問題とみなす方法[3]である。しかしこの方法はコンパイル時間が長くかかるほか、実装が複雑になることが予想されたため今回は採用しなかった。

cccでは、linear scan register allocationを使用した。これはPolettoらによって[4]で使われたレジスタ割り当てアルゴリズムだ。 これはグラフ彩色による手法に比べて割り当てにかかる計算量が少なくて済む上に、ほとんどの場合で同程度に効率の良いコードを出力できる。

cccの実装では、まずIR上でbackward data-flow analysis[1]を行い、仮想レジスタの生存区間を求めたのち、レジスタ割り当てを行う。 生存区間解析の実装はほぼ[5]で使われているアルゴリズムの通りである。 レジスタ割り当てのアルゴリズム[6]を元にしたが、固定レジスタを扱うために一部変更を加えている。 実際に使用したアルゴリズムアルゴリズム4に示す。

f:id:coorde:20191211224045p:plain
アルゴリズム4

このアルゴリズムでは、割り当てに際して三つのグローバルな変数を持っている。

  • availableは現在利用可能な物理レジスタのリスト*8で、後に述べる優先度でソートされている。
  • activeは現在使われている仮想レジスタのリストで、生存区間の終了が遅い順にソートされている。
  • resultは仮想レジスタから割り当てられた物理レジスタへの写像*9

これらの変数に対する操作は、AllocSpecificReg(アルゴリズム8、PDF版に掲載)とReleaseReg(アルゴリズム9、PDF版に掲載)の二つの操作に抽象化されている。 アルゴリズム本体ではこれら二つの操作とspillを適切な条件で行うことで、割り当てを行なっている。 また、availableは次の条件もとソートされている。(アルゴリズム5) なお、関数呼び出しで保存されないレジスタ*10のことをscratch registerと呼ぶ。

  1. 現在の関数内の固定レジスタで使用されている物理レジスタより、そうでない物理レジスタを優先する。
  2. 現在の関数が関数呼び出しを含むならば、scratch registerでない物理レジスタを優先する。そうでないならばscratch registerを優先する。

AllocSpecificReg(アルゴリズム8、PDF版に掲載)からわかる通り、割り当てる物理レジスタavailableの先頭から選ばれる。これにより、アルゴリズム5で優先されているものから順に割り当てられる物理レジスタが選出されることになる。

f:id:coorde:20191211224105p:plain
アルゴリズム5

さて、linear scan register allocationは、生存区間に対する一回の走査によって行われる。 アルゴリズム6に走査部分のアルゴリズムを示す。また、spill関連のアルゴリズムをPDF版のアルゴリズム7に示してある。 固定レジスタの割り当てでは、必要な物理レジスタがすでに割り当てられていた場合にそれをspillすることで物理レジスタを確保する。また、spillの対象のレジスタを選ぶ際に固定レジスタを避けるようにしている。それ以外はほぼ[6]の通りである。

f:id:coorde:20191211225939p:plain
アルゴリズム6

図5にレジスタ割り当ての例を示す。全て仮想レジスタが物理レジスタに割り当てられているだけでなく、変換前に固定レジスタだったレジスタは、正しく指定されたレジスタに割り当てられていることが見て取れる。

f:id:coorde:20191211224127p:plain
図5: レジスタ割り当て前後のIRの変化例

評価

ターゲット固有IRへの変換や最適化の効果を確かめるために、ベンチマークを行った。 ベンチマーク環境は以下の通り。

  • CPU: AMD Ryzen 7 2700
  • RAM: 32GB
  • kernel: 5.2.8-arch1-1-ARCH
  • OS: Arch Linux
  • gcc: 9.1.0

今回は三種類のプログラムをベンチマークに用いた。それぞれ次の通り。

  • 14queen - N-queen問題のn=14の場合の全ての解を求める
  • sort - 30000000個のランダムな要素からなる配列のマージソート
  • pi - 円周率を200000桁求める

以下の5種のコンパイラにこれらのプログラムをコンパイルさせ、コンパイル時間と実行時間、および出力コードの行数を計測した。 計測はそれぞれ8回行い*11、平均値を算出した。

  1. 固定レジスタを導入する前のccc (naive)
  2. 固定レジスタを導入し14本のレジスタを活用できるようになったccc (better_alloc)
  3. 2.にmem2reg最適化を導入したccc (mem2reg)
  4. gcc -O0
  5. gcc -O1

コンパイル時間

コンパイル時間のベンチマーク結果を表2と図6に示す。

f:id:coorde:20191211224203p:plain
表2: ベンチマーク結果: コンパイル時間

f:id:coorde:20191211224220p:plain
図6: コンパイラごとのコンパイル時間の比較

実行時間

実行時間のベンチマーク結果を表3と図7に示す。なお、naiveのsortについてはその時点でのcccの実装にバグがあり実行時エラーが生じているため正常な計測ができていない。

f:id:coorde:20191211224243p:plain
表3: ベンチマーク結果: 実行時間

f:id:coorde:20191211224259p:plain
図7: コンパイラごとの実行時間の比較

出力コード行数

出力コード行数のベンチマーク結果を表4に示す。

f:id:coorde:20191211224435p:plain
表4: ベンチマーク結果: 出力コード行数

考察と展望

当然ながらcccはどのベンチマークにおいてもgccよりも速くコンパイルできている。 cccの方が高速なコードを出力しているケースにおいても、最適化を行っていないgcc -O0と比べて最適化を行ったcccの方が高速にコンパイルできている。 効率よくコンパイルするという目標はよく達成できていると思う。*12

その一方で実行時間については、ほとんどのベンチマークgcc -O0より遅いという結果になった。しかしmem2regがpiでgcc -O0より高速なコードを出力できている。 これは14queenとsortが配列に対する操作が基本となるベンチマークであるのに対し、piはスカラ変数に対する操作が中心であることに起因すると考えている。 配列操作はどうしてもメモリアクセスが必要となってしまうが、スカラ変数に対する操作はmem2regでレジスタ操作に置き換えることができる。そのためpiではmem2reg最適化の効果が強く出たのではないかと考えられる。

また、表4を見ると実行時間が遅い項目は出力コード行数も多くなっていることがわかる。 したがって、cccをより高性能なコンパイラにするために、今後は出力命令数を減らすためにIR命令セットの再検討を行いたい。 また、まだ実装していないloop unwindingや末尾再帰などの最適化パスも実装し、最終的にgcc -O1に主要なベンチマークで勝利できるコンパイラを目指す。

結論

本記事ではcccコンパイラの実装について紹介した。 効率の良いコードに効率よくコンパイルするという目標を念頭に、cccのバックエンドにおける最適化やレジスタ割り当てのアルゴリズム、および実装上の工夫について説明した。 最後にベンチマークを示し、本記事で説明したアルゴリズムの実装によってcccの出力コードの効率が向上することを確かめた。

参考文献

  • [1] AV エイホ. コンパイラ: 原理・技法・ツール. サイエンス社, 2009.
  • [2] Rui Ueyama. 低レイヤを知りたい人のための c コンパイラ作成入門. https://www.sigbus.info/compilerbook. (Accessed on 12/11/2019).
  • [3] Gregory J Chaitin, Marc A Auslander, Ashok K Chandra, John Cocke, Martin E Hopkins, and Peter W Markstein. Register allocation via coloring. Computer languages, Vol. 6, No. 1, pp. 47–57, 1981.
  • [4] Massimiliano Poletto, Dawson R Engler, and M Frans Kaashoek. tcc: A system for fast, flexible, and high-level dynamic code generation. In ACM SIGPLAN Notices, Vol. 32, pp. 109–121. ACM, 1997.
  • [5] Christian Wimmer. Linear scan register allocation for the java hotspottm client compiler. Master’s thesis, Johannes Kepler University Linz, 2004.
  • [6] Massimiliano Poletto and Vivek Sarkar. Linear scan register allocation. ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 21, No. 5, pp. 895–913, 1999.

*1:それについてはその都度記載しています

*2:もちろんIntermediate Representationなのだが、中間表現全体を指すわけではなく特定の段階の中間表現を指してIRと呼んでいる。「名付けた」と言っているのもそのためである。

*3:翻訳単位に対応するIRは、翻訳単位内で定義された複数の関数IRが集まったものである

*4:ここでは“命令の種類”の意味で使っており、cccのIRで書く命令に対応する自然数があるというわけではない

*5:入力オペランドの表記としてrsが一般的だと気づいたのはある程度cccを実装し終えた後でした...

*6:LLVMに同じような名前の最適化パスがあり、実際それから名前は着想を得たが、最適化の内容については関連はないものとする

*7:集合の実装にBit Vectorと呼ばれるデータ構造を使用しており、集合の演算が非常に効率的に行える

*8:availableとactiveには先頭と末尾へのポインタを保持した双方向リンクリストを用い、要素の挿入/取得が定数時間で行えるようにしている

*9:物理レジスタと仮想レジスタには自然数のインデックスがついているので、レジスタからの写像は配列で実装されている

*10:System V ABIではrax, rdi, r9など

*11:なんで8回にしたかまるで記憶がない

*12:自己満足の話であり、gccより効率が良いと言いたいわけではない。

セキュリティ・キャンプ全国大会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:嬉しい