Rubyで学ぶRuby 第9回

インタプリタの完成、そしてブートストラップへ

こんにちは。はじめてのプログラミングでRubyを学びながらRubyインタプリタを作っていく連載も、今回でいよいよ最終回です。 自分だけのRubyインタプリタを完成させていきましょう。

前回までの記事で、インタプリタに実装してきたRubyの機能は、 四則演算（第4回）、 変数（第5回）、 分岐（第6回）、 関数（第7回と第8回）でした。 これを拡張して、さらに配列とハッシュを実装すれば、これまで学んだRubyの機能をすべて実装したインタプリタ（MinRubyインタプリタ）のできあがりです。

しかし、それで終わりではありません。もう一歩、考察を進めてみましょう。

MinRubyインタプリタを作るのに使っているRubyの機能は、四則演算、変数、分岐、関数、配列、ハッシュだけです。 そして、今回の記事で、これらがすべてMinRubyインタプリタの機能になります。 つまり、「MinRubyインタプリタの実装で使われているすべての言語機能」をMinRubyインタプリタに実装できたことになります。

ということは、自分で書いたMinRubyインタプリタで、自分で書いたMinRubyインタプリタを動かせるということです。 これが、この連載のもう一つの最終目標、ブートストラップです。

それでは、MinRubyインタプリタのブートストラップを目指して、まずは配列を実装していきましょう。

配列を実装する

変数の実装でも関数の実装でも、 作る側（変数代入・関数定義）と使う側（変数参照・関数呼び出し）のコードをそれぞれ書く必要がありました。 配列でも、同様に、「配列を作る」処理と「配列を使う」処理を書く必要があります。

Rubyで配列を作るときの方法として、この連載の第3回では[x, y, z]のような記法を学びました。 ちなみに、データ構造を作るこのような記述のことを構築子と呼びます。

Rubyで配列を使うときの方法として、やはり第3回の記事では2つのケースを学びました。1つは配列参照（例えばary[0]）、 もう1つは配列代入（例えばary[0] = 42）です。

ということは、配列を実装するには配列構築子、配列参照、配列代入の3つについて処理を書けばいいことになります。

配列構築子の実装

いつものように、まずは抽象構文木を眺めてみて、それを参考に実装すべき処理を考えましょう。 次の配列を例として考えます。

[1, 2, 3, 6 * 7]

このような配列構築子がMinRubyプログラムに出てきたとき、その抽象構文木は次のような形になります。

["ary_new",
  ["lit", 1],
  ["lit", 2],
  ["lit", 3],
  ["*", ["lit", 6], ["lit", 7]]]

絵にするとこうです。

"ary_new"というラベルの後に、構築子の中に書かれた式が並んでいるのがわかります （「ary」は、配列を表す英語のarrayのつもりです）。

MinRubyプログラムの抽象構文木に、このような枝が出てきたとき、それをどうやって処理すればいいでしょうか？ いろいろな方法が考えられますが、ここでは単純に、Rubyの配列を使うことにします。 第6回でif文を実装したときと同じように、 ターゲット言語であるMinRubyの機能を、Ruby言語の機能にそのまま丸投げするわけです。

実際のコードは次のようになります。

when "ary_new"
  ary = []
  i = 0
  while tree[i + 1]
    ary[i] = evaluate(tree[i + 1], genv, lenv)
    i = i + 1
  end
  ary

空のRuby配列を作り、MinRubyの配列構築子の中に書かれた式をevaluateした結果を順番に入れています。 これをMinRubyインタプリタのevaluate関数に追記すれば、MinRubyの配列の出来上がりです。

配列参照の実装

次は配列参照です。次の例で考えましょう。

ary = [1]
ary[0]

このMinRubyコードの抽象構文木は、こんなふうになっています。

["stmts",
  ["var_assign", "ary", ["ary_new", ["lit", 1]]],
  ["ary_ref", ["var_ref", "ary"], ["lit", 0]]]

絵にするとこうなります。

複数の式の抽象構文木なので、全体は"stmts"です。 その中の1つめの式（"var_assign"で始まるほう）は、代入を表しています。 "ary"という変数に、先ほど実装した配列構築子（"ary_new"）の枝を代入しているのがわかりますね。

