Rubyで学ぶRuby 第4回

Rubyで電卓を作る

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

前回は、関数を使った木の扱い方について紹介しました。 今回の目標は、関数と木についてもう少し掘り下げつつ、「四則演算の木」を扱うプログラム、 すなわち電卓アプリをRubyで作ることです。

●Rubyのライブラリと、そのインストールについて

今回は本題に入る前に、ちょっとRubyのライブラリについて話をしましょう。

プログラミング言語では、全員が使うわけでもない機能は後付けで必要な人だけが 追加できるようになっていて、Rubyにもそのような仕組みがあります。 それがライブラリです。

この連載ではRubyを作りながらRubyを学んでいるわけですが、 今回の記事では、ちょっとゼロから作るのは面倒な機能を使いたいので、 その機能を筆者のほうでminrubyという名前のライブラリにしておきました。 そこで、minrubyライブラリをインストールする方法をまず説明しておきます。

インストールといっても、特に難しいことはありません。 コンソールでgem install minrubyというコマンドを実行するだけです。 gem というコマンドが、インターネット上の決まった場所で管理されているライブラリを 自動的にパソコン内の適切な場所にダウンロードしてくれて、 そのインストールまですべてやってくれます。

C:¥Ruby > gem install minruby ⏎
Fetching: minruby-1.0.gem (100%)
Successfully installed minruby-1.0
Parsing documentation for minruby-1.0
Installing ri documentation for minruby-1.0
Done installing documentation for minruby after 0 seconds
1 gem installed
C:¥Ruby > 

ただ、ネットワークへの接続に制限があったり、管理者権限を持っていなかったりで、 gemコマンドがうまく実行できないこともあるかもしれません。 そんな場合には、minruby.rb をダウンロードし、 プログラムと同じフォルダに置いておくだけでも大丈夫です （この方法はminrubyライブラリでは使えますが、 ライブラリによってはその他の設定が必要になる場合もあるので注意してください）。

これで必要なライブラリminrubyの準備は完了です。使い方はそのときがきたら説明します。

電卓はインタプリタ

さて、今回の目標はすでに言ったように「Rubyで電卓を作ること」ですが、 Rubyで計算をするという話だったら、連載の第1回からすでに何度もやっています。 Rubyだけで計算ができるのに、どうして電卓なんてものが必要になるんでしょうか？

そもそも、この連載の目標は、MinRubyというプログラミング言語のインタプリタを作ることだったはずです。 電卓を作ることが、プログラムを実行するインタプリタにどう関係するのでしょうか？

実を言うと、電卓には、プログラミング言語のインタプリタとよく似たところがあります。 電卓がすることを思い返してみてください。 電卓は、計算式を受け取って、それを解釈し、計算した結果を表示してくれます。 これはインタプリタの動作そのものです（忘れてしまった人は第1回の記事を読み直しましょう）。 つまり電卓は、「四則演算のインタプリタ」だといえるのです。

この先MinRubyインタプリタを作っていく上で、変数や分岐や関数などのさまざまな言語機能を実装していくことになります。 その言語機能の中には、四則演算も含まれます。 よって、遅かれ早かれ四則演算インタプリタを実装することは必要になります。 また、四則演算はこれから実装していく言語機能の中で一番簡単なものです。 なので、まずはここから始めましょう。

では、その「四則演算のインタプリタ」をどうやって作ればいいでしょうか。 ヒントは、前回の記事で最後に見た「計算の木」です。 電卓というインタプリタが受け取って解釈する「計算式」は、木と非常に相性がよかったのでした。

今回は、まず計算の木を使って計算式の答えを導く方法について考えてみましょう。

あらためて計算の木について考える

たとえば2 * 4を表す計算の木は次のようになります。

そして、2 * 4を部分式として持つ1 + 2 * 4は次のようになります。

2 * 4の計算式をそのまま部分木に持っているところがポイントです。 複雑な計算式でも、部分木の組み合わせで表現していくことができます。

この計算の木は次のルールで「実行」できます。 まず葉は、持っている値をそのまま実行結果とします。 それから節は、それぞれの部分木の実行結果を、演算子に従って計算したものが実行結果です。

