p20250815a
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* スタックマシンに関する幻想について
-(by [[K]], 2025.08.15)
** (0) はじめに
-なんかよくわからないけど、スタックマシンはレジスタマシン...
-しかしいろいろ実験してきた私としては「ん？それは本当か？...
-私が思うに、どこかの偉い人がもっともらしく説明したせいで...
-だからそれらに疑問を提示して、私なりの実験をして、その結...
-[目次]
--(1) スタックマシンでバイトコードを設計すれば、プログラ...
--(2) スタックマシンを想定してアセンブラを出力するなら、...
--(3) 逆ポーランド記法で書かれた式をレジスタマシン向けの...
--(4) 余興：ポーランド記法をレジスタマシン向けのアセンブ...
--(5) 余興：uckはどうやってバイトコードを短くしたか？
--(6) もっと細かい余談を、Q&A形式で
----
-[Q:0-1] すみません、そもそもスタックマシンってなんですか？
--[A:0-1] 普通の機械語では、どのレジスタとどのレジスタを...
--しかしスタックマシンでは演算命令に演算対象を書きません...
--スタックマシンのこの挙動は、逆ポーランド記法と相性が良...
--しかしスタックマシンはアウトオブオーダ実行などに難があ...
--逆ポーランド記法との相性の良さから、スタックマシンはレ...
~
** (1) スタックマシンでバイトコードを設計すれば、プログラ...
-私はJavaのバイトコードの説明の時に、初めてこの話を聞きま...
-Rubyの実行エンジンである RubyVMでもスタックマシンを採用...
-ではJavaのバイトコードは結果としてコンパクトになっている...
-まずは「 i = i + 3; 」で考えたいと思います。レジスタマシ...
-レジスタマシンの場合、「ADD」「i」「3」で3語でした。スタ...
-スタックマシンが不利になりやすい最大の要因はレジスタ変数...
-次に「 y = a * x + b; 」で考えてみます。
-レジスタマシン：「 MUL3 tmp,a,x; ADD3 y,tmp,b; 」→ 8語
-スタックマシン：「 PUSH a; PUSH x; MUL; PUSH b; ADD; POP...
-このように式が長くなってくると、レジスタマシンでは一時変...
-次は「 y = a * x * x + b * x + c; 」でやってみます。
-レジスタマシン：「 MUL3 tmp,a,x; MUL tmp,x; MUL3 tmp2,b,...
-スタックマシン：「 PUSH a; PUSH x; MUL; PUSH x; MUL; PUS...
-だいぶ差が縮まってきました。
-まあここまでの考察で、「長い式がたくさん想定されるならス...
~
** (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 %...
} else if (pri >= 5 && (op == '+' || op == '-')) {
q = compile(4); sprintf(a + strlen(a), "%c %...
} 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...
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に入っています、という意味です。...
>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-1')とし...
#include <stdio.h>
#include <string.h>
const char *s;
char a[4096], t;
void resetTmp() { t = 't'; }
char newTmp() { return t++; }
char compile(int pri)
{
char r, q, n, op;
if (*s == '(') {
s++; r = compile(99); s++; // ')'を読み飛ばす.
} else {
r = *s++; // 数値もしくは変数.
}
for (;;) {
op = *s++;
if (pri >= 4 && (op == '*' || op == '/' || op ==...
q = compile(3); n = newTmp(); sprintf(a + st...
} else if (pri >= 5 && (op == '+' || op == '-')) {
q = compile(4); n = newTmp(); sprintf(a + st...
} else
break;
}
s--; return r;
}
int main(int argc, const char **argv)
{
s = argv[1]; if (s == NULL) return 1;
resetTmp(); char r = compile(99); printf("%sresult=%...
return 0;
}
-こうすれはたぶん読みやすくなります。
----
-(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", o...
} else if (pri >= 5 && (op == '+' || op == '-')) {
compile(4); sprintf(a + strlen(a), "%c\n", o...
} 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命令があるので、そ...
-（まあそれはレジスタマシンがメモリ上にある変数をレジスタ...
- MUL(t, 2, 3); や ADD(u, 1, t); をどうやってx86のアセン...
~
** (3) 逆ポーランド記法で書かれた式をレジスタマシン向けの...
-まず、逆ポーランド記法で書かれた式をスタックマシン向けの...
-ではレジスタマシン向けに変換するのはどのくらいの手間でし...
-(3-1) ''レジスタマシン用の逆ポーランド記法コンパイラ''[1...
#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...
} 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
-こんな感じでうまくいきました。だからたいして大変ではない...
-「私の自作言語では数式を逆ポーランド記法で書くので、コン...
-私はそれが配慮すべきほどの問題とは思えません。
~
** (4) 余興：ポーランド記法をレジスタマシン向けのアセンブ...
-(4-1)''ポーランド記法→レジスタマシン''（p2r）[21行]
#include <stdio.h>
#include <string.h>
const char *s;
char a[4096], t;
char val()
{
char op = *s++, x, y;
if (strchr("*/%+-", op) != 0) {
x = val(); y = val(); sprintf(a + strlen(a), "%c...
}
return op; // 数値もしくは変数.
}
int main(int argc, const char **argv)
{
s = argv[1]; if (s == NULL) return 1;
t = 't'; char r = val(); printf("%sresult=%c\n", a, ...
return 0;
}
>p2r *-+XY1+AB
+ t,X,Y
- u,t,1
+ v,A,B
* w,u,v
result=w
----
-(4-2)''ポーランド記法→スタックマシン''（p2s）[21行]
#include <stdio.h>
#include <string.h>
const char *s;
char a[4096];
void val()
{
char op = *s++;
if (strchr("*/%+-", op) != 0) {
val(); val(); sprintf(a + strlen(a), "%c\n", op);
} else {
sprintf(a + strlen(a), "push %c\n", op); // 数...
}
}
int main(int argc, const char **argv)
{
s = argv[1]; if (s == NULL) return 1;
val(); printf("%s", a); return 0;
}
>p2s *-+XY1+AB
push X
push Y
+
push 1
-
push A
push B
+
*
~
** (5) 余興：uckはどうやってバイトコードを短くしたか？
-uckの前身であるOSECPU-VMの高密度バイトコードでは、(1)の...
-uckではスタックマシンの利点も捨てがたいと思い始めたので...
-uckを説明するにはhh4がーみたいな話をしなければいけなくな...
--uckでは4bit命令として0x0～0x6が使えます。このうちの0x0...
--uckでは8bit命令として0x80～0xbfが使えます。このうちの0x...
--uckでは12bit命令として0xc00～0xdffが使えます。このうち...
--（以下略）
-これらのPUSH命令には引数はなく、どんな値をPUSHするかは命...
-このように命令番号の「半分以上」を引数なしPUSH命令に割り...
--もっというと、負の数のPUSHって滅多に使わないので、その...
--そのせいでたとえば8bit形式では-9をPUSHできないわけです...
--このようにより長い命令長を選んでいけばどんな数値もPUSH...
-PUSH命令のコストが無視できるようになれば、スタックマシン...
-[Q] ということは、uckはスタックマシンなの？
--[A] いやあ、そう言うときっと本当のスタックマシンに怒ら...
--ポーランド記法になっているのは、どんな演算子が先行して...
~
** (6) もっと細かい余談を、Q&A形式で
-[Q:6-1] なんか全体的に、コードが短すぎる気がするが？(2)...
--[A:6-1] いやでも、ちゃんと動いていますし・・・。構造は...
-[Q:6-2] 単純にprintfせずに、aに対してsprintfで追記してい...
--[A:6-2] aに追記しているのは、外部に出力する前に、最適化...
--毎回strlenするのは明らかに無駄ですが、まあ今回は小規模...
-[Q:6-3] (2-1)で出てきた疑似コードから、実際のx86のアセン...
--[A:6-3] いろいろな方法が考えられますが、できるだけ簡単...
>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に入っています、という意味です。...
;; MUL(t, 2, 3);
MOV EAX,2
IMUL EAX,3
MOV [ESP+x],EAX ; xは変数tに対応するメモリオフセット.
;; ADD(u, 1, t);
MOV EAX,1
ADD EAX,[ESP+x] ; xは変数tに対応するメモリオフセット.
MOV [ESP+y],EAX ; yは変数uに対応するメモリオフセット.
--このような方法だとレジスタをEAXしか使わないことになりま...
--こういう出力をするコンパイラの実装は簡単ですが、他のレ...
--[追記] buntan-pcプロジェクトのuchanさんは、スタックマシ...
//-（編集中）
// スタックマシンをバイトコードに採用すれば、プログラムが...
// スタックマシン・モデルを採用すれば、コンパイラが書きや...
// スタックマシンなCPUでも性能高く作れる。
終了行:
* スタックマシンに関する幻想について
-(by [[K]], 2025.08.15)
** (0) はじめに
-なんかよくわからないけど、スタックマシンはレジスタマシン...
-しかしいろいろ実験してきた私としては「ん？それは本当か？...
-私が思うに、どこかの偉い人がもっともらしく説明したせいで...
-だからそれらに疑問を提示して、私なりの実験をして、その結...
-[目次]
--(1) スタックマシンでバイトコードを設計すれば、プログラ...
--(2) スタックマシンを想定してアセンブラを出力するなら、...
--(3) 逆ポーランド記法で書かれた式をレジスタマシン向けの...
--(4) 余興：ポーランド記法をレジスタマシン向けのアセンブ...
--(5) 余興：uckはどうやってバイトコードを短くしたか？
--(6) もっと細かい余談を、Q&A形式で
----
-[Q:0-1] すみません、そもそもスタックマシンってなんですか？
--[A:0-1] 普通の機械語では、どのレジスタとどのレジスタを...
--しかしスタックマシンでは演算命令に演算対象を書きません...
--スタックマシンのこの挙動は、逆ポーランド記法と相性が良...
--しかしスタックマシンはアウトオブオーダ実行などに難があ...
--逆ポーランド記法との相性の良さから、スタックマシンはレ...
~
** (1) スタックマシンでバイトコードを設計すれば、プログラ...
-私はJavaのバイトコードの説明の時に、初めてこの話を聞きま...
-Rubyの実行エンジンである RubyVMでもスタックマシンを採用...
-ではJavaのバイトコードは結果としてコンパクトになっている...
-まずは「 i = i + 3; 」で考えたいと思います。レジスタマシ...
-レジスタマシンの場合、「ADD」「i」「3」で3語でした。スタ...
-スタックマシンが不利になりやすい最大の要因はレジスタ変数...
-次に「 y = a * x + b; 」で考えてみます。
-レジスタマシン：「 MUL3 tmp,a,x; ADD3 y,tmp,b; 」→ 8語
-スタックマシン：「 PUSH a; PUSH x; MUL; PUSH b; ADD; POP...
-このように式が長くなってくると、レジスタマシンでは一時変...
-次は「 y = a * x * x + b * x + c; 」でやってみます。
-レジスタマシン：「 MUL3 tmp,a,x; MUL tmp,x; MUL3 tmp2,b,...
-スタックマシン：「 PUSH a; PUSH x; MUL; PUSH x; MUL; PUS...
-だいぶ差が縮まってきました。
-まあここまでの考察で、「長い式がたくさん想定されるならス...
~
** (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 %...
} else if (pri >= 5 && (op == '+' || op == '-')) {
q = compile(4); sprintf(a + strlen(a), "%c %...
} 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...
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に入っています、という意味です。...
>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-1')とし...
#include <stdio.h>
#include <string.h>
const char *s;
char a[4096], t;
void resetTmp() { t = 't'; }
char newTmp() { return t++; }
char compile(int pri)
{
char r, q, n, op;
if (*s == '(') {
s++; r = compile(99); s++; // ')'を読み飛ばす.
} else {
r = *s++; // 数値もしくは変数.
}
for (;;) {
op = *s++;
if (pri >= 4 && (op == '*' || op == '/' || op ==...
q = compile(3); n = newTmp(); sprintf(a + st...
} else if (pri >= 5 && (op == '+' || op == '-')) {
q = compile(4); n = newTmp(); sprintf(a + st...
} else
break;
}
s--; return r;
}
int main(int argc, const char **argv)
{
s = argv[1]; if (s == NULL) return 1;
resetTmp(); char r = compile(99); printf("%sresult=%...
return 0;
}
-こうすれはたぶん読みやすくなります。
----
-(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", o...
} else if (pri >= 5 && (op == '+' || op == '-')) {
compile(4); sprintf(a + strlen(a), "%c\n", o...
} 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命令があるので、そ...
-（まあそれはレジスタマシンがメモリ上にある変数をレジスタ...
- MUL(t, 2, 3); や ADD(u, 1, t); をどうやってx86のアセン...
~
** (3) 逆ポーランド記法で書かれた式をレジスタマシン向けの...
-まず、逆ポーランド記法で書かれた式をスタックマシン向けの...
-ではレジスタマシン向けに変換するのはどのくらいの手間でし...
-(3-1) ''レジスタマシン用の逆ポーランド記法コンパイラ''[1...
#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...
} 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
-こんな感じでうまくいきました。だからたいして大変ではない...
-「私の自作言語では数式を逆ポーランド記法で書くので、コン...
-私はそれが配慮すべきほどの問題とは思えません。
~
** (4) 余興：ポーランド記法をレジスタマシン向けのアセンブ...
-(4-1)''ポーランド記法→レジスタマシン''（p2r）[21行]
#include <stdio.h>
#include <string.h>
const char *s;
char a[4096], t;
char val()
{
char op = *s++, x, y;
if (strchr("*/%+-", op) != 0) {
x = val(); y = val(); sprintf(a + strlen(a), "%c...
}
return op; // 数値もしくは変数.
}
int main(int argc, const char **argv)
{
s = argv[1]; if (s == NULL) return 1;
t = 't'; char r = val(); printf("%sresult=%c\n", a, ...
return 0;
}
>p2r *-+XY1+AB
+ t,X,Y
- u,t,1
+ v,A,B
* w,u,v
result=w
----
-(4-2)''ポーランド記法→スタックマシン''（p2s）[21行]
#include <stdio.h>
#include <string.h>
const char *s;
char a[4096];
void val()
{
char op = *s++;
if (strchr("*/%+-", op) != 0) {
val(); val(); sprintf(a + strlen(a), "%c\n", op);
} else {
sprintf(a + strlen(a), "push %c\n", op); // 数...
}
}
int main(int argc, const char **argv)
{
s = argv[1]; if (s == NULL) return 1;
val(); printf("%s", a); return 0;
}
>p2s *-+XY1+AB
push X
push Y
+
push 1
-
push A
push B
+
*
~
** (5) 余興：uckはどうやってバイトコードを短くしたか？
-uckの前身であるOSECPU-VMの高密度バイトコードでは、(1)の...
-uckではスタックマシンの利点も捨てがたいと思い始めたので...
-uckを説明するにはhh4がーみたいな話をしなければいけなくな...
--uckでは4bit命令として0x0～0x6が使えます。このうちの0x0...
--uckでは8bit命令として0x80～0xbfが使えます。このうちの0x...
--uckでは12bit命令として0xc00～0xdffが使えます。このうち...
--（以下略）
-これらのPUSH命令には引数はなく、どんな値をPUSHするかは命...
-このように命令番号の「半分以上」を引数なしPUSH命令に割り...
--もっというと、負の数のPUSHって滅多に使わないので、その...
--そのせいでたとえば8bit形式では-9をPUSHできないわけです...
--このようにより長い命令長を選んでいけばどんな数値もPUSH...
-PUSH命令のコストが無視できるようになれば、スタックマシン...
-[Q] ということは、uckはスタックマシンなの？
--[A] いやあ、そう言うときっと本当のスタックマシンに怒ら...
--ポーランド記法になっているのは、どんな演算子が先行して...
~
** (6) もっと細かい余談を、Q&A形式で
-[Q:6-1] なんか全体的に、コードが短すぎる気がするが？(2)...
--[A:6-1] いやでも、ちゃんと動いていますし・・・。構造は...
-[Q:6-2] 単純にprintfせずに、aに対してsprintfで追記してい...
--[A:6-2] aに追記しているのは、外部に出力する前に、最適化...
--毎回strlenするのは明らかに無駄ですが、まあ今回は小規模...
-[Q:6-3] (2-1)で出てきた疑似コードから、実際のx86のアセン...
--[A:6-3] いろいろな方法が考えられますが、できるだけ簡単...
>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に入っています、という意味です。...
;; MUL(t, 2, 3);
MOV EAX,2
IMUL EAX,3
MOV [ESP+x],EAX ; xは変数tに対応するメモリオフセット.
;; ADD(u, 1, t);
MOV EAX,1
ADD EAX,[ESP+x] ; xは変数tに対応するメモリオフセット.
MOV [ESP+y],EAX ; yは変数uに対応するメモリオフセット.
--このような方法だとレジスタをEAXしか使わないことになりま...
--こういう出力をするコンパイラの実装は簡単ですが、他のレ...
--[追記] buntan-pcプロジェクトのuchanさんは、スタックマシ...
//-（編集中）
// スタックマシンをバイトコードに採用すれば、プログラムが...
// スタックマシン・モデルを採用すれば、コンパイラが書きや...
// スタックマシンなCPUでも性能高く作れる。
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