2つめの式（絵で右側にあるほう）が、これから実装したい配列参照の抽象構文木です。 ちょっと見づらいですが、["ary_ref", 配列を表す式, インデックスを表す式]という形をしています。 （インデックスというのは、「配列のN番目」というときのNのことで、 ary[0]だったら0がインデックスです。）

配列参照の抽象構文木が出てきたときにMinRubyにやってほしいことは、 「配列を表す式が表す配列」から、「インデックスを表す式が表すインデックス」番目にある値をとってくることです。

そこで、まず配列を表す式（ary[0]で言えばaryの部分）をevaluateし、「配列を表す式が表す配列」を手に入れます。 次に、インデックスを表す式（ary[0]で言えば0の部分）をevaluateして、「インデックスを表す式が表すインデックス」を手に入れます。 ユーザのプログラムにもインタプリタにもバグがなければ、前者はRuby言語の配列に、後者はRuby言語の数になるはずです。 あとは、Ruby言語レベルで配列参照すれば実装完了です。

when "ary_ref"
  ary = evaluate(tree[1], genv, lenv)
  idx = evaluate(tree[2], genv, lenv)
  ary[idx]

配列構築子と配列参照が実装できたところで、いったんテストができます。次のプログラムを実行してみましょう。

ary = [1, 2, 3]
p(ary[0]) #=> 1
p(ary[1]) #=> 2
p(ary[2]) #=> 3

配列代入の実装

最後は配列代入です。次のようなコードがMinRubyプログラムに出てきた場合を考えます。

ary = [1]
ary[0] = 42

このコードは次のような抽象構文木になります。

["stmts",
  ["var_assign", "ary", ["ary_new", ["lit", 1]]],
  ["ary_assign", ["var_ref", "ary"], ["lit", 0], ["lit", 42]]]

絵はこうなります。

やはり複数の式で、注目すべき部分は2つめの式、 ["ary_assign", 配列を表す式, インデックスを表す式, 代入したい値の式]という 構文になっているほうです（絵でいえば右側）。

この配列代入の抽象構文木の評価も、先ほど実装した配列参照のときとほとんど同じです。 3つの式を順次evaluateし、Ruby言語レベルで配列代入をして終わりです。

when "ary_assign"
  ary = evaluate(tree[1], genv, lenv)
  idx = evaluate(tree[2], genv, lenv)
  val = evaluate(tree[3], genv, lenv)
  ary[idx] = val

これをevaluateに組み込めば、配列を一通り実装できたことになります。 次のようなコードを実行して動作を試してみてください。

ary = [1, 2, 3]
ary[0] = 42
p(ary[0]) #=> 42
p(ary[1]) #=> 2
p(ary[2]) #=> 3

ハッシュを実装する

ハッシュの実装でも、配列の場合と同様に、ハッシュ構築子とハッシュ参照とハッシュ代入の実装が必要です。 まずはハッシュ構築子の抽象構文木を見てみましょう。 次のようなコードを例に考えます。

{ 1 => 10, 2 => 20, 3 => 30 }

このMinRubyコードの抽象構文木はこうなります。

["hash_new",
  ["lit", 1], ["lit", 10],
  ["lit", 2], ["lit", 20],
  ["lit", 3], ["lit", 30]]

"hash_new"というマーカーに続けて、ハッシュの中に並んでいる式を順番に並べた構造になっていますね。

ハッシュも、配列と同様に、Ruby言語のハッシュの機能にそのまま丸投げする実装にしましょう。 抽象構文木に出てくる式を順番にevaluateしてRuby言語のハッシュに入れていきます。

when "hash_new"
  hsh = {}
  i = 0
  while tree[i + 1]
    key = evaluate(tree[i + 1], genv, lenv)
    val = evaluate(tree[i + 2], genv, lenv)
    hsh[key] = val
    i = i + 2
  end
  hsh

残るはハッシュ参照とハッシュ代入の実装です。 が、実はRubyでは、配列参照とハッシュ参照、配列代入とハッシュ代入は、 それぞれ完全に同じ構文をしています。 そのため、すでに実装した"ary_ref"と"ary_assign"は、ハッシュの場合にも完全に正しく動作します。 よって、ハッシュのためにこれ以上何かを実装する必要はありません。

