Rubyで学ぶRuby 第5回

Rubyで変数付き電卓を作ってみる

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

前回は、Rubyで四則演算インタプリタ（電卓）を作りました。 今回からは、このインタプリタを拡張して、いよいよMinRubyインタプリタを作っていきます。

まずは前回の四則演算インタプリタを改造して、入力をファイルに書いて渡せるようにしましょう。 本物のRubyインタプリタも、ファイルに書かれたプログラムを読み取って実行できます。 MinRubyインタプリタも、ファイルに書いたMinRubyプログラムを実行するようにしたいので、 ベースにする前回の四則演算インタプリタもそのように改造します。

そのあとで、四則演算インタプリタに、今回の目標である「変数」を導入していきます。 連載の第1回では、変数のことを「値を覚えてくれる人」であると説明しました。 それを作るわけですから、値を覚えておくための仕組みが何かしら必要です。 Rubyで使えるそのような仕組みとして、「ハッシュ」というものを学びます。

ファイルから入力を読み取る

電卓のソースコード（再掲）

前回作った電卓のソースコードは次のようなものでした （長ったらしくなるので少し改変しています）。

require "minruby"
def evaluate(tree)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1]) + evaluate(tree[2])
  when "-"
    evaluate(tree[1]) - evaluate(tree[2])
  when "*"
    evaluate(tree[1]) * evaluate(tree[2])
  when "/"
    evaluate(tree[1]) / evaluate(tree[2])
  end
end
# ① 計算式の文字列を読み込む
str = gets
# ② 計算式の文字列を計算の木に変換する
tree = minruby_parse(str)
# ③ 計算の木を実行（計算）する
answer = evaluate(tree)
# ④ 計算結果を出力する
p(answer)

見てのとおり、現在の四則演算インタプリタでは、ユーザが手で入力した計算式を読み込み（①）、それを計算の木にして（➁）から評価し（③）、その結果を本物のRubyの関数pで出力しています（④）。 覚えていない人は第4回を復習しておいてください。

ソースコードを読み込むようにする

まずは、①の部分の改造です。四則演算インタプリタでは計算式をコンソールに直接打ち込んでいましたが、計算式をソースコードとしてファイルから読み込むようにしましょう。

# ① 計算式の文字列を読み込む
str = gets

としていたところを、次のように書き換えてください。

# ① 計算式の文字列を読み込む
str = minruby_load()

minruby_loadは筆者のライブラリが提供している関数で、コマンドラインに渡されたファイルを読み込んで文字列として返します。

デバッグ出力関数pを実装する

次は、計算結果を出力する④の部分を改造します。

現在の四則演算インタプリタでは、計算の木を評価してから、その結果を本物のRubyのp関数を使って出力しています。 しかし、ここで四則演算インタプリタの関数として、式を評価して内容を表示してくれるデバッグ出力関数pを作っておくことにします。

名前がどちらもpなので混乱してしまうかもしれませんが、四則演算インタプリタへの入力で本物のRubyのp関数を使うわけにはいかないので、 ソースコードとして計算式を渡すときには四則演算インタプリタの関数であるpを実装して、それを使う必要があります。

とはいえ、関数の実装については次々回できちんと詳しく解説するので、今回は内容を深く気にせずにevaluateの定義の最後の部分に次のような仮の実装を入れておいてください。 （かいつまんで何をしているか説明すると、木の一部として「p(なにか計算式)」を表すような節があった場合、引数である「なにか計算式」を評価した結果を本物のRubyのpで表示しています。）

def evaluate(tree)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1]) + evaluate(tree[2])
  when "-"
    evaluate(tree[1]) - evaluate(tree[2])
  when "*"
    evaluate(tree[1]) * evaluate(tree[2])
  when "/"
    evaluate(tree[1]) / evaluate(tree[2])
  when "func_call"          # 仮の実装
    p(evaluate(tree[2]))
  end
end

デバッグ関数pを実装したことで、プログラム自身が計算結果を出力する命令を利用可能になったので、最後に本物のRubyで結果を出力することはもう不要です。 もともとの四則演算インタプリタに入れていた次の命令は消してください。

# ④ 計算結果を出力する
p(answer)

これで四則演算インタプリタに渡すソースコードの中でデバッグ出力関数pを使えるようになりました。

四則演算インタプリタにソースコードを渡して実行する

