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

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

(by K, 2025.08.15)

↑

(0) はじめに

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

↑

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

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

（編集中）

↑

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

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

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

#include <stdio.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) スタックマシン用のコンパイラ[32行]

#include <stdio.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命令があるので、その分だけ実行速度は落ちるかもしれません（実行しなければいけない命令数が増える）。
（まあそれはレジスタマシンがメモリ上にある変数をレジスタにロードするコストと同じなので、レジスタ変数を使わないなら実質的には同じことではあります。）

↑

(3) 逆ポーランド記法で書かれた式をレジスタマシン向けのアセンブラ記法に直すのは結構な手間がかかる

まず、逆ポーランド記法で書かれた式をスタックマシン向けのアセンブラに直すのは、言うまでもなく非常に簡単です。定数もしくは変数の前にPUSHをつけて、演算命令はそのままにすればいいからです。
ではレジスタマシン向けに変換するのはどのくらいの手間でしょうか？

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

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

int main(int argc, const char **argv)
{
    const char *s = argv[1]; if (s == NULL) return 1;
    char t = 't', a[4096], *p = &a[4096], c; a[0] = 0;
    while ((c = *s++) != '\0') {
        if (strchr("*/%+-", c) != 0) {
            sprintf(a + strlen(a), "%c %c,%c,%c\n", c, t, p[1], p[0]); *++p = t++;
        } else {
            *--p = c;
        }
    }
    printf("%sresult=%c\n", a, *p);
    return 0;
}

>cnv 123*+
* t,2,3
+ u,1,t
result=u

>cnv 12+3*
+ t,1,2
* u,t,3
result=u

>cnv XY+1-AB+*
+ t,X,Y
- u,t,1
+ v,A,B
* w,u,v
result=w

こんな感じでうまくいきました。
だからレジスタマシンでも問題なく実行できます。