したがって、以上でMinRubyインタプリタの機能がすべて実装できたことになります！

ブートストラップ

ではいよいよ、この連載の最終目標であったブートストラップに入ります。

ブートストラップという用語は、"pull yourself up by your bootstrap" （ブートストラップを引っ張って自分自身を持ち上げる）という英語の慣用句に由来します。

bootstrapという英単語を見ると「ブーツの靴ひも」のことに思えるかもしれませんが、これは靴ひもの意味ではありません。 ブーツのかかとの上にある、ブーツを履くときに引っ張り上げる取っ手です（図参照）。 先の慣用句は「ブーツの取っ手を引っ張って自分自身を持ち上げる」という意味で、 もともとは「不可能なこと」のたとえでした。 しかし、今では「（他人の助けを借りずに）自力で成長する」という意味が一般的なようです。

この慣用句にちなんで、プログラミング言語の分野では、 「言語Xの処理系を言語Xで書いて動かすこと」を俗にブートストラップと言っています。

ブートストラップの動かし方

ブートストラップについて考える前に、MinRubyインタプリタでふつうのプログラムを実行するときのことを思い出してみましょう。 あるプログラムをMinRubyインタプリタで動かすには、 そのプログラムがprog.rbというファイルに保存されているとして、次のように実行すればいいのでした （MinRubyインタプリタはinterp.rbという名前のファイルに保存しているとします）。

C:¥Ruby > ruby interp.rb prog.rb ⏎

これで何をしているかというと、こういう状況になっています。

1. RubyでMinRubyインタプリタを実行し（ruby interp.rb ...）、
2. そのMinRubyインタプリタでプログラムを動かす（... prog.rb）

いまやりたいのはブートストラップ、つまりMinRubyインタプリタでMinRubyインタプリタを動かすことなので、 この例のプログラム（prog.rb）をMinRubyインタプリタ（interp.rb）に置き換えればよさそうです。

C:¥Ruby > ruby interp.rb interp.rb ⏎

とはいえ、インタプリタを動かすには、そのインタプリタで動かすべきプログラムも一緒に与えないと意味がありません。 そこで、次のようなシナリオを考えましょう。

1. RubyでMinRubyインタプリタを実行し、
2. そのMinRubyインタプリタ（親）でMinRubyインタプリタ（子）を動かし、
3. そのMinRubyインタプリタ（子）はプログラムを動かす

これで、次のようにすればブートストラップができそうですね。

C:¥Ruby > ruby interp.rb interp.rb prog.rb ⏎

FizzBuzzプログラムでブートストラップ

具体的なプログラムで実際にブートストラップできるかやってみましょう。 題材として、第2回の練習問題で作成したFizzBuzzプログラムを取り上げます。 FizzBuzzプログラムは、こんなことをするプログラムでしたね。

• 1から100までの数を順番に出力する
• ただし、3で割り切れる数の場合は数の代わりに"Fizz"を出力し、
• 5で割り切れる数の場合は数の代わりに"Buzz"を出力し、
• 3でも5でも割り切れる数の場合は"FizzBuzz"を出力する

FizzBuzzプログラムをRubyで書くとこうなります。

i = 1
while i <= 100
  if i % 3 == 0
    if i % 5 == 0
     p("FizzBuzz")
    else
     p("Fizz")
    end
 else
    if i % 5 == 0
     p("Buzz")
    else
     p(i)
    end
  end
  i = i + 1
end

これをfizzbuzz.rbというファイルに保存して次のように実行すればよさそうです。

C:¥Ruby > ruby interp.rb interp.rb fizzbuzz.rb ⏎

ただ、現状のままでは、まだこのコマンドは動きません。 もう少しだけ準備が必要です。

組み込み関数の準備

なぜ現状でブートストラップできないかというと、まだMinRubyインタプリタに必要な組み込み関数が足りないからです。 もっといえば、MinRubyインタプリタに実装済みの組み込み関数はpしかありません。 しかし、実際に利用している組み込み関数は、pだけではありません。 MinRubyインタプリタが使っている組み込み関数をすべて列挙するとこうなります。

• p
• require
• minruby_parse
• minruby_load
• minruby_call

