P′′

P′′ (P double prime) is a primitive computer programming language created by Corrado BöhmBöhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, 185-194, July 1964.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.) in 1964 to describe a family of Turing machines.

Definition

$\mathcal^$ (hereinafter written P′′) is formally defined as a set of words on the four-instruction alphabet $\$, as follows:

Syntax

# $R$ and $\lambda$ are words in P′′.
# If $q_1$ and $q_2$ are words in P′′, then $q_1 q_2$ is a word in P′′.
# If $q$ is a word in P′′, then $(q)$ is a word in P′′.
# Only words derivable from the previous three rules are words in P′′.

Semantics

* $\$ is the tape-alphabet of a Turing machine with left-infinite tape, $\Box$ being the ''blank'' symbol, equivalent to $c_0$.
* 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.
* $\alpha$ is a predicate saying that the current symbol is not $\Box$. It is not an instruction and is not used in programs, but is instead used to help define the language.
* $R$ means move the tape-head rightward one cell (if possible).
* $\lambda$ means replace the current symbol $c_i$ with $c_$, and then move the tape-head leftward one cell.
* $q_1 q_2$ means the function composition $q_2 \circ q_1$. In other words, the instruction $q_1$ is performed before $q_2$.
* $(q)$ means iterate $q$ in a while loop, with the condition $\alpha$.

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 $($, $)$ and the four words $r, r^\prime, L, R$ where $r \equiv \lambda R, r^\prime \equiv r^n$ with $r^n$ denoting the $n$th iterate of $r$, and $L \equiv r^\prime \lambda$. These are the equivalents of the six respective Brainfuck commands , , , , , . Note that since $c_ \equiv c_0 \equiv \Box$, incrementing the current symbol $n$ times will wrap around so that the result is to "decrement" the symbol in the current cell by one ($r^\prime$).

Example program

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

:$R(R)L(r^\prime(L(L))r^\prime L)Rr$

which translates directly to the equivalent Brainfuck program:

> ˆ’[<[<−<.html"_;"title="[<.html"_;"title="ˆ’[<[<">ˆ’[<[<−<">[<.html"_;"title="ˆ’[<[<">ˆ’[<[<−<+

The_program_expects_an_integer_to_be_represented_in_''bijective_numeration.html" ;"title=".html"_;"title="ˆ’[<[<">ˆ’[<[<−<.html" ;"title="[<.html" ;"title="ˆ’[<[<">ˆ’[<[<−<">[<.html" ;"title="ˆ’[<[<">ˆ’[<[<−<+

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

References

Weblinks

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


{{DEFAULTSORT:P
Models of computation
Academic programming languages
Experimental programming languages