p20250815a のバックアップ(No.2)

スタックマシンに関する幻想について

(by K, 2025.08.15)

↑

(0) はじめに

なんかよくわからないけど、スタックマシンはレジスタマシンよりも〇〇に優れているみたいな話を時々聞きます。
しかしいろいろ実験してきた私としては「ん？それは本当か？？」と思うのです。
私が思うに、どこかの偉い人がもっともらしく説明したせいで、その後だれも疑わず検証もせず、妄信している内容がいくつかある気がしてなりません。
だからそれらに疑問を提示して、私なりの実験をして、その結果を示したいと思います。

↑

(1) スタックマシンをバイトコードに採用すれば、プログラムのバイト数が減る

私はJavaのバイトコードの説明の時に、初めてその話を聞きました。
Rubyの実行エンジンである RubyVMでもスタックマシンを採用していて、その理由はこれだと聞いた記憶があります。

（編集中）

↑

(2) スタックマシンを想定してアセンブラを出力するなら、コンパイラが書きやすい

論より証拠だと思うので書き比べてみます。
- ルール：変数は1文字。定数も1桁。演算子は()*/%+-のみ。スペースを入れてはいけない。式としておかしいものも入力しない想定。
  - レジスタマシンかスタックマシンかの違いを見るだけならこの仕様でまったく問題ない。

(2-1) レジスタマシン用のコンパイラ[33行]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char *s;
char a[4096], t;

char compile(int pri)
{
    char r, q, op;
    if (*s == '(') {
        s++; r = compile(99); s++; // ')'を読み飛ばす.
    } else {
        r = *s++; // 数値もしくは変数.
    }
    for (;;) {
        op = *s++;
        if (pri >= 4 && (op == '*' || op == '/' || op == '%')) {
            q = compile(3); sprintf(a + strlen(a), "%c %c,%c,%c\n", op, t, r, q); r = t++;
        } else if (pri >= 5 && (op == '+' || op == '-')) {
            q = compile(4); sprintf(a + strlen(a), "%c %c,%c,%c\n", op, t, r, q); r = t++;
        } else
            break;
    }
    s--; return r;
}

int main(int argc, const char **argv)
{
    s = argv[1]; if (s == NULL) return 1;
    t = 't'; char r = compile(99); printf("%sresult=%c\n", a, r);
    return 0;
}

このプログラムをコンパイルして、reg.exeを作ったとします。

>reg 1+2*3
* t,2,3    → MUL(t, 2, 3); // t=2*3;
+ u,1,t    → ADD(u, 1, t); // u=1+t;
result=u   → 計算結果はuに入っています、という意味です。 tとかuは一時変数です。

>reg (1+2)*3
+ t,1,2
* u,t,3
result=u

>reg (X+Y-1)*(A+B)
+ t,X,Y
- u,t,1
+ v,A,B
* w,u,v
result=w

(2-2) スタックマシン用のコンパイラ[33行]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char *s;
char a[4096];

void compile(int pri)
{
    char op;
    if (*s == '(') {
        s++; compile(99); s++; // ')'を読み飛ばす.
    } else {
        sprintf(a + strlen(a), "push %c\n", *s++); // 数値もしくは変数.
    }
    for (;;) {
        op = *s++;
        if (pri >= 4 && (op == '*' || op == '/' || op == '%')) {
            compile(3); sprintf(a + strlen(a), "%c\n", op);
        } else if (pri >= 5 && (op == '+' || op == '-')) {
            compile(4); sprintf(a + strlen(a), "%c\n", op);
	 } else
            break;
    }
    s--;
}

int main(int argc, const char **argv)
{
    s = argv[1]; if (s == NULL) return 1;
    compile(99); printf("%s", a);
    return 0;
}

このプログラムをコンパイルして、stk.exeを作ったとします。

>stk 1+2*3
push 1
push 2
push 3
*
+
 
>stk (1+2)*3
push 1
push 2
+
push 3
*

>stk (X+Y-1)*(A+B)
push X
push Y
+
push 1
-
push A
push B
+
*

見ての通り、どちらも問題なくコンパイルできています。コンパイラの行数は同じでした。
確かに、レジスタマシンの方が少し記述量が多そうな感じです。でも、その程度の差ですよ？
このわずかな差が問題になるでしょうか？

スタックマシンの場合、PUSH命令が必要になるので、その分だけ実行速度は落ちるかもしれません
（まあそれはレジスタマシンでもメモリ上にある変数をレジスタにロードするコストと同じなので、レジスタ変数を使わないなら同じことではあります）。

（編集中）