bootstrap

第11回 カーネル/VM 探検隊

Transcript

1. アセンブリ言語のみで 言語処理系を作った話 （原題: ブートストラッピングで言語処理系を作った話) 第11回 カーネル／VM探検隊 中村 晃一
2. 本日の資料・コード •https://speakerdeck.com/nineties/bootstrap •https://github.com/nineties/amber
3. 自己紹介 • 中村晃一(@9_ties) • IoTデバイスを作っています • idein.jp • 課外活動 • 圏論勉強会、パターン認識・機械学習勉強会などの講師
4. 処理系作りが趣味でした • 学生実験でコンパイラ係に • O’CamlでminCamlコンパイラを作ったり • Haskellでも作りました github.com/nineties/Choco • 大学院では最適化コンパイラの研究をしました • 特殊なプロセッサの為のコンパイラを書いたり • 型推論器を書いたり
5. 自分の言語を作ろうと思いました • 言語名: 最初はrowl ⇒ 後にamber • ただ作るだけでなくその過程を楽しみたい • どうやったら楽しめるだろうか？
6. 縛りを入れて作ろう • ルール 1. 実装言語はアセンブリ言語のみ 2. 既存ライブラリは使ってはならない 3. コード生成ツールは使ってはならない libcなど Cなどの高級言語 flex/bisonなど
7. 作戦：ブートストラッピング アセンブリ言語でちょっと高級な言語1の処理系を書く 言語1でもうちょっと高級な言語2の処理系を書く 言語kでamberの処理系を書く amberでamberの処理系を書く 今ココ(暫らく放置中)
8. 何の意味があるの？ • 純粋に楽しみとして • 知識・技術・ノウハウを磨くのに役に立つかも • 効率の良い学習方法ではありませんが・・・ • ツール群を作った先人への尊敬と感謝が芽生える
9. 以下ダイジェストでお見せします
10. 1.アセンブリで言語「rowl0」を実装
11. アセンブリより少し高級な言語を作ります • 言語名: rowl0 • コンパイラ名: rlc
12. トークンの正規表現から
13. 状態遷移図を書いて
14. 状態遷移表にして
15. レキサを作ります
16. 文法をBNFで書いたら
17. 再帰降下法でパーサを作ります
18. コード生成はパースと同時にやりました • この時点でメモリ管理を実装 するのは面倒 ⇒ 構文木作るの面倒 コード生成
19. 最初の言語「rowl0」が完成！ • 変数管理が出来ない • 関数引数はp0,p1,p2,... • ローカル変数はallocate(n)でスタックメモ リを確保し x0,x1,x2,...で参照
20. 2.「rowl0」でLISP系言語「rowl-core」を実装
21. 一旦LISPを作る事にしました • 言語名: rowl-core • インタプリタ名: rlci • 実装が容易 • メタプログラミングによる生産性向上
22. さっきと同じ感じでレキサ・パーサを作る
23. アセンブリよりかなり記述が楽
24. evalも作っていきます。
25. メモリ管理はまだしません • mmapしか使えないので負担が大きい 1. 不要になったメモリは回収しない 2. 足りなくなったら新たに確保 3. 動かし続けるといつか死ぬ • 次の世代のコンパイルだけ出来ればあと不要なので良しとした malloc, free
26. LISP系言語「rowl-core」が完成！ • lambdaやmapが使えたり • マクロが使える！
27. 3.「rowl-core」で「VM記述言語」を作る
28. 次の世代では仮想マシンを導入します。 • その為の「VM記述用言語」を作成。 • LISPの強みを生かして、言語内DSLとして作成 • レキサ・パーサの実装は不要！
29. こんな感じでVM用コンパイラを書きます
30. 今回は高階関数とかも使えます • 生産性がぐっと向上！
31. 4.「VM記述言語」で仮想マシン「rlvm」を実装
32. 言語内DSLでVMのコードを書いていきます
33. ガベコレもようやく実装します • コピーGCにしました
34. 組み込み関数も作っていきます
35. ここでメタプログラミングの活用例を紹介します • 以下は、VMの命令セットのテーブル
36. 命令テーブルから色々自動生成します • 命令の追加・削除を自 動的に反映 • LISPだとこういう仕組み 作るのが楽な気がする vm_instructions VMのevalループ リンカ ディスアセンブラ アセンブラ amber内部で使うアセンブラ
37. 命令セットを作っていきます
38. 浮動小数点数演算や
39. 多倍長整数演算なども用意しました
40. 例外機構なども作ります
41. 継続も作ってみました
42. 仮想マシン「rlvm」が完成！ • 186命令 • スタックマシン • コピーGC • 例外機構 • shift/reset限定継続 • 浮動小数点数演算、多倍長整数演算
43. 5.VM用ツールチェインを作る
44. VMは出来たがプログラミング環境がない • VM上のツールチェインを作る • VM用中級言語「rowl1」 • アセンブラ • コンパイラ • リンカ • ディスアセンブラ
45. 言語・アセンブラ・コンパイラを作ります • これらは次世代で捨てるので「rowl-core」の言語内DSLにします
46. リンカ、ディスアセンブラを作ります • 「rowl1」で記述し、これら自身もVM上で動くように実装 • リンカはメモリを食うのでGCのある環境でやりたかった
47. ディスアセンブラの出力はこんな感じ
48. VM上でプログラミングが可能に！ • 分割コンパイルが出来る • デバッグもしやすい • メモリも潤沢に使える • 例外とかも使える • 普通の事が出来るようになっただけ・・・でも達成感がとても大きい！
49. 6.「rowl1」で「amber」を実装
50. いよいよamberの実装に入ります • 動的スクリプティング言語として作る • インスタンスベースオブジェクト指向 • 先ほど作った「rlvm」上で動作
51. アセンブラを作ります • さっき作ったアセンブラは プログラム実行前にコンパイル • これは、プログラム実行時に その場でコンパイル • アドレスはバックパッチ
52. オブジェクトシステムを作ります • スロット、メッセージ、 ペアレントへの委譲
53. オブジェクトシステム上に中核機能を作っていきます • 動的パターンマッチングエンジンと • 部分関数関数の融合メカニズム
54. この上にコンパイラを作ります • コンパイラ自体を通常のオブジェクトとして実装 VM オブジェクトシステム パターンマッチングエンジン コンパイラ amberのコアシステム 構文木のマッチング リソース管理
55. クロージャ変換も実装しました
56. この上にパーサを作ります • 実行時にパーサをコンパイル • 各パーサは通常のオブジェクト(クロージャ) VM オブジェクトシステム パターンマッチングエンジン コンパイラ amberのコアシステム コンパイル パーサ
57. とてもシンプルな文法 1. リテラルは式である 2. hがシンボル、e1,..,en (n>=0) が式の時h{e1, ..., en}も式である 3. 以上で定まるもののみがamberの式である • これと、あるトリックを後で組み合わせる
58. Packrat法で実装します • 後のトリックのため • 従ってレキサ不要
59. 浮動小数点数のエンコード・デコードは苦労します • libcが無いので自分で作ります • 先ほど作った多倍長整数演算が必要になります “3.14” 0x40091eb851eb851f stortod, sprintf
60. amberが完成！ • 動的スクリプティング言語 • VM上で動作 • インスタンスベースオブジェクト指向 • 動的パターンマッチングエンジンと部分関数融合が中核機能 • レキシカルクロージャ • すごく高級になってきた！
61. 7. 「amber」の標準ライブラリを作る
62. amberのテーマは自己拡張性 • amberの文法は標準ライブラリで定義されている • amber/lib/syntax/parse.ab • 起動時に自身の文法を構築する
63. 起動時はリテラルとh{e1,..,en}という文法だけ
64. amberの文法を定義する為の文法を定義する
65. 今定義された文法でamberの文法を定義する
66. 続いてマクロシステムを作る
67. マクロで更に文法を増強
68. リッチな構文が使えるようになりました
69. オブジェクトシステムも増強します
70. 継承などが使えるようになりました
71. ここで開発停止です • 更新予定はありません • 以下でインタプリタが起動(Linuxのみ) • makeのログで以上のブートストラッピングの過程を見てみましょう % git clone https://github.com/nineties/amber.git % cd amber % make; sudo make install % amber
72. まとめ rowl0 rlc rlci rowl-core as VM記述言語 rlvm rowl1 リンカ ディスアセン ブラ コンパイラ コンパイラ amber インタプリタ 実装 実装 実行 言語 ツール • 大分高級な所まで到達出来たので満足