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

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

(by K, 2025.08.15)

↑

(0) はじめに

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

[目次]
- (1) スタックマシンでバイトコードを設計すれば、プログラムのバイト数が減る
- (2) スタックマシンを想定してアセンブラを出力するなら、コンパイラが書きやすくなる
- (3) 逆ポーランド記法で書かれた式をレジスタマシン向けのアセンブラ記法に直すのは結構な手間がかかる
- (4) 余興：ポーランド記法をレジスタマシン向けのアセンブラ記法やスタックマシンの向けのアセンブラ記法に直す

↑

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

私はJavaのバイトコードの説明の時に、初めてこの話を聞きました。
Rubyの実行エンジンである RubyVMでもスタックマシンを採用していて、その理由はこれだと聞いた記憶があります。
ではJavaのバイトコードは結果としてコンパクトになっているのかと言えば、全然そんなことはないです。でもそれはこのスタックマシン性に由来しているというよりは、他の理由の方が主のような気はしますが。

まずは「 i = i + 3; 」で考えたいと思います。レジスタマシンで、かつiがレジスタ変数なのであれば、「 ADD i,3; 」だけで済みます。これに対して、スタックマシンであれば、「 PUSH i; PUSH 3; ADD; POP i; 」が必要になります。
レジスタマシンの場合、「ADD」「i」「3」で3語でした。スタックマシンの場合、7語になっています。仮に「1語は少なくとも1バイトを要する」と考えるなら、この例ではスタックマシンはかなり不利です。
スタックマシンが不利になりやすい最大の要因はレジスタ変数を全く持てないところだと思います。とにかくpushしなければ演算対象にできないわけです。

次に「 y = a * x + b; 」で考えてみます。
レジスタマシン：「 MUL3 tmp,a,x; ADD3 y,tmp,b; 」→ 8語
スタックマシン：「 PUSH a; PUSH x; MUL; PUSH b; ADD; POP y; 」 → 10語
このように式が長くなってくると、レジスタマシンでは一時変数を明示して書かなければいけない分だけ少しずつ不利になってきます。スタックマシンは一時変数を書く必要がありません。一時変数の名前をどうするか（or一時変数としてどのレジスタを使うか）なんて、全く本質的ではないどうでもいいことです。それを明示的に書かされる分だけレジスタマシンは不利です。

次は「 y = a * x * x + b * x + c; 」でやってみます。
レジスタマシン：「 MUL3 tmp,a,x; MUL tmp,x; MUL3 tmp2,b,x; ADD tmp,tmp2; ADD3 y,tmp,c; 」→ 18語
スタックマシン：「 PUSH a; PUSH x; MUL; PUSH x; MUL; PUSH b; PUSH x; MUL; ADD; PUSH c; ADD; POP y; 」 → 19語
だいぶ差が縮まってきました。

（編集中）

↑

(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

こんな感じでうまくいきました。
だからたいして大変ではないのです。

↑

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

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

(0) はじめに

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

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

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

(4) 余興：ポーランド記法をレジスタマシン向けのアセンブラ記法やスタックマシンの向けのアセンブラ記法に直す