Rubyで学ぶRuby 第6回

分岐を実装する

こんにちは。Rubyを作りながらRubyを学ぼうという連載企画、第6回です。

前回は、Rubyで変数付き四則演算インタプリタを作りました。 今回は、これを拡張して分岐を実装します。

現状の確認

まず、変数付き四則演算インタプリタの現状のソースコードを省略せずに載せておきます。 第4回の練習問題にあった、剰余や比較式の実装についても加えてあります。

require "minruby"
def evaluate(tree, env)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1], env) + evaluate(tree[2], env)
  when "-"
    evaluate(tree[1], env) - evaluate(tree[2], env)
  when "*"
    evaluate(tree[1], env) * evaluate(tree[2], env)
  when "/"
    evaluate(tree[1], env) / evaluate(tree[2], env)
  when "%"
    evaluate(tree[1], env) % evaluate(tree[2], env)
  when "**"
    evaluate(tree[1], env) ** evaluate(tree[2], env)
  when "<"
    evaluate(tree[1], env) < evaluate(tree[2], env)
  when "<="
    evaluate(tree[1], env) <= evaluate(tree[2], env)
  when "=="
    evaluate(tree[1], env) == evaluate(tree[2], env)
  when ">="
    evaluate(tree[1], env) >= evaluate(tree[2], env)
  when ">"
    evaluate(tree[1], env) > evaluate(tree[2], env)
  when "func_call"  # 仮の実装
    p(evaluate(tree[2], env))
  when "stmts"
    i = 1
    last = nil
    while tree[i]
      last = evaluate(tree[i], env)
      i = i + 1
    end
    last
  when "var_assign"
    env[tree[1]] = evaluate(tree[2], env)
  when "var_ref"
    env[tree[1]]
  end
end
# ① 計算式の文字列を読み込む
str = minruby_load()
# ② 計算式の文字列を計算の木に変換する
tree = minruby_parse(str)
# ③ 計算の木を実行（計算）する
env = {}
evaluate(tree, env)

今回はこれをさらに拡張して、if文とwhile文を実装していきます。

でもその前に、ここまでのおさらいをしておきましょう。 上記のソースコード、すなわち「変数付き四則演算インタプリタ」は何をしているのでしょうか？ 連載の第3回から第5回までの話を思い返してみましょう。

0. 「木」という構造があった。「関数」を使うと木をたどることができた（第3回）
1. 四則演算の式を「木」として表現できた。その木をたどって式の答えを返す「関数」を作った（第4回）
2. 式を並べた複文も「木」として表現できることを見た。プログラムは複文なので、プログラムもまた「木」として表現できる。その木（抽象構文木）をたどって結果を返す「関数」を作った（第5回の前半）
3. プログラムでは「変数」（値を覚えておいてくれるもの）を使いたい。どの変数にどんな値を覚えさせたかを管理する「環境」というものを用意した。変数への代入があったら、変数名と値の対応を環境に格納していく。環境は刻々と変化するので、抽象構文木をたどる関数では次々に持ちまわることにした（第5回の後半）

これらの話が現状のインタプリタの姿にどう対応しているかというと、

1. 最初に定義しているevaluate関数が、木をたどる関数
2. 変数treeに代入したminruby_parseの結果が、抽象構文木
3. 変数envに代入した空のハッシュが、環境の初期状態
4. 最後のevaluate(tree, env)で、2の抽象構文木と3の環境を指定して実行開始

そしてevaluate関数は、見かけは長いですが、見てのとおり1つの大きなcase文になっています （case文を忘れた人は第2回を読み直しましょう）。 木の節（tree[0]）に応じた条件分岐のかたまりにすぎません。

たとえば、節が"+"だったら、その先に2つあるはずの部分木を足し合わせます。 部分木がすぐに葉（しかもリテラル）ならいいのですが、そうとは限らないので、そこで2つの部分木に対して再帰的にevaluateを使っています （再帰を忘れた人は第3回を、 リテラルについて忘れた人は第4回を読み直しましょう）。 そんなふうに再帰的に木をたどっていくと、どの部分木もいつかはリテラルな葉（lit）に行きつくので、そのときは葉の値（tree[0]）を単純に返します。

