hs2bfでBrainfuckの近くを考えているとちょっとした考えが浮かんだので書いてみます。
ここではBrainfuckを言語として見るのではなく、BFネイティブな機械を考えてみます。
次のような例を考えてみましょう: d(ptr)にvalをコピーする
少なくともvalは
コピーしなければいけないので、どこかに一時変数用の領域を挿入する必要があります。
しかし、ptrの分だけ移動したり、そこまでvalを運んだりするのはどのようにすればいいでしょうか?
一見すると出来ないような気がしますが、実は簡単です。
解決法は
使うメモリの容量を3倍にするです。
例えばval=3,ptr=2だとこのようになります:
val ptr 0 1 2
valをcopy:
ptrをcopy:
ptrを減らしつつvalとptrを右に移動:
3 |
0 |
0 |
2 |
0 |
0 |
d0 |
3 |
2 |
d1 |
|
|
d2 |
|
|
3 |
0 |
0 |
2 |
0 |
0 |
d0 |
0 |
0 |
d1 |
3 |
2 |
d2 |
|
|
3 |
0 |
0 |
2 |
0 |
0 |
d0 |
0 |
0 |
d1 |
3 |
1 |
d2 |
|
|
3 |
0 |
0 |
2 |
0 |
0 |
d0 |
0 |
0 |
d1 |
0 |
0 |
d2 |
3 |
1 |
3 |
0 |
0 |
2 |
0 |
0 |
d0 |
0 |
0 |
d1 |
0 |
0 |
d2 |
3 |
0 |
移動:
3 |
0 |
0 |
2 |
0 |
0 |
d0 |
0 |
0 |
d1 |
0 |
0 |
3 |
0 |
0 |
|
(変化分は
赤にしてあります)
これなら簡単そうです。ポイントは
といったところでしょうか。
つまり内部的に使うメモリ容量を定数倍して、適当な置換を考えれば
レジスタを追加した命令セットが実装できます。さらに足し算や掛け算も定数倍
*1の時間で実装できます。
このような処理を行っても先に述べた
BFらしさ、つまりテープ2本の
チューリングマシン風の制限が残っています。
比較
この
無駄さを見ると「効率悪すぎ。やっぱBFはネタ言語だよな。」などと思うところですが(実際その通りですが)、あえて理由を考えてみると:
- レジスタや四則演算などの基本的な命令が効率よく実装できていない
- ランダムアクセス可能なメモリを持った機械と処理時間のオーダーが違う
1は気のせいです。定数倍でしか変わらないので、「効率の良い」実装と外からでは区別がつきません。
2はもっと根本的な問題です。これは多分変えられません。つまりこの点に関しては優劣をつけられます。
そもそも
どうしてこのようなことを思ったのかというと(当然hs2bfの実装に必要ということもあるのですが)、graph reductionと
ノイマン型、さらに原始的な
チューリングマシンとの間の違いの大きさに改めて気づかされたということもあるでしょう。
しかし現在の微妙な状況(メモリアクセス遅い・クロック上がらない・並列計算普及しない)を見てるとそろそろ根本的な転換があるのかな、と感じている(というより期待している)からなんですね。
あとはUIと計算の関係についてです。これについてはそのうち書くかもしれません。