ここまでの改造により、ファイルをソースコードとして四則演算インタプリタに渡せば、ファイルに書かれた計算式の結果が表示されるようになりました。 さっそく試してみましょう。 次の1行を書いたファイルをtest.rbという名前で保存してください。

p(40 + 2)

そして次のように実行してみてください。

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

念のために補足すると、test.rbはRubyプログラムではなく、四則演算インタプリタのプログラムですよ。 四則演算インタプリタのほうは、ruby interp.rbという部分で、本物のRubyにより実行しています。

ちょっとインタプリタっぽくなってきましたね！

複数の式を扱えるようにする（複文）

計算式とプログラムの違い

ここで、計算式とプログラムの違いを考えてみます。計算式は、例えば次のような文字列で表されます。

1 + 2

プログラムは、例えば次のような文字列です。

x = 1
y = 2
p(x + y)

プログラムには、計算式には出てこなかった変数や関数などが出てきます。が、実はもっと本質的な違いがあります。さらに簡単なプログラムを見てみましょう。

1 + 2
6 * 7
40 + 2

変数も関数もありませんが、これも立派なプログラムです。 計算するだけで何も出力しないので、まったく無意味なプログラムではありますが、それでも計算式とは本質的に異なるところが現れています。それは「式が複数ある」ということです。

計算式は、その1つの式を実行して1つの値になったら終わりです。一方プログラムは、そのような計算式を何個も並べることができ、それらを上から順番に実行していきます。 このように複数の計算式を並べたものを複文といいます。計算式とプログラムの大きな違いは、プログラムは全体として複文になっているという点です（なお、プログラム全体以外にもif文の中身や関数定義の中身も複文になっています。これらについてはおいおい出てきます）。

現状のインタプリタを改造して、単一の計算の木ではなく複文を扱うようにしていきましょう。

複文の抽象構文木

まず、複文とは何かを観察するため、先の無意味なプログラムをminruby_parseしてみましょう。 次のようなRubyプログラムを書いて実行してみてください（改行は見やすさのために入れているのではありません。この通りに入力する必要があります）。

