Rubyで電卓を作る

アスキー 10月26日(水)09時00分配信

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

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

4

電卓はインタプリタ

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

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

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

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

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

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

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

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

Ruby木

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

Ruby木

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

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

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

4

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

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

抽象構文木

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

Ruby木

それからという式を考えます。

Ruby木

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ruby木

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

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

Ruby木

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

Ruby木

というわけで、の結果に含まれているについては、いまのところは気にしないでください。

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

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

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

Ruby木

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

Ruby木

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

関数の引数と返り値

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

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

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

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

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

関数は引数としてとを受け取り、 と出力したあと、最後のの値を計算して返します。

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

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

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

4

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

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

足し算の木を扱う

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

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

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

まずは話を簡単にするため、足し算だけの木を考えます。 たとえばを考えます。

Ruby木

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

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

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

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

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

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

めでたく動きました。

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

四則演算に対応

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

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

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

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

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

まとめ

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

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

練習問題

1. 演算の追加

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

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

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

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

2. 比較式の追加

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

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

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

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

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

3. 最大の葉

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

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

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

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

第3回の練習問題の答え

1. さまざまな木

2. 葉だけ列挙する

3. 帰りがけ順

アスキー
もっと見る もっと見る

【あわせて読む】

    最終更新: 10月26日(水)09時00分

    【関連ニュース】

    【コメント】

    • ※コメントは個人の見解であり、記事提供社と関係はありません。

    【あなたにおススメ】