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

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
kpap0001 へ行く。
- 1 (2020-02-25 (火) 18:04:14)
- 2 (2020-02-25 (火) 19:49:08)
- 3 (2020-02-25 (火) 23:01:23)
- 4 (2020-02-26 (水) 14:52:20)
- 5 (2020-02-26 (水) 18:05:05)
- 6 (2020-02-26 (水) 20:44:19)
- 7 (2020-02-27 (木) 08:44:33)
- 8 (2020-04-21 (火) 15:12:38)

K-PAP #1

(by K, 2020.02.25)

↑

(0) はじめに

K-PAPはEssen開発プロジェクトとは無関係のプログラミング言語開発プロジェクトです。
Essenプロジェクトのwikiの中に寄生しているのは、単に新規wikiを立ち上げるほど盛り上がるかどうか自信が持てなかったためです。

↑

(1) PAP (Perfect Auto-Programming) について

Wikipediaには「無限の猿定理」という項目があり、そこには以下のような説明がある。
- これは、ランダムに文字列を作り続ければどんな文字列もいつかはできあがるという定理である。
- 比喩的に「猿がタイプライターの鍵盤をいつまでもランダムに叩きつづければ、ウィリアム・シェイクスピアの作品を打ち出す」などと表現されるため、この名がある。
これをプログラミングに適用すると、「ランダムにプログラムを作れば、いつかは目的のプログラムを得られる」と考えられる。
さらにこれを一歩推し進めて、所定の条件内（たとえば総バイト数が100KB以下であることなど）で全てのパターンを尽くして、その中で目的を達することができるプログラムのみを選別することにすれば、それだけでプログラミングが可能になるだろう。
これはもちろん大変な時間がかかるし、それゆえに現実的でも実用的でもない。
しかしこのやり方なら、人間は一切のアルゴリズムやプログラミングテクニックを習得する必要はなく、機械がありとあらゆるアルゴリズムやテクニックを発明してくれるようになる。
これはKの考える「夢」のプログラミングのうちの一つであり、これを以降PAPと称することにする。
- こんなのができたら、私のような普通のプログラマは失業しそうなので、夢は夢でも「悪夢」かもしれないが（苦笑）。

（手っ取り早く、どの程度のことができるのか知りたければ、下の「(5)実例」まで読み飛ばしてください。）

↑

(2) PAPの非現実性と可能性

PAPは基本的に全パターン探索を行う。つまり、たった4バイトの機械語プログラムの全探索であっても、それだけで42.9億パターンについて目的を満たしているかどうかをチェックしなければいけない。
これが8バイトになれば、1844京パターンになる。仮に並列演算などで頑張って1パターンあたり平均1ナノ秒でチェックできたとしても、すべてのチェックを終えるには58.4年を要することになる。
もちろん8バイト程度ではろくなプログラムは書けない。x86の機械語ならせいぜい2～3命令程度のことしかできないだろう。それでこんなレベルでは、100KBなど、試算する気にすらならない。・・・これがPAPの非現実性である。

しかしだからと言ってあきらめてしまうのは早計であるとKは考えた。もしかしたら有効な枝刈りアルゴリズムがあって、それを適用すれば数時間程度でもちょっとしたことはできるかもしれない。
もちろん大きな期待はできないが、しかしPAPに対して何をすればどこまでできるのかということを知っておくのは、それほど無益でもないはずだ。
- ちなみに、K自身も、2020年2月になるまでは、一考にすら値しないと思うほど、PAPについてはあきらめていた。それが、やっと、もしかしたらちょっとくらいはできるかもしれないと思うようになった次第である。

↑

(3) K-PAPにおける仮想マシン

ここから先、「K-PAP」という語が出てくるが、これはPAPによって自動プログラミングをするための言語で、今回開発するものの名称である。この言語は、どんな条件でどんな動作のプログラムを探したらいいのかを記述する。
K-PAPでは、x86の機械語を前提にするのではなく、以下のような簡易なレジスタマシンを前提にする。なお、これの設計に際してはOSECPU-VMの仕様をかなり参考にした。
- 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, INVALID }; // 要求している出力: フィボナッチ数列(例).
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, p[0], p[4], p[12], p[16]);
    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 && c != 0x17) return -2;	// (未定義参照).
        if (0x20 <= c && c <= 0x25 && v[j] == INVALID) return -2;	// (未定義参照).
        if (0x1a <= c && c <= 0x1b && sr <= 0) return -5; // (div0). 本来のdiv0対策なら負の場合を除外する必要はないが、gccでは除外しておかないとたまにハングアップになる.
        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; continue; }
        if (c == 0x21) { if (v[j] != sr) goto jmp; continue; }
        if (c == 0x22) { if (v[j] <  sr) goto jmp; continue; }
        if (c == 0x23) { if (v[j] >= sr) goto jmp; continue; }
        if (c == 0x24) { if (v[j] <= sr) goto jmp; continue; }
        if (c == 0x25) { if (v[j] >  sr) goto jmp; continue; }
        kerrorExit("test: internal error : c=0x%02x", c); // これはエラー終了させる自作ライブラリ関数.
    }
    return 0;	// (十分な出力をする前に終わってしまった).
}

