P′′ (P double prime) is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines. It provided one of the earliest formulations of the single-entry single-exit principle central to structured programming.
Definition
P′′ is formally defined as a set of words on the four-instruction alphabet <math>\{ \, R, \lambda, (, ) \, \}</math>, as follows:
Syntax
- <math>R</math> and <math>\lambda</math> are words in P′′.
- If <math>q_1</math> and <math>q_2</math> are words in P′′, then <math>q_1 q_2</math> is a word in P′′.
- If <math>q</math> is a word in P′′, then <math>
(q)</math> is a word in P′′.
- Only words derivable from the previous three rules are words in P′′.
Semantics
Let a finite alphabet <math>\mathcal C = \{ c_0 \equiv \Box \} \cup \{c_1, c_2, \dots, c_n\}</math>, with <math>n \ge 1</math>, be given, together with a Turing Machine equipped with a tape that is infinite to the left and divided into squares, only finitely many of which initially contain non-blank symbols. The remaining squares contain the blank symbol <math>c_0</math>. The machine has a single head that can read and write one square at a time and move along the tape.
For formalization, the alphabet symbols <math>c_i</math> are identified with their indices <math>i</math>. The integer <math>0</math> corresponds to the blank symbol (<math>\Box</math>). Arithmetic on squares is performed modulo <math>(n+1)</math>, so incrementing <math>n</math> produces <math>0</math> and decrementing <math>0</math> produces <math>n</math>. This formulation matches Böhm’s definition and differs only in notation, replacing symbolic alphabet elements with their numerical indices.
A program (called: "word") operates on a tape configuration consisting of a given initial tape together with the position of the head. Each tape square contains a value from the set <math>\{0,1,\dots,n\}</math>. All but finitely many squares initially contain the value <math>0</math>.
Instructions
:{| class="wikitable"
! Char. !! Instruction
|-
| <math>R</math> || Shift the tape-head one square to the right (if possible). If the head is already at the right end of the tape, the instruction has no effect.
|-
| <math>\lambda</math> || Increment the current square modulo <math>(n+1)</math>, then shift the head one square to the left.
|-
| <math>(</math> || Jump forward past <math>)</math> if the current square = <math>0</math>
|-
| <math>)</math> || Jump backward past <math>(</math> if the current square <math>\neq 0</math> For example, <math>\{\lambda R\}^3 \; \rightarrow \; \lambda R \, \lambda R \, \lambda R</math>.
Example 1
Böhm defines three macro's <code>r</code>, <code>r'</code> and <code>L</code>:
- <math>r \equiv \lambda R</math>
:This snippet adds <math>1 \bmod (n+1)</math> to the current square.
- <math>L \equiv r^\prime \lambda \equiv \{\lambda R \}^n \lambda</math>
:This macro shifts the head one square to the left.
Example 2
Based on these macro's, Böhm gives the following word to compute the predecessor <math>(x-1)</math> of an integer <math>x > 0</math>:
:<math>R(R)L(r^\prime(L(L))r^\prime L)Rr</math>
When P′′ is defined using square values in <math>\{0, 1, \dots, n\}</math>, the number <math>x</math> is represented in bijective base-n notation <math>(d_1 , \dots , d_k)_{bijn}</math>, most significant digit first. These tuples appear in consecutive squares, flanked by <math>0</math>s, with the tape head on the leftmost <math>0</math>.
The expansion of the macro's depends on the modulus.
Modulus = 2, when tape squares take values in <math>\{0 \equiv \Box, 1 \} \,</math>
When square values are in <math name="inline">\{0, 1 \}</math>, the word expands to
:<math>
R(R){\{\lambda R\}^1 \lambda} ( {\{\lambda R\}^1} ( {\{\lambda R\}^1 \lambda}({\{\lambda R\}^1 \lambda}) ) {\{\lambda R\}^1} {\{\lambda R\}^1 \lambda} ) R \lambda R
</math>
that is
:<math>R(R)\lambda R \lambda ( \lambda R (\lambda R \lambda(\lambda R \lambda) ) \lambda R \lambda R \lambda ) R \lambda R</math>
In bijective base‑1 notation the number <math>8</math> (for example) is encoded as <math>(1,1,1,1,1,1,1,1)_{bij1}</math>.<br/>So the initial tape will be (with head position <u>underlined</u>)
:<math>\phantom{\vert 1 \;} \cdots \; \vert \; \underline{0} \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 0 \; \rVert</math>
After execution of the word the tape configuration is
:<math>\phantom{\vert 1 \;} \cdots \; \vert \; 0 \; \vert \; \underline{0} \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 0 \; \rVert</math>
, which corresponds to the bijective base‑1 encoding for 7.
Modulus = 3, when tape squares take values in <math>\{0, 1 , 2 \} \,</math>
When square values are in <math name="inline">\{0, 1, 2 \}</math>, the word expands to
:<math>
R(R){\{\lambda R\}^2 \lambda} ( {\{\lambda R\}^2} ( {\{\lambda R\}^2 \lambda}({\{\lambda R\}^2 \lambda}) ) {\{\lambda R\}^2} {\{\lambda R\}^2 \lambda} ) R \lambda R
</math>
that is
:<math>R(R)\lambda R\lambda R\lambda(\lambda R\lambda R(\lambda R\lambda R\lambda(\lambda R\lambda R\lambda))\lambda R\lambda R\lambda R\lambda R\lambda)R\lambda R</math>
In bijective base‑2 notation the number <math>8</math> is encoded as <math>(1,1,2)_{bij2}</math>.<br/>So the initial tape will be (with head position <u>underlined</u>)
:<math>\phantom{\vert 1 \;} \cdots \; \vert \; \underline{0} \; \vert \; 1 \; \vert \; 1 \; \vert \; 2 \; \vert \; 0 \; \rVert</math>
After execution of the word the tape configuration is
:<math>\cdots \; \vert \; 0 \; \vert \; \underline{0} \; \vert \; 1 \; \vert \; 1 \; \vert \; 1 \; \vert \; 0 \; \rVert</math>
, which corresponds to the bijective base‑2 encoding for 7.
Modulus = 256, when tape squares take values in <math>\{0, 1 , 2, \cdots, 255 \}</math>
When P′′ is defined with an alphabet of size <math>256, \, \Sigma = \{ 0, 1, \cdots, 255 \}</math>, the word expands to
:<math>
R(R){\{\lambda R\}^{255} \lambda} ( {\{\lambda R\}^{255 ( {\{\lambda R\}^{255} \lambda}({\{\lambda R\}^{255} \lambda}) ) {\{\lambda R\}^{255 {\{\lambda R\}^{255} \lambda} ) R \lambda R
</math>
Its full length is
<math>3077</math> characters.
In bijective base‑255 notation the number <math>35048731</math> (for example) is encoded as <math>( 2, 29, 1, 1 )_{bij255}</math>.<br/>The initial tape will be (with head position <u>underlined</u>):
:<math>\phantom{\vert 0\;} \cdots \; \vert \; \underline{0} \; \vert \; 2 \; \vert \; 29 \; \vert \quad \; 1 \; \vert \quad \; 1 \; \vert \; 0 \; \rVert</math>
After execution of the word the tape configuration is
:<math>\cdots \; \vert \; 0 \; \vert \; \underline{0} \; \vert \; 2 \; \vert \; 28 \; \vert \; 255 \; \vert \; 255 \; \vert \; 0 \; \rVert</math>
, which corresponds to the bijective base‑255 encoding for <math>35048730</math>.
Foundation of structured programming
Böhm proved that P′′ is Turing-complete:
The language demonstrates that programs can be written without using selection (if-then-else) constructs, only sequence and iteration are necessary. P′′ words are evaluated from left to right with backward control eliminated recursively. Böhm’s paper on the language P′′ is one of the earliest explicit statements of what we now call the single-entry single-exit (SESE) property:
This design anticipated Dijkstra's 1968 advocacy of structured programming. While Dijkstra argued programmers should avoid goto statements, Böhm's P′′ prevented unstructured control flow through language design—enforcing structure at the source rather than requiring later transformation or programmer discipline.
His results were restated in the 1966 Böhm-Jacopini structured program theorem, which combined Böhm's selection elimination with Jacopini's flowchart transformation method.
Relation to other programming languages
P′′ versus languages based on WHILE
In conventional high-level languages, a while loop executes a block of code based on a fixed boolean expression that is evaluated at the start of each iteration. The same condition is tested each time the loop executes:
:<syntaxhighlight lang="python">
while condition_expression:
- loop body
</syntaxhighlight>
In P′′, loops are written as <math>(q)</math>, where <math>q</math> is a sequence of instructions. Loop continuation is determined dynamically by the tape head: after executing <math>q</math>, the program examines the value of the current tape square, which may change during execution because instructions in <math>q</math> can move the head. This makes P′′ loops more general than conventional pre-test loops, as the loop condition is embedded in the data rather than specified separately. A conventional while loop is equivalent to a P′′ loop only when at <math>'('</math> and <math>')'</math> the head points to the same square.
Not every P′′ loop can be trivially transcribed to a standard <code>while</code> loop. For example, the word <math>(\lambda)</math>
- does nothing if the head scans initially <math>0</math>; otherwise
- goes to the left until it scans <math>0</math>, incrementing each square on its way.
This word cannot be translated to a <code>while</code> loop without rethinking the logic.
Relation to Brainfuck
In formal language theory, the language Brainfuck (hereafter: BF) may be regarded as a mirrored instantiation of P′′, where P′′ is defined with an alphabet of size <math>256, \, \Sigma = \{ 0 \equiv \Box, 1, \cdots, 255 \}</math>.
The two languages differ only in the orientation of their tapes: P′′ operates on a left-infinite tape, whereas BF operates on a right-infinite tape. As is standard for Turing-machine–like models, this difference can be eliminated by mirroring the tape and reversing the direction of head movement.
Under this convention, there exists a literal one-to-one correspondence between the instructions of P′′ and BF. Arithmetic operations and loop constructs are preserved directly, while head movements are reversed to account for the mirrored tape orientation. In other words, P′′ and BF are bisimilar under macro expansion with mirrored tapes/heads and disregarded input.
Instruction correspondence
:{| class="wikitable"
! # !! P′′ pattern !! BF pattern !! Meaning
|-
| 1 || <math>\{ \lambda R \}^{255} \lambda</math>