P′′(P double prime)という言語を知る

Brainfuckはesolangとして有名ですが、そんな言語にも影響を与えた言語を知っていますか。
今回はそんな言語に関する記事です。

P′′とは何か

P′′とはチューリングマシンの一種を記述するための言語です。
詳しい文法や意味論に関してはwikiの記事をご覧ください。

以下にP′′からBrainfuckに変換可能な対応表を書いておきます。

P′′	Brainfuck
R	>
λ	+<
(	[
)	]

逆にBrainfuckからP′′に変換する対応表は以下の通りです。

Brainfuck	P′′
[	(
]	)
+	λR
-	後述
>	R
<	後述
.	なし
,	なし

Brainfuckとの関係性

BrainfuckとP′′の大きな差は入出力命令があるか否かですが、それ以外は互換性があります。

配列の互換性

P′′はチューリングマシンの一種を記述する言語であるため、チューリングマシンが持つテープというものを持ちます。
これは長さが無制限であり、その表面に記号を読み書きすることができます。
ここでは記号と言いましたが、これは数値であったりアルファベットであったり、難しくいうなら有限個の異なる状態を表すことができるということです。
簡単に言えば長さが無限の配列です。
さて、Brainfuckの配列は長さは無制限ではないですが30000個の配列は十分な長さを持つと解釈します。
そしてBrainfuckの配列はbyte配列なので00からFFまでの256種類の状態を読み書きできます。

さらにP′′のテープには空白記号と言った記号が存在しますが、これはBrainfuckの配列では00が空白記号であると定義することが多いです。
P′′において空白はループを抜ける時に使います。

命令の互換性

命令の互換性に関しては前章の表で示しました。
しかし、入出力命令である.,,以外にも対応を示していない命令が2つあります。
一つは-、そしてもう一つは<です。

さて、<の対応に関して、BrainfuckとP′′の表記を混ぜてざっくりと言ってしまうと、-λです。
これはλが+<であることを踏まえれば-λは-+<となり、-+は相殺され<になると言えばわかるでしょう。

もう一つの、というか一番の問題は-です。
先ほど示した<の対応付けに関しても-の問題は依然と残っています。
とりあえずここでは定義をよく知ったBrainfuckで考えてみましょう。
Brainfuckでは多くの場合、00に対して-をするとFFになります。
これは+を255回行ったものと同じ結果になります。
つまり、brainfuckの配列がbyte配列である場合、

-

と

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

は等価です。
それをふまえてP′′について考えましょう。
P′′ではn種類の記号が読み書きできます。
記号の集合は{C₀,C₁,C₂,C₃,...C_n-1}で、n種類の状態を表現できます。
ただしC₀は空白記号です。

さて、Brainfuckはこのnが256の例です。
そして-は+を255個繋げたものです。
この255という数字はnが256であることに注意したらn-1です。

ではP′′ではどうでしょうか。
P′′ではBrainfuckの+はλRに対応しています。
そしてBrainfuckの-はBrainfuckの+をn-1個繋げたものである点に注意すると、Brainfuckの-に対応するP′′の書き方はλRをn-1個繋げたものに対応しています。

P′′からBrainfuckの定義を再確認する

BrainfuckがP′′に対応することを前章までで確認してきました。
その上でBrainfuckの仕様を確認します。

「P′′はあくまで影響を与えただけであり、正当な拡張ではないのでBrainfuckの定義と比較するのはナンセンスだ」という意見はあるかもしれませんが、その点に関しては今回は取り上げません。

配列の長さ

Brainfuckの配列の長さは30000ですが、P′′の定義では無制限です。
だから、30000というものは必ず守るべき仕様というよりは十分おきな数であるとみなせる場合は長さは多少適当でも良いのかもしれません。

配列の要素のサイズ

Brainfuckの配列の要素はbyte配列で実装している場合は256種類、各要素が2byteの配列は65536種類、4byteなら4294967296種類の状態を扱えます。
P′′はn種類の状態を扱えます。
これはBrainfuckのインタプリタなどの実装によって異なります。
しかしながら、文字を扱うことを考えるとASCII文字くらいは扱えて欲しいと考えると1byte、256種類の状態を扱えるくらいがちょうどいいのかもしれません。

入出力

Brainfuckには入出力がありますがP′′には入出力がないです。
ただ、これに関してはBrainfuckをより使いやすくするための拡張であると考えるのが良いでしょう。