分岐を実装する

アスキー 2016年11月23日(水)12時00分配信

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

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

現状の確認

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

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

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

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

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

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

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

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

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

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

r6

文を実装する

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

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

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

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

r6

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

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

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

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

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

部分木の評価はのようにすればいいので、次のように素直に書けます。

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

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

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

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

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

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

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

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

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

r6

文を実装する

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

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

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

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

r6

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

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

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

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

文は?

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

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

r6

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

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

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

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

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

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

r6

まとめ

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

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

練習問題

1. 帰ってきたFizzBuzz

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

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

2. の実装

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

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

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

違いは、最初に条件判定を行うかどうかです。 普通の文はまず最初に条件判定を行いますが、 文は最初の条件判定を行いません。 最初のをやに置き換えると違いがわかります。

をMinRubyに実装してみましょう。

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

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

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

3. 文の意味

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

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

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

第5回の練習問題の答え

1. おさらい

2. 足し算のカウント

3. デバッグのコツ

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

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

【あわせて読む】

    最終更新: 2016年11月23日(水)12時00分

    【関連ニュース】

    【コメント】

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

    【あなたにおススメ】