require "minruby"
pp(minruby_parse("
1 + 2
6 * 7
40 + 2
"))

次のような出力が表示されるはずです（上記のプログラムをexperiment1.rbというファイルに保存したとします）。

C:¥Ruby > ruby experiment1.rb ⏎
["stmts",
  ["+", ["lit", 1], ["lit", 2]],
  ["*", ["lit", 6], ["lit", 7]],
  ["+", ["lit", 40], ["lit", 2]]]
C:¥Ruby > 

これらを木の図として表現すると、次のようになります。

計算の木が3つ並んでいます。それぞれ1 + 2、6 * 7、40 + 2です。 そして、これらを束ねた"stmts"という名前の節が、木全体となっています。 stmtsはstatements（複文）の略です。 これは、「子どもの計算の木を左から順番に計算せよ」という意味を持つ木です。

複文の実装

evaluate関数を拡張して、複文に対応しておきましょう。 まずは"stmts"という節に対するwhenを追加します。 現状の四則演算インタプリタinterp.rbのevaluateの最後に次のように追記してください。

def evaluate(tree)
  case tree[0]
  when "+"
    # (略)
  when "stmts"
    # ここを埋める
  end
end

複文の木を表す配列の0番めには"stmts"という文字列が入っていて、 それ以降の要素に肝心の複数の文が入っています。 そこで1番めから最後までを順番に処理していきます。 順番に計算するにはwhile文を使うのでしたね。

def evaluate(tree)
  case tree[0]
  when "+"
    # (略)
  when "stmts"
    i = 1
    while tree[i] != nil
      # ここを埋める
      i = i + 1
    end
  end
end

tree[i]はiが配列の長さを超えるとnilを返します。 よって、tree[i] != nilという条件を使えば、「配列の1番目から終わりまで」という繰り返しを書くことができます。

あとは、複文の木が子どもとして持っている部分木を順次実行していけば出来上がりです。 これは再帰呼び出しで実装できます。

def evaluate(tree)
  case tree[0]
  when "+"
    # (略)
  when "stmts"
    i = 1
    while tree[i] != nil
      evaluate(tree[i])
      i = i + 1
    end
  end
end

なお、プログラムの場合にはあまり意味がないのですが、複文にも返り値があります。 一番最後に実行した計算の木の返り値をそのまま返すことになっています。 関数定義の本体も複文で、一番最後の式が返り値になることと対応しています。 ついでにこれも対応しておきましょう。

def evaluate(tree)
  case tree[0]
  when "+"
    # (略)
  when "stmts"
    i = 1
    last = nil
    while tree[i] != nil
      last = evaluate(tree[i])
      i = i + 1
    end
    last
  end
end

lastという変数が増えていますね。 lastには、子どもの計算の木を実行するたびに、その結果を上書きで代入していっています。 そのため、while文を終わったときには、最後に実行した計算の木の結果がlastに入っています。 複文は、このlastの中身をそのまま返り値とします。

複文の実行

次のプログラムを実行してみましょう。test.rbというファイルで保存してください。

p(1 + 2)
p(6 * 7)
p(40 + 2)

そして次のように実行してみてください。

C:¥Ruby > ruby interp.rb test.rb ⏎
3
42
42
C:¥Ruby >

3つの計算式の結果がそれぞれ表示されましたね！

変数を実装する

では、いよいよ変数の実装に入っていきます。

ひとくちに変数といっても、作らないといけない操作は2つあります。 変数を作る「変数代入」（x = 1のような記述）と、 変数を使う「変数参照」（p(x)のような記述）です。

まずは変数を作らないと使えないので、変数代入のほうから考えていきましょう。

変数代入の抽象構文木

複文のときのように、minruby_parseが作る抽象構文木の姿を見ながら考えることにしましょう。 次のような変数代入を含むプログラムを用意してください。

require "minruby"
pp(minruby_parse("
x = 1
y = 2 * 3
"))

これを実行すると、こんな抽象構文木が得られます（上記のプログラムをexperiment2.rbという名前で保存した場合）。

C:¥Ruby > ruby experiment2.rb ⏎
["stmts",
  ["var_assign", "x", ["lit", 1]],
  ["var_assign", "y", ["*", ["lit", 2], ["lit", 3]]]]

図にすると次のようになります。

左側のvar_assignの部分木がx = 1に対応し、右側の部分木がy = 2 * 3に対応します。 つまり、var_assignの意味は「右側の部分木を計算した結果を、左側の変数名の変数に代入する」ということになります。

var_assignの実装をしていきましょう。例によってevaluateにwhenを追加します。

def evaluate(tree)
  case tree[0]
  # (略)
  when "var_assign"
    # ここを埋める
  end
end

さて、ここで手が止まります。どう実装したものでしょうか。

ハッシュ

代入は「この名前の変数に値を覚えさせろ」という、インタプリタに対する命令でした。 今私たちはインタプリタを作っているので、覚えておく立場になります。 変数名という文字列と、それに対応する値を対応付けて覚えておくにはどうすればいいでしょうか。

このようなときに、ハッシュという言語機能が使えます。 ハッシュとはまさに、値と値の対応表のようなデータ構造です （Ruby以外ではハッシュテーブルや辞書、連想配列などとも呼ばれます）。

ハッシュを作るには次のように書きます。

{ "foo" => 1, "bar" => 2 }

これで、"foo"という文字列に1という数を、"bar"という文字列に2という数を対応づけたハッシュができます。 しかし、このままでは別の場所で使えないので、ふつうは次のように、変数を用意してそこに作ったハッシュを代入します。

hsh = { "foo" => 1, "bar" => 2 }

これで変数hshにハッシュが代入されました。とりあえずhshの中身をpで見てみます。

p(hsh) #=> {"foo"=>1, "bar"=>2}

"foo"に対応する値を読み出すには次のように書きます。

p(hsh["foo"]) #=> 1

さらに、すでにあるハッシュに新たな対応を追加したり、すでにある対応の値を更新したりすることもできます。

# 対応を追加
hsh["answer"] = 42
p(hsh["answer"]) => 42
p(hsh) #=> {"foo"=>1, "bar"=>2, "answer"=>42}
# すでにある対応の値を更新
hsh["foo"] = 100
p(hsh["foo"]) #=> 100
p(hsh) #=> {"foo"=>100, "bar"=>2, "answer"=>42}

ハッシュの値を読み出したり更新したりするときの記法は、配列で使う記法（「[」と「]」）とよく似ています。 配列は、「値を並べたもので、i番めの値を自由に取り出せるもの」であり、 いうなれば「自然数と値の対応表」です。 ハッシュは、それを一般化して、自然数以外のものを対応の目印に使えるようにしたものだと考えられます。 そう考えると、ハッシュの値の読み出しと書き込み・更新が配列のそれと同じ記法なのは、ちっとも不思議なことではありませんね。

環境：変数名と値の対応関係

では、ハッシュを使って、変数名と値の対応を覚えるようにしましょう。 インタプリタの業界では、この変数名と値の対応関係のことを環境といいます。

環境は、evaluate関数の中で、変数を定義したり参照したりするときに使います。 そのため、evaluate関数の中で常に参照できる必要があります。 そこでevaluate関数の引数を増やし、その増やした引数を環境の受け渡しに使うことにします。

def evaluate(tree, env)
...（省略）...
end

環境は英語で「environment」なので、引数の名前はenvとしました。

evaluate関数の中では再帰的にevaluateを呼んでいるので、その部分もenv引数をとるように直す必要があります。 しかしその前に、一番最初にevaluateを呼ぶときに渡す環境を用意しましょう。 最初はどんなハッシュを環境として用意すればいいと思いますか？

# ③ 計算の木を実行（計算）する
env = {}
answer = evaluate(tree, env)

ここでは、空のハッシュを作り、それをevaluateに渡すことにしました。 これは、「このインタプリタの実行を開始するときには何の変数も定義されていない」ことを表しています。

次は、evaluate関数の中で再帰的にevaluateを呼んでいる部分を改造していきましょう。

def evaluate(tree, env)
  case tree[0]
  when "+"
    evaluate(tree[1], env) + evaluate(tree[2], env)
  when "-"
    evaluate(tree[1], env) - evaluate(tree[2], env)
  # (略)
  end
end

少し面倒くさいのですが、定義の部分をdef evaluate(tree, env)と書き換えるだけでなく、 evaluate関数を再帰呼び出しする全箇所で、受け取った環境をそのまま渡す必要があります。 いわばバトンリレーですね。 このようにすることで、evaluate関数の中で常に、その時点でのenvが参照できるようになります。

envをいじらずにそのまま渡すだけということは、その演算が環境に依存しないことを意味します。 たとえば、足し算自体は、何かの変数の値に依存して挙動を変えたり、何かの変数を書き換えたりしません。 上記の定義のwhen "+"に対応する部分では、envに手を加えずにそのまま再びevaluateに渡していますが、 これがまさに、変数を書き換えないという足し算自体の性質を表しているといえます。

変数代入を実装する

環境を受け渡す仕組みが整ったところで、ようやく変数代入を実装できるときがきました。

def evaluate(tree, env)
  case tree[0]
  # (略)
  when "var_assign"
    # ここを埋める
  end
end

この穴を埋めます。 変数代入の木は["var_assign", 変数名, 式]という形だったので、 tree[1]は変数名、tree[2]は式を表す部分木です。 まず、式を表す部分木を実行して値にします（再帰呼び出しですね！）。 その結果を、変数名に対応する値としてハッシュに書き込みます。

def evaluate(tree, env)
  case tree[0]
  # (略)
  when "var_assign"
    env[tree[1]] = evaluate(tree[2], env)
  end
end

これで、ついに変数代入が実装できました。

変数参照を実装する

代入は実装できたので、次は参照を実装しましょう。 やはり、まずは変数参照を含む次のプログラムをminruby_parseして、抽象構文木がどんな姿になるのかを見てみましょう。

require "minruby"
pp(minruby_parse("
x = 1
y = x + 2
"))

これを実行すると、こんな抽象構文木になりました（上記のプログラムをexperiment3.rbという名前で保存した場合です）。

C:¥Ruby > ruby experiment3.rb ⏎
["stmts",
  ["var_assign", "x", ["lit", 1]],
  ["var_assign", "y", ["+", ["lit", 2], ["var_ref", "x"]]]]
C:¥Ruby > 

図にすると次のようになります。

左のvar_assignは先に出てきたものと同じです。 右のvar_assignも似ていますが、右上にvar_refという木ができています。 これが変数参照を表しています。 ここでは、xという変数名の変数が覚えている値を返す、という意味です。

var_refを実装していきます。 といっても、環境のハッシュの中で、変数名に対応する値を読みだすだけです。 変数名はtree[1]に入っているので、それでenvを引けばOK。

def evaluate(tree, env)
  case tree[0]
  # (略)
  when "var_ref"
    env[tree[1]]
  end
end

これで変数参照も実装できました。

前回「とりあえず気にするな」と言っていたlitですが、 ここで初めてlit以外で終わる葉が出てきたので簡単に説明します。 litはliteral（リテラル）の略で、 リテラルとは、返すべき値そのものを文字通り示す文字列のことです （literalは「文字通りの」という意味の英単語です）。 つまり、x = 42やp(42)の中の42の部分がリテラルです。 リテラルは数値に限らず、例えばs = "こんにちは"の"こんにちは"の部分も文字列のリテラルです。

動作確認

では、変数代入と変数参照を使ったプログラムを動かしてみましょう。 次のプログラムをtest.rbというファイル名で保存して、ruby interp.rb test.rbと実行して3が出れば成功です。

x = 1
y = x + 2
p(y)

動きましたか？

まとめ

四則演算と複文と変数のあるプログラムを実行できるインタプリタを実装しました。 現状のソースコードを全部載せておきます。

require "minruby"
　
def evaluate(tree, env)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1]) + evaluate(tree[2])
  when "-"
    evaluate(tree[1]) - evaluate(tree[2])
  when "*"
    evaluate(tree[1]) * evaluate(tree[2])
  when "/"
    evaluate(tree[1]) / evaluate(tree[2])
  when "func_call" # 仮の実装
    p(evaluate(tree[2]))
  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)
# ③ 計算の木を実行（計算）する
answer = evaluate(tree)

今回、実質的に追加したのは"stmts"と"var_assign"と"var_ref"だけなので、 行数にするとたったの12行です。 しかし、なかなか濃密な12行と感じられるのではないでしょうか。 このインタプリタで、いろいろなプログラムを走らせてみてください。

次回は分岐を実装します。どんどんプログラムっぽくなっていきますのでお楽しみに。

練習問題

1. おさらい

第1回と第2回（変数のみ）のプログラムをMinRubyインタプリタで動かしてみてください。 たとえば、第2回で登場した次のcalc2.rbを、

answer = (1 + 2) / 3 * 4 * (56 / 7 + 8 + 9)
p(answer)

こんなふうに実行してみましょう。

C:¥Ruby > ruby inter.rb calc2.rb ⏎

期待通りの結果になるでしょうか？

2. 足し算のカウント

足し算を実行した回数を返す特殊な変数plus_countを追加してみてください。 次のように動けば正解です。

plus_count = 0
x = 1 + 2 + 3
p(plus_count) #=> 2
x = 1 + 2 + 3
p(plus_count) #=> 4

ヒント：evaluateの中で足し算を処理するところでは、envは単にたらいまわしするだけでした。 そのときにplus_countをカウントアップするように変更すればOKです。

プログラムの高速化を考えるとき、どういう種類の計算をどのくらい行っているかを 数えたくなることが多々あります。これを行うツールをプロファイラといいます。 プロファイラの指標や実装には非常にさまざまな方法がありますが、 このように興味のある処理を実行した回数を数える特殊な変数を入れるのは、 最も原始的なプロファイラであると言えます。

3. デバッグのコツ

evaluateの再帰呼び出しに与える部分木を間違えると、よくわからないエラーが発生すると思います。 そんなときはevaluateの最初にpp(tree)を入れ、どこでエラーが起きているかを調べるといいのですが、普段はそのようにすると大量の出力が出て煩わしいでしょう。 そこで、evaluateがどのように扱っていいかわからない節に出会ったとき、そのことを報告させるようにするとよいでしょう。これを実装してみてください。

ヒント：case文には、どのwhen節にもマッチしなかった場合に実行すべき処理を示す else節を書くことができます（第4回参照）。これを利用してください。

第4回の練習問題の答え

1. 演算の追加 と 2. 比較式の追加

def evaluate(tree)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1]) + evaluate(tree[2])
  when "-"
    evaluate(tree[1]) - evaluate(tree[2])
  when "*"
    evaluate(tree[1]) * evaluate(tree[2])
  when "/"
    evaluate(tree[1]) / evaluate(tree[2])
  when "%"
    evaluate(tree[1]) % evaluate(tree[2])
  when "**"
    evaluate(tree[1]) ** evaluate(tree[2])
  when "<"
    evaluate(tree[1]) < evaluate(tree[2])
  when "<="
    evaluate(tree[1]) <= evaluate(tree[2])
  when "=="
    evaluate(tree[1]) == evaluate(tree[2])
  when ">="
    evaluate(tree[1]) >= evaluate(tree[2])
  when ">"
    evaluate(tree[1]) > evaluate(tree[2])
  end
end

3. 最大の葉

def max(tree)
  if tree[0] == "lit"
    tree[1]
  else
    left  = max(tree[1])
    right = max(tree[1])
    if left < right
      right
    else
      left
    end
  end
end