1 + 2 * 4の計算の木を例に、実際に実行してみましょう。 葉は、そのまま1や2が実行結果になります。 それから(*)の節に注目します。左の部分木は葉で、その実行結果は2でした。 右の部分木も葉で、やはり実行結果は4でした。 この節はかけ算を表すので、2と4を掛けた8が、この(*)の節の実行結果となります。 最後に(+)の節に注目します。 左の部分木は葉で、その実行結果は1でした。 右の部分木は、先ほど8になりました。 この節は足し算を表すので、1と8を足した9が、実行結果となります。 振り返って、1 + 2 * 4を計算すると9なので、確かに計算結果になっているようです。

この処理は計算の木をたどっているだけなので、 前回の関数を使えばわりと簡単に書けそうですね（具体的には後述）。 文字列をそのまま実行しようとすると、こんなに簡単にはなりません。

よって一般的なインタプリタの実装では、 計算式の文字列をいったん計算の木に変換してから実行されます。 この変換のことを構文解析またはパースといい、 得られる木のことを構文木といいます。

抽象構文木

もう少し計算の木について考えてみます。 2 + 4という計算式は次の計算の木になります。

それから1 * (2 + 4)という式を考えます。

この木は1 + 2 * 4の木と構造は同じで、(+)と(*)が入れ替わっただけです。 実行して、結果が6になることを確認してください。

さて、1 + 2 * 4と1 * (2 + 4)は木の構造は同じですが、 文字列として表現したときは（演算子の入れ替わり以外に）括弧の有無という違いがあります。 もちろん、括弧をなくした1 * 2 + 4では意味が変わってしまいますね。 このように、文字列の表現では曖昧性をなくすための余分な記号（ここでは括弧）が必要ですが、 木で表現した場合はこのような記号が不要になります。

さらに、プログラム文字列の中には、読みやすさなどのために空白や改行を入れたり、 コメントを入れたりします。これらもプログラムの実行には関係のないものです。

このように、文字列の中には実行に必要のない情報が含まれているので、 構文解析の段階でこれらの情報を除去して、実行の処理が簡潔になるようにします。 このように、なにかを行う上で不要な情報を除去することを「抽象化」といい、 抽象化が施された構文木のことを抽象構文木といいます。

インタプリタの動作の流れ

「計算の木」について思い出し、その「実行」という概念を手に入れたところで、 もっとも基本的なインタプリタである「四則演算のインタプリタ」、すなわち電卓を書いていきましょう。 このインタプリタは、「計算式」というプログラムを受け取り、その計算結果を出力します。

こんな風に動くものを作っていきます。

C:¥Ruby > ruby interp.rb ⏎
1 + 1                              <= 入力
2                                  <= 出力
C:¥Ruby > ruby interp.rb ⏎
(1 + 2) / 3 * 4 * (56 / 7 + 8 + 9) <= 入力
100                                <= 出力

プログラムを実行するインタプリタの基本的な動作の流れは、 「プログラムを読み込む」「読み込んだプログラムを実行する」というものです。

今回の四則演算インタプリタに当てはめると、 「計算式を入力する」「入力した計算式を計算する」という流れになります。 ただ、計算式にはpのような出力命令が含まれないので、 そのままでは計算した結果がわかりません。 そこで最後に「計算結果を出力する」という処理も行うことにします。

読み込むプログラムは、通常はテキストファイル、すなわちただの文字列です。 四則演算インタプリタにとってのプログラム（計算式）も "1 + 2 * (3 + 4)"のような文字列です。 文字列のまま実行することも原理的には可能ですが、 インタプリタの実装が極めて煩雑になるので、 通常は「読み込んだプログラムを実行しやすい形式に変換する」「実行する」 という段階を踏みます。 この「実行しやすい形式」として、前回出てきた「木」がよく使われます。

まとめると、今回書くインタプリタの構成は次のようになります。

# ① 計算式の文字列を読み込む
str = gets
2notsugi
# ② 計算式の文字列を構文解析して計算の木にする
tree = ...
# ③ 計算の木を実行（計算）する
answer = ...
# ④ 計算結果を出力する
p(answer)

①と④はもう完成しているので、②と③の穴を埋めていきましょう。

計算式の文字列を計算の木に変換する

まずは②の構文解析、つまり計算式の文字列を計算の木に変換する部分を作る必要があります。

とはいえ構文解析は、それだけで専門書が一冊書けるくらいに広範な分野である一方で、 実を言うとインタプリタの実装においてそこまで重要な話ではありません （もちろん実用的なインタプリタを作るときは重要な話がいっぱいあります）。

