前回からはじめたバイトコード入門。なかなかバイトコードに入れなくても申し訳ないのですが、今回はスタックマシンについて紹介します。
- 準備編 (前回)
- スタックマシン (今回)
スタックマシン
スタックマシンというのは計算モデルの1つです。
スタックマシンと、よく引き合いに出される計算モデルにレジスタマシンがあります。
この2つの計算モデルはメモリーの使い方にあります。
- スタックマシン: メモリーをスタックとする計算モデル
- レジスタマシン: メモリーをレジスタとする計算モデル
純粋なスタックマシンはスタックだけで構成しますが、通常はランダムアクセスができるメモリーと組み合わせで使われることが多いです。これはレジスタマシンでも同様で、通常はレジスタ以外にメモリーを使用します。
スタックマシンにはJVMの他にも.NET Frameworkでも使用されています。
一方、既存のほとんどのCPUがレジスターマシンになります。
たとえば、レジスターマシンで加算を行う場合、aレジスタの値とbレジスタの値を加算して結果をaレジスタに格納するというような命令になります(add a, bのような感じです)。
命令の対象が明確に記述されているので、分かりやすいはずです(とはいうものの、機械語でプログラムを書けと言われてもイヤですけど😰)
では、スタックマシンはどのように動作するのでしょう？
ここでは、単純な例としてHPの電卓でスタックマシンの動作を説明していきます。
HPの電卓
HPというと、紆余曲折あってPCやプリンターのHP Inc.とサーバーのHPEになっていますが、かつては計測機器を扱う会社でした。そんなHPが1970年代から2000年代にかけて電卓を作っていたのでした。
当時は、関数電卓やプログラム電卓といったらHPという感じで、そこそこ使われていました。プログラム電卓というのは、その名の通りプログラムが組める電卓です。
このHPの電卓は、なんといっても入力方式が独特でした。
たとえば、1+2を計算する場合、通常の電卓であれば 1 + 2 = と入力しますね。これに対し、HPの電卓は 1 [Enter] 2 [Enter] + と入力しました([Enter]というボタンがあったのです)。
[Enter]を省略して記述すると 1 + 2 は 1 2 + になるということです。この数式の書き方は逆ポーランド記法と呼ばれています。
逆ポーランド記法
ちょっと脱線気味ですが、逆ポーランド記法についても説明しておきましょう。
「逆」とついていることから分かるかもしれませんが、「逆」ではないポーランド記法もあります。というか、こちらが先ですね。
ポーランド記法はJan Łukasiewicz (ヤン・ウカシェヴィチ)が発案した数式の記法です。
演算子を先に記述することから前置記法とも呼ばれます。
私たちが通常使用している 1 + 1 のような記法は演算子が数値の間に記述されるので中置記法と呼びます。逆ポーランド記法は演算子が最後なので、後置記法になります。
逆ポーランド記法の利点はカッコを使用せずに数式を記述できるところです。
たとえば、以下の数式はどうでしょう。
(2 + 3) × 5 + (4 - 2) ÷ 2
これを逆ポーランド記法で記述すると以下のようになります。
2 3 + 5 × 4 2 - 2 ÷ +
カッコがないというのは、電卓でメモリ機能(M+やM-、MRCなど)を使わなくても計算ができるということで、入力が簡単になります。まぁ、逆ポーランド記法で考えなければいけないというハードルはありますけど。
そして、もう1つの利点が、逆ポーランド記法はスタックを使えば簡単に実装できるということです。
スタックを使用した逆ポーランド記法の計算
では、逆ポーランド記法の数式をスタックを使用して計算してみましょう。
ルールは簡単です。
- 数値であれば(HPの電卓では、[Enter]が入力されたら)その値をスタックに積む
- 演算子であれば、演算に必要な個数のデータをスタックから取り出し、計算結果を再びスタックに積む
では、1 + 2をやってみましょう。
電卓であれば、スタックの先頭を表示していれば計算結果が表示されます。
複雑な数式でも計算の途中結果がスタックに保持されているので、スタックとは別のメモリーを使用しなくても計算が実行できます。
電卓では計算だけですが、一般のスタックマシンでも同様に必要なデータをスタックに置き、処理の結果を再びスタックに置くという過程で処理が進みます。
これはJVMでも同様です。
では、次回は実際にJVMでどのようにスタックマシンが構成されているのか紹介する予定です。
0 件のコメント:
コメントを投稿