いかがでしょうか。現状のインタプリタのどの部分で何をやっているのか思いだしていただけたでしょうか？ 今回の記事では、いま作っているインタプリタに対して、抽象構文木にifやwhileに相当する節が出てきたときに何をすればいいかを教えてあげます。 言い方を変えると、このインタプリタにif文とwhile文の実装を組み込みます。

if文とwhile文を実装するということは、このインタプリタで条件分岐があるプログラムを実行できるようになるということです。 ここまでくれば、もういっぱしのプログラミング言語のインタプリタを実装しているぞ、と公言してもいいでしょう。 そこで以降では「四則演算インタプリタ」という呼び方をやめて、このインタプリタを正式に「MinRubyインタプリタ」と呼ぶことにします。

if文を実装する

それではMinRubyインタプリタにif文を実装していきます。目標は次のMinRubyプログラムを動かせるようにすることです。

if 0 == 0
  p(42)
else
  p(43)
end

まずは、このMinRubyプログラムの抽象構文木がどのような姿になるか、前回同様にminruby_parseを使って確かめてみましょう。 次のプログラムをファイルに書いて、experiment4.rbという名前で保存してください。

require "minruby"
pp(minruby_parse("
if 0 == 0
  p(42)
else
  p(43)
end
"))

これをRubyで実行すれば抽象構文木のようすを確認できます。

C:\Ruby > ruby experiment4.rb ⏎
["if",
 ["==", ["lit", 0], ["lit", 0]],
 ["func_call", "p", ["lit", 42]],
 ["func_call", "p", ["lit", 43]]]
C:\Ruby > 

図に描くと次のような木です。"if"という新しいラベルが増えていますね。

一見すると難しくなってきたように見えるかもしれませんが、if文の意味を思い出しながら眺めれば単純です。 if文の意味は、

1. まずtree[1]の条件式を評価する、
2. trueだったらtree[2]を評価する、
3. falseだったらtree[3]を評価する

というものでしたね。 そう思って先ほどの抽象構文木を見れば、要は次のような構造をしているのだとわかるはずです。

["if",
  条件式,
  条件式がtrueの場合に実行するコード,
  条件式がfalseの場合に実行するコード]

では、このような構造の木をどうやってRubyで処理し、MinRubyのif文を実装すればいいでしょうか？

当たり前ですが、これは分岐です。そして、Rubyで分岐をするにはif文を使うのでした。 Rubyのif文を使って、この構造をプログラムに落としこんでみましょう。

部分木の評価はevaluate(tree[1], env)のようにすればいいので、次のように素直に書けます。

def evaluate(tree, env)
  case tree[0]
  when "if"
    if evaluate(tree[1], env)
      evaluate(tree[2], env)
    else
      evaluate(tree[3], env)
    end
  ...(略)...
  end
end

きつねにつままれたような気分かもしれませんが、これだけでちゃんと動きます。 最初に目標にした次のプログラムを実際に動かしてみてください。

if 0 == 0
  p(42)
else
  p(43)
end

なお、このif文の実装では、特に環境をいじっていないことに注目してください。変数envを単にevaluateの引数として横流ししているだけで、環境の中身を読み出したり変更したりはしていません。 if文で分岐の方向を変えるのには変数の値を（通常は）使うので、これはちょっと不思議に思うかもしれません。

しかしよく考えてみると、変数を参照するのは条件式（比較式）であり、if文そのものは、比較式の評価結果を見て分岐の方向を決定しているだけです。 実際、上記のプログラムでも0 == 0という（当たり前な）比較式を使っています。if文と変数は独立しているのです。

ちょっと寄り道：インタプリタとは

「ifを実装するのにif文を使うのってインチキなのでは？」と思うかもしれません。でも、これこそがインタプリタの本質です。

インタプリタとは、言語Xで書かれたプログラムを実行する、言語Yで書かれたプログラムです。たとえば（本物の）Rubyインタプリタは、Ruby言語で書かれたプログラムを実行する、機械語で書かれたプログラムです。（本物の）Rubyインタプリタでは、Rubyプログラムのif文を機械語のif文（に相当する言語機能）で実装しています。

同様に、MinRubyインタプリタは、MinRuby言語で書かれたプログラムを実行する、Rubyで書かれたプログラムです。なので、MinRubyプログラムのif文をRubyのif文で実装したわけです。

インタプリタの本質は、高レベルの言語機能を低レベルの言語機能に丸投げすることです。if文の実装では、非常に綺麗に丸投げできました。しかし、すべての言語機能が常に丸投げできるわけでもありません。低レベルの言語には存在しない言語機能を高レベルの言語に持たせる場合は、低レベルの言語機能を組み合わせて実装する必要があります。また、前回実装した変数のように、単純な丸投げが難しい場合もあります。

ついでにいうと、この連載はMinRubyの数値やtrue/false/nilなどの値を、そのままRubyの対応する値として流用しています。しかし、そうしなければならないわけではありません。たとえば、MinRubyの5という数字を、Rubyの-5を使って表すことにしてもかまいません。あるいは、["num", 5]という配列で表すということにしてもかまいません。それでは話がむやみに複雑になるので、Rubyの対応する値を使っているだけです。

while文を実装する

MinRubyの分岐はif文だけではありませんでした。次はwhile文を実装しましょう。

と言っても、実はif文とほとんど同じ要領で実装できます。 while文の実装をまるまる練習問題にしようかと迷ったくらいなので、自信のある人は続きを読む前にちょっと考えてみてください。

実装を考えるときの目標にするのは次のサンプルプログラムです。

i = 0
while i < 10
  p(i)
  i = i + 1
end

このプログラムの抽象構文木をいつものように求めると次のような姿をしていることがわかります。

["stmts",
 ["var_assign", "i", ["lit", 0]],
 ["while",
  ["<", ["var_ref", "i"], ["lit", 10]],
  ["stmts",
   ["func_call", "p", ["var_ref", "i"]],
   ["var_assign", "i", ["+", ["var_ref", "i"], ["lit", 1]]]]]]

新たに登場したラベルは"while"です。

while文の抽象構文木も、意味を考えながら眺めれば見た目ほど難しくはありません。

["while",
 条件式,
 ループ内のコード本体]

では、MinRubyのwhile文をRubyで実装していきましょう。 if文と同様、while文も「Rubyのwhile文」を使って実装できます。

def evaluate(tree, env)
  case tree[0]
  when "while"
    while evaluate(tree[1], env)
      evaluate(tree[2], env)
    end
  ...(略)...
  end
end

これでおしまいです。目標として使ったサンプルプログラムを動かしてみてください。

case文は？

もうひとつ、MinRubyにはcase文という分岐もありました。次のサンプルプログラムを目標にしながらcase文も実装してみましょう。

case 42
when 0
  p(0)
when 1
  p(1)
else
  p(2)
end

このプログラムの抽象構文木はこうなります。

["if",
 ["==", ["lit", 42], ["lit", 0]],
 ["func_call", "p", ["lit", 0]],
 ["if",
  ["==", ["lit", 42], ["lit", 1]],
  ["func_call", "p", ["lit", 1]],
  ["func_call", "p", ["lit", 2]]]]

あれ、新しいラベルがありませんね？ この抽象構文木を見る限り、このcase文は次のif文によるプログラムとまったく同じです。

if 42 == 0
  p(0)
else
  if 42 == 1
    p(1)
  else
    p(42)
  end
end

ということで、MinRubyのcase文のために新たに実装することは何もありません。 現状のMinRubyインタプリタで先ほどのcase文のプログラムを実行してみてください。

にしても、同じ抽象構文木になってしまうというのに、case文なんて必要なんでしょうか？ if文だけあればいいのではないでしょうか？

確かに、抽象構文木が同じなのだから、MinRubyを実装しているRubyから見ればif文もcase文も同じです。 minruby_parseは、case文を見たらif文の入れ子として抽象構文木を作って返すようにできています。

しかし、プログラムの書き方や見た目が違うのは、MinRubyプログラムを書く人間にとっては大きな違いがあります。 ifの入れ子が深くなれば、分岐の条件を間違える可能性も高くなるでしょう。 そんなときにcase文を使ってすっきり書けるような問題もたくさんあるのです。

このように、構文解析の段階で他の言語機能を使ったプログラムに変換して扱うものを糖衣構文や構文糖と言います。 文字通り、口当たりのよい構文で他の構文をくるむというわけです。

この連載では糖衣構文を紹介するためにMinRubyのcase文を糖衣構文として実装しましたが、 本当のRubyのcase文は単純な糖衣構文ではありません。

まとめ

今回までで、四則演算と変数、それに分岐とループのあるプログラムを実行できるMinRubyインタプリタを実装しました。 現状のソースコードを全部載せておきます。

require "minruby"
def evaluate(tree, env)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1], env) + evaluate(tree[2], env)
  when "-"
    evaluate(tree[1], env) - evaluate(tree[2], env)
  when "*"
    evaluate(tree[1], env) * evaluate(tree[2], env)
  when "/"
    evaluate(tree[1], env) / evaluate(tree[2], env)
  when "func_call"  # 仮の実装
    p(evaluate(tree[2], env))
  when "stmts"
    i = 1
    last = nil
    while tree[i]
      last = evaluate(tree[i], env)
      i = i + 1
    end
    last
  when "var_assign"
    env[tree[1]] = evaluate(tree[2], env)
  when "var_ref"
    env[tree[1]]
  when "if"
    if evaluate(tree[1], env)
      evaluate(tree[2], env)
    else
      evaluate(tree[3], env)
    end
  when "while"
    while evaluate(tree[1], env)
      evaluate(tree[2], env)
    end
  end
