簡単な仮想計算機を作ろう（実装編）：Javaでコンパイラの基礎を理解する（3）（1/3 ページ）

　スタックというデータ構造を利用すれば、少ない命令数でプログラムの基本要素となる算術式の計算を実現できます。そこで、本連載のコンパイラでターゲットマシンとする仮想計算機は仮想スタックマシンとして実装することにしてみました。今回はプログラミング言語Javaを使って、この仮想スタックマシンを実装します。また、Java APIで用意されているスタックについても解説します。

スタックとは何か？

　前回はコンピュータが計算しやすい算術式の表現方法として、後置記法を紹介しました。また、仮想スタックマシンSvm1の設計と、後置記法で表記された算術式からSvm1で計算可能なオブジェクトコードがいかに簡単に生成できるか、についても解説しました。

　今回は、実際にSvm1をプログラミング言語Javaで実装し、算術式から手動で生成したSvm1用オブジェクトコードを実行するまでを解説します。

　仮想スタックマシンを実装するに当たって、スタックというデータ構造について理解している必要がありますから、まずはこれについて、簡単なプログラムを交えながら解説することにします。なお、プログラムについてはJava SE 5以上を前提とします。

　スタックはデータ構造の1つで、LIFO（Last In First Out）という性質を持っています。これは、最後に入れたデータを最初に取り出すことができるという意味になります。

　ボール（値）を上からしか出し入れできない、不透明な長い箱をイメージするとよいでしょう。このような箱からボールを取り出すには、最後に入れたボール（値）からしか取り出せないということになります。

図1　スタックのイメージ

　値をスタックへ格納する操作はpushと呼ばれ、値をスタックから取り出す操作はpopと呼ばれます。この2つの基本操作でスタックへ格納するデータをコントロールできます。オレンジ矢印が値を積むpushの操作を表し、グレイ矢印が値を取り出すpopの操作を表しています。次に取り出せるデータを参照するためのpeekという操作が提供されることもあります。

　スタックにはどのような値がどういう順番で格納されているのかについては隠ぺいされていて、スタックを使用するプログラムからは見えないという点も重要です。

　このように、スタックでは単純な操作しかできないのですが、後置記法と組み合わせることにより結構複雑な計算を実現できます。基本動作を理解するために、スタックの使い方と簡単な実装方法について見てみましょう。

Java APIを使ってスタックを実装してみる

　JavaのAPIには、java.util.Stackというスタックを表現するクラスが標準で用意されています。これを使って、スタックの基本動作の確認をしてみましょう。次に示すような順番でスタックへ値を積んだり、スタックから値を取り出したりしてみます。

図2　スタックの動作例

　ここでは、図2のボール1をItem1、ボール2をItem2のように表すことにします。図2の動作例に従い、Item1、Item2、Item3の値を順にスタックへ積んだ（push）後、スタックから値を取り出します（pop）。このとき、一番上にある値はItem3なので、これが取り出されます。

　次に、Item4、Item5の値を順にスタックへ積んでから、3回連続でスタックから値を取り出します。このとき、スタックの上から順に値が取り出されるので、Item5、Item4、Item2の順に出てきます。このタイミングでは、スタックにはItem1しか残っていないということになります。

　最後に、ここへItem6を積んで、2回連続でスタックから値を取り出します。すると、Item6、Item1の順で値が取り出されます。

public class JavaStackTest {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<String>();
        stack.push("Item1");
        stack.push("Item2");
        stack.push("Item3");
        System.out.println(stack.pop()); // Item3
        stack.push("Item4");
        stack.push("Item5");
        System.out.println(stack.pop()); // Item5
        System.out.println(stack.pop()); // Item4
        System.out.println(stack.pop()); // Item2
        stack.push("Item6");
        System.out.println(stack.pop()); // Item6
        System.out.println(stack.pop()); // Item1
    }
}

> javac JavaStackTest.java
> java JavaStackTest
Item3
Item5
Item4
Item2
Item6
Item1

　どうでしょう、実行結果を見ても、最後に入れたデータを最初に取り出せるのが分かるはずです。

プリミティブ型の場合

　さて、ここでjava.util.Stackは基本的に参照型を対象としているため、プリミティブ型のデータを対象とする場合は独自にクラスを自作するか、データをラッパークラスのインスタンスに置き換えるかのどちらかになります。

　Java SE 5からのオートボクシング機能により、データをラッパークラスのインスタンスに置き換える方法は自動で使えるようになっています。

　そこで、ここではプリミティブ型の1つであるint型の値を対象とするスタックを表すIntStackクラスを自作して、スタックの実装方法について確認をしてみましょう。概念を理解することに重点を置くため、エラー処理については省略します。java.util.Stackなどがどのように実現されているか想像できるようになれば、ここでは十分です。

　IntStackクラスはint型の値を対象とするので、int型のデータを扱うように、popメソッド、pushメソッドを宣言します。内部では、int型配列のdataフィールドを使ってデータを保存し、どこまでスタックに値が積まれているかを表すためにスタックポインタをint型のspフィールドに用意します。

　本来であれば、spは配列の添字に指定できる値しか取らないようにチェックをするべきですが、ここでは省略しているので気を付けてください。重要なのは、スタックというデータ構造の概念自体は非常に単純で、操作もpushメソッドとpopメソッドさえあれば十分である、という点にあります。

public class IntStack {
    private int[] data = new int[256];
    private int sp = 0;
    public int pop() { return data[--sp]; }
    public void push(int value) { data[sp++] = value; }
}

　それでは、IntStackクラスを使って、JavaStackTestクラスと同様な処理を記述してみましょう。同じように動作することが確認できるはずです。ここでは、int型のデータを扱うので、数値をそのまま使用します。

public class IntStackTest {
    public static void main(String[] args) {
        IntStack stack = new IntStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop()); // 3
        stack.push(4);
        stack.push(5);
        System.out.println(stack.pop()); // 5
        System.out.println(stack.pop()); // 4
        System.out.println(stack.pop()); // 2
        stack.push(6);
        System.out.println(stack.pop()); // 6
        System.out.println(stack.pop()); // 1
    }
}

> javac IntStackTest.java
> java IntStackTest
3
5
4
2
6
1

　java.util.Stackクラスを使ったときと同様な結果となっていることが分かります。これで、スタックの動作は理解できたはずです。それでは次に、このスタックを使って仮想スタックマシンを実装してみましょう。