読者です 読者をやめる 読者になる 読者になる

計算模型のはなし

hs2bfでBrainfuckの近くを考えているとちょっとした考えが浮かんだので書いてみます。


ここではBrainfuckを言語として見るのではなく、BFネイティブな機械を考えてみます。

Brainfuckでの例

次のような例を考えてみましょう: d(ptr)にvalをコピーする

val ptr d0 d1 d2 ...
少なくともvalはコピーしなければいけないので、どこかに一時変数用の領域を挿入する必要があります。 しかし、ptrの分だけ移動したり、そこまでvalを運んだりするのはどのようにすればいいでしょうか? 一見すると出来ないような気がしますが、実は簡単です。 解決法は使うメモリの容量を3倍にするです。 例えばval=3,ptr=2だとこのようになります:
 val    ptr     0        1      2
3 2 d0 d1 d2
valをcopy:
3 0 3 2 d0 d1 d2
ptrをcopy:
3 0 3 2 0 2 d0 d1 d2
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と計算の関係についてです。これについてはそのうち書くかもしれません。

*1:オペランドの大きさが固定のため