end
# ① プログラムの文字列を読み込む
str = minruby_load()
# ② プログラムの文字列を抽象構文木に変換する
tree = minruby_parse(str)
# ③ 抽象構文木を実行（計算）する
env = {}
evaluate(tree, env)

ここまでくれば、もう「プログラミング言語処理系を作った」といっても過言ではありませんが、 もうひとつ重要な機能が足りません。それは関数です。 次回は、この連載で最大の難関になるかもしれない、関数の実装を紹介する予定です。

練習問題

1. 帰ってきたFizzBuzz

第2回の練習問題2や練習問題3で書いたプログラムをMinRubyで動かしてみてください。

また、if文やwhile文を使う好きなプログラムを書いて、 MinRubyとRubyの両方で動かしてみてください。 たとえば、階乗を計算するプログラム（1 * 2 * 3 * ...を計算するプログラム）や、 素数を順番に出力するプログラム（2、3、5、7、11...と表示するプログラム）などが 書けると思います。

2. begin ... end whileの実装

本物のRubyには2種類のwhile文があります。1つは、本文で述べたwhile文です。

i = 10
while i > 0
  p(i)
  i = i - 1
end

もう1つは、begin ... end whileで条件が後に書かれるwhile文です。

i = 10
begin
  p(i)
  i = i - 1
