micro Elixir / ZEAM ロードマップ(2018年度)
SWEST20にて発表した micro Elixir / ZEAM 構想(下記)について，2018年度のロードマップを発表します。
ロードマップ 第1段階
手始めにコード生成系から着手しています。
この検討は micro Elixir で基軸となる Polymorphic LLVM インラインアセンブラの開発に向けて行なっています。
たとえば加算は，整数と浮動小数点数といった複数の型で同じように機能します。このような性質を 型多相(Polymorphic) といいます。
アセンブリコードを記述する時には，整数の加算命令は add，浮動小数点数の加算命令は fadd，整数と浮動小数点数の組み合わせの時には浮動小数点数へのキャストの命令 sitofp を挿入した上で fadd といった具合に，型に合わせて命令を多少変化させていく必要性はあるものの，どの型の場合にも加算を行うという目的は同一です。そこで，型多相にLLVMアセンブリコードを記述する Polymorphic LLVM でアセンブリコードを記述すると，Elixir との接続性が良くなるのではないかと考えました。
また，Rustのような型安全なコードを生成することは，とても重要になってくると考えています。型に当てはまらない値を与えた時に，どんな場合でも適切にエラーとして処理してくれる性質のことを型安全(type safe)といいます。
Polymorphic LLVM によるインラインアセンブリコード記述でも Rust のように基本的に型安全性を保証するようにしたいと考えています。
そこで，型多相かつ型安全なコード生成について研究を進めました。
今までの開発成果
|> ZEAM開発ログ v.0.4.0 型多相かつ型安全なNIFをC言語で書いてみる
|> ZEAM開発ログ v.0.4.1 型多相かつ型安全なNIFの LLVM IR コードを読み解く
|> ZEAM開発ログ v.0.4.2 型多相かつ型安全なNIFのコードを分岐予測の観点で最適化する
|> ZEAM開発ログ v.0.4.3 型多相かつ型安全なNIFでオーバーフローを検出する
|> ZEAM開発ログ v.0.4.4 INT64判定をマクロで簡単に判定する
|> ZEAM開発ログ v.0.4.5 ビット列について調べてみる
|> ZEAM開発ログ v.0.4.6 OKを使ってNIFのエラー処理をエレガントに書いてみる
|> ZEAM開発ログ v.0.4.7 BigNum をどのようにNIFで扱うか考える
|> ZEAM開発ログ v.0.4.8 INT64判定をGPUベンチマークに組込む
以上の研究により，C言語や LLVM IR でどのようなコードを生成すれば型多相かつ型安全で，分岐予測の観点で最適化されたコードを生成できるかがわかりました。
この研究成果を受けて，近日中に算術命令と論理演算命令をサポートするインラインアセンブラを開発します。このインラインアセンブラは，Elixirのマクロ機能を用い，Elixirのコード中に埋め込まれたインラインアセンブリコード記述から，LLVM IR のコードを生成し，NIFとして Erlang VM に組み込んで実行できるようにします。
この段階では，型安全性を最重要視し，型検査のコードを確実に入れていくことを目指します。まだ実行効率については考慮しません。また，整数演算はINT64の範囲に収まるものとし，収まらない場合にはエラーを発生させることにします。
第1段階の目標リリース時期は2018年10月頭ごろまでを想定しています。
ロードマップ 第2段階
第2段階では，第1段階のインラインアセンブラを利用して，整数型(INT64)・浮動小数点型の変数と，算術式・論理演算式，そしていくつかの基本的な制御構造からなる micro Elixir ファーストバージョンをコンパイルして Erlang VM の NIF として実行できる処理系 ZEAM ファーストバージョンを開発します。
プログラムを記述するためには条件分岐が不可欠です。一般的なアセンブリ言語では原始的にブランチ命令を用いることが多いですが，これには次の問題点があります。
- ブランチ命令では表現力に乏しい: Elixir の強力なパターンマッチや制御構造と比べて，ブランチ命令はあまりにも原始的で表現力に乏しいです。
- ブランチ命令で型安全性を保証するのが面倒: ブランチ命令ではラベルを用いて飛び先を指定しますが，ラベルが正しいアドレスになっていることを保証する機構を設計・実装するのはやや面倒です。
- ブランチ命令を用いて形成される任意の制御構造が有限時間内に完了することを保証できない: このような問題を停止性問題といいますが，停止性問題を判定できるアルゴリズムは存在しないことが証明されています。ブランチ命令を内在する限り，私たちが目標の1つとしているハードリアルタイム性の保証のために必要なプログラムコードの実行時間の推定ができなくなってしまいます。
そこで，インラインアセンブリコードからブランチ命令を排除することにしました。代わりに，Elixir の持つ強力な制御構造をサポートすることにします。この段階では，まだ繰り返しはサポートしないものとします。
第2段階の目標リリース時期は2018年12月頭ごろまでを想定しています。
ロードマップ 第3段階
第3段階では，単一の型の要素からなるリスト構造と Enum.map による繰り返しをサポートします。
リストについて，当面，単一の型の要素に限定するのは，データ構造を簡素化し高速化できるようにするためです。
繰り返しは再帰ではなく，Enum.map を基調とします。任意の再帰を含むプログラムの停止性問題を証明することはできない一方，ループを構成するのが有限長のリストに対する Enum.map だけならば，有限時間で終了することが保証できるからです。
第3段階の目標リリース時期は2019年1月末ごろまでを想定しています。
ロードマップ 第4段階
第4段階では Enum.map に対する SIMD 命令の生成をサポートします。この機能は Hastega (ヘイスガ) と称し，将来は GPU や FPGA へと発展していきます。
第4段階の目標リリース時期は2019年2月末ごろまでを想定しています。
この機能と，別途，研究開発するElixirベースの機械学習ライブラリを結合し，高速に動作する機械学習環境を構成します。
追記: 助言を受けて修正案を出しました！
「ZEAM開発ログ v.0.4.9 助言を受けて研究計画について再考する」(Qiita記事)を参照ください。
新しい研究計画案は次のようになります。
新しい研究計画
|> ロードマップ第1段階: Polymorphic LLVM インラインアセンブラによる型多相・型安全なコード生成 (2018年10月リリース)
|> ロードマップ第2段階: リスト構造と Enum.map，SIMD命令のサポート (Hastega: ヘイスガ) (2018年12月リリース)
|> ロードマップ第3段階: インライン展開・定数伝播と，最適化前提のElixir制御構造のサポート (2018年3月リリース)