RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話

（↓Firefox だとアニメgifが再生されない場合があるようです。ファイルをクリックして画像だけ表示すると動くものが見れます。）

きれいにまとまってないですが、箇条書き＋α程度で雑にメモ。

---

ブログに書いていたもの¹を Qiita に引っ越してきました。元の記事公開日は 2019-05-04 です。

TechRacho さんの週刊Railsウォッチ（20210209後編）で紹介されました（ありがとうございます ）。こちらもあわせて読んでいただけるとよいかと。

できたもの

• 2018年5月のゴールデンウィーク残り2日というところ（5/5）で思い立って初めて、 5/18 完成。
  • もっと早く公開したかったんですが仕事が忙しくて燃え尽きたりしていて結局1年かかってしまいました。
  • 去年の言語実装 Advent Calendar に超初心者枠で参加しようかと考えてたんですが、間に合わず……。
• それを原型を損ねない程度に名前を変えたり最終的に不要になった部分を消したりしたものです。
• 実装言語は Ruby。いちばん慣れていてサッと始められるので。

---

完成直後（ライフゲームが最初に動いた時点）の状態も見られるようにタグを付けています。
https://github.com/sonota88/vm2gol-v1/tree/20180518

汚いしひどいコードなので正直恥ずかしいんですが、この状態も生々しくてコンテンツとしては面白いかもしれません。やけくそか。ヒマな人向け。

※ その後作り直した v2 もあります。その後の改良も加わったものが見たい、パーサまで揃ったものが見たいという場合はこちらを見てください。
※ (2021-02-21 追記) v2 にいくつか機能を足してセルフホストできるようになりました。

製作過程のメモ

どういうステップを踏んで何を実装していったか、具体的な話はこちらに書きました。あまり省略せずにその都度 diff を貼っていくスタイルです。

動かし方

サードパーティなライブラリへの依存はなく、Ruby（と標準ライブラリ）だけあれば動きます。

# コード生成
ruby vgcg.rb gol.vgt.json > gol.vga.yaml

# アセンブル
ruby vgasm.rb gol.vga.yaml > gol.vge.yaml

# VMで実行
ruby vgvm.rb gol.vge.yaml

これらの処理をまとめて行うために run.sh というシェルスクリプトを使って動かしていました。

./run.sh gol.vgt.json

概要

VM

• 600行弱
• CPU
  • 高水準言語の都合に合わせたものではなく、汎用な CPU を想定して簡略化したもの
  • レジスタは a, b, c, d, pc, sp, bp, zf, of
    • c, d, of は途中で不要になった
  • 命令セット … x86 っぽいオレオレ
  • 数値演算は Ruby に丸投げ
• メモリ
  • ただの Ruby の配列。整数 or 文字列（！）のどちらかが入る。
  • 3つの領域に分けた
    • メイン領域（機械語コードを配置する場所）
    • スタック領域
    • VRAM領域
  • 配列の添字がそのままアドレス

機械語コード

こういう YAML ファイル。バイナリではなくテキストですが、機械語のつもり。

---
- call
- 1029
- exit
- label
- vram_set
- push
- bp
- cp
- sp
- bp
- sub_sp
- 1
- set_reg_a
- "[bp+4]"
- set_reg_b
- "[bp+2]"
- mult_ab
- cp
- reg_a
...

• これを YAML.load_file したものをそのままメインメモリ領域にズボッと入れる。
  富豪的。
• こういうものなので、「バイトコード」とは言えないかなと思って「機械語コード」と呼んでます
  • 実在するCPU向けではなくオレオレVM向けなので「仮想機械語〜」のように呼ぶのがより適切？

アセンブラ・アセンブリコード

アセンブリコードも YAML。

