P′′のソースを表示

{{Infobox programming language
 | name                   = P′′
 | paradigm               = [[命令型プログラミング]], [[構造化定理]]
 | released               = 1964
 | designer               = [[コラド・ベーム]]（Corrado Böhm）
 | typing                 = なし
 | dialects               = [[Brainfuck]]
 | influenced             = [[Brainfuck]]
|fetchwikidata=}}

'''P′′''' （P double prime：ピーダブルプライム<ref>https://github.com/Pbtflakes/pdbl</ref>）は1964年に[[コラド・ベーム]]<ref name="bohm1964">Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.</ref><ref name="bohm1966">Böhm, C. and Jacopini, G.: "Flow diagrams, Turing machines and languages with only two formation rules", CACM 9(5), 1966.  (Note: This is the most-cited paper on the [[構造化定理|structured program theorem]].)</ref>によって作成された、[[チューリングマシン]]の一種を記述するための言語である。

チューリングマシンを記述するがゆえにその仕様は原始的である。[[チューリングマシン]]にもかかわらず、状態遷移はテープの内容とテープヘッドの位置だけで表現されるので、[[有限オートマトン]]の概念が希薄である。

==定義==
<math display="inline">\mathcal{P}^{\prime\prime}</math> (以下 '''P′′''')は以下のように4つの命令アルファベット <math display="inline">\{R, \lambda, (, )\}</math> におけるワードの集合として形式的に定義される（formally defined）。

===文法===
# <math display="inline">R</math> と <math display="inline">\lambda</math> は P′′ のワードである。
# もしも <math display="inline">q_1</math> と <math display="inline">q_2</math> が P′′ のワードならば、それらを繋げた <math display="inline">q_1 q_2</math> も P′′ のワードである。
# もしも <math display="inline">q</math> が P′′のワードならば、<math display="inline">(q)</math> も P′′ のワードである。
# 以上の3つの法則から得られるワードだけが P′′ のワードである。

===意味論===
* <math display="inline">\{\Box, c_1, c_2, \ldots, c_n\}</math> は無限長のテープを搭載した[[チューリングマシン]]のテープ・アルファベット（テープに書かれるデータの種類）である。<math display="inline">\Box</math> は空白の記号であり、<math display="inline">c_0</math> と等価である。
* P′′ の全命令は、全てのあり得るテープの構成の集合 <math display="inline">X</math> の[[順列]]である。つまり、テープの内容とテープヘッドの位置の両方を考慮した全てのあり得る構成である<ref group="注釈">原文は "All instructions in P′′ are permutations of the set X of all possible tape configurations; that is, all possible configurations of both the contents of the tape and the position of the tape-head." となっている。テープの内容とテープヘッドの位置の両方を考慮した全てのあり得る構成が命令になるとは理解し難い。</ref>。
* <math display="inline">\alpha</math> は述語（値を受け取ってから真偽が決定するもの）であり、現在位置のシンボルは <math display="inline">\Box</math> ではないことを示している。これは命令ではなく、プログラム中で使用されない。しかし、その代わりとして言語の定義を補助するために使われる。
* <math display="inline">R</math> は、（可能であれば）1セル分テープヘッドを右方向へ移動することを意味する。
* <math display="inline">\lambda</math> は、現在位置のシンボル <math display="inline">c_i</math> を <math display="inline">c_{(i+1) \bmod (n+1)}</math> に置き換える（つまり、現在位置のシンボルが <math display="inline">c_n</math> のときは <math display="inline">c_0</math> に置き換えられる）。そして、テープヘッドを1セル分左方向へ移動することを意味する。
* <math display="inline">q_1 q_2</math> は[[写像の合成|関数の合成]] <math display="inline">q_2 \circ q_1</math> を意味する。言い換えると、命令 <math display="inline">q_1</math> は <math display="inline">q_2</math> の前に実行される。
* <math display="inline">(q)</math> は、条件 <math display="inline">\alpha</math> が成立している間だけ while ループで <math display="inline">q</math> を反復することを意味する。

== 他のプログラミング言語との関連 ==
* [[Brainfuck]] 言語は、P′′ の<ref group="注釈">英語版Wikipediaではこの部分に「a minor」という形容も付いているが、それは特に訳す意味は無いと思われる。</ref>非形式的な変種（informal variation）である（Brainfuck はテープの代わりにメモリを使うので、I/Oを扱わないところは異なる）。ベームはあらゆる[[計算可能関数]]を計算するのに十分な基本関数の集合のそれぞれに対して明確な P′′ のプログラムを提供している。使用したものは <math display="inline">(</math>, <math display="inline">)</math> そして4つのワード <math display="inline">r \equiv \lambda R</math>、  <math display="inline">r^\prime \equiv r^n</math>（ここで <math display="inline">r^n</math> は <math display="inline">r</math> の <math display="inline">n</math> 回の反復である）、 <math display="inline">L \equiv r^\prime \lambda</math>、 <math display="inline">R</math> だけである。これらは6つの Brainfuck の命令 {{tt|[, ], +, -, <, >}} と等価である。注意するべきは、<math display="inline">c_{n+1} \equiv c_0 \equiv \Box</math> なので、現在位置のシンボルをn回インクリメントするとラップアラウンド（<math display="inline">c_n</math> をインクリメントすると <math display="inline">c_0</math>になること）する。そのため、一つの <math display="inline">r^\prime</math> によって、その結果は現在位置のシンボルをデクリメントすることになる（訳注：テープ・アルファベットは n+1 種類あるので、n回インクリメントするとラップアラウンドして1つ少ない数のテープ・アルファベットになる）。

== プログラムの例 ==
ベーム<ref name="bohm1964" />は、''x'' > 0 を満たす整数''x''の前の数 (''x''-1) を計算する以下のプログラムを提供している。

:<math>R(R)L(r^\prime(L(L))r^\prime L)Rr</math>

これを等価の[[Brainfuck]]のプログラムに直接変換すると、
<syntaxhighlight lang="bf">
 >[>]<[−[<[<]]−<]>+
</syntaxhighlight>

このプログラムは [[:en:Bijective numeration|bijective base-k 記法]]で表現されているある一つの整数を想定している。<math display="inline">c_1, c_2 \ldots, c_k</math> は <math display="inline">1, 2, \ldots, k</math> にそれぞれエンコードされる。そして、数字列の前後に <math display="inline">\Box</math> がある（例えば、bijective base-2 の場合、数字の8は <math display="inline">\Box c_1 c_1 c_2 \Box</math> とエンコードされる。なぜなら、bijective base-2 において8は112である）。計算の最初と最後に数字列の前にある <math display="inline">\Box</math> の上にヘッドが位置することになる。

==注釈==
{{Reflist|group="注釈"}}

== 出典 ==
{{Reflist}}

{{DEFAULTSORT:P double prime}}
[[Category:プログラミング言語]]