そこでこの連載では、構文解析そのものについては深入りしないことにします。 冒頭で著者が用意したminrubyライブラリをインストールしましたが、 これには構文解析の機能も入っているので、それを使っていきます。

minrubyライブラリをgem install minrubyとしてインストールした場合は、 次のプログラムを実行してみてください。

require "minruby"
tree = minruby_parse("1 + 2 * 4")
p(tree)
  #=> ["+", ["lit", 1], ["*", ["lit", 2], ["lit", 4]]]

もしminruby.rbを手動でダウンロードした場合は、 最初のrequire "minruby"をrequire "./minruby"に置き換えてください。

minruby_parse(文字列)とすることで、計算式の文字列が計算の木（を表す配列）に変換されます。 上の例では"1 + 2 * 4"という計算式を変換しています。 いままでの木とちょっと違うのは、葉が単に値を配列に入れたものではなく、 "lit"という文字列と値のペアになっているところです。

このようになっているのは、次回以降で四則演算インタプリタをMinRubyインタプリタへと拡張していくときに必要になるためです。

上の木は、実質的には次の木と同じです。

この木から、「lit」のところを枝の一部とみなして無視すれば、いままでの木と同じです。

というわけで、minruby_parse(文字列)の結果に含まれている"lit"については、いまのところは気にしないでください。

もっと大きな計算式の変換もやってみましょう。

p(minruby_parse("(1 + 2) / 3 * 4 * (56 / 7 + 8 + 9)"))
  #=> ["*", ["*", ["/", ["+", ["lit", 1], ["lit", 2]], ["lit", 3]], ["lit", 4]], ["+", ["+", ["/", ["lit", 56], ["lit", 7]], ["lit", 8]], ["lit", 9]]]

長すぎて見づらいですね。 pの代わりにppという出力命令を使うことで、 改行を入れて多少見やすく表示してくれます。

pp(minruby_parse("(1 + 2) / 3 * 4 * (56 / 7 + 8 + 9)"))
  #=> ["*",
  #=>   ["*", ["/", ["+", ["lit", 1], ["lit", 2]], ["lit", 3]], ["lit", 4]],
  #=>   ["+", ["+", ["/", ["lit", 56], ["lit", 7]], ["lit", 8]], ["lit", 9]]]

絵にすればこうなります。

"lit"を取り除いてしまえばこうです。

枝が多いだけで、おなじみの計算の木になってますね！

ppという命令はRubyに組み込みのものではなく、 著者のライブラリが用意しているものです。 より正確には、Rubyに標準で用意されているppというライブラリを、 著者のライブラリの中で読み込んでいます。

関数の引数と返り値

ところで、p(...)という出力命令やminruby_parse(...)という構文解析命令と、 前回出てきた関数のpreorder(...)は、いずれも形としては非常によく似ています。 つまり、pやminruby_parse、あるいはpreorderといった「名前」と、何かしらの値を受け取るための「丸かっこ」、という形です。

名前()

もうお気づきの方もいるかもしれませんが、実はpやminruby_parseは 特別な命令ではなく、preorderと同じように関数として定義されているものです。 pはRubyが内部的に定義している関数です。 minruby_parseは著者のライブラリで定義されている関数です。

というわけで、前回は関数のことを「木をたどるための強力な道具」だと言いましたが、 実は関数は木のためだけのものではありません。 pやminruby_parseのように、処理や命令に名前をつけて使い回すためにも使われます。

関数は、0個以上の値を受け取り、定義された手順に従った動作をして、一般には1つの値を返します。 関数が受け取る値のことを引数といい、返す値のことを返り値といいます。

次のような簡単な関数を例に、引数と返り値について見てみましょう。

def add(x, y)
  p "Addition!"
  x + y # 最後の行の値が返される
end

関数addは引数としてxとyを受け取り、 "Addition!"と出力したあと、最後のx + yの値を計算して返します。

関数addは次のように使います。

answer = add(40, 2) #=> "Addition!"
p(answer)           #=> 42

この例では、40および2という2つの引数に対してaddを適用しています。

関数適用のことを「関数を呼ぶ」と表現することもありますが、その表現を使って言えば、 「add(40, 2)と呼び出した場合、xは40、yは2なので、add(40, 2)は42を返す」というわけです。