end while i > 0

これら2つのプログラムは同じ動きをします。

違いは、最初に条件判定を行うかどうかです。 普通のwhile文はまず最初に条件判定を行いますが、 begin ... end while文は最初の条件判定を行いません。 最初のi = 10をi = 0やi = -1に置き換えると違いがわかります。

begin ... end whileをMinRubyに実装してみましょう。

なお、実装を開始する前にminrubyライブラリを更新する必要があります。 gemでインストールした人はgem updateコマンドを実行してください。 ファイルをダウンロードした人は再度ダウンロードして、上書きしてください。

ヒント1：上記のサンプルプログラムをminruby_parseすると、 while2というラベルが出てきます。これを実装してください。

ヒント2：普通のwhile文を実装したときと同じように、 begin ... end while文自身を使って実装するのでもよいですが、 普通のwhile文を使ってbegin ... end while文を実装してみると、 両者の違いをよりいっそう理解できると思います。

3. case文の意味

MinRubyのcase文とRubyのcase文の意味の違いを見るために、 次のプログラムをMinRubyとRubyの両方で実行して、挙動の違いを確認してください。

case p(42)
when 0
  p(0)
when 1
  p(1)
else
  p("others")
end

そして、MinRubyでは何が起きているか、どうしてこのような違いが起きたかを 考えてみてください。

ヒント：関数pは引数の値をそのまま返り値とします。

第5回の練習問題の答え

1. おさらい

略

2. 足し算のカウント

def evaluate(tree, env)
  case tree[0]
  when "+"
    env["plus_count"] = env["plus_count"] + 1
    evaluate(tree[1]) + evaluate(tree[2])
  ...(略)...
  end
end

3. デバッグのコツ

def evaluate(tree, env)
  case tree[0]
  else
    p("error")
    pp(tree)
raise("unknown node")
  ...(略)...
  end
end

（raise("...")と書くことで、プログラムの動作を停止させることができます。）