- call main
- exit
- label to_vi
- push bp
- cp sp bp
- sub sp 1
- sub sp 1
- sub sp 1
- set_reg_d [bp+4]
- set_reg_a [bp+2]
- cp reg_d reg_b
- mult_ab
- cp reg_a [bp-3]
- set_reg_d [bp-3]
- set_reg_a [bp+3]
- cp reg_d reg_b
- add_ab_v2
- cp reg_a [bp-1]
...

• ジャンプ先などのアドレス指定が実アドレスでなくラベル名になっている他は、
  内容的には上の機械語コードとほぼ同じ。
• アセンブラは 60行弱
• 実アドレスへの変換以外にアセンブラでやっているのは入れ子の構造を flatten して1次元にしてるくらい。
  • この 1次元化の処理も削っても良かったかも（そうすれば CPU 部分もさらに簡略化できる（そこまでやると簡略化しすぎという気も））

---

パースをサボるために YAML にしたものの、インデントなどで構造を把握しやすくした方が良かったかなと思います。こんな感じで:

  call main
  exit
label vram_set
  push bp
  cp sp bp
  sub_sp 1
  ...

この程度なら行ごとに line.strip.split(" ") で済みそう（v2 ではそうしています）。

コード生成器・高水準言語部分

コード生成器は 600行弱。

コード生成器に与える高水準言語相当のコードは、フォーマットとしてはJSON（ただし、 // でのコメントあり）。

