QubitFuck(仮称)
元ネタ→http://shinh.skr.jp/m/?date=20080206#p08
量子の気分(というより宇宙消失の気分)だけ味わえそうなものを考えてみました。
Brainfuckと同じく8命令予定ですので初心者向けかもしれません。
仮想マシンの構成としては、qubitの無限列があって、カーソルがどこかを指しています。
各qubitは0か1を取ることができて、最初は全部0です。
命令は次のものがあります。
| ? | 現在位置に重ね合わせ状態を置く |
| ! | 現在位置を収束させる |
| . | 現在位置の1ビットデータを出力する |
| , | 入力した1ビットデータを現在位置にセットする |
| > | カーソルを右に1qubit移動 |
| カーソルを左に1qubit移動 | |
| [ | 現在位置が0なら対応する]の次にジャンプ |
| ] | 対応する[にジャンプ |
+と-が?と!になった以外は、データ単位をバイトではなくビットにしたBrainfuckと同じです。
?は、現在位置に0がセットされた場合と1がセットされた場合の並列計算を開始します。
!は、以前?が使われた位置で実行されると、並列計算をやめて!を実行した世界を採用します。それ以外は効果なしです。もしかしたら過去に上位次元の存在がその位置で?を実行したかもしれませんが、我々はその結果分岐した世界の片方に生きていますので、!を実行したことで見知らぬ平行世界が消滅して我々の世界が採用されても、我々にはそれに気付く方法がありません。
平行世界の関係は何重にもできます。?を2回実行して、!を1回実行すると、2回目の?で分岐した世界は収束しますが、1回目の?で分岐した世界はそのままです。A位置で?してその後B位置で?してその後A位置で!すると、2回の?で分岐した4つの世界のうち、A位置が現在の世界と同じ2つの世界が生き残ります……のほうが2回目の?ごと巻き戻して単一世界に戻るよりも応用が利きそう。
分岐した世界で,.を実行すると、バッファリングされて、ある世界で読まれたデータは他の世界でも読まれることになりますし、出力したデータは、世界がひとつに収束した時に初めてコンソールに出てきます。(ただし現在のアーキテクチャ上に実装する場合)
通常の文字単位の端末とI/Fするためには,と.は1文字につき8回実行する必要がありますが些細な問題です。ビットオーダーは処理系定義としておきます。わあ、なんて最悪。下位からにしておきましょう。
ではプログラミングしてみましょう。
演算は、任意に0と1を作れて、あとNANDができたらなんでもできますので、まず任意の位置に0と1をセットすることから始めましょう。
例えば、現在位置を0にセットするには、次の命令列を実行します。
現在位置が0の世界と1の世界を作り出し0の世界を採用する寸法です。
?[]!
例えば、現在位置を1にセットするには、次の命令列を実行……。
･……。
どうすればいいんだろう。Brainfuckですと、[-]+か。+が無い。
少なくともNOTが必要……ということで、命令の追加改変を考えます。
ええと……NOTは、あるところで?して、前の状態の反転になったら!する、という実装が考えられます。それができるならNANDもできそうです。
ですから、本当に必要なのは、if-then-elseのelseですね。[]はwhileですから、if-thenの代わりには使えてもelseの代わりはできませんから。
| { | 現在位置が0なら対応する/の次へジャンプ |
| / | 対応する}へジャンプ |
| } | 何もしない |
?{/!} # 0にセット
?{!/} # 1にセット
{?{/!}/?{!/}} # NOT
{>{>?{/!}/>?{!/}}/>>?{!/}} # @0と@1のNANDを@2にセット……うーん。
Brainfuckに比べて随分軟弱になってしまいそうです。なんでも簡単にできるじゃん。}が何もしないのが気に入りません。命令数が11になって2桁になるのが気に入りません。
もっと原始的で回りくどいプリミティブはないかしらん……。
大体、Brainfuckは[-]の形が使えたためにという制御文に意味があるのです。0か1しかないのに片方を特別扱いするは……真偽値と考えたら当たり前ですね。これはこれでいいのか。
やっぱNANDを用意しますか。そうすれば0 NAND 0=1ですので1も作れます。しかしカーソルは1個なのに2項演算子って気持ち悪いですよね……。
Brainfuck系にあうのはどちらかといえば単項のNOT……NOTと[]でNANDが書ければOKなわけです。仮にNOTを;としてやってみますか。セミコロンなのは、打ち易い位置にある以上の意味は無いです。記号としては^や~の方が適切と思いますが、これらはなるべく使いたくないですしね。
?[]! # 0にセット ?[]!; # 1にセット
……ダメ、セミコロンダメ。受け付けない。
^や~も試してみましたがこれらは目立たないのでダメです。
#にしましょう。Modulaでは不等号の意味です。そうするとコメントに#が使えなくなりますのでこっちにセミコロンを使いましょう。どうせこんなのCGIに使うことなんかあり得ない、あり得ない、あり得ない……と自己暗示。
NAND……NAND……よーするに11のときだけ0でそれ以外1になるから、そりゃ。
?[]! ; 0にセット ?[]!# ; 1にセット >>?[]!<<#[>>#<<#]>#[>?[]!#<#]> ; @0と@1のNANDを@2にセット, @0と@1は0になる
書けました……が、破壊的になってしまいました。
ということはコピーも必要になりますね。
>?[]!>?[]!<<[>#>#<<#] ; @0を@1と@2にコピー, @0は0になる
非破壊的コピーは無理でしょうか……私の頭では無理です。
とりあえずこれで何でも書けそうです。
しかし、このままですと、0にセットと1にセットがイディオムと化して、平行世界の他の用途が、ホントの並列計算を必要とする時ぐらいしか残りそうに無いです。あとは単なるビット単位Brainfuckになってしまって面白くないです。
もっと、いかにも平行世界平行世界した分岐/ループが必要とされています。
というわけで#をボツにして考え直します。
勘ですが、!が良くないような気がします。
?で世界が分岐したあと、てんでに計算を進めて、正しいことがわかればその世界を採用するという流れを徹底させるような制御文でなければなりません。
C=A+Bを計算するとき、AとBからCを計算するのがこれまでのプログラミングでしたが、これからはCにありとあらゆる値を取りうる可能性を持たせた上で、たまたまCがAとBの和になっている世界を採用する、と、こうあるべきです。
!を再定義しましょう。なおはやっぱり続投します。
| ! | 現在位置を収束させる, 対応する?と同じレベルまで[]を抜ける |
この新定義では、?していない位置で!を実行すると、プログラムの終了になります。過去に上位次元の存在がその位置で?を実行したあと、我々の全体はどこかの[]の中で動いていると考えると、それを抜けるわけですからつまり終了です。
あとNOTを没にしたので#はコメントに使います。
これで割と自然な形で1にセットも書けるようになりました。
?[]! # 0にセット ?[!] # 1にセット
1にセットの使用は注意が必要で、?[!]!なんてやってしまうとふたつの!のどっちが先に実行されるかわからないため、1/2でプログラムが終了してしまいます。?[!]の後は、しばらく!と離しておかなければなりません。どれくらい離すと安全かは処理系定義……は流石に何もできなくなるので、平行世界で実行される命令数は2離されることはないとします。つまり順序はともかく均等に実行されるってことです。
あ、それで今思いつきましたが、単に?!とすると乱数が取れますね。0や1よりも乱数のほうが簡単なのが、量子の気分でいい感じです。これを確定させるため、分岐した0の世界と1の世界のどちらを先に実行するかは均等な確率でなければならないとします。
さて問題は、この新定義!でNOTが書けるかということですが……。
書けたら8命令のままQubitFuckを完成できます。
>?[<[]>!]<><><[!]> # @1に@0のNOTをセット
……ど、どうでしょう。
@0が0の場合、@1が0の世界がダミーの<><>を実行している間に、@1が1の世界がひとつ目の!に到達します。これで@1が0の世界は消えて、@1が1の世界が残ります。!を実行したのでひとつ目の]は通り抜けます。最後の[は@0が0なのでスキップされます。
@0が1の場合、@1が1の世界は内側の[ ]で無限ループします。@1が0の世界は最初の[ ]に入りませんのでそのまま実行を続けて、最後の[には@0が1ですので入って、!で世界を収束させつつ最後の]を抜けます。
おお、良さそうです。しかも平行世界を利用したプログラミングっぽい！
心残りがあるとすれば、[!...]の様に書いても!以降は実行されないことですね。
つまりwarningが言語に導入されてしまったわけです。
これはD1.0時代のWalter先生言うところの設計ミスですよ。最近はそうでもないみたいで悲しいですが。
というわけでちょっと直します。
| ! | 現在位置を収束させる, 次の]に到達すると対応する?と同じレベルまで[]を抜ける |
これなら[>!<]のようなのもアリになって、記述力が増すはずです。
!が中に入った[]がwhileではなくifになっただけという話かも知れません……。?と同じレベルまで抜ける云々は要らなくて、これでいいかも。
| ! | 現在位置を収束させる, !の入っている最も内側の]はループしない |
ただしこっちの定義ではexit代わりに使えなくなります。
どうしましょうね。
処理系を作ってみて、どっちが便利かで決めるしかないでしょうか。
誰か作ってください。
今日考えた仕様まとめ。
| ? | 現在位置に重ね合わせ状態を置く |
| ! | 現在位置を収束させる, 次の]に到達すると対応する?と同じレベルまで[]を抜ける or !の入っている最も内側の]はループしない |
| . | 現在位置の1ビットデータを出力する |
| , | 入力した1ビットデータを現在位置にセットする |
| > | カーソルを右に1qubit移動 |
| カーソルを左に1qubit移動 | |
| [ | 現在位置が0なら対応する]の次にジャンプ |
| ] | 対応する[にジャンプ |
- 入出力のビットオーダーは下位から。
- 平行世界で実行される命令数は2離されることはない。
- 分岐した0の世界と1の世界のどちらを先に実行するかは均等な確率でなければならない。
ちなみに世の中にはこんなのもあるようです。
http://www.esolangs.org/wiki/Quantum_brainfuck
http://www.esolangs.org/wiki/Expandable_Quantum_Brainfuck
