molecular coordinates

/var/log/coord_e.log

自作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に使わせることで心の健康を取り戻しました。やったね。

まとめ

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

初手脱落

みてこれ

実は過去にも2本ぐらいブログを書き始めかけたことがあるのですが,結局続きませんでした. 今回は続くように頑張ります.

続かなかった(つか始まってないじゃんねこれ)

というか、ずっとこのブログ一般公開してなくて、とても虚しい感じになってた。ワロ

と言っても、ツイッチャー以外で日本語を書く場面がないとどんどん下手なオタク構文しか喋れない人間になっていく気がする

たまにここに書くかなーって

Hello, Blogging

ノリでブログ始めました.

技術的なことはQiitaと両方に書くかもしれませんし,あっちだけに書くかもしれません.

学生LTなどイベントに参加したあとに記事を書きたいな〜とか,Qiitaの規約違反が怖いようなこと(有益かどうか,微妙なことなど)を書ける場所が欲しいな〜ということで開設しました.

実は過去にも2本ぐらいブログを書き始めかけたことがあるのですが,結局続きませんでした. 今回は続くように頑張ります.