これらの関数は、いつものように、Ruby言語本体に実装されている同名の関数に丸投げすることにします。 やりかたはpと同様、genvに対応を覚えさせておくだけです。

genv = {
  "p" => ["builtin", "p"],
  "require" => ["builtin", "require"],
  "minruby_parse" => ["builtin", "minruby_parse"],
  "minruby_load" => ["builtin", "minruby_load"],
  "minruby_call" => ["builtin", "minruby_call"],
}

関数呼び出しのかっこの省略

今しれっと、requireを組み込み関数に含めました。実は、そうなんです。 requireは特別な命令でもなんでもなく、ライブラリのソースコードを読み込んで実行する組み込み関数なのです。

でも関数ということは()が必要なはずですよね。 しかし、実はRubyでは、この関数呼び出しのかっこを省略できるのです。 つまり、

require "minruby"

と書いていたrequireですが、これはRubyでは

require("minruby")

の構文糖（第6回参照）なのです。

ほかにも、たとえばデバッグ出力のpや無引数の関数ではかっこを書かないことのほうが多いです。

p 42 #=> 42

かっこを省略して読みやすくなることも多々ありますが、 無暗に省略するとかえって読みにくくなったり、想定と異なる抽象構文木になって思わぬ挙動になってしまったりするので、節度を保って利用してください。

比較式と剰余演算の準備

もう一つ、現状のMinRubyインタプリタをブートストラップするために足りない機能として、比較式があります。 MinRubyインタプリタのソースコードにはmhd[0] == "builtin"という比較式が入っているので、これをサポートしておく必要があるのです。

ついでに、プログラムの題材であるFizzBuzzプログラムをふつうに実行するうえで必要になるので、他の比較式と剰余演算（%）も入れておきます。

when "%"
  evaluate(tree[1], genv, lenv) % evaluate(tree[2], genv, lenv)
when "<"
  evaluate(tree[1], genv, lenv) < evaluate(tree[2], genv, lenv)
when "<="
  evaluate(tree[1], genv, lenv) <= evaluate(tree[2], genv, lenv)
when "=="
  evaluate(tree[1], genv, lenv) == evaluate(tree[2], genv, lenv)
when "!="
  evaluate(tree[1], genv, lenv) != evaluate(tree[2], genv, lenv)
when ">="
  evaluate(tree[1], genv, lenv) >= evaluate(tree[2], genv, lenv)
when ">"
  evaluate(tree[1], genv, lenv) > evaluate(tree[2], genv, lenv)

これらをevaluateに追加するだけです。 （実は、どちらも第4回の練習問題で登場しているのですが、 これまでinterp.rbのソースでは省略していました。）

ブートストラップしてみる

いよいよ、問題のコマンドを実行してみましょう。

C:¥Ruby > ruby interp.rb interp.rb fizzbuzz.rb ⏎

FizzBuzzが出力されれば、ブートストラップ大成功です。 つまり、「fizzbuzz.rbを実行するMinRubyインタプリタプログラム」を MinRubyインタプリタで実行することができました。

これに成功したら、次は、「『fizzbuzz.rbを実行するMinRubyインタプリタプログラム』を実行するMinRubyインタプリタプログラム」をMinRubyインタプリタで実行しましょう。 分解して言うと、

1. RubyでMinRubyインタプリタを動かし、
2. MinRubyインタプリタ（親）でMinRubyインタプリタ（子）を動かし、
3. そのMinRubyインタプリタ（子）でMinRubyインタプリタ（孫）を動かし、
4. そのMinRubyインタプリタ（孫）はFizzBuzzプログラムを動かす

ということです。コマンドとしては次のようになります。

C:¥Ruby > ruby interp.rb interp.rb interp.rb fizzbuzz.rb ⏎

さらに段数を増やすこともできます。 そのたびにMinRubyインタプリタが新たに実行されるので、動作がどんどん遅くなっていくことが確認できるはずです。

Rubyでスタックを増やす方法

もし段数を増やしすぎて、stack level too deep (SystemStackError)というエラーが出たら、 Ruby本体が使っているスタックと呼ばれるメモリを使い尽くしてしまったということです。 以下のように実行すれば、Ruby本体が使うスタック領域を増やすことができます （setはWindowsのコマンドプロンプトの場合のコマンドなので、環境に合わせて読み替えてください）。

