この記事はなに？
- 先日チューリング完全を達成した、ここ数ヶ月行っている「プログラミング言語を作ろう」というYoutube配信のまとめ記事です。
- 各回で行った開発内容と、その開発の解説資料と動画アーカイブへのリンク、それから一旦チューリング完全を達成したのでそこまでの感想と反省点を記載しています。
- 主にお役に立つのは解説資料と感想の部分になるかな……？
そもそもあなたはだあれ？
- バーチャルテックリード「ゆにる ゆに」です！
- とあるメガベンチャーのテックリードがバーチャル化されて出来たVtuberです。
- プログラミング言語を作る配信をしたり、チーミング戦術のお話をしたりしています。
- twitchなんかではスーパーマリオワールドのRTA走者もやってます。
- 詳しくは以下の自己紹介動画をどうぞ……！
まずは各回の配信まとめ
| 回数 | 内容 | 動画リンク | 資料リンク | 備考 |
|---|---|---|---|---|
| 第1.0回 | 開発環境構築 | https://youtu.be/Exe9Z9gbL4E | ありません💦 | LLVMを動かせるようにしつつ、最低限のトークナイザー/ジェネレータの実装まで行いました。まだデビュー直後で配信なれしてなくてマイクを裏表で使っちゃったのでこの回は色々とひどいです；_； (見ようと思う方は、ここはもうスキップしちゃってください。) |
| 第2.0回 | 1+1の実装 | https://youtu.be/_7dRCkaIl7E | Slide | パーサを実装して1+1を処理できるようにしました！ |
| 第2.5回 | トークナイザーのリファクタリング | https://youtu.be/CvWyZtVRCFs | Slide | 初めてのリファクタリング回。トークナイザーをミーリーマシンとみなしてテーブル管理にして統一/単純化しました。 |
| 第3.0回 | 四則演算を全て実装しよう！ | https://youtu.be/mXoNI6xIo54 | slide | ASTを拡張して四則演算すべてを行えるように拡張しました！ |
| 第3.5回 | パーサのリファクタリング | https://youtu.be/U3Koaoe8o8w | slide | ここまで純粋に手書きしていたパーサを(簡単な)パーサコンビネータを導入して楽に読み書きできるようにしました！ |
| 第4.0回 | 条件式とIF式 | https://youtu.be/qLW_xw2zJ6U | slide | 条件式とIF式を導入して、条件分岐を行えるようにしました！ |
| 第4.5回 | ジェネレータのリファクタリング | https://youtu.be/147pjsdZSqI | slide | ジェネレータ関連コードのリファクタリングを行いました |
| 第5.0回 | 順次実行と変数の定義・代入・展開 | https://youtu.be/GfZJE5y1-hs | slide | 言語に順次実行と変数の概念を導入しました！ |
| 第5.5回 | コンパイルの高速化 | https://youtu.be/c5HsMPW7eNM | slide | PEG文法に対する単純な再帰下降構文解析器だったので速度が全然出なかったところを、PackratParserにすることでベンチマーク基準25倍の高速化を実現しました！(正確には指数時間が線形時間になった) またプロファイラを導入して実際に解析をする様子も記録できたので良かったなと思っています。 |
| 第6.0回 | While文の導入 | https://youtu.be/TXN5eB48DgM | slide | While文を導入しました！これで順次/分岐/繰り返しのプログラミング言語3要素が揃いました。ところでこれでチューリング完全だと思われるかもしれませんが、「実はこの時点ではチューリング完全ではない」というのがこの回のポイントです。そのあたりは資料の方に詳しい解説を与えて配信でも解説してみました。ネタバレするとこの回で手に入った能力は線形拘束オートマトン相当、です。 |
| 第7.0回 | チューリング完全！ | https://youtu.be/0zj7Wh2Rquc | slide | この回で(理屈上)チューリング完全を達成しました‼実際にやったこととしては、関数定義と関数呼び出しを行えるようにする一連の文法を導入し、再帰呼び出しでいろいろな事ができる状態にしてあります。 |
プログラミング言語作り(一旦)完走の感想
一通りチューリング完全に至るまでプログラミング言語の作成を完走した感想と反省は以下のようなものです。
Dockerコンテナ内で環境を作るのはかなり良い方針だったと思うが、デバッガの扱いには注意。
Dockerコンテナ内にLLVM環境を構築して、docker-composeにより、その環境内にソースをマウントして利用する、という初期に考えた方針自体はスムーズに進んでる限りは割と便利でした。
ただLLVM-IRを動かすlliのような依存部分はしかたないのですが、それ以外のコンパイラ部分は外でもビルドできるようにしておいて、ビジュアルに使えるデバッガを使えるようにしたほうがよいです。
コンテナ内でgdbやdelveなどを扱うのは面倒だと思いますが、
実際の配信でも、コンテナ外で簡単なサンプルコードを実際にコンパイルさせてみてデバッグするシーンが結構ありました。かなり必要性が高いです。
LLVM-IRを、もうちょっと体系的に理解してから始めたほうが良かったかも。
LLVM-IRはすごくよいものです。
諸々の呼び出し規約の管理やら、registerの割付やら何も苦労せずにすむわけで、
LLVM-IRを覚えてしまえば圧倒的にコンパイラづくりにおいて楽ができます。
ただLLVM-IRは文法が結構癖があったり、挙動として覚えることが多いので、
それなりに体系的な理解が必要になる印象でした。特に
- SSA, phi命令関連の知識
- register名称やlabel名称にある程度順序が強制されることや、blockを切る必要など
- 変数全てに型の概念がついてくるので「とりあえずintと仮定して出したらいい」とはいかないこと
- 膨大なアトリビュート周りの挙動
- 変数確保のためのstore, loadの挙動
などの理解が甘いために「あっ！この方針じゃ実装通らないじゃん！」というシーンが結構生じました。
コンパイラ側のデータ構造自体に関わるレベルの課題になることが多かったので、
やはりある程度体系的に知っておく必要があると思います。
ちなみに私はアセンブリの学習のノリで、clangが出してくれるLLVM-IRをなんとなく読んで、それを切り貼りして乗り切るというスタイルで配信をしてしまいました。
逆にLLVMは膨大で全部覚えきってから始めるのは「いつまでも始められない」という罠もありそうです。
そういう意味で考えると「とにかく手をつけてから体系化する」という今回のclangの出力を読む方針はおすすめできるのですが、流石に事前知識をもうちょっとだけ仕入れたほうが楽だったと思います。
(このあたりは配信を見ていただけると、実際そういう方針で理解をしていく姿を確認できる、、、かもしれません。)
Ｃ言語ソースコードからclangを使ってLLVM-IRを出すのには以下のようなコマンドを使うので覚えておいてもよいでしょう。
clang -c -S -emit-llvm code.c
テストコードはものすごく重要
テストコードにはめちゃくちゃ助けられました。書いててよかったテストケース！みたいなのたくさん。
配信の都合でTokenizer, Parser, Generatorの大まかな単位でしかテスト書かなかったけど、もっと細かい単位でテストしてたらむしろ楽だったかもしれないなあと反省しています。
Generatorの実装がASTのメソッドにべったりしてしまった
Generator周りはASTモジュール側の関数としてベッタリ実装されていて、そのせいで肥大化している印象でした。
ASTはただのデータ構造と見做してVisitor的な別の物を作ってそちらに実装するとかしたらよかったなーって思っています。
どんな文法で作り上げたいのかはある程度先によーく考えたほうがいい
初回配信は実は「いきあたりばったりにプログラミング言語を作る」というタイトルで、そういうコンセプトで始めたのですが、こういういきあたりばったりはやっぱりよくなかったです。
最初期はPEGでいくのかBNF(+LL(1)とかLR(1)とか)でいくのか、みたいなことすら全然決めてなかったのですが、そのためにパーサの実装であっちいったりこっちいったりして時間がすごく浪費されてしまったところがあります。
あなたの言語に必要な要素の列挙を事前にやっておくと、きっとスムーズになります。
パーサコンビネータはすごい発明 / 愚直に書くことで肌感を得られるものがある
第３．５回目(パーサのリファクタリング)でそれまで可能な限り手で書いていたパーサを抽象化して、パーサコンビネータを作りました。
これでパーサのコードが眼を見張るほど簡素化されたので本当に感動しました。
パーサコンビネータ自体は以前から他ではよく使っていたし、良いものだとはわかっていたことなんですが、
むしろ最初から使っていたので「具体的にどれくらいの差が生まれるのかなあ」というのを肌感ではわかっていませんでした。「あえて愚直に書いてみる」「きれいなものと比較してみる」ということで学べるものがあるんじゃないかな、と今は感じています。
配信にはあからさまに不向き💦💦💦
これはVTuber的なお話なんですが、配信でやるには厳しいネタだった気もします💦💦
というのも通常のコンパイラを実装する限りは、文字列程度の要素しか表現できない状況になりがちで、
比較的内容も高等なので話題に乗りやすい視聴者さんも少なくなりがちだからです。
単に実装しているのを延々見せるのはあまり視聴者の方にとって面白い物だったかというと怪しく……。
そういう理由でチューリング完全を達成した今、引き続きオブジェクト(構造体)の実装や、型の実装を同じ配信スタイルで行うかといったことは悩んでいます。
単トピックごとに絞ってお話するならもっと短くまとまった動画になるかなと思うのでそういう方針にするか、
もっと別のためになりやすいエンジニアリングの話題を今後はやっていきたいかもなあ……と。
プログラミング言語を作るのは、それ自体とっても楽しい❗
ただやっぱりプログラミング言語、いろいろな文法を自分なりに考えて作っていくのはとても楽しいです❗
この記事を読んだあなたが、プログラミング言語を一度実装してみる機運になれば……！