関数として見ると、minruby_parseは引数として1つの文字列を受け取り、 返り値として配列の値を1つ返します。 pは、引数として1つの値を受け取り、返り値として引数をそのまま返す関数です。

では、関数の引数と返り値について分かったところで、いよいよ計算の木を実行する関数を書いていきましょう。

足し算の木を扱う

先に示したインタプリタの流れの現状を確認しましょう。

require "minruby"
# ① 計算式の文字列を読み込む
str = gets
# ② 計算式の文字列を計算の木に変換する
tree = minruby_parse(str)
# ③ 計算の木を実行（計算）する
answer = ...
# ④ 計算結果を出力する
p(answer)

②の変換は、ライブラリを使ったのでminruby_parse(str)でおしまいです。

それでは本題の③を説明していきます。

まずは話を簡単にするため、足し算だけの木を考えます。 たとえば(1 + 2) + (3 + 4)を考えます。

この木をたどって、葉の値の合計を求める関数sumを書いていきましょう。 木をたどる関数は、木の中のすべての部分木について、 同じプログラムの断片を実行するのでした。 sumでは、どのようなプログラム断片を書けばいいかを考えていきます。

一度に考えるとややこしいので、葉1つだけからなる部分木の場合と、 節の場合に分けて考えてみます。

葉1つからなる部分木に対して関数sumが返すべき値は、 その葉に入っている値そのものです。 なぜなら、この部分木には値が1つしかなく、合計はその値そのものだからです。 葉1つからなる部分木が変数treeに入っていると仮定します。 前述のように、葉は["lit", 値]で表されます。 よって、このときはtree[1]を返せばよいとわかります。 このときの関数sumの定義は次のようになります。

def sum(tree)
  tree[1]
end

それから、節からなる部分木の場合を考えます。 いまは足し算しか考えていないので、この節は["+", 左の部分木, 右の部分木]という 配列になっています。 この部分木に対して関数sumが返すべきなのは、 「左の部分木に含まれる葉の値の合計値」と「右の部分木の合計値」です。 これを計算するには、いままさに定義中の関数sumを使うことができます。

def sum(tree)
  left  = sum(tree[1])
  right = sum(tree[2])
  left + right
end

さて、ここまで葉の場合と節の場合で分けて考えていましたが、 これらを合体させます。難しいことはありません。 配列の0番目の値が"lit"か"+"かで、単純に分岐できます。

def sum(tree)
  if tree[0] == "lit"
    tree[1]
  else
    # ここでは tree[0] == "+"
    left  = sum(tree[1])
    right = sum(tree[2])
    left + right
  end
end

これでできあがりです。この関数を使ってみましょう。

tree = minruby_parse("(1 + 2) + (3 + 4)")
answer = sum(tree)
p(answer) #=> 10

めでたく動きました。

一気に説明したので、きつねにつままれたような気分になった場合は、 関数の先頭でp(tree)とすることで実際の部分木を見ながら動きを確認していくとわかりやすいと思います。

関数の返り値は関数の最後の式ですが、最後にif文がある場合は、 それぞれの分岐の最後にある値が返されます。 sumの場合、葉の場合にはtree[1]が、節の場合にはleft + rightの計算結果が返り値です。

四則演算に対応

今度は足し算以外の演算に対応しましょう。 想像するよりもずっと簡単です。単純に分岐を増やせば終わりです。 たとえば、かけ算に対応します。

def evaluate(tree)
  if tree[0] == "lit"
    tree[1]
  else
    if tree[0] == "+"
      left  = evaluate(tree[1])
      right = evaluate(tree[2])
      left + right
    else
      # ここでは tree[0] == "*"
      left  = evaluate(tree[1])
      right = evaluate(tree[2])
      left * right
    end
  end
end

もはや足し算だけではなくなったので、関数の名前をsumからevaluateに変えました。 evaluateは「評価」という意味で、「実行」と同じような意味の英単語です。

同様に引き算と割り算もサポートできます。 ただし、この方法では分岐が複雑になって見通しが悪いので、 このようなときのためにRubyにはcase文という分岐が用意されています。 これを使うと、次のように簡潔に書けます。

def evaluate(tree)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    left  = evaluate(tree[1])
    right = evaluate(tree[2])
    left + right
  when "-"
    left  = evaluate(tree[1])
    right = evaluate(tree[2])
    left - right
  when "*"
    left  = evaluate(tree[1])
    right = evaluate(tree[2])
    left * right
  else
    # ここでは tree[0] == "/"
    left  = evaluate(tree[1])
    right = evaluate(tree[2])
    left / right
  end
