自作OCamlコンパイラでセルフホストした
概要
ここ最近作っていたOCaml*1コンパイラmlml*2でセルフホストを達成しました。ヤッター
mlmlには以下に代表されるような、OCamlの基本的な機能が実装されています。
- 再帰関数
- ヴァリアント、レコード
- パターンマッチ
- カリー化
- モジュール
mlmlの特徴
ほぼフルスクラッチ
今回LLVMやパーサジェネレータに頼らないコンパイラづくりを体験するのが目的の一部だったので、結果的にフルスクラッチらしきこと*3になりました。OCamlの標準ライブラリ以外の外部ライブラリを使用しておらず、字句解析器・構文解析器は手書きです。
OCamlで書かれている
セルフホストしたのでそれはそうなんですが、OCamlで書かれています。
また、言語処理系を書く場合ランタイムライブラリはC言語で用意してリンクする場合が多いと思いますが、今回は謎に意地を張ってしまい全てOCaml内で完結させました。これがよかったのかはよくわからないんですが、文字列などのデータ構造を扱うのにコード生成部と共通のコードを使えるので保守性が上がった(気がします)。
x86_64のアセンブリを吐く
GAS*4に流すことを想定している、x86_64 glibcの環境向けのアセンブリを吐きます。
今までLLVM IRを出力するコンパイラしか作ったことがなかったので、x86もやってみようと今回チャレンジしてみました。
duneの真似をするバンドラーがくっついている
mlmlではduneをビルドシステムとして使っています。そのため気軽にソースを複数のファイル・ディレクトリに分割して開発できました。
しかしセルフホストするときに自分自身が複数のファイルに分割されていると、それらをまとめる部分も作らなければいけません。 ということで、mlmlにはduneの動作をシミュレートするバンドラーがくっついています。内部ではファイル間の依存関係を解決する部分まで書く羽目になりました。これはかなり沼で*5、セルフホストをやる上では設計ミスだったなと思っています。カッコつけずに少ないファイルで作ればよかった。
作り始めたきっかけ
なんとなくOCamlを書けるようになろうと思ったので、公式のチュートリアルをやりました。4月の初め頃のことです。
それが一通り終わったのでコンパイラを作ることにしました。
今ですが、OCamlの練習として(?)パーサジェネレータとLLVMを使わない縛りでコンパイラを書いている
— 歯車 (@coord_e) 2019年4月4日
やっと簡単なコード生成ができるようになった (x86に不慣れすぎる...) pic.twitter.com/O7KdJaYPja
コンパイラならなんでも良かったんですが、@ushitora_anqouさんの記事"はりぼて自作OCamlコンパイラAQamlでセルフホストしてみた | カオスの坩堝"を読んでセルフホストは楽しそうだなー思い、OCamlコンパイラを作ることに決めました。
その後はハッシュタグ#mlml_compilerに進捗を投稿しつつ制作を続け、開始からだいたい50日でセルフホストに至りました。二ヶ月ですね*6
実装の方針
完璧なOCamlコンパイラを作ろうとしたらいつまでたっても終わらないので、制作を始めるときにいくつか制限を決めました。
出力コードの効率は気にしない
x86_64を直接扱うコンパイラを書くのは初めてなので、まずは効率を気にせず確実に動くコードを吐かせることを優先してコードを書いていくことにしました。
型システムは作らない
これなんですが、作り始めた当時「型システムは実行時エラーを静的に検出するためのものなのに僕は型情報に依存したコード生成をやっている*7!型がなくてもコード生成ができるべきだ」という考えがあったことに起因します。(あとで知ったんですがこの考えは正しいわけではなく、OCaml含む大抵の言語は型情報が項に内因的に含まれています*8。よってコード生成で型情報を利用するのは当然のことです)
結果、型なしでOCamlを実装することになりました。意外にも大体の機能が型推論なしで実装できたんですが、使い勝手が悪かったり一部妥協があったりします。*9
テストイメージ内以外での動作は考えない
出力の可搬性を重視したいならLLVM IRを吐けばいい話なので、"動く環境が存在する"ことを重視することにしました。開発用のDockerイメージを用意し、その内部でテストなどを走らせました。
Dockerコンテナ内でワークフローを回せるようになっているので、macOSやWindowsでも開発が行えるようになっています(きっと)
内部構成
技術的な詳細は別記事にまとめたので、ここでは処理の流れを描いた図を示すだけに留めます。
クロージャ変換やα変換、ヴァリアント/レコード/パターンマッチを実装する体験ができたのは良かったです。作る前はどうやってやるのか見当もつかなかったので...
セルフホストについて
mlmlでは
ことを検証し、セルフホストできたという結論に達しました。*10
セルフホスト用スクリプトを書いたので、誰でも試すことができます。cloneしたディレクトリで以下のコマンドを実行します*11(完了まで一日ぐらいかかります)
./dev/exec.sh ./dev/self_host.sh
ちなみに"セルフホスト"の定義についてTwitterでアンケートをとったら以下のようになりました。
"セルフホスト"
— 歯車 (@coord_e) 2019年5月20日
「自分自身をコンパイルできる」派が優勢のようです。僕は「第一世代と第二世代の出力が一致する」派です。真相はいかに
感想
前方参照がないことのキツさ*12やヴァリアント・レコードの実装の簡単さ*13といったことを身をもって感じられたのが一番の収穫だと思っています。
OCamlへの理解は深まったかというとそうでもなくて、オブジェクト指向やGADT、ファンクタなどに触れていない。これは残念です。(セルフホストがしたかったのでしょうがないが)
あとは地味に再帰をガリガリ書く関数型プログラミングをやるのは今回が初だったりするので、慣れることができてよかったなと思っています 再帰にかなり苦手意識があったので...
今後の展望
TaPLを読み進めたりSoftware Foundationsを進めたりしたいのでしばらくはmlmlから離れるつもりです。しかし、例外の実装には興味があるのでいずれmlmlに追加したいなと思っています。
次回に続く
読んでいただきありがとうございました。
次は役に立つことを書くぞ!! (技術的な詳細を書いていこうと思います)
追記: 実装の詳細について書きました。
*1:とある関数型プログラミング言語 http://ocaml.org/
*2:開始当初は"モルモル"と読むつもりだったが実際そう読んだことはない
*3:ビビリなので自信がない 「フルスクラッチ」ってなんだ?
*5:しかもSys.readdirを実装しなきゃいけない!!
*6: ゴールデンウィーク中に終わらせるつもりだったんですが全然終わらなかった(それはそう)
*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
参考:
- Raspberry Pi - Install Clang 8 and compile C++17 programs | Solarian Programmer
- Raspberry Pi - Install GCC 8 and compile C++17 programs | Solarian Programmer
まとめ
うちにあるラズパイ全滅したかと思ってめちゃ焦った(なんか頑張ったら動くようになった)
— 歯車.v (@coord_e) 2019年1月21日
*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:
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++の表を一部修正
【適当】モチベーションを維持しながら開発する方法
注: このブログでは内容の正しさを検証する気がないので真に受けると後悔するかもしれません
エモくなったのでCIが頑張ってる間に書く
🎉 一週間かけてやっとCI通過🎉
— coordeは起きれない (@coord_e) 2018年12月26日
今回1週間ぐらいCIが通らなくて病んでしまったので(なんてか弱い心!)、そこからちょっと教訓じみたものを捻り出しました
それは何かというと: (自分からの距離)x(1サイクルにかかる時間)が大きい環境で試行錯誤をしない
※主観しかないので、任意の文の先頭に"coordeの場合は"をつけていただければ幸いです。
自分からの距離 is
コードが走る場所と自分の、心理的な距離
イメージとしては ローカル<コンテナ内<リモート<CI
になる
このパラメータは、
- シェルが使いたいときに使えるか
- こちらからの操作に対するレスポンスが早いか
- ファイルシステムにアクセスできるか
- 物理的な距離
- など
で評価される気がします。知らんけど。
1サイクルにかかる時間 is
結果が得られて、次の行動を決定するまでにかかる時間
。多分。
ビルドするのに時間がかかるプロジェクトならこれが大きくなるし、Dockerイメージのビルドとかもでかい。
これが大きくなる最悪のパターンとしては機械学習がある(と思う)。
(自分からの距離)x(1サイクルにかかる時間)が大きいこと is
CIで機械学習する
とか、CIで大きなプロジェクトをビルドする
とか
どうやって小さくするのか
まあCIでビルドするな!なんて無理な話なので、近くの環境でうまくいくことを保証してから遠くに持っていけばいいと思う、するとCIで試行錯誤する範囲が小さくなるので...
なので僕の場合はDockerイメージに固めて、ローカルでうまくいったDockerfileをCIに使わせることで心の健康を取り戻しました。やったね。
まとめ
Dockerを使い始めたら何もかもがうまくいくようになりました ここ一週間の苦労が嘘のようです (10代男性)
— coordeは起きれない (@coord_e) 2018年12月26日
ブログではなるべく敬語ではなく普通に書こうと思っていたんだけど、難しい...やめるか