["stmts"

 // バッファ配列用
 ,["func"
   ,"to_vi"
   ,["w", "x", "y", "offset"]
   ,[
      ["var", "vi"] // vram index
     ,["var", "vi_buf"]

...

  ,["func"
    // 関数名
   ,"main"
    // 引数
   ,[]
    // 本体
   ,[
      ["_debug", "start ----"]
     ,["var", "w"]
     ,["set", "w", 5]
     ,["var", "h"]
     ,["set", "h", 5]

     // 配列の初期化 5x5, グライダー / x, y, val
     ,["set", "vram[1]", 1]
     ,["set", "vram[7]", 1]
     ,["set", "vram[10]", 1]
     ,["set", "vram[11]", 1]
     ,["set", "vram[12]", 1]

     // メインループ
     ,["var", "cnt"]
     ,["while", ["eq", 1, 1], [
       ["set", "cnt", ["+", "cnt", 1]]

       // gen_next_step
       ,["call", "gen_next_step_loop", "w", "h"]

       // バッファの内容で置換
       ,["call", "replace_with_buf_v2"]
     ]]

    ]
  ]
]

• これを JSON.parse すれば構文木がゲットできる。ずるい。
• S式ですねー
• C言語のような何かを想定したオレオレ
• 変数の型は数値のみ
• 中間コード生成はやってません。
  素朴に構文木を辿ってアセンブリコードに変換していくだけ。

グラフィック

• ライフゲームなので2次元のグラフィック表示が必要
• VRAM はサイズ 50 の配列で、これを半分に分けて（片方は次世代生成用のバッファ）、
  それぞれを縦横 5x5 としてターミナルに print するだけ。かわいい。

---- memory (vram) ----
..... .....
@.@.. ..@..
.@@.. @.@..
.@... .@@..
..... .....

• VRAM といいつつ、1個の配列専用のヒープ領域みたいなものでもあり、
  なんとなくずるい気がしますが、とにかくこれでやりました。
  • VRAM ではなくヒープ領域的なものであり、
    そこを覗き見ているだけだ、ということにしてもいい？ どうなんでしょう。
  • 「VRAMっていうのはこういうものだ」という知識がないので……
  • ↑ この、よく分かってなさをお楽しみください……

方針

• 期限は2週間

• 理論とかを全部理解してから作ろうとしない

• CPU の専門家やアセンブラの専門家やコンパイラの専門家になりたいのではない

• とにかく動けばいい

• 調べものは最小限

  • これは意識的にそうした。極力調べずに（＝どうしても分からなかったらそのとき最低限調べる）、それまでに聞きかじったボンヤリした知識を動員して憶測で適当にやる。
  • 寄り道しない・脇道にそれない

• 不可欠でない部分はさくっと捨てる

  • 「不可欠」というのは、「今回自分が知りたいこと」「完走するのに最低限必要なもの」
    「後からすげかえたりするのが難しそうなもの」くらいの意味

• VM〜コード生成部分を作る

  • 加算器部分からは作らない。前にちょっとやったので。
  • 高級言語のパース部分はやらない。なんとなくだけど知ってるので。

• 汚くていい

  • 自分が学習して満足できればよい。自分の中に知見なり経験値なりが貯まればよい。
  • できたものはゴミでよい。どうせずっと使い続けるものではない。

• 作りつつその都度ブログ書いていくのもライブ感あって良さそうとも考えたけど、これもスピードが落ちそうなのでボツ。外部公開のことは考えないことに。

  • 途中で更新止まると悲しいし

• 達人プログラマーでいうところの曳光弾。あれをやる。

  • 自分の性格的にもその方が向いてる（早く見通しを得て不安をなくして余裕を得たい）

---

少し例えが暴力的でしたが、この手は新規プロジェクト、特に今まで構築されたことがないようなものを実現する場合に適用することができます。あなたは射撃手のように暗闇の目標を狙わなければならないのです。元になるシステムが存在していない場合、ユーザーの要求は曖昧なものとなります。さらに、不慣れなアルゴリズム、開発技法、言語、ライブラリを使って、未知の世界に直面していくことになるのです。また、プロジェクトの完了まで長い期間がかかるため、作業環境も変化していく可能性が高いでしょう。

（達人プログラマー ピアソン・エデュケーション版 p48）

---

「正しく」やる時間がない人間は、重要な箇所だけに集中して枝葉を無視する。その結果、いくつかの細かい点は次のバージョンに回そうと計画する。ここで注意する点は、次のバージョンなど永久に作られないかもしれないということだ。しかし、「足りない部分は後でなんとかすればいい」と思い込むことで、脇道に迷い込むことを避けられる。それはまた、初期バージョンの細かな欠点についてのよい言い訳にもなる。

（UNIXという考え方 p34）

---

なぜ2週間か

• 頓挫するから。

• 平日昼間は仕事だし、夜・朝もそんなに時間使えないし、土日もいろいろやることある。

• これまでの経験でも、長期化するとなんか仕事が忙しくなってきて中断してそれっきりとか、他におもしろそう（で簡単そうなもの）なものを見つけてそっちをやり始めて逃避したりで結局頓挫するパターンが多くて身に染みているから。絶対頓挫する。100%頓挫する。自信を持って断言できる。

• で、いったんオレオレの適当な方法で動くものを作れば、その後で「正しいやり方」の解説を見聞きしたときに「あーなるほど、似たようなことやってたわ～」とか「こうすれば良かったのかーっ」ってなるはず。それでよい。それは2週間を終えた後でよい。

• とにかく頓挫だけはしたくなかった。頓挫しないことが最も重要な意思決定方針。

感想

• おもしろかった！！！！
• 楽しかった！！！！！
• ！！！！！！！！
• 十分自己満足できた（大事）！！！！
• コード生成～VM実行部分に対するイメージがだいぶ解像度上がった感じ
• 全部いっぺんに作ったの良かった
  • たとえば既存の何か（たとえば x86 だとか GNU as だとか）に合わせて作ろうとすると調べるのに時間取られる
  • 下位レイヤーのことを全部知ってるし、何が起こってるか全部把握できる（なぜなら自分で作ってるから）
    • 謎挙動は発生するけど、自分が書いた1000行ちょっとのコードのどこかに必ず原因がある
    • ダンプでも何でもできるし、なんなら下位レイヤーを自分の都合のよいように決めて変えてしまえばよい
• 下から上に向かって作ったの良かった
  • 低水準から高水準へ向かう発展の歴史を辿るような流れになっていて、おもしろい
  • 上位レイヤーがなぜこうなっているのか？（下位レイヤーによる制約） が自然な流れで分かる
  • つねに下位レイヤーのドッグフーディングをしている感じ。
    「動くものがなかなかできなくてつまらない」にはならなかった。
• 目標をライフゲームにしたの良かった
  • 仕様や機能が必要かの判断で悩まなくて済む・無駄なものを作らなくて済む
    • ライフゲームを動かすのに必要そうだったらやる。必要なさそうだったらやらない。
  • 簡単すぎず、難しすぎず、ちょうどよい負荷（自分にとって）
• Turing Complete FM の内容がちょびっと分かるようになった！！気がする！！！！！！！
• これでやっと nand2tetris やふつパイラの入り口に立ったぞ……
• 10年前の自分に送りつけて「教材作ってあげたから今すぐやれ」「Ruby とエディタとターミナルだけあればできるから」「タダで読める製作過程の記録まである。この通り作ればできあがるぞ」と言いたい
  • 他の人に薦められるかというと微妙（オレオレなので）

困ったこと

教材の問題

• どれが（自分にとって）良い教材なのか分からない
• 入門者だし、界隈の事情に詳しくないので判断基準がない
• 現代の最先端のもの、専門家（を目指している人）向けのものは難しすぎる
  • いきなり 64bit の世界から始まるし
• 昔のCPU向けのものだと今のものより素朴で入りやすいのでは？ とか、現代のものでも組み込み向けはどうかな？ などと思って調べたりもしたけど、資料の探し方もよく分からないし、ある程度知識のある人向けに書かれていたりしてよく分からない（効率がとても悪い）
  • TCFM #29 で hikalium さんが「道が見えるようになるためには一回そこに行ってみないと分からない」という話をされてましたが、ほんとそれ
    • ブートストラップ問題
  • 昔のものだとそもそも実行環境どうするの？ ってとこから始めないといけない。
    エミュレータがあっても、まずはその使い方を知らないといけない。
• 目移りする
  • 「x86 でやることにしようかな」 → 「あ、なんか良さげな解説見つけた…けど ARM 向けだなあ…」みたいになってなかなかターゲットを決められない（例は適当です）
• 結局エイヤでオレオレすることに
• どのみち自分に完全にぴったりな教材は存在しないので、教材を自分で作るみたいになった

入れ子の式

x = (2 * (3 + 4)) のように入れ子になっている式を

 ,["var", "x"] // 変数の宣言
 ,["set", "x", ["*", 2, ["+", 3, 4]]]

みたいに書きたくてあれこれ検討したものの、まじめに取り組むと何日か溶けそうな気がしたため

 ,["var", "temp"]
 ,["set", "temp", ["+", 3, 4]]
 ,["var", "x"]
 ,["set", "x", ["*", 2, "temp"]]

のように一時変数を使う形にして回避しました。うーん、これは悔しい。

自動テスト

• これはちょっとした賭けでしたが、テストコードは書かずに進めました
  • できあがりがどういう形になるのか分からない状態でのスタートだったため、下手にテストコードを書いてしまうとそっちの修正で時間取られそうな気がして……
  • 既存の仕様に準拠するならともかく、今回は上から下までオレオレで、作りながら仕様が変わっていくと予想された（実際はあまり変わらなかったけど、それも作ってみないと分からないので）
• バグが出ると「やっぱり書いておけばよかったかな……」とは思ったものの、結果的にはなんとかなった
  • 運が良かった
• とはいえ、まったくの無策だった訳ではなく、↓ のようなことはしていました
  • 動作確認程度のちょっとしたものはその都度書いたり
  • 生成されたアセンブリコード・機械語コードのファイルも
    git のトラッキング対象にしておいて、
    壊れていないことを git diff で確かめたり

どういう状態から始めたか

CPU

CPU のことをよく知らなかったので 2016年末～2017年頭頃に何冊か流し読みして、半加算器動かして足し算できる、みたいなのは書いてみた（この頃はアセンブラ、コード生成器まで作る気はなかった）。

• マンガでわかるCPU
• 自作エミュレータで学ぶx86アーキテクチャ
  • 達人出版会
• CPUの創りかた
• 30日でできる！　OS自作入門
  • 達人出版会
  • CPUの本ではないですがなんとなく流れでこの頃に読みました。
    アセンブリ部分もあるし今回のをやるのに参考になっていると思います。

※なので、2週間でまったくのゼロから始めたわけではなくて、構想期間が1,2年くらいあり、その間に本やネットであれこれ読んだりいろいろ妄想したりしてました。その上で、考えても埒が明かないのでやっぱり実際に書いてみよう！ となった、という流れです。

アセンブリ

• 聞きかじりでなんとなく知ってるくらい。
• アセンブリ言語でプログラムを書いたことはない。
• mov があって比較とジャンプとかするらしいぞ、くらい。
• なるほど分かったぞそれを組み合わせればいろいろできるんだな！？ くらいの認識。

コンパイラ

• パーサ部分はなんとなくは知ってる
• だいぶ前に読んだ（両方ともさらっと読んだだけで実際には自分で書いたりしてない）（どっちも青木さんの本ですね）:
  • Rubyを256倍使うための本 無道編
  • ふつうのコンパイラをつくろう
    • これを読んだときは構文解析部分に興味があったので後半（コード生成の部分）は読んでなかった気がする
• BNFで文法定義して構文木作って何かやるんでしょ？
  …何かというのはつまり、えーとアセンブリ言語のコードを生成する（？）んですよね、
  で、具体的にどうやるかというと…（分からない

という感じ。つまり、半加算器～構文木の間で何が起こっているのかが分かっていなかった。

C言語どのくらい知ってる？

• 学生の頃は趣味プログラムをCで書いてた
• 十数年前なのでもうだいぶ忘れた
  • 当時入門書として読んでいたのは前橋さんの
    C言語 体当たり学習 徹底入門
    で、この本＋αくらいの知識
• OpenGL で3Dグラフィック描いたりとかはしてたけど
  クリティカルなメモリ管理が必要なものはあまり書いてなかったはず
• その後 Ruby を使うようになり、
  趣味プログラムの99%くらいは Ruby で用が足りるのでC言語で書かなくなった

元ネタ・きっかけなど

nand2tetris

• https://www.nand2tetris.org/
  • 日本語版の書籍は コンピュータシステムの理論と実装
• 企画というか発想の元はこれ
• たしか 2016年頃に知って、読んだ
• 最初に nand2tetris のコンセプトを知ったときは、
  2週間〜1ヶ月くらい根詰めればどうにかなるかなあと甘い期待を抱いたけど無理で、
  流し読みだけでやめてしまっていた
• もっと簡略化した教材かなと思ってたけど、
  思ったよりきっちり進めてくスタイルの、教科書っぽい本だった
• 問題をもっと簡単にしてハードルを下げまくらないといけない

ライフゲームならテトリスより簡単そう（ユーザからの入力もない）だし、簡単な割には面白い動きが生成されるので自己満足度高そう。「ライフゲームが動いたら嬉しいだろうなぁ…」と、完成したときの満足感をモワモワ～と妄想しつつ……

rebuild.fm るいさんゲスト回（2016-08-09）

40分あたりから 8cc の話。インクリメンタルに作ると良いという話。これを聞いたとき、やっぱりそうですよねえ、そうだろうなあと思った記憶があります。明らかに当企画のきっかけの一つです。

その後 Turing Complete FM が始まり、なんか楽しそうなのでやってみたい！ という気分が盛り上がりました。

TODO

時間とやる気が揃ったら続きをやりたい。下記は「今回やってないこと」「今回捨てた・削ったもの」のリストでもあります。

• nand から作って nand2gol にする
  • (2020-05-03) 1bit CPU 作るところまではやりました: リレー式論理回路シミュレータを自作して1bit CPUまで動かした
• VM
  • [bp+1] とかを VM が直接（正規表現で…）解釈しているので、もうちょっと機械語っぽく
• 高級言語・コンパイラ部分
  • 入れ子の式の計算をできるようにする
    • 今回回避してしまったので、最低限ここまではちゃんとやりたい
    • (2019-12-15) できるようにしました
  • 配列
  • 構造体
  • ポインタ
  • 再帰
  • 型
  • 字句解析・構文解析（ちゃんとCっぽいフォーマットのソースをパースする）
    • (2020-05-04) パーサも作りました
• グラフィック
  • あると楽しい
• リンカ
• OS
  • 難しそう
  • いろいろ削りまくればあるいは……？

ざっくり工程

• まず簡単なVM
  • 30行くらいの簡単なものからスタート
• メモリにプログラムを直接書く
• ファイルからロードするようにする
• 機械語コード書きつつ
  • 命令を追加していく
  • アセンブラを作ってラベルを実アドレスに変換
  • 条件分岐、ループ、サブルーチンなど、必要そうなものを用意
• ある程度できてきたらコード生成器を作りだす
  • 変数、条件分岐、ループ、関数などをアセンブリコードに変換
• 部品が揃ってきたらライフゲームを動かす

ざっくり書くとこんな感じですが、実際は行きつ戻りつしていて、終盤でもライフゲーム書きながらVM部分を修正したりしてました。

こちらで製作過程を書いていますので詳しくはそっちを見ていただければと思います。

その他の参考書籍など

v1 を作る前〜作っている時に読んだもの

• つくって学ぶプログラミング言語 RubyによるScheme処理系の実装 - 達人出版会

• RubyでつくるRuby ゼロから学びなおすプログラミング言語入門（紙書籍＋PDF版） – 技術書出版と販売のラムダノート

• 32ビットコンピュータをやさしく語る はじめて読む486【委託】 - 達人出版会

• ひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017 - Qiita

  • 下の方が半導体から始まっていて、すごいなーと思いながら読んでいました。

  • 最適化は理解の敵

• くじけちゃいけない！ マシン語入門 平塚憲晴 : 平塚憲晴 : Free Download, Borrow, and Streaming : Internet Archive

  • MSX

v1 を作った後に読んだもの

※流し読み含む

• 低レイヤを知りたい人のためのCコンパイラ作成入門
• 速攻MinCamlコンパイラ概説
• Compiler basics (1): lisp to assembly | notes.eatonphil.com
  • JavaScript
• Rubyのしくみ　Ruby Under a Microscope | Ohmsha
  • この本に限らず、Ruby の VM の話もうっすら分かるようになって良かった
• Rubyで作る奇妙なプログラミング言語　プレミアムブックス版 | マイナビブックス
  • 達人出版会
  • 2019-03 頃に読んだ
  • この本の存在は昔から知ってはいましたが、
    esoteric language というのは上級者の遊戯であって自分にはハードルが高そうというイメージがあり、
    なんとなく読まずに過ごしてきました。
    しかし、今実際に読んでみると、難解そうに見えるのは表面だけで、
    中身は良い意味で普通の（汎用的な、使い回しの効く）言語処理系の話です。
    コードもコンパクトですし、もっと早く読んでいればよかった。
    先に読んで写経でもしていれば、 vm2gol の内容ももう少し違ったものになっていたかもしれません。

ブックマーク

• はてなブックマーク - CPUに関するsonota88のブックマーク
• はてなブックマーク - Compilerに関するsonota88のブックマーク
• はてなブックマーク - Assemblyに関するsonota88のブックマーク
• はてなブックマーク - Emulatorに関するsonota88のブックマーク

他に Ruby 関連で書いたもの

1. https://memo88.hatenablog.com/entry/2019/05/04/232236 ↩