kpap0001
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* K-PAP #1
-(by [[K]], 2020.02.25)
** (0) はじめに
-K-PAPはEssen開発プロジェクトとは無関係のプログラミング言...
-Essenプロジェクトのwikiの中に寄生しているのは、単に新規w...
** (1) PAP (Perfect Auto-Programming) について
-Wikipediaには「無限の猿定理」という項目があり、そこには...
--これは、ランダムに文字列を作り続ければどんな文字列もい...
--比喩的に「猿がタイプライターの鍵盤をいつまでもランダム...
-これをプログラミングに適用すると、「ランダムにプログラム...
-さらにこれを一歩推し進めて、所定の条件内（たとえば総バイ...
-これはもちろん大変な時間がかかるし、それゆえに現実的でも...
-しかしこのやり方なら、人間は一切のアルゴリズムやプログラ...
-これは[[K]]の考える「夢」のプログラミングのうちの一つで...
--こんなのができたら、私のような普通のプログラマは失業し...
-（手っ取り早く、どの程度のことができるのか知りたければ、...
** (2) PAPの非現実性と可能性
-PAPは基本的に全パターン探索を行う。つまり、たった4バイト...
-これが8バイトになれば、1844京パターンになる。仮に並列演...
-もちろん8バイト程度ではろくなプログラムは書けない。x86の...
-しかしだからと言ってあきらめてしまうのは早計であると[[K]...
-もちろん大きな期待はできないが、しかしPAPに対して何をす...
--ちなみに、[[K]]自身も、2020年2月になるまでは、一考にす...
** (3) K-PAPにおける仮想マシン
-ここから先、「K-PAP」という語が出てくるが、これはPAPによ...
-K-PAPでは、x86の機械語を前提にするのではなく、以下のよう...
--OSECPU-VMについては、 http://osecpu.osask.jp/wiki/ に詳...
-命令は全て固定長であり、1命令は32bit*4=128bitとなってい...
|命令番号|p0|p1|p2|機能|
|00||||プログラムの終端・終了|
|01||||ジャンプ先ラベル定義|
|02|||lb|無条件ジャンプ(lbはラベル番号)|
|05||r1||値を出力(r1)|
|10|r0|r1/imm||OR_ r0,r1/imm|
|11|r0|r1/imm||XOR r0,r1/imm|
|12|r0|r1/imm||AND r0,r1/imm|
|14|r0|r1/imm||ADD r0,r1/imm|
|15|r0|r1/imm||SUB r0.r1/imm|
|16|r0|r1/imm||MUL r0,r1/imm|
|17|r0|r1/imm||LET r0,r1/imm|
|18|r0|r1/imm||SHL r0,r1/imm|
|19|r0|r1/imm||SAR r0,r1/imm|
|1a|r0|r1/imm||DIV r0,r1/imm|
|1b|r0|r1/imm||MOD r0,r1/imm|
|20|r0|r1/imm|lb|CMPJE_ r0,r1/imm,lb|
|21|r0|r1/imm|lb|CMPJNE r0,r1/imm,lb|
|22|r0|r1/imm|lb|CMPJL_ r0,r1/imm,lb|
|23|r0|r1/imm|lb|CMPJGE r0,r1/imm,lb|
|24|r0|r1/imm|lb|CMPJLE r0,r1/imm,lb|
|25|r0|r1/imm|lb|CMPJG_ r0,r1/imm,lb|
-まだ配列にアクセスする機能を持っていないし、整数演算しか...
-以下にこの仮想マシンをテスト実行するためのシンプルなプロ...
#define INVALID ((int) 0x800055aa)
#define REG 0x80005a00
int dst[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
long long tc = 0LL;
int test(int *p, int t1)
{
int v[64], i, c, sr;
if ((tc & 0xffffff) == 0) // 中間報告用の簡易表示.
printf(" %d (%02x %02x %02x %02x) \r", (int) ...
tc++; // テストした回数.
for (i = 0; i < 64; i++)
v[i] = INVALID;
int lb[100], lbn = 0, l, dp = 0;
for (i = 0; p[i] != 0; ) {
if (p[i] == 0x01) { lb[lbn++] = i; } // LB
i += 4;
}
for (i = 0; p[i] != 0; ) {
t1--; if (t1 <= 0) return -3; // (timeout)
c = p[i];
sr = p[i + 2];
i += 4;
if ((sr & ~0x3f) == REG)
sr = v[sr & 0x3f];
if (sr == INVALID) return -2; // (未定義参照).
if (c == 0x01) { continue; } // LB
if (c == 0x02) { // JMP
jmp: l = p[i + (-4 + 3)];
if (l >= lbn) return -1; // (未完成プログラ...
i = lb[l];
continue;
}
if (c == 0x05) { // OUT
if (dst[dp] != sr) return -4; // (正しくない...
if (dst[++dp] == INVALID) return t1; // 残り...
continue;
}
int j = p[i + (-4 + 1)];
if (0x10 <= c && c <= 0x1b && v[j] == INVALID &&...
if (0x20 <= c && c <= 0x25 && v[j] == INVALID) r...
if (0x1a <= c && c <= 0x1b && sr <= 0) return -5...
if (c == 0x10) { v[j] |= sr; continue; } // OR
if (c == 0x11) { v[j] ^= sr; continue; } // XOR
if (c == 0x12) { v[j] &= sr; continue; } // AND
if (c == 0x14) { v[j] += sr; continue; } // ADD
if (c == 0x15) { v[j] -= sr; continue; } // SUB
if (c == 0x16) { v[j] *= sr; continue; } // MUL
if (c == 0x17) { v[j] = sr; continue; } // LET
if (c == 0x18) { v[j] <<= sr; continue; } // SHL
if (c == 0x19) { v[j] >>= sr; continue; } // SAR
if (c == 0x1a) { v[j] /= sr; continue; } // DIV
if (c == 0x1b) { v[j] %= sr; continue; } // MOD
if (c == 0x20) { if (v[j] == sr) goto jmp; conti...
if (c == 0x21) { if (v[j] != sr) goto jmp; conti...
if (c == 0x22) { if (v[j] < sr) goto jmp; conti...
if (c == 0x23) { if (v[j] >= sr) goto jmp; conti...
if (c == 0x24) { if (v[j] <= sr) goto jmp; conti...
if (c == 0x25) { if (v[j] > sr) goto jmp; conti...
kerrorExit("test: internal error : c=0x%02x", c)...
}
return 0; // (十分な出力をする前に終わってしまった).
}
-今回は、dst[]の値が直接埋め込まれているが、これは本来はK...
** (4) K-PAPで扱える問題
-x86でWindowsやLinuxの一般的なプログラムと比べると、K-PAP...
-このような仕様になっているのは、もちろん以降の実験・研究...
-また配列を利用する方法や入力値を受け付ける方法などについ...
-先に示したテスト実行プログラムでは、要求された出力数列の...
-しかしこれはバグなどではなく、わざとそうしているのである...
-K-PAPでは、基本的に数列は無限長で、記述された部分はその...
-OUT命令は、上記のテスト実行プログラムでは、レジスタ番号...
-JMP先に指定するのはプログラムカウンタに対する相対値では...
-たとえば、無条件JMPの直後は、LB命令が来なければいけない...
** (5) 実例
-ここで肝心のコード生成器や、枝刈りのテクニックについて説...
-そろそろ有用性がどの程度あるのか確認できなければ、読むの...
-''(5-1)フィボナッチ数列''
1 1 2 3 5 8 13 21 34 55 89 144 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--これは数秒で答えを見つけてきた。
--私は当初、レジスタを3つ使うアルゴリズムを考えていた。実...
#0: [LET v0, 0] [LET v1, 1] [LB 0] [OUT v1] [LET v2, v1]...
// C言語で書くと・・・
int i = 0, j = 1, k;
for (;;) {
printf("%d ", j);
k = j;
j += i;
i = k;
}
--しかし、K-PAPはレジスタを2つしか使わないハイレベルなテ...
#1: [LET v0, 0] [LET v1, 1] [LB 0] [OUT v1] [ADD v0, v1]...
// C言語で書くと・・・
int i = 0, j = 1;
for (;;) {
printf("%d ", j);
i += j;
printf("%d ", i);
j += i;
}
--これがわかるだろうか。1回のループにつき2つの数値を出力...
--私は正直なところ、フィボナッチ数列のプログラムなんかが...
--しかし私自身はただ希望する出力結果を書いておくだけで、...
--私は、プログラミングがあまり得意ではない人に、フィボナ...
--配列 a[i] を用意して、 a[i+2]=a[i]+a[i+1]; をfor文で回...
--しかしそんな人でも、K-PAPを使えば、配列を使わずに計算で...
--教えるほうとしても、ややこしいロジックを教えるよりはK-P...
--とまあ、こんな説明をしてもほとんどわかってもらえないだ...
--私が驚いたのは、私の想像していなかったコード（#1）がい...
-''(5-2)二重ループが必要になる数列''
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--これも数秒で答えを見つけてきた。
#2: [LET v0, 1] [LB 0] [LET v1, 0] [LB 1] [OUT v0] [ADD ...
// C言語で書くと・・・
int i = 1, j;
for (;;) {
j = 0;
do {
printf("%d ", i);
j++;
} while (i != j);
i++;
}
--以下も一応違うがほとんど同じである。
#3: [LET v0, 1] [LET v1, 0] [LB 0] [OUT v0] [ADD v1, 1] ...
// C言語で書くと・・・
int i = 1, j = 0;
for (;;) {
do {
printf("%d ", i);
j++;
} while (i != j);
i++;
j = 0;
}
--どちらもちゃんとできている。
-''(5-3)素数の数列''
2 3 5 7 11 13 17 19 23 29 31 37 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--これはやっぱりだめだった。1時間程度回してみたが歯が立た...
-''(5-4)自乗の数列''
1 4 9 16 25 36 49 64 81 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--1秒程度で結果が出てきた。
#4: [LET v0, 1] [LB 0] [LET v1, v0] [MUL v1, v0] [OUT v1...
// C言語で書くと・・・
int i = 1, j;
for (;;) {
j = i;
j *= i;
printf("%d ", j);
i++;
}
--さらにこんなものも。
#5: [LET v0, -1] [LET v1, 0] [LB 0] [ADD v0, 2] [ADD v1,...
// C言語で書くと・・・
int i = -1, j = 0;
for (;;) {
i += 2;
j += i;
printf("%d ", j);
}
--#4の結果は平凡なものだと思う。#5は自乗の数列の階差数列...
--こういう書き方も全く見逃さないのがPAPの威力だと思う。
** K-PAP #2 につづく
* こめんと欄
-(5-3)の素数の数列で17が抜けていて半素数の21が入っていま...
-ごしてきありがとうございます！ -- [[K]] SIZE(10){2020-04...
#comment
終了行:
* K-PAP #1
-(by [[K]], 2020.02.25)
** (0) はじめに
-K-PAPはEssen開発プロジェクトとは無関係のプログラミング言...
-Essenプロジェクトのwikiの中に寄生しているのは、単に新規w...
** (1) PAP (Perfect Auto-Programming) について
-Wikipediaには「無限の猿定理」という項目があり、そこには...
--これは、ランダムに文字列を作り続ければどんな文字列もい...
--比喩的に「猿がタイプライターの鍵盤をいつまでもランダム...
-これをプログラミングに適用すると、「ランダムにプログラム...
-さらにこれを一歩推し進めて、所定の条件内（たとえば総バイ...
-これはもちろん大変な時間がかかるし、それゆえに現実的でも...
-しかしこのやり方なら、人間は一切のアルゴリズムやプログラ...
-これは[[K]]の考える「夢」のプログラミングのうちの一つで...
--こんなのができたら、私のような普通のプログラマは失業し...
-（手っ取り早く、どの程度のことができるのか知りたければ、...
** (2) PAPの非現実性と可能性
-PAPは基本的に全パターン探索を行う。つまり、たった4バイト...
-これが8バイトになれば、1844京パターンになる。仮に並列演...
-もちろん8バイト程度ではろくなプログラムは書けない。x86の...
-しかしだからと言ってあきらめてしまうのは早計であると[[K]...
-もちろん大きな期待はできないが、しかしPAPに対して何をす...
--ちなみに、[[K]]自身も、2020年2月になるまでは、一考にす...
** (3) K-PAPにおける仮想マシン
-ここから先、「K-PAP」という語が出てくるが、これはPAPによ...
-K-PAPでは、x86の機械語を前提にするのではなく、以下のよう...
--OSECPU-VMについては、 http://osecpu.osask.jp/wiki/ に詳...
-命令は全て固定長であり、1命令は32bit*4=128bitとなってい...
|命令番号|p0|p1|p2|機能|
|00||||プログラムの終端・終了|
|01||||ジャンプ先ラベル定義|
|02|||lb|無条件ジャンプ(lbはラベル番号)|
|05||r1||値を出力(r1)|
|10|r0|r1/imm||OR_ r0,r1/imm|
|11|r0|r1/imm||XOR r0,r1/imm|
|12|r0|r1/imm||AND r0,r1/imm|
|14|r0|r1/imm||ADD r0,r1/imm|
|15|r0|r1/imm||SUB r0.r1/imm|
|16|r0|r1/imm||MUL r0,r1/imm|
|17|r0|r1/imm||LET r0,r1/imm|
|18|r0|r1/imm||SHL r0,r1/imm|
|19|r0|r1/imm||SAR r0,r1/imm|
|1a|r0|r1/imm||DIV r0,r1/imm|
|1b|r0|r1/imm||MOD r0,r1/imm|
|20|r0|r1/imm|lb|CMPJE_ r0,r1/imm,lb|
|21|r0|r1/imm|lb|CMPJNE r0,r1/imm,lb|
|22|r0|r1/imm|lb|CMPJL_ r0,r1/imm,lb|
|23|r0|r1/imm|lb|CMPJGE r0,r1/imm,lb|
|24|r0|r1/imm|lb|CMPJLE r0,r1/imm,lb|
|25|r0|r1/imm|lb|CMPJG_ r0,r1/imm,lb|
-まだ配列にアクセスする機能を持っていないし、整数演算しか...
-以下にこの仮想マシンをテスト実行するためのシンプルなプロ...
#define INVALID ((int) 0x800055aa)
#define REG 0x80005a00
int dst[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
long long tc = 0LL;
int test(int *p, int t1)
{
int v[64], i, c, sr;
if ((tc & 0xffffff) == 0) // 中間報告用の簡易表示.
printf(" %d (%02x %02x %02x %02x) \r", (int) ...
tc++; // テストした回数.
for (i = 0; i < 64; i++)
v[i] = INVALID;
int lb[100], lbn = 0, l, dp = 0;
for (i = 0; p[i] != 0; ) {
if (p[i] == 0x01) { lb[lbn++] = i; } // LB
i += 4;
}
for (i = 0; p[i] != 0; ) {
t1--; if (t1 <= 0) return -3; // (timeout)
c = p[i];
sr = p[i + 2];
i += 4;
if ((sr & ~0x3f) == REG)
sr = v[sr & 0x3f];
if (sr == INVALID) return -2; // (未定義参照).
if (c == 0x01) { continue; } // LB
if (c == 0x02) { // JMP
jmp: l = p[i + (-4 + 3)];
if (l >= lbn) return -1; // (未完成プログラ...
i = lb[l];
continue;
}
if (c == 0x05) { // OUT
if (dst[dp] != sr) return -4; // (正しくない...
if (dst[++dp] == INVALID) return t1; // 残り...
continue;
}
int j = p[i + (-4 + 1)];
if (0x10 <= c && c <= 0x1b && v[j] == INVALID &&...
if (0x20 <= c && c <= 0x25 && v[j] == INVALID) r...
if (0x1a <= c && c <= 0x1b && sr <= 0) return -5...
if (c == 0x10) { v[j] |= sr; continue; } // OR
if (c == 0x11) { v[j] ^= sr; continue; } // XOR
if (c == 0x12) { v[j] &= sr; continue; } // AND
if (c == 0x14) { v[j] += sr; continue; } // ADD
if (c == 0x15) { v[j] -= sr; continue; } // SUB
if (c == 0x16) { v[j] *= sr; continue; } // MUL
if (c == 0x17) { v[j] = sr; continue; } // LET
if (c == 0x18) { v[j] <<= sr; continue; } // SHL
if (c == 0x19) { v[j] >>= sr; continue; } // SAR
if (c == 0x1a) { v[j] /= sr; continue; } // DIV
if (c == 0x1b) { v[j] %= sr; continue; } // MOD
if (c == 0x20) { if (v[j] == sr) goto jmp; conti...
if (c == 0x21) { if (v[j] != sr) goto jmp; conti...
if (c == 0x22) { if (v[j] < sr) goto jmp; conti...
if (c == 0x23) { if (v[j] >= sr) goto jmp; conti...
if (c == 0x24) { if (v[j] <= sr) goto jmp; conti...
if (c == 0x25) { if (v[j] > sr) goto jmp; conti...
kerrorExit("test: internal error : c=0x%02x", c)...
}
return 0; // (十分な出力をする前に終わってしまった).
}
-今回は、dst[]の値が直接埋め込まれているが、これは本来はK...
** (4) K-PAPで扱える問題
-x86でWindowsやLinuxの一般的なプログラムと比べると、K-PAP...
-このような仕様になっているのは、もちろん以降の実験・研究...
-また配列を利用する方法や入力値を受け付ける方法などについ...
-先に示したテスト実行プログラムでは、要求された出力数列の...
-しかしこれはバグなどではなく、わざとそうしているのである...
-K-PAPでは、基本的に数列は無限長で、記述された部分はその...
-OUT命令は、上記のテスト実行プログラムでは、レジスタ番号...
-JMP先に指定するのはプログラムカウンタに対する相対値では...
-たとえば、無条件JMPの直後は、LB命令が来なければいけない...
** (5) 実例
-ここで肝心のコード生成器や、枝刈りのテクニックについて説...
-そろそろ有用性がどの程度あるのか確認できなければ、読むの...
-''(5-1)フィボナッチ数列''
1 1 2 3 5 8 13 21 34 55 89 144 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--これは数秒で答えを見つけてきた。
--私は当初、レジスタを3つ使うアルゴリズムを考えていた。実...
#0: [LET v0, 0] [LET v1, 1] [LB 0] [OUT v1] [LET v2, v1]...
// C言語で書くと・・・
int i = 0, j = 1, k;
for (;;) {
printf("%d ", j);
k = j;
j += i;
i = k;
}
--しかし、K-PAPはレジスタを2つしか使わないハイレベルなテ...
#1: [LET v0, 0] [LET v1, 1] [LB 0] [OUT v1] [ADD v0, v1]...
// C言語で書くと・・・
int i = 0, j = 1;
for (;;) {
printf("%d ", j);
i += j;
printf("%d ", i);
j += i;
}
--これがわかるだろうか。1回のループにつき2つの数値を出力...
--私は正直なところ、フィボナッチ数列のプログラムなんかが...
--しかし私自身はただ希望する出力結果を書いておくだけで、...
--私は、プログラミングがあまり得意ではない人に、フィボナ...
--配列 a[i] を用意して、 a[i+2]=a[i]+a[i+1]; をfor文で回...
--しかしそんな人でも、K-PAPを使えば、配列を使わずに計算で...
--教えるほうとしても、ややこしいロジックを教えるよりはK-P...
--とまあ、こんな説明をしてもほとんどわかってもらえないだ...
--私が驚いたのは、私の想像していなかったコード（#1）がい...
-''(5-2)二重ループが必要になる数列''
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--これも数秒で答えを見つけてきた。
#2: [LET v0, 1] [LB 0] [LET v1, 0] [LB 1] [OUT v0] [ADD ...
// C言語で書くと・・・
int i = 1, j;
for (;;) {
j = 0;
do {
printf("%d ", i);
j++;
} while (i != j);
i++;
}
--以下も一応違うがほとんど同じである。
#3: [LET v0, 1] [LET v1, 0] [LB 0] [OUT v0] [ADD v1, 1] ...
// C言語で書くと・・・
int i = 1, j = 0;
for (;;) {
do {
printf("%d ", i);
j++;
} while (i != j);
i++;
j = 0;
}
--どちらもちゃんとできている。
-''(5-3)素数の数列''
2 3 5 7 11 13 17 19 23 29 31 37 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--これはやっぱりだめだった。1時間程度回してみたが歯が立た...
-''(5-4)自乗の数列''
1 4 9 16 25 36 49 64 81 ...
--という数列を作るためのプログラムをK-PAPで探索させた。
--1秒程度で結果が出てきた。
#4: [LET v0, 1] [LB 0] [LET v1, v0] [MUL v1, v0] [OUT v1...
// C言語で書くと・・・
int i = 1, j;
for (;;) {
j = i;
j *= i;
printf("%d ", j);
i++;
}
--さらにこんなものも。
#5: [LET v0, -1] [LET v1, 0] [LB 0] [ADD v0, 2] [ADD v1,...
// C言語で書くと・・・
int i = -1, j = 0;
for (;;) {
i += 2;
j += i;
printf("%d ", j);
}
--#4の結果は平凡なものだと思う。#5は自乗の数列の階差数列...
--こういう書き方も全く見逃さないのがPAPの威力だと思う。
** K-PAP #2 につづく
* こめんと欄
-(5-3)の素数の数列で17が抜けていて半素数の21が入っていま...
-ごしてきありがとうございます！ -- [[K]] SIZE(10){2020-04...
#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