end

caseの直後に書かれた式を評価して、その値がwhenの後に書かれたどれかの値と一致したら そのwhenの後の命令が実行されます。 どのwhenの値とも一致しなかったら、elseの後の命令が実行されます。 if文と同様、case文もそれぞれの最後の式が返り値になります。

これでついに四則演算インタプリタの実行部分が書けました。 インタプリタ全体のプログラムは次のようになります。

require "minruby"
def evaluate(tree)
  # (略)
end
# ① 計算式の文字列を読み込む
str = gets
# ② 計算式の文字列を計算の木に変換する
tree = minruby_parse(str)
# ③ 計算の木を実行（計算）する
answer = evaluate(tree)
# ④ 計算結果を出力する
p(answer)

次のように動作させてみてください。

C:¥Ruby > ruby interp.rb ⏎
1 + 1                              <= 入力
2                                  <= 出力
C:¥Ruby > ruby interp.rb ⏎
(1 + 2) / 3 * 4 * (56 / 7 + 8 + 9) <= 入力
100                                <= 出力

まとめ

四則演算インタプリタを書きました。 かなり駆け足で説明したので、おそらく消化不良になっている人も多いと思います。 作成したプログラムに出力命令を追加して実行したり、 練習問題を解いたりして、理解を深めてください。

次回からは、このインタプリタを拡張して、MinRubyインタプリタに仕立てていきます。 第5回は、手始めに「変数」をサポートする予定です。

練習問題

1. 演算の追加

あなたのインタプリタを拡張して、剰余や累乗をサポートしてください。

Rubyでは剰余は%、累乗は**で表します。

p(8 % 3)  #=> 2
p(2 ** 4) #=> 16

ヒント：構文解析はすでに剰余や累乗に対応しています。

minruby_parse("8 % 3")
  #=> ["%", ["lit", 8], ["lit", 3]]

あとは、関数evaluateの中にwhenを追加するだけです。

2. 比較式の追加

あなたのインタプリタを拡張して、比較式をサポートしてください。

比較式とは、1 == 1や1 > 1といった、数同士が等しいか大小関係にあるかを判定する式のことです。 この式を計算すると、trueまたはfalseというオブジェクトが返ります。

p(1 + 1 == 2) #=> true
p(1 + 1 == 3) #=> false
p(1 + 1 <  2) #=> false
p(1 + 1 <  3) #=> true

つまり、あなたのインタプリタを以下のように実行したとき、trueが表示されるようにevaluateを拡張できれば正解です。

require "minruby"
def evaluate(tree)
  # (略)
end
tree = minruby_parse("2 * 3 > 2 + 3")
result = evaluate(tree)
p(result) #=> true

なお、true + 1やtrue > falseのように意味のない式が与えられたときは、どのような挙動になってもかまいません。

ヒント：ややこしいですが、やることは練習問題1とまったく同じです。

3. 最大の葉

木を受け取って、一番大きい値の葉を返す関数maxを書いてみてください。次のように動けば正解です。

p(max(minruby_parse("1 + 2 * 3"))) #=> 3
p(max(minruby_parse("1 + 4 + 3"))) #=> 4

演算子の種類は無視してかまいません。

ヒント1：evaluate関数を作ったときの考え方を思い出してください。 すなわち、葉1つだけからなる部分木の場合と、節の場合に分けて考えます。

ヒント2：葉1つだけの場合は、その値をそのまま返します。節の場合は、この部分木に対して関数maxが返すべきなのは、「左の部分木に含まれる葉の最大値」と、「右の部分木の最大値」の大きいほうの値ですね。

第3回の練習問題の答え

1. さまざまな木

node1 =
  ["節1",
    ["節2",
      ["葉A"],
      ["節3",
        ["葉B"],
        ["葉C"]
      ]
    ],
    ["葉D"]
  ]

2. 葉だけ列挙する

def preorder(tree)
  if tree[1] == nil
    p(tree[0])
  else
    preorder(tree[1])
    preorder(tree[2])
  end
end

3. 帰りがけ順

def preorder(tree)
  if tree[0].start_with?("節")
    preorder(tree[1])
    preorder(tree[2])
  end
  p(tree[0])
end