C:¥Ruby > set RUBY_THREAD_VM_STACK_SIZE=4000000 ⏎
C:¥Ruby > ruby interp.rb interp.rb interp.rb fizzbuzz.rb ⏎

minruby_loadの細かい話

MinRubyインタプリタを次のようにブートストラップで起動するとき、

C:¥Ruby > ruby interp.rb interp.rb fizzbuzz.rb ⏎
                         ~~~(1)~~~ ~~~~(2)~~~~

MinRubyインタプリタ（親）は、まず実行すべきプログラムを読み込むために、 minruby_loadを使います。 それで読み込まれるのは、上記の下線(1)で示されるファイルinterp.rbです。 このファイルはMinRubyインタプリタ（子）です。 このファイルからMinRubyインタプリタ（子）を読み込んだら、それを抽象構文木にし、 その抽象構文木をevaluateしていきます。

すると、そのうち、minruby_loadを"func_call"するノードに遭遇します。 その処理は、そのままMinRubyインタプリタ（親）のminruby_loadに丸投げされます。 これは、MinRubyインタプリタ（親）から見れば、2度目のminruby_loadの呼び出しです。 これによって読み込まれるのが、下線(2)で示されるファイルfizzbuzz.rbなら、 MinRubyインタプリタ（子）がFizzBuzzプログラムを評価実行していけます。 しかし、MinRubyインタプリタ（親）には、 どうして2度目のminruby_load呼び出しの対象がfizzbuzz.rbであるとわかるのでしょうか？

実は、minruby_loadは呼び出されるたびに「次」のファイルを読み込むようになっています。 つまり、たとえばexperiment5.rbというファイルで次のように2回呼ばれているとしたら、

p(minruby_load())
p(minruby_load())

次のようにRubyを実行することでfoo.txtとbar.txtの内容を順次読み込んで出力してくれるのです。

C:¥Ruby > ruby experiment5.rb foo.txt bar.txt ⏎
"(foo.txt の内容)"
"(bar.txt の内容)"

そのため、MinRubyインタプリタ（親）の2度目のminruby_load呼び出しの対象は無事にfizzbuzz.rbになります。

ちなみに、requireもMinRubyインタプリタ（親）と（子）の両方に呼ばれます。 しかし、requireは同じライブラリを複数回読み込もうとしても、 2回目以降のrequireは何もしないことになっています。 よって、MinRubyインタプリタ（子）がrequireを呼んでもブートストラップに悪影響が出ることはありません。

まとめ

ついに、本連載の本当の目標であった「自作インタプリタのブートストラップ」に到達しました。おめでとうございます。 最終的なMinRubyのソースコード（interp.rb）は次のとおりです。

require "minruby"
 
