P′′

Short description: Primitive programming language created in 1964

P′′

Paradigm	Imperative, structured
Designed by	Corrado Böhm
First appeared	1964
Typing discipline	untyped
Dialects
Brainfuck
Influenced
Brainfuck

P′′ (P double prime) is a primitive computer programming language created by Corrado Böhm in 1964 to describe a family of Turing machines.

Definition

[math]\displaystyle{ \mathcal{P}^{\prime\prime} }[/math] (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet [math]\displaystyle{ \{R, \lambda, (, )\} }[/math], as follows:

Syntax

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

Semantics

• [math]\displaystyle{ \{\Box, c_1, c_2, \ldots, c_n\} }[/math] is the tape-alphabet of a Turing machine with left-infinite tape, [math]\displaystyle{ \Box }[/math] being the blank symbol, equivalent to [math]\displaystyle{ c_0 }[/math].
• All instructions in P′′ are permutations of the set [math]\displaystyle{ X }[/math] of all possible tape configurations; that is, all possible configurations of both the contents of the tape and the position of the tape-head.
• [math]\displaystyle{ \alpha }[/math] is a predicate saying that the current symbol is not [math]\displaystyle{ \Box }[/math]. It is not an instruction and is not used in programs, but is instead used to help define the language.
• [math]\displaystyle{ R }[/math] means move the tape-head rightward one cell (if possible).
• [math]\displaystyle{ \lambda }[/math] means replace the current symbol [math]\displaystyle{ c_i }[/math] with [math]\displaystyle{ c_{(i+1) \bmod (n+1)} }[/math], and then move the tape-head leftward one cell.
• [math]\displaystyle{ q_1 q_2 }[/math] means the function composition [math]\displaystyle{ q_2 \circ q_1 }[/math]. In other words, the instruction [math]\displaystyle{ q_1 }[/math] is performed before [math]\displaystyle{ q_2 }[/math].
• [math]\displaystyle{ (q) }[/math] means iterate [math]\displaystyle{ q }[/math] in a while loop, with the condition [math]\displaystyle{ \alpha }[/math].

Relation to other programming languages

• P′′ was the first "GOTO-less" imperative structured programming language to be proven Turing-complete
• The Brainfuck language (apart from its I/O commands) is a minor informal variation of P′′. Böhm gives explicit P′′ programs for each of a set of basic functions sufficient to compute any computable function, using only [math]\displaystyle{ ( }[/math], [math]\displaystyle{ ) }[/math] and the four words [math]\displaystyle{ r, r^\prime, L, R }[/math] where [math]\displaystyle{ r \equiv \lambda R, r^\prime \equiv r^n }[/math] with [math]\displaystyle{ r^n }[/math] denoting the [math]\displaystyle{ n }[/math]th iterate of [math]\displaystyle{ r }[/math], and [math]\displaystyle{ L \equiv r^\prime \lambda }[/math]. These are the equivalents of the six respective Brainfuck commands [, ], +, -, <, >. Note that since [math]\displaystyle{ c_{n+1} \equiv c_0 \equiv \Box }[/math], incrementing the current symbol [math]\displaystyle{ n }[/math] times will wrap around so that the result is to "decrement" the symbol in the current cell by one ([math]\displaystyle{ r^\prime }[/math]).

Example program

Böhm gives the following program to compute the predecessor (x-1) of an integer x > 0:

[math]\displaystyle{ R(R)L(r^\prime(L(L))r^\prime L)Rr }[/math]

which translates directly to the equivalent Brainfuck program:

>[>]<[−[<[<]]−<]>+

The program expects an integer to be represented in bijective base-k notation, with [math]\displaystyle{ c_1, c_2 \ldots, c_k }[/math] encoding the digits [math]\displaystyle{ 1, 2, \ldots, k }[/math] respectively, and to have [math]\displaystyle{ \Box }[/math] before and after the digit-string. (E.g., in bijective base-2, the number eight would be encoded as [math]\displaystyle{ \Box c_1 c_1 c_2 \Box }[/math], because 8 in bijective base-2 is 112.) At the beginning and end of the computation, the tape-head is on the [math]\displaystyle{ \Box }[/math] preceding the digit-string.

External links

• P′′Online interpreter: Demonstrating the iterative 99 Bottles of Beer song construed in 337568 P′′ instructions.