今回は、dst[]の値が直接埋め込まれているが、これは本来はK-PAPで自由に設定できるものである。

↑

(4) K-PAPで扱える問題

x86でWindowsやLinuxの一般的なプログラムと比べると、K-PAPの仮想マシンはAPIが非常に貧弱で、ただ整数列を出力することしかできない。
このような仕様になっているのは、もちろん以降の実験・研究・考察を単純にするためである。もちろんより複雑なモデルを構築することもできるが、そうなると正常動作しているかの確認はより一層複雑になり、本質的ではない（と私が思う）ところで大いに苦労することになる。
また配列を利用する方法や入力値を受け付ける方法などについてもすでに十分なアイデアをもっているが、まずは現状の命令セットでどこまでできるかを確認してから拡張するほうが良いと思われる。やみくもに問題を複雑にしていくと、うまくいかなかったときの解析が困難になるだけである。

先に示したテスト実行プログラムでは、要求された出力数列の最後の数を出力するや否や、その時点でプログラムは「適合」と判定されるようになっている。つまりそこできちんと停止するかどうかを確認していない。
しかしこれはバグなどではなく、わざとそうしているのである。もし数列長に意味があり、既定の長さで止めたいのであれば、人間が出力数カウンタなどを追加して、きちんと止まるように改造すればいいだろう。
K-PAPでは、基本的に数列は無限長で、記述された部分はそのほんの一部であり、残りは省略されているという解釈をする。なぜそう考えるのかといえば、そう考えることで「この数列の次の数は何か？」という問題を解くことにも使えるようになるし、この前提によってプログラムは必ず無限ループを含まなければいけないことになり、その制約により探索範囲を狭めることができるからだ。

OUT命令は、上記のテスト実行プログラムでは、レジスタ番号だけではなく即値指定も可能なのだが、しかし仕様としてはこれを「許されない組み合わせ」であるとする。もちろん1命令で任意の定数を出力できるのは手軽で便利なのだが、それを許すなるとコード生成時にその組み合わせについても探索しなければならなくなる。適当なレジスタに定数を入れたのちにOUTすることでも結果的には同じことができるのだから、とりあえずはそれを強いることにしたい。

JMP先に指定するのはプログラムカウンタに対する相対値ではなく、ラベル番号の絶対値である。これはそのほうが全探索プログラムを作るのが容易になるからである。またラベル番号制をとったのは、コード上での分岐先を明示するためである。
たとえば、無条件JMPの直後は、LB命令が来なければいけない。もしそうでなければこの部分はデッドコードになって無駄になるからである。そしてコード生成器は、LB命令を配したからにはここに分岐するコードを必ず生成するようにしている。

↑

(5) 実例

ここで肝心のコード生成器や、枝刈りのテクニックについて説明をすべきなのかもしれないが、それをいったん保留にして、このアプローチでどの程度のことができたのかを紹介したい。
そろそろ有用性がどの程度あるのか確認できなければ、読むのが疲れるだろうと思うからである。

(5-1)フィボナッチ数列
```
1 1 2 3 5 8 13 21 34 55 89 144 ...
```
- という数列を作るためのプログラムをK-PAPで探索させた。
- これは数秒で答えを見つけてきた。
- 私は当初、レジスタを3つ使うアルゴリズムを考えていた。実際、そのようなコードが出力されていた（#0）。
```
#0: [LET v0, 0] [LET v1, 1] [LB 0] [OUT v1] [LET v2, v1] [ADD v1, v0] [LET v0, v2] [JMP 0]

// C言語で書くと・・・
int i = 0, j = 1, k;
for (;;) {
    printf("%d ", j);
    k = j;
    j += i;
    i = k;
}
```
- しかし、K-PAPはレジスタを2つしか使わないハイレベルなテクニックのコードも見つけてきた（#1）。
```
#1: [LET v0, 0] [LET v1, 1] [LB 0] [OUT v1] [ADD v0, v1] [OUT v0] [ADD v1, v0] [JMP 0]

// 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-PAPの使い方を教えるほうがはるかに簡単である。
とまあ、こんな説明をしてもほとんどわかってもらえないだろう。それはわかっている。

私が驚いたのは、私の想像していなかったコード（#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 v1, 1] [CMPJNE v0, v1, 1] [ADD v0, 1] [JMP 0]

// 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] [CMPJNE v0, v1, 0] [ADD v0, 1] [LET v1, 0] [JMP 0]

// 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 19 21 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] [ADD v0, 1] [JMP 0]

// 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, v0] [OUT v1] [JMP 0]

// C言語で書くと・・・
int i = -1, j = 0;
for (;;) {
    i += 2;
    j += i;
    printf("%d ", j);
}
```
- #4の結果は平凡なものだと思う。#5は自乗の数列の階差数列が奇数列になることを利用したもので、MUL命令を使わずに計算できている。
- こういう書き方も全く見逃さないのがPAPの威力だと思う。

↑

K-PAP #2 につづく

↑

こめんと欄

コメント	お名前	NameLink