def evaluate(tree, genv, lenv)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1], genv, lenv) + evaluate(tree[2], genv, lenv)
  when "-"
    evaluate(tree[1], genv, lenv) - evaluate(tree[2], genv, lenv)
  when "*"
    evaluate(tree[1], genv, lenv) * evaluate(tree[2], genv, lenv)
  when "/"
    evaluate(tree[1], genv, lenv) / evaluate(tree[2], genv, lenv)
  when "%"
    evaluate(tree[1], genv, lenv) % evaluate(tree[2], genv, lenv)
  when "<"
    evaluate(tree[1], genv, lenv) < evaluate(tree[2], genv, lenv)
  when "<="
    evaluate(tree[1], genv, lenv) <= evaluate(tree[2], genv, lenv)
  when "=="
    evaluate(tree[1], genv, lenv) == evaluate(tree[2], genv, lenv)
  when "!="
    evaluate(tree[1], genv, lenv) != evaluate(tree[2], genv, lenv)
  when ">="
    evaluate(tree[1], genv, lenv) >= evaluate(tree[2], genv, lenv)
  when ">"
    evaluate(tree[1], genv, lenv) > evaluate(tree[2], genv, lenv)
  when "stmts"
    i = 1
    last = nil
    while tree[i]
      last = evaluate(tree[i], genv, lenv)
      i = i + 1
    end
    last
  when "var_assign"
    lenv[tree[1]] = evaluate(tree[2], genv, lenv)
  when "var_ref"
    lenv[tree[1]]
  when "if"
    if evaluate(tree[1], genv, lenv)
      evaluate(tree[2], genv, lenv)
    else
      evaluate(tree[3], genv, lenv)
    end
  when "while"
    while evaluate(tree[1], genv, lenv)
      evaluate(tree[2], genv, lenv)
    end
  when "func_def"
    genv[tree[1]] = ["user_defined", tree[2], tree[3]]
  when "func_call"
    args = []
    i = 0
    while tree[i + 2]
      args[i] = evaluate(tree[i + 2], genv, lenv)
      i = i + 1
    end
    mhd = genv[tree[1]]
    if mhd[0] == "builtin"
      minruby_call(mhd[1], args)
    else
      new_lenv = {}
      params = mhd[1]
      i = 0
      while params[i]
        new_lenv[params[i]] = args[i]
        i = i + 1
      end
      evaluate(mhd[2], genv, new_lenv)
    end
  when "ary_new"
    ary = []
    i = 0
    while tree[i + 1]
      ary[i] = evaluate(tree[i + 1], genv, lenv)
      i = i + 1
    end
    ary
  when "ary_ref"
    ary = evaluate(tree[1], genv, lenv)
    idx = evaluate(tree[2], genv, lenv)
    ary[idx]
  when "ary_assign"
    ary = evaluate(tree[1], genv, lenv)
    idx = evaluate(tree[2], genv, lenv)
    val = evaluate(tree[3], genv, lenv)
    ary[idx] = val
  when "hash_new"
    hsh = {}
    i = 0
    while tree[i + 1]
      key = evaluate(tree[i + 1], genv, lenv)
      val = evaluate(tree[i + 2], genv, lenv)
      hsh[key] = val
      i = i + 2
    end
    hsh
  end
end
 
# ① プログラムの文字列を読み込む
str = minruby_load()
 
# ② プログラムの文字列を抽象構文木に変換する
tree = minruby_parse(str)
 
# ③ 抽象構文木を実行（計算）する
genv = {
  "p" => ["builtin", "p"],
  "require" => ["builtin", "require"],
  "minruby_parse" => ["builtin", "minruby_parse"],
  "minruby_load" => ["builtin", "minruby_load"],
  "minruby_call" => ["builtin", "minruby_call"],
}
lenv = {}
evaluate(tree, genv, lenv)

while文の条件について補足

第2回では、分岐の条件式がtrueやfalseになった場合の挙動を説明しましたが、 それ以外の値になった場合の挙動について説明していませんでした。 Rubyでは、falseとnilを偽として扱い、それ以外の値すべてを真として扱います。

第5回ではwhile tree[i] != nilというコードを書いていましたが、 いつの間にか説明なしでwhile tree[i]と書いてしまっていました（すみません）。 これらはtree[i]がfalseになる場合のみ、挙動が異なります。 ただし抽象構文木のノードの部分にfalseがいきなり現れることはないので、 実質的には同じ意味となります。

あとがき

この連載では、Rubyインタプリタを題材として、Rubyプログラミングの概要を紹介してきました。 プログラミング初心者の方でもわかるよう、説明内容を厳選して丁寧に説明したつもりです。 そのため、この連載で紹介したRubyの言語機能は、全体から見るとものすごく一部になっています。 Rubyで自由にプログラムを書けるようになるには、『初めてのRuby』（Yugui著、オライリー・ジャパン）などの本を読むといいでしょう。

この連載のもう一つの意図は、すでにRubyや他言語のプログラミングを知っている方に、 「インタプリタの実装」というのはそんなに難しいものではない、 ということを伝えることでした。それが実現できていたら嬉しいです。 なにしろ、本質的には、この連載で作り上げたほんの100行強のプログラムで書けるのですから。

もちろん、必要最小限の言語機能しか実装していませんし、 実用的なインタプリタを目指すにはこれはスタート地点に過ぎません。 抽象構文木を作る部分（構文解析）も、この連載では扱いませんでした。 それらは興味を持った皆さんへの自習問題としたいと思います。

ということで、Rubyを作りながらRubyを学ぶ連載は今回でいったん終わります。 ありがとうございました。