友達とBrainfuck命令セットCPUを作っている話
これは木更津高専アドベントカレンダーの13日目の記事です。
Introduction
多くの人はBrainfuckの名前だけ聞いたことがあるはずです。Brainfuckは普通のプログラミング言語とは違って、8文字の記号のみで記述される難解プログラミング言語の一つと言われています。これだけの情報であれば、Brainfuckはただ難読化されたプログラミング言語と思う人もいるかも知れないですね。しかし、そうではないのです。
Brainfuckは以下の8つの命令のみで構成されるプログラミング言語です。シンプルな言語でありながらチューリング完全です。
| Instruction | Description |
|---|---|
| > | ポインタをインクリメントする。 |
| < | ポインタをデクリメントする。 |
| + | ポインタが指す値をインクリメントする。 |
| - | ポインタが指す値をデクリメントする。 |
| . | ポインタが指す値を出力に書き出す。 |
| , | 入力から1バイト読み込み、ポインタが指す先に書き込む。 |
| [ | ポインタが指す値が0なら、対応する ] の直後にジャンプする。 |
| ] | ポインタが指す値が0でないなら、対応する [ の直後にジャンプする。 |
私がBrainfuckについて理解を深めたのは高専の授業中、同級生との雑談の中でした。彼は、BrainfuckでHello Worldを表示させるプログラムを書いて見せてくれました。コードは忘れたので、wikipediaのコードを引用します。
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
これを見たときに非常に洗練されたプログラミング言語だと気付きました。Hを出すためにn回インクリメントするわけでもなく、ループを使って頭良くプログラムできています。
私はBrainfuckのプログラムを見たときに以下の3つに気付きました。
- プログラム実行時に、裏側で何が起こっているか全てわかる（わからないとプログラムできない）
- 少なすぎない、多すぎない命令セット
- メモリの扱い方は低レイヤっぽいが、アセンブリとは異なるワクワク感
ここで面白いのが、3の低レイヤっぽさです。Brainfuckはアセンブリのように、オペコードとオペランドの命令で構成されていると考えられます。しかし、残念ながらBrainfuckはアセンブリではありません。多くのBrainfuckソースコードはインタプリタを通じて実行されます。
ここで私は考えました。Brainfuckソースコードをインタプリタを通さずにハードウェアで動かしたいと。一緒にBrainfuckについて話していた2人と、「Brainfuckのコードを入力すると、ロジックICで構成されたCPUが計算をしてくれるようなコンピュータ」を作ろうと意気投合しました。
ここからは余談です
Brainfuckをそのままアセンブリのようにハードウェア実行するのは簡単にできないのだろうか？ Brainfuckのインタプリタ、コンパイラは何をしているのだろうか？ という疑問が浮かび上がりました。
結論として、Brainfuckのループ命令においてジャンプすべきアドレスを見つけるのが自明でないことがわかりました。
例えば、 [ という命令を実行するとき、現在見ているメモリの値が0であれば対応する ] にジャンプしなければなりません。Brainfuckのインタプリタやコンパイラはジャンプする先を予め計算しておくことで、ジャンプする先を明示的に示しています。
高機能なALUを作らなくて済むし、データ型が存在しないけれどもジャンプ先をハードウェアで見つけなければならなくなりました。
What is the goal?
Brainfuckのコードを入力し、プログラムを実行するハードウェアを実現させる
Brainfuckの命令セットを実行するような自作CPUを設計、ICで実装することです。作りたい。
リレーを使ってCPUを自作した彼の作品のように、ワクワクする物を作りたいです。
Roadmap
難しいので、抽象的なレイヤから具体的（ハードウェア）なレイヤに至るまでn個の段階に分け、それぞれでバグや設計に不都合が生じないことを確認しながら進めていこうと思います。
- 全体アーキテクチャ、命令ごとの状態遷移図が書けている
- 論理回路図が作成できている
- 部品込み回路図が作成できている
- ハードウェアアーキテクチャが作成できている
- 作る
1. 全体アーキテクチャ、命令ごとの状態遷移図が書けている
CPUを作る最低限の機能と構成を検討します。
各要素(e.g. レジスタ、ALU)をどのように繋げたらBrainfuckの命令が実行できるかを考えます。
また、命令ごとにレジスタの値、メモリの値がどのように変化していくかの状態遷移図を作成します。
2. 論理回路図が作成できている
ここでは、論理回路シミュレータを使って論理回路図を作成します。
この段階では、バスを使ってデータがどのように流れて演算されているかを検証します。具体的な演算器、バスの構成については議論しません。
ROMから命令をフェッチしてきて正しい結果が得られるかをテストします。
3. 部品込み回路図が作成できている
このフェーズでは回路図を作成します。論理回路図を基にしてモジュールの構成にどんな素子を使うか、具体的な配線の構成を議論します。
骨が折れる作業だと予想しています。8bitであれは8本のバスを配線する必要があるなどして、回路図は非常に大きくて複雑になるはずなので気合の人力デバッグ作業になります。
4. ハードウェアアーキテクチャが作成できている
回路図で省略されていたハードウェアの物理的な構成について議論します。
5. 作る
部品調達をして、作ります！！！！
Progress
自分を含めて3人の仲間でコツコツとやっています。全員寮生なので、点呼が終わった後にホワイトボードに集まって進めています。
全体アーキテクチャ図ができました。仲間内の命名規則を使っているので注意です。
保持するレジスタは4つあります。
- アドレス(値を参照する)
- フラグ(ループをスキップするかのフラグ)
- ループのネストをカウントするレジスタ x 2 (
[と])
全体アーキテクチャ図
1クロックごとにそれぞれのモジュールがどのようにデータが受け渡されたり評価されたりするかを図で示しました。
命令が実行されたときのシーケンス図
ここまでできたら、論理回路シミュレータに実装したくなるのですが、1つ問題があります。それはこれまでデコーダがブラックボックスとして扱われていたことです。データを選別するセレクタは裏側に命令を解釈するデコーダに繋がっていますが、デコーダの仕様についての検討が残っています。
今時点では、命令に対応したビット列を割り当て、デコーダの設計をしています。
チームの一人が作成した真理値表です。笑っちゃうくらい筋肉です。この真理値表をたたき台にして妥当性を全員で検証していきます。
まとめ
Brainfuckの命令セットでCPUを作ろうとした経緯、進捗を書きました。
やればやるほど、既存のCPUの命令セットがいかに合理的かがわかります。
Brainfuckコンピュータが完成するのが待ち遠しいです。
Discussion