magicpak: 静的リンクなしで小さなDockerイメージを作る
おはようございます!!!coord_eです、よろしくどうぞ。
実行に必要なファイルだけをうまく集めれば、静的リンクせずとも小さなDockerイメージを作ることができます。本記事では、その作業を自動で行ってくれるツール magicpak
を作ったので、紹介します。
Dockerイメージ縮小オタク2(ツー)
☝️前編です。実行に必要なファイルだけをうまく集めれば別に静的リンクしないでも小さなDockerイメージが作れるよねって話です。
本記事では、上の記事でやったこと(実行に必要なファイルを集める)を自動でやってくれるツール magicpak
を紹介します*1。
magicpak: Build minimal docker images without static linking
magicpak
は、対象の実行可能ファイルの実行時の依存ファイルを解析して集めるツールです。これを使い、静的リンクなしで小さなDockerイメージを作ることができます。
加えて、集まった依存ファイルが対象の実行可能ファイルを動かすのに十分かどうかテストする機能、また対象の実行可能ファイルをupxで圧縮する機能が付いています。これらは便利機能であり、便利です*2。
静的リンクがどうしてもできなくて*3前記事のようなことをしなければならなくなった時に重宝すると思います。また、実行可能ファイルをそのまま(ビルドし直したりすることなく)Dockerイメージにできるのも強みで、ビルドが単純に面倒だったりソースが公開されていなかったりする時に力を発揮するのではないでしょうか。
詳しい使い方についてはREADMEを参照してください。
例
magicpak
を使い、brittany
というHaskellコードフォーマッタのDockerfileを以下のように書くことができます。このDockerfileから作られるイメージのサイズはたった15.6MBです。
FROM magicpak/haskell:8 RUN cabal new-update RUN cabal new-install brittany RUN magicpak $(which brittany) /bundle -v \ --dynamic \ --dynamic-stdin "a = 1" \ --compress \ --upx-arg -9 \ --upx-arg --brute \ --test \ --test-stdin "a= 1" \ --test-stdout "a = 1" \ --install-to /bin/ FROM scratch COPY --from=0 /bundle /. CMD ["/bin/brittany"]
この他にもいくつかの例が example/ 以下にあります。
しくみ
magicpak
は、以下の二つの方法で依存ファイルを解析しています:
- 静的解析. ELFを解析して動的リンクされたライブラリを集めます。
- 動的解析. その他の依存ファイルを、システムコールのトレースによって集めます。
ここではこれらの解析とテスト機能の実装について簡単に説明します。
静的解析: 動的リンクの依存ライブラリの解析
前記事ではldd(1)を使って依存ライブラリを一覧していました。もちろん magicpak
でもldd(1) の結果をパースすることはできますが、一方でこの出力はいわばログのようなものです。ldd(1) の manpage に出力の例は載っていますが、正確な文法は記載されていません。さらに、環境によってはldd(1)は不正確な結果を表示することのある簡単なシェルスクリプトの実装になっていることがあります*4。こういった理由からmagicpak
ではldd(1)の出力をパースせずに、documented な方法のみを用いて解析を行うことにしました*5。
さて、動的リンクされる依存ライブラリの名前はELFにそのまま格納されています。readelf(1)で見てみましょう。
$ readelf -d /bin/bash Dynamic section at offset 0xd8450 contains 25 entries: Tag Type Name/Value 0x0000000000000001 (NEEDED) Shared library: [libreadline.so.8] 0x0000000000000001 (NEEDED) Shared library: [libdl.so.2] 0x0000000000000001 (NEEDED) Shared library: [libc.so.6] ... (省略)...
libreadline.so.8
や libdl.so.2
など、依存ライブラリの名前が確かに埋め込まれています。しかしここで必要なのは、これらライブラリとしてロードされる実際のファイルのパスです。依存ライブラリ名から実際のパスを見つけ出す必要があります。
GNU/Linuxで(依存ライブラリの探索を含めて)動的リンクを担っているのはld.so(8)です。実はld.so(8)のmanpageに依存ライブラリの探索方法は書いてあります。そのためそれに従って探索をしていけばいいようにも思えるのですが、現実は非情、探索方法がドキュメント化されているといってもいくつかの部分が実装依存です*6。そのため、実際に探索をさせてみるまでどのライブラリが使われるか予測できないことが多いです。
magicpak
では対象の実行可能ファイルが用いるld.so(8)に実際に探索を行わせつつ、様々な事情から一部は自前で探索を行うことでなるべく現実の挙動と同じになるように依存ライブラリを探索しています。依存ライブラリの探索について筑波大学情報科学類誌WORD 入学祝い号2020 の『動的リンクの依存関係を解析しよう』という記事に書いたので、詳しくはそちらを参照してください。
動的解析: システムコールトレーサによる解析
さて、実行可能ファイルが実行時に必要とするファイルは動的リンクされるライブラリだけではありません。例えば辞書データや画像などの*7リソースを実行可能ファイルと別に配置し、実行時に読み込んで使用するといったことは往々にしてあると思います。そういった依存ファイルを見つけ出すために、magicpak
は動的解析を行います。
プロセスとOSとのやりとりはシステムコールを用いて行われます。ファイルを開く操作もシステムコールを介して行われるため、実行の過程でシステムコール呼び出しがどのように行われているかを解析できれば依存ファイルを調べることができそうです。そして、システムコール呼び出しをトレースすることができるのがptrace(2)です。
ptrace(2) を用いた便利なCLIとして strace(1) があります。これは引数のコマンドを実行し、そのプロセスのシステムコール呼び出しとその引数、戻り値を標準出力に出力してくれるツールです。strace(1)を用いてシステムコール呼び出しの様子を見てみます:
$ strace bash -c true 2>&1 | grep open openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3 openat(AT_FDCWD, "/usr/lib/libreadline.so.8", O_RDONLY|O_CLOEXEC) = 3 openat(AT_FDCWD, "/usr/lib/libdl.so.2", O_RDONLY|O_CLOEXEC) = 3 openat(AT_FDCWD, "/usr/lib/libc.so.6", O_RDONLY|O_CLOEXEC) = 3 openat(AT_FDCWD, "/usr/lib/libncursesw.so.6", O_RDONLY|O_CLOEXEC) = 3 ... (省略)...
このように、ptrace(2)を使うとプロセスの呼び出したシステムコールとその引数を追いかけることができます。すなわち、ptrace(2)でopen系のシステムコールの呼び出しを記録していけばプロセスが開いたファイルを一覧することができます。
magicpak
では対象の実行可能ファイルを実際に実行し、システムコール呼び出しをptrace(2)でトレースしています。そしてopen(2)やopenat(2)で開いているパスが存在した時、対象の実行可能ファイルはそのファイルに依存するとみなして記録していきます。ptrace(2)を用いた解析アルゴリズムについても簡単に筑波大学情報科学類誌WORD 入学祝い号2020 の『動的リンクの依存関係を解析しよう』という記事に書きました。詳しくはそちらや、magicpak
での実装を参照してください。
テスト
対象の実行可能ファイルが実行時に必要とするファイルをmagicpak
が必ず集めることができるとは限りません。なぜなら、プログラムの実行時の挙動を実行前に完璧に把握することはできないためです。
そのような状況で、生成されたイメージについてある程度安心するためにmagicpak
はテスト機能を備えています。これは生成された依存ファイルと対象の実行可能ファイルだけを置いた時に(=生成されるDockerイメージと同じ状況)、正しくテストコマンドが実行できるのか確認するものです。テスト機能の実装にはchroot(2)を使っています*8。
おわりに
今回は少し設計に気を使って、(気負わない程度に)クリーンアーキテクチャを意識してコードを書いてみたんですがどうなんでしょう。そのおかげか開発体験は良かったです。それから、Rustをやってるとオブジェクトが今どこにいてどう動くのかコード上で表現できていいですね...フフ...
Dockerイメージ縮小オタク
おはようございます!!!@coord_eです、よろしくどうぞ。
動機
dockerイメージが小さくなると→嬉しい!*1
一般的なテク
multi-stage build
ビルド環境とか最終的なイメージには必要ないんで...ビルドした後、必要なものだけ最終的なイメージに引っ張ってきます。
upx
バイナリ詰めるマン。なんでかバイナリサイズが1/10とかになる*2。普通に怖い
スム〜ズに本題に入るためにまずシングルバイナリを否定します。シングルバイナリを否定してもいいですか?シングルバイナリがかわいそうですが...
シングルバイナリ作るのしんどくないですか?しんどいですね。みんながみんなGoを書いているわけではないので...
実は、シングルバイナリを作らず極小dockerイメージを作る方法があるんです!*3
実行に必要なものをリストアップしよう
シェル芸をな*4
大体の場合*5*6*7*8、実行に必要なものは実行ファイルそれ自体と動的リンクされたライブラリ、そして動的リンカ(プログラムインタプリタ)です*9。前者はldd(1)で、後者はreadelf(1)でそれぞれ取得します。
{ \ echo "/path/to/your/executable"; \ readelf -l "/path/to/your/executable" \ | grep "program interpreter" \ | sed -e 's/^.*: \(.*\)\]$/\1/'; \ ldd "/path/to/your/executable" \ | awk -F'=>' '{print $2}' \ | sed -e 's/(.*)//' -e '/^\s*$/d' \ | awk '{$1=$1};1'; \ }
おそらくリンクが混ざっているので、次のコマンドにパイプして*10リンク元とリンク先を両方ともリストに加えてやります。
xargs -I{} bash -c "echo {}; readlink -f {};"
これで実行に必要なファイルのリストができました!あとはこれを次のコマンドにパイプして、全ての必要なファイルを一つのディレクトリに詰めます。
xargs -I{} cp -r --parents {} /bundle
いいですね。では†次のステージ†へ...
FROM scratch COPY --from=0 /bundle/ /.
必要なものは全部 /bundle/
に入ってるので、ベースイメージはscratch
です。 COPY
でさっき/bundle
にコピーしたファイル達を /
に展開して...終了!
実例
hlintというHaskellのLintツールのイッミジを作ってみます。Haskell製のツールで、シングルバイナリを作るのがちょっとめんどくさい*11、なので今回の食材にぴったり。...では、出来上がったDockerfileがこちらです!
FROM haskell:8 RUN cabal new-update # install ARG INSTALL_DIR=/usr/bin RUN cabal new-install hlint-2.2.11 --installdir "${INSTALL_DIR}" --install-method copy # prepare for compression WORKDIR /tmp ADD https://github.com/upx/upx/releases/download/v3.95/upx-3.95-amd64_linux.tar.xz upx.tar.xz RUN tar --strip-components=1 -xf upx.tar.xz && mv upx /usr/bin/ # compress executable RUN cp "${INSTALL_DIR}/hlint" /tmp/hlint_copy RUN upx -q -9 --brute "${INSTALL_DIR}/hlint" # collect runtime dependencies RUN { \ echo "${INSTALL_DIR}/hlint"; \ echo "$(which git)"; \ readelf -l /tmp/hlint_copy \ | grep "program interpreter" \ | sed -e 's/^.*: \(.*\)\]$/\1/'; \ { ldd /tmp/hlint_copy; ldd $(which git); } \ | awk -F'=>' '{print $2}' \ | sed -e 's/(.*)//' -e '/^\s*$/d' \ | awk '{$1=$1};1'; \ } | xargs -I{} bash -c "echo {}; readlink -f {};" \ | xargs -I{} cp -r --parents {} /bundle # copy FROM scratch COPY --from=0 /bundle/ /. WORKDIR /work CMD ["${INSTALL_DIR}/hlint"]
hlint
には--git
オプションがあって、git
管理対象のファイルのみにlintを行うといったことができます。そこそこ便利なので、--git
オプションが使えるように上のDockerfileではgit
を同梱しています。このように必要なものをザクザク足していくことも、できるんですね(小並感)。でも、イメージサイズは?はい、こちらになります!
$ docker image ls ... coorde/hlint 2.2.11 662fad71d2d6 4 weeks ago 13.6MB ...
小さめで嬉しいですね。今回作ったcoorde/hlintはボクがバイト先で作っているソフトウェアのCI上でブンブン働いています。
まとめ
Dockerで...どっかーんwwwwwwwwwwww
— coord_e (@coord_e) 2020年3月22日
参考文献
- GitHub - larsks/dockerize: A tool for creating minimal docker images from dynamic ELF binaries.
- List binary dependencies to build a minimal docker image from scratch · GitHub
- How to create the smallest possible docker container of any image — Xebia Blog
- Creating minimal Docker images from dynamically linked ELF binaries · The Odd Bit
型クラスのご紹介
この記事は型 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
には二つの実装があり、引数がint
かfloat
かによって呼び分けることができます。=
についても同様で、実際に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
え〜、list
もoption
もFunctor
と呼ばれる共通の構造を持っており、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におけるリテラルにはの書体を使用する。メタ変数が集合の上を動くことをと表記する。列について、のときは空の列とする。また、メタ変数 の0個以上の列をと表記し、列に含まれる要素を元とする集合を]と表記する。
二項関係と, の元, について、を]と表記する。またをと表記する。
その他、集合や関係に関して標準的な記法を用いる。また今後も定義を述べた後にそれに関係する略記や記法を導入することがあり、それについてはその都度記載する。
形式化
class
, instance
宣言を式中で陽に扱う、高階型クラスの体系を考える。推論規則は[2]や[5]をベースにしている。[5]の形式化とは、class
/instance
が式である、型変数のカインドを明示している、の二点で異なっている。
型は[2]の定義をそのまま使う。は型コンストラクタ名で、int
とMaybe
とかそういうのです。
え〜 が我々が普段呼ぶところの型なんですが、ここでは[2]に倣って型コンストラクタと呼ぶことにします。待って、型に乗っている は*8…これは型の種 (kind) です。種とは何かの説明はここではしませんが、直感的な説明としては「型の型」です。[6]の29章に詳しく書いてあると思います。さて、種を以下のように定義します:
を特に型 (type) と呼びます*9。は種 を持つ型コンストラクタ、 は型を取って型を返す型コンストラクタ変数、といった具合です。型の定義に内因的に種が含まれている点に注意してください。なお、今後とをそれぞれ単に, と表記することがあります。またをと表記します。さらに型中の型変数をそれぞれで置き換えた型をと表記します。また の代わりに型を部分に含む別の要素を置く場合があるが、その場合は部分の型に同様に代入したものを表記している(ただし型スキームに対しては定義しない.)*10。
次に型にまつわる様々を定義していきます。
はクラス名、は述語 (predicate)であり、述語はとクラス との関連を表しています。
それぞれ型、修飾型 (qualified type)、型スキーム (type scheme)です。型スキームで全称量化されている型コンストラクタ変数 はだけでなく任意のカインドを取ることができる点に注意してください。なお、のの部分のことを指してコンテキスト (context)と呼びます。
さて、下に今回の言語の文法*11を示します。なお、 を1
, "string"
みたいなリテラルの上を動く文字として使用しています。
ここに推論規則を当てていきます。ただし:
- にはリテラルとそれに対応する型が入っています。例えばです。
- は型環境 (type environment)で、変数と対応する型スキームが入っています。は型付けが進むに従って変更されていきます。
- は述語の集合です。後に述べる型付け関係に用いられているとき、これを前提(premise)と呼ぶことにします。前提はコンテキストの置き場で、直感的には述語を除去するときに使えるの前提条件です。実際にの上で除去できるコンテキストは消せると行った操作があります()。
- は
class
とinstance
によって定まる、コンテキストの包含を表す二項関係です。この のもと、での時が実際に除去可能 (直観的にはならば) だということを表す二項関係を定義します。
これらを用いて型付け規則を定義します。型付け関係はの形をしており、「, , のもとで式 は型スキームが付く」と読みます。下に具体的な型付け規則を示します。なお、規則中で、をの略記として、また]をの略記として用いています。
と 以外はほとんど[2]からの引用です*12。 一方でclass
とinstance
については[2]の中で
The precise definition of entailment is determined by the class and instance declarations that appear in a given program.
としか言及されていないので*13、 と 、あとあたりを自分で考えました (👈大丈夫か?)
推論例
この推論規則の適用の様子をいくつか紹介します。まずは一応おさらいとして普通のHMの範囲で型付けの様子を見てみよう:
let id = \x. x in (id id) 1
ウォウ〜。デカいがまあこんな感じ*14。 で束縛前に型スキームにしてやることで、使うときに で好きな型にインスタンス化してやることができる。よかったね
じゃあ次は型クラスを使った式の推論を見てみる。
class Eq a^* where eq :: a -> a -> bool in instance Eq int where eq = eqInt in eq 1 2
でがしっかり葬り去られているのが見えると思います。
ここからコンテキスト付きのインスタンスとか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:型になんか乗っていますが、は単にメタ変数として扱います
*10:このあたり雑で申し訳ない...+型スキームは少なくともそうじゃないので
*11:superclassの表記が左矢印なのはPureScriptの真似
*12:表記を変えたぐらい
*13:[2]ではclassとinstanceはグローバルに宣言されることになっているので、式について議論する分にはこれで十分だったんじゃないかな
*14:居ない環境は省略している
cccコンパイラのバックエンド
この記事は言語実装 Advent Calendar 2019の23日目です。
おはようございます!!!coord_eです、よろしくどうぞ。
はじめに
実は、この記事の大半の文章は以前に別の目的で執筆したものです。
そういえばcccについて記事を書いていないな、ということで、少し内容を変更しつつ体裁を整えて公開することにしました。
なお、ブログやスライドなどで散々「セルフホストする」「gcc -O1
に勝つ」と豪語しておりましたが、そのどちらも達成できていません。残念。
この記事にはPDF版があります。以下のリンクからダウンロードできます。
元がなので多分PDFの方が読みやすいです。基本的にはPDFとはてなブログの内容は同一ですが、長いアルゴリズムなどは省略してPDFにのみ載せていることがあります*1。また、内容が同じ二つの文書を同時にup-to-dateに保つのは大変そうなので、何か変更する必要が生じたときは僕のやる気によってはPDF版のみ更新してはてなブログの内容が古くなる可能性があります。
この記事のソースはGitHubに公開しています。 また、誤字や誤謬を発見された方は@coord_eまでご連絡いただくかリポジトリにIssueやPull Requestを送ってくださると幸いです。
概要
cccは、自分がセキュリティ・キャンプ2019に参加した際に開発したコンパイラだ。 C11のサブセットをコンパイルする事ができ、暗黙の型変換や初期化子、宣言子に代表される複雑な言語機能を規格に忠実に実装している。 さて、cccは効率の良いコードに効率よくコンパイルすることをテーマに開発を行った。 そのテーマのもと、出力コードの効率を高めるためにcccに実装した技術についてこの記事では説明する。 最後にベンチマークの結果を示し、実装の効果を確かめる。
cccコンパイラの構成
cccコンパイラはCのソースコードを受け取りアセンブリのコードを出力する。cccではワンパスでは行えないと思われる変形や最適化を用いているため、コンパイルの段階に応じて複数の中間表現を用いている。
一つ目の中間表現が抽象構文木(Abstract Syntax Tree, AST)だ。これは構文解析の結果を木構造で表現したもので、この上で意味解析が行われる。 もう一つの中間表現はIRと名付けた*2。これはASTよりもアセンブリに近い構造を持っており、この上で最適化やレジスタ割り当てが行われる。IRについては次節で詳しく説明している。
図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つの種類がある。
- 仮想レジスタ(virtual register)は、IR生成の際に使われる、無限個存在するレジスタ。
- 物理レジスタ(physical register)は、レジスタ割り当てが終わったレジスタ。有限個であり、出力コードのレジスタに一対一で対応している。
- 固定レジスタ(fixed regitser)は、後に説明するターゲット固有IRへの変換で生成される、割り当てられる物理レジスタが事前に決まっている仮想レジスタ。
IRを表す図中では、n番目の仮想レジスタをvn
、n番目の物理レジスタをrn
、rn
に割り当てられるm番目の固定レジスタはf(vm:rn)
と表記する。
さて、IR命令の命令セットを表1に示す。 なお、今後の表やアルゴリズムでは命令の出力オペランドを、n番目の入力オペランドを]と表記する。*5
表には記載がないが、これらの他にBIN_IMM
といった片方のオペランドに定数をとる命令やBR_CMP
といった複合命令が実装されている。これらは主にレジスタ上のデータの流れを用いた最適化であるデータフロー最適化で効率的なアセンブリを出力するために用いている。
IRはASTから生成され、IRの上で最適化やレジスタ割り当てが行われたのちにコード生成パスでx86_64のアセンブリに変換される。
ターゲット固有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にこの変換の例を示す。関数呼び出しや除算が固定レジスタを使うように変換されているのが見て取れる。
最適化
効率の良いコードを出力するため、最適化を行う。 cccではデッドコード削除やコピー伝播に代表されるデータフロー最適化やAST上の定数畳み込みなどを実装しているが、ここではそれらについては説明しない。 特にデータフロー最適化について、技術書展8にOtakuAssemblyで記事を出す予定なので、ぜひそちらを楽しみにしていてください。
さて、ここではLOAD
/STORE
以外の操作を受けていないスタック上の領域をレジスタで置き換える最適化について説明する。
この最適化パスをmem2regと名付けた*6。
mem2regで使用および実装したアルゴリズムをアルゴリズム1に示す。
ここではアドレスとして用いられているレジスタをアドレスレジスタ(address register)と呼ぶ。
LOAD
/STORE
命令のアドレスの位置にあるオペランドとして使われているレジスタがアドレスレジスタである。
CollectUses
(アルゴリズム2)でアドレスレジスタのうち、置き換え可能なものを求める。
ここではアドレスレジスタをcandidates
に集めながら、LOAD
/STORE
以外の操作を受けているレジスタをexcluded
に集めている。
また、STACK_ADDR
命令で代入されているレジスタを個別にin_stack
に集めている。
さて、置き換え可能なアドレスレジスタは、以下の3条件を満たしているものである。
- スタックのアドレスを保持している
LOAD
/STORE
以外の操作を受けていない- 置き換え不可能なアドレスレジスタと同じスタック位置を共有していない
1., 2.を満たすアドレスレジスタの集合は、で求められる*7。 そして3.を満たさないものを除外するために、置き換え不可能なアドレスレジスタのスタック位置の集合を求め、そのあとにそれを共有しているものを除外するというナイーブな方法をとった。
そして、置き換え可能なアドレスレジスタが求められたのち、ReplaceInstructions
(アルゴリズム3、PDF版に掲載)で命令をレジスタを使うように書き換えている。
図4にこの最適化による変形の例を示す。一部のスタックに対する操作がレジスタに置き換わっていることが見て取れる。 この最適化による出力コードの効率の変化についてはこの記事の後半で検討する。
レジスタ割り当て
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に示す。
このアルゴリズムでは、割り当てに際して三つのグローバルな変数を持っている。
available
は現在利用可能な物理レジスタのリスト*8で、後に述べる優先度でソートされている。active
は現在使われている仮想レジスタのリストで、生存区間の終了が遅い順にソートされている。result
は仮想レジスタから割り当てられた物理レジスタへの写像*9。
これらの変数に対する操作は、AllocSpecificReg
(アルゴリズム8、PDF版に掲載)とReleaseReg
(アルゴリズム9、PDF版に掲載)の二つの操作に抽象化されている。
アルゴリズム本体ではこれら二つの操作とspillを適切な条件で行うことで、割り当てを行なっている。
また、available
は次の条件もとソートされている。(アルゴリズム5)
なお、関数呼び出しで保存されないレジスタ*10のことをscratch registerと呼ぶ。
- 現在の関数内の固定レジスタで使用されている物理レジスタより、そうでない物理レジスタを優先する。
- 現在の関数が関数呼び出しを含むならば、scratch registerでない物理レジスタを優先する。そうでないならばscratch registerを優先する。
AllocSpecificReg
(アルゴリズム8、PDF版に掲載)からわかる通り、割り当てる物理レジスタはavailable
の先頭から選ばれる。これにより、アルゴリズム5で優先されているものから順に割り当てられる物理レジスタが選出されることになる。
さて、linear scan register allocationは、生存区間に対する一回の走査によって行われる。 アルゴリズム6に走査部分のアルゴリズムを示す。また、spill関連のアルゴリズムをPDF版のアルゴリズム7に示してある。 固定レジスタの割り当てでは、必要な物理レジスタがすでに割り当てられていた場合にそれをspillすることで物理レジスタを確保する。また、spillの対象のレジスタを選ぶ際に固定レジスタを避けるようにしている。それ以外はほぼ[6]の通りである。
図5にレジスタ割り当ての例を示す。全て仮想レジスタが物理レジスタに割り当てられているだけでなく、変換前に固定レジスタだったレジスタは、正しく指定されたレジスタに割り当てられていることが見て取れる。
評価
ターゲット固有IRへの変換や最適化の効果を確かめるために、ベンチマークを行った。 ベンチマーク環境は以下の通り。
今回は三種類のプログラムをベンチマークに用いた。それぞれ次の通り。
以下の5種のコンパイラにこれらのプログラムをコンパイルさせ、コンパイル時間と実行時間、および出力コードの行数を計測した。 計測はそれぞれ8回行い*11、平均値を算出した。
- 固定レジスタを導入する前のccc (naive)
- 固定レジスタを導入し14本のレジスタを活用できるようになったccc (better_alloc)
- 2.にmem2reg最適化を導入したccc (mem2reg)
- gcc -O0
- gcc -O1
コンパイル時間
実行時間
実行時間のベンチマーク結果を表3と図7に示す。なお、naiveのsortについてはその時点でのcccの実装にバグがあり実行時エラーが生じているため正常な計測ができていない。
出力コード行数
出力コード行数のベンチマーク結果を表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回にしたかまるで記憶がない
セキュリティ・キャンプ全国大会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です。
思うこと
いい環境で好きなことをできるのは本当に楽しい
「コンパイラのことだけ考えていてもいい」って明示的に許可された空間が良い
— coord.e (@coord_e) August 16, 2019
コーディングに集中できる環境(ディスプレイ、水分、お菓子)がありつつ実装で困ったことがあればすぐ講師の方々に相談できる最高の空間がありました。そこで作業している時間がとても楽しかったです、あの環境を用意してくださった運営やチューター、そして講師の方々には心から感謝しています。
また、コンパイラや言語処理系が好きな人たちと話すのは楽しかったしいい刺激になりました。1日目に部屋に帰った時は「おれが見ていた世界は狭かったんだな...」みたいな謎の感情をやっていた
飯の時間に多種多様な分野の人々と話したのも楽しかったです。めっちゃ面白い人だな〜と思って話していた人が、聞けば有名なプロだった、なんてことも
一方で、参加前はセキュリティキャンプについて5日間のコーディング合宿みたいなもんだと思っていたのですが、その認識は間違いでした。書ける期間は実質3日だし、2日目以外は夜に色々と他のイベントがある
なのでもっとコード書きたかったというのはあります*8 いやそれは趣旨と違うやろ せやね
来年以降参加する人へのアドバイスですが、参加前はプログラムとkintoneをよく確認した方がいいです。特にkintone、結構大事なアンケートが来ていたりするので日常的なチェックを忘れずに...
進捗はどうですか
満足したらまた別にブログ書くから待ってね
成果報告時点の進捗はこんな感じ↓
まとめ
いや最高に楽しかった
— coord.e (@coord_e) August 17, 2019
五日間ありがとうございました!
セキュリティ・キャンプ全国大会2019に参加してきます
明日(2019/8/13)からセキュリティ・キャンプ全国大会2019に参加してきます*1。私は「Y-Ⅱ Cコンパイラを自作してみよう!」ゼミに参加します。
セキュリティ・キャンプ全国大会って何?
セキュリティ・キャンプ全国大会2019は、セキュリティ・キャンプのメインイベントとして実施している合宿形式の勉強会です。 エキスパートによる実践的な講義が受講できます。また、これまでにセキュリティ・キャンプに参加された修了生による学習支援があります。
セキュリティ・キャンプ全国大会2019 ホーム:IPA 独立行政法人 情報処理推進機構
なんでこのコースにしたの
コンパイラが書きたかったので
応募用紙には何を書いたの
[問1] これまでのプログラミング歴(C言語に限りません)について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。
今までやってきたことを羅列しつつ、それぞれの取り組みで特に自分が努力したところ、またその取り組みから何が得られたのかを書くように心がけました。コンパイラに関係ないことも書くには書いた(でも低レイヤ寄りな部分を強調した)。
[問2] コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。
字句解析してトークン列ができて、構文解析してASTができて...みたいなことを書きました、各段階の表現が持っている意味がどう変化していくかみたいなのを意識した書き方をしました。
[問3] C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか?考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。
C言語のディスりが軸になっていた気がする。仕様が複雑だから大変〜みたいな... これはこれまでのプログラミング経験によって結構ばらつきそうだし、(どれだってそうだが)思ってることを書けばいいんじゃないかなあ
[問4] 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。
コンパイラへの熱意をアピールし、キャンプでは今までやったことのない分野に挑戦したいと書いた。
Cコンパイラ
参加が決まった段階から事前学習ということでCコンパイラを書いています。↓こんな感じ
キャンプ前にセルフホストしてキャンプ中は最適化やるぞ〜とか思ってたらもう前日だよ、助けてくれ*2
目標はセルフホストしつつ、gcc -O1より速い*3コードを吐かせることです
参加者の皆さんへ
名刺が無限にあるからもらってね
5日間よろしくお願いします。
まとめ
キャン今日じゃなくて明日だよねってN回確認してる
— coord.e (@coord_e) August 12, 2019
mlmlの実装について
前記事: 自作OCamlコンパイラでセルフホストした - molecular coordinates
mlmlの制作のまとめとしてここに実装の詳細を記しておきます。
mlmlとは
自作OCamlコンパイラです。詳しくは前記事を参照してください。
全体の構成
以下の図にmlmlの構成を示します。
ファイル名を入力として受け取ります(①)。そのファイルをエントリポイントとしてBundlerが必要なソースを集めて一つのASTに纏め、Analysisに渡します(②)。AnalysisがASTに様々な変形を施し、Codegenに渡します(③)。CodegenはASTからアセンブリを生成し、出力します(④)。
依存関係の解決 (Bundler)
mlml/mlml/bundler at develop · coord-e/mlml · GitHub
まず受け取ったファイルに字句解析・構文解析を済ませます。次に構文解析によって作られたASTに対して依存関係の解析を行い、そのファイルが依存しているモジュールを探します。見つかった依存モジュールに対しても同じように解析を行い、下のようなツリー状のデータ構造*1を構築します。
次に、”自身が依存するモジュールが常に自分の前に存在するように"、このツリーを潰して直線状に並べます。(追記: この操作はトポロジカルソートと呼ぶようです。@syobon_hinataさん、ありがとうございます)
最後にこの並びに従ってモジュールを並べてやることで、それぞれのモジュールが必要なモジュールを参照可能な状態になった大きな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 ()
ここではソースコード上で表記されている名前(f
、Module.g
など)を相対パス、変換後(Resolve後)の名前を絶対パスと呼ぶことにしましょう。
さて、このコード内では二回f
という相対パスが使われていますが、その二つは実は違う実体を参照していることがわかります。
参照先が明確になるよう書き換えてみると(1)のf
はModule1.f
、(2)のf
はModule2.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
ここではf
がx
, 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
内でa
、b
が参照されていますが、それは関数の引数(x
)ではありません。ここではa
、b
のような変数をキャプチャ変数と呼ぶことにします。また、それとは別に、引数や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 ) 実際に中身を使うときは右シフトすれば元の値が取り出せます。
いちいち整数を扱う度にこの変換を噛ませるのは大きなオーバーヘッドになりそうですが、意外とそうでもないのがこの表現の面白いところです。
例えばn+m
を考えると、求めるmarkedな値は(n+m)*2+1
となります。これは(n+m)*2+1=(n+m)*2+2-1=(n*2+1)+(m*2+1)-1
と変形できるので、markedな整数同士の加算はadd
とdec
の二命令で実装できるわけです!これと同じように減算や乗算、論理否定なども"値を取り出す→計算する→作り直す"の手順を踏まずに少ない命令数で実装できます。最初に考えた人頭いいなあ。
ということで、値のLSBを見れば数値なのかポインタなのか判別できるようになりました。
ポインタに続くデータのサイズ & 文字列なのかどうか
ポインタが指す先の一つ目のデータにデータサイズを格納しています。
ただ、文字列かどうかも判別しなければいけないのでこのデータサイズ用の領域のLSBをこのフラグに使っています。データサイズ領域のLSBが1なら文字列、0ならそれ以外のデータです。
具体例を見ていきましょう。下の図に(1, (2, 3))
をmlmlがどう扱うかを示します。背景の色が黒ならLSB=1、白ならLSB=0であることを表しています。
タプルは文字列ではないので、データサイズ領域のLSBは0になっています。
文字列を含む構造は以下のようになります。文字列の長さをデータサイズ領域の次にmarked intとして格納しています。これは文字列長がO(1)で求められると色々と*12便利だからです。
構造比較の実装
と、いうような感じで値の種類を実行時に判別しています。
構造比較演算子=
はランタイムライブラリで実装されています。基本的には値の種類を見て再帰的に構造を比較していく感じです。
各種データ構造の実装
タプルは先ほどの画像で示した通りデータが並んでいるだけです。
ヴァリアントはインデックス付きのタプルとして実装しました。以下の型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
ここで、型t
はvalue
とtuple
の二つのフィールドをもつレコード型です。出現順にフィールドにインデックスをつけていきます。ここでは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 GCはmalloc
をGC_malloc
に変えるだけでお手軽にGCが使えてしまう*13 、本当に最高な優れものです。GCなしだとセルフホストしようとした時にあっという間にメモリを食いつぶしてしまったので、GCが必須でした。
おわり
ここまで読んでくださりありがとうございました。mlmlの実装で凝ったことしている部分はだいたいこんな感じです。
あまり調べもせず思いついた方法に突っ走ってしまう傾向が強かった気がしています。モジュールの扱いはかなり改善の余地があると感じているので次に似たようなことをするときはもう少しマシな実装になるよう前例を調べてみようと思います。ocamlのモジュールはレコードになっているらしい*14。
参考資料
mlmlの制作にあたり、以下の資料を参考にしました。
- GitHub - ushitora-anqou/aqaml: Yet another tiny self-hosted OCaml compiler with an also tiny standard library.
- はりぼて自作OCamlコンパイラAQamlでセルフホストしてみた | カオスの坩堝
- パーサとレキサはaqamlを参考に作りました。ありがとうございます。
- The OCaml system, release 4.07
- 速攻MinCamlコンパイラ概説
- OCamlのformat (型安全なprintf/scanf) の仕組み - 簡潔なQ
- Compiler Explorer
- Random memo of OCaml programming
*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