P′′

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 { R , λ , ( , ) } {\textstyle \{\,R,\lambda ,(,)\,\}}, as follows:

Syntax

1. R {\displaystyle R} and λ {\displaystyle \lambda } are words in P′′.
2. If q 1 {\displaystyle q_{1}} and q 2 {\displaystyle q_{2}} are words in P′′, then q 1 q 2 {\displaystyle q_{1}q_{2}} is a word in P′′.
3. If q {\displaystyle q} is a word in P′′, then ( q ) {\displaystyle (q)} is a word in P′′.
4. Only words derivable from the previous three rules are words in P′′.

Semantics

Let a finite alphabet C = { c 0 ≡ ◻ } ∪ { c 1 , c 2 , … , c n } {\displaystyle {\mathcal {C}}=\{c_{0}\equiv \Box \}\cup \{c_{1},c_{2},\dots ,c_{n}\}}, with n ≥ 1 {\displaystyle n\geq 1}, 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 c 0 {\displaystyle c_{0}}. 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 c i {\displaystyle c_{i}} are identified with their indices i {\displaystyle i}. The integer 0 {\displaystyle 0} corresponds to the blank symbol (◻ {\displaystyle \Box }). Arithmetic on squares is performed modulo ( n + 1 ) {\displaystyle (n+1)}, so incrementing n {\displaystyle n} produces 0 {\displaystyle 0} and decrementing 0 {\displaystyle 0} produces n {\displaystyle n}. 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 { 0 , 1 , … , n } {\displaystyle \{0,1,\dots ,n\}}. All but finitely many squares initially contain the value 0 {\displaystyle 0}.

Instructions

Char. Instruction R {\displaystyle R} 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. λ {\displaystyle \lambda } Increment the current square modulo ( n + 1 ) {\displaystyle (n+1)}, then shift the head one square to the left. ( {\displaystyle (} Jump forward past ) {\displaystyle )} if the current square = 0 {\displaystyle 0} ) {\displaystyle )} Jump backward past ( {\displaystyle (} if the current square ≠ 0 {\displaystyle \neq 0}

Example words

Define { H } k → H H … H ⏟ k times {\displaystyle \{H\}^{k}\;\rightarrow \;\underbrace {HH\dots H} _{k{\text{ times}}}} as repeated application of an instruction sequence. For example, { λ R } 3 → λ R λ R λ R {\displaystyle \{\lambda R\}^{3}\;\rightarrow \;\lambda R\,\lambda R\,\lambda R}.

Example 1

Böhm defines three macro's r, r' and L:

• r ≡ λ R {\textstyle r\equiv \lambda R}

This snippet adds 1 mod ( n + 1 ) {\displaystyle 1{\bmod {(}}n+1)} to the current square.

• r ′ ≡ { r } n ≡ { λ R } n {\displaystyle r'\equiv \{r\}^{n}\equiv \{\lambda R\}^{n}}

This snippet subtracts 1 mod ( n + 1 ) {\displaystyle 1{\bmod {(}}n+1)} from the current square.

• L ≡ r ′ λ ≡ { λ R } n λ {\textstyle L\equiv r^{\prime }\lambda \equiv \{\lambda R\}^{n}\lambda }

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 ( x − 1 ) {\displaystyle (x-1)} of an integer x > 0 {\displaystyle x>0}: R ( R ) L ( r ′ ( L ( L ) ) r ′ L ) R r {\displaystyle R(R)L(r^{\prime }(L(L))r^{\prime }L)Rr}

When P′′ is defined using square values in { 0 , 1 , … , n } {\displaystyle \{0,1,\dots ,n\}}, the number x {\displaystyle x} is represented in bijective base-n notation ( d 1 , … , d k ) b i j n {\displaystyle (d_{1},\dots ,d_{k})_{bijn}}, most significant digit first. These tuples appear in consecutive squares, flanked by 0 {\displaystyle 0}s, with the tape head on the leftmost 0 {\displaystyle 0}.

The expansion of the macro's depends on the modulus.

Modulus = 2, when tape squares take values in { 0 ≡ ◻ , 1 } {\displaystyle \{0\equiv \Box ,1\}\,}

When square values are in { 0 , 1 } {\displaystyle \{0,1\}}, the word expands to R ( R ) { λ R } 1 λ ( { λ R } 1 ( { λ R } 1 λ ( { λ R } 1 λ ) ) { λ R } 1 { λ R } 1 λ ) R λ R {\displaystyle 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} that is R ( R ) λ R λ ( λ R ( λ R λ ( λ R λ ) ) λ R λ R λ ) R λ R {\displaystyle R(R)\lambda R\lambda (\lambda R(\lambda R\lambda (\lambda R\lambda ))\lambda R\lambda R\lambda )R\lambda R}

In bijective base‑1 notation the number 8 {\displaystyle 8} (for example) is encoded as ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ) b i j 1 {\displaystyle (1,1,1,1,1,1,1,1)_{bij1}}. So the initial tape will be (with head position underlined) | 1 ⋯ | 0 _ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 ‖ {\displaystyle {\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 }

After execution of the word the tape configuration is | 1 ⋯ | 0 | 0 _ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 ‖ {\displaystyle {\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 }

, which corresponds to the bijective base‑1 encoding for 7.

Modulus = 3, when tape squares take values in { 0 , 1 , 2 } {\displaystyle \{0,1,2\}\,}

When square values are in { 0 , 1 , 2 } {\displaystyle \{0,1,2\}}, the word expands to R ( R ) { λ R } 2 λ ( { λ R } 2 ( { λ R } 2 λ ( { λ R } 2 λ ) ) { λ R } 2 { λ R } 2 λ ) R λ R {\displaystyle 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} that is R ( R ) λ R λ R λ ( λ R λ R ( λ R λ R λ ( λ R λ R λ ) ) λ R λ R λ R λ R λ ) R λ R {\displaystyle 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}

In bijective base‑2 notation the number 8 {\displaystyle 8} is encoded as ( 1 , 1 , 2 ) b i j 2 {\displaystyle (1,1,2)_{bij2}}. So the initial tape will be (with head position underlined) | 1 ⋯ | 0 _ | 1 | 1 | 2 | 0 ‖ {\displaystyle {\phantom {\vert 1\;}}\cdots \;\vert \;{\underline {0}}\;\vert \;1\;\vert \;1\;\vert \;2\;\vert \;0\;\rVert }

After execution of the word the tape configuration is ⋯ | 0 | 0 _ | 1 | 1 | 1 | 0 ‖ {\displaystyle \cdots \;\vert \;0\;\vert \;{\underline {0}}\;\vert \;1\;\vert \;1\;\vert \;1\;\vert \;0\;\rVert }

, which corresponds to the bijective base‑2 encoding for 7.

Modulus = 256, when tape squares take values in { 0 , 1 , 2 , ⋯ , 255 } {\displaystyle \{0,1,2,\cdots ,255\}}

When P′′ is defined with an alphabet of size 256 , Σ = { 0 , 1 , ⋯ , 255 } {\textstyle 256,\,\Sigma =\{0,1,\cdots ,255\}}, the word expands to R ( R ) { λ R } 255 λ ( { λ R } 255 ( { λ R } 255 λ ( { λ R } 255 λ ) ) { λ R } 255 { λ R } 255 λ ) R λ R {\displaystyle 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} Its full length is 3077 {\displaystyle 3077} characters.

In bijective base‑255 notation the number 35048731 {\displaystyle 35048731} (for example) is encoded as ( 2 , 29 , 1 , 1 ) b i j 255 {\displaystyle (2,29,1,1)_{bij255}}. The initial tape will be (with head position underlined):

| 0 ⋯ | 0 _ | 2 | 29 | 1 | 1 | 0 ‖ {\displaystyle {\phantom {\vert 0\;}}\cdots \;\vert \;{\underline {0}}\;\vert \;2\;\vert \;29\;\vert \quad \;1\;\vert \quad \;1\;\vert \;0\;\rVert }

After execution of the word the tape configuration is ⋯ | 0 | 0 _ | 2 | 28 | 255 | 255 | 0 ‖ {\displaystyle \cdots \;\vert \;0\;\vert \;{\underline {0}}\;\vert \;2\;\vert \;28\;\vert \;255\;\vert \;255\;\vert \;0\;\rVert }

, which corresponds to the bijective base‑255 encoding for 35048730 {\displaystyle 35048730}.

Foundation of structured programming

Böhm proved that P′′ is Turing-complete:

For every partial recursive function f {\displaystyle \mathbb {f} } of m ≥ 0 {\displaystyle m\geq 0} variables a programme P j ∈ P ′ ′ {\displaystyle \mathrm {P} _{j}\in {\mathcal {P}}^{\prime \prime }} exists which computes it.

— Böhm (1964)

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:

a) It is only possible to enter a cycle from its first instruction, ... b) It is only possible to exit a cycle from its last instruction.

— Böhm (1964)

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:

while condition_expression: # loop body

In P′′, loops are written as ( q ) {\displaystyle (q)}, where q {\displaystyle q} is a sequence of instructions. Loop continuation is determined dynamically by the tape head: after executing q {\displaystyle q}, the program examines the value of the current tape square, which may change during execution because instructions in q {\displaystyle q} can move the head. This makes P′′ loops more general than conventional while 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 ′ ( ′ {\displaystyle '('} and ′ ) ′ {\displaystyle ')'} the head points to the same square.

Not every P′′ loop can be trivially transcribed to a standard while loop. For example, the word ( λ ) {\displaystyle (\lambda )}

• does nothing if the head scans initially 0 {\displaystyle 0}; otherwise
• goes to the left until it scans 0 {\displaystyle 0}, incrementing each square on its way.

This word cannot be translated to a while 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 256 , Σ = { 0 ≡ ◻ , 1 , ⋯ , 255 } {\displaystyle 256,\,\Sigma =\{0\equiv \Box ,1,\cdots ,255\}}.

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

# P′′ pattern BF pattern Meaning 1 { λ R } 255 λ {\displaystyle \{\lambda R\}^{255}\lambda } > Composite pattern for head move 2 { λ R } 255 {\displaystyle \{\lambda R\}^{255}} - Arithmetic decrement (mod 2 56 {\displaystyle {\bmod {2}}56\,}) 3 λ R {\displaystyle \lambda R} + Arithmetic increment (mod 2 56 {\displaystyle {\bmod {2}}56\,}) 4 λ {\displaystyle \lambda } +> Arithmetic increment plus head move 5 R {\displaystyle R} < Head move 6 ( {\displaystyle (} [ Loop start 7 ) {\displaystyle )} ] Loop end

The correspondences between P′′ and BF can be interpreted as (nondeterministic) bidirectional term-rewrite rules. For example, the BF program +> can be translated to P′′ in two ways:

1. λ {\displaystyle \lambda }, by applying rule 4,
2. λ R { λ R } 255 λ {\displaystyle \lambda R\{\lambda R\}^{255}\lambda }, by applying rules 3 and 1.

Note that the tape heads in P′′ and BF move in opposite directions.

Tape mirroring

Execution of the translated program requires a mirrored tape configuration. The left-infinite tape on which P′′ operates ⋯ | A | B | C | D _ | E | F | G ‖ {\displaystyle \cdots \;|\;A\;|\;B\;|\;C\;|\;{\underline {D}}\;|\;E\;|\;F\;|\;G\;\rVert }

must be mirrored to a right-infinite tape on which BF operates ‖ G | F | E | D _ | C | B | A ⋯ {\displaystyle \lVert \;G\;|\;F\;|\;E\;|\;{\underline {D}}\;|\;C\;|\;B\;|\;A\;\cdots }

The BF head is initialized at the position corresponding to the P′′ head under mirroring. With this arrangement, execution of a BF program related by the instruction correspondence mimics the behavior of the corresponding P′′ program.

Loosely speaking, P′′ — when defined with an alphabet of size 256 — can be translated into BF by

1. replacing every occurrence of λ {\displaystyle \lambda } with +<, and then, in the resulting program,
2. reversing the direction of all pointer-movement instructions < and >.

Example translation from P′′ to BF

Consider the P′′ program from example 2 above: R ( R ) { λ R } 255 λ ( { λ R } 255 ( { λ R } 255 λ ( { λ R } 255 λ ) ) { λ R } 255 { λ R } 255 λ ) R λ R {\displaystyle 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} that is R ( R ) λ R λ R λ R ⋯ ⋯ ⋯ R λ R {\displaystyle R(R)\lambda R\lambda R\lambda R\cdots \cdots \cdots R\lambda R}

The tape

• P′′ starts computations on a populated tape, with a given head position.
• BF starts computations on an empty tape, with the head pointing to the lefmost cell.

So the translated BF program first has to up its tape to the mirrored copy of the tape on which the P′′ program started.

In bijective base‑255 notation the number 35048731 {\displaystyle 35048731} is encoded as ( 2 , 29 , 1 , 1 ) b i j 255 {\displaystyle (2,29,1,1)_{bij255}}. In P′′, an initial tape can be (with head position underlined): ⋯ | 0 _ | 2 | 29 | 1 | 1 | 0 ‖ {\displaystyle \cdots \;\vert \;{\underline {0}}\;\vert \;2\;\vert \;29\;\vert \;1\;\vert \;1\;\vert \;0\;\rVert }

In BF, the mirrored tape ‖ 0 | 1 | 1 | 29 | 2 | 0 _ | ⋯ {\displaystyle \lVert \;0\;|\;1\;|\;1\;|\;29\;|\;2\;|\;{\underline {0}}\;|\;\cdots }

can be input by the code

// Cell 0 = 0 >+// Cell 1 = 1 >+// Cell 2 = 1 >+++++++++++++++++++++++++++++// Cell 3 = 29 >++// Cell 4 = 2 >// Head initially on cell 5

The execution of a program translated to BF will transform the mirrored tape to the final state

‖ 0 | 255 | 255 | 28 | 2 | 0 _ | 0 | ⋯ {\displaystyle \lVert \;0\;|\;255\;|\;255\;|\;28\;|\;2\;|\;{\underline {0}}\;|\;0\;|\;\cdots }

which corresponds to the bijective base‑255 encoding for 35048730 {\displaystyle 35048730}.

The program The correspondences 1, 2, 3 in the table above are optimizing rules that correspond to the macro's L, r' and r given by Böhm. Using these shortcuts the shortest translation to BF has 18 instructions (+ the initialization of the tape):

<[<]>[-[>[>]]->]<+

When no shortcut is applied, the shortest translation by the rules has 4612 instructions, not including instructions required to initialize the tape.

See also

• Structured program theorem

Notes and references

Notes

References

Bibliography

External links

• Barendregt, Henk (6 November 2019). (PDF). Radboud University Nijmegen.

• Elsner, Mathias. . www.mathiaselsner.de.: Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.

• Esolangs Wiki. . Esolangs.