# P′′

(hereafter written **P′′**) is a primitive programming language created by Corrado Böhm ^{1}^{,}^{2} in 1964 to describe a family of Turing machines.

## Syntax

`R`and`λ`are words in P′′.- If
`p`and`q`are words in P′′, then`pq`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′′.

In BNF:
```
<word> ::= R|λ|<word><word>|(<word>)
```

## Semantics

`{a`is the tape-alphabet of a Turing machine with left-infinite tape, a_{0}, a_{1}, ..., a_{n}}(n ≥ 1)_{0}being the*blank*symbol.`R`means move the tape-head rightward one cell (if any).`λ`means replace the current symbol`a`by_{i}`a`(taking_{i+1}`a`), and then move the tape-head leftward one cell._{n+1}= a_{0}`(q)`means iterate`q`in a while-loop, with condition that the current symbol is not`a`._{0}- A program is a word in P′′. Execution of a program proceeds left-to-right, executing
`R`,`λ`, and`(q)`as they are encountered, until there is nothing more to execute.

## Relation to other programming languages

Brainfuck (apart from its I/O instructions) is a simple informal variation of Böhm's P′′. Böhm^{1} gives explicit P′′ programs for each of a set of basic functions sufficient to compute any partial recursive function -- and these programs are constructed entirely from six P′′ words precisely equivalent to the respective Brainfuck commands `+`

, `-`

, `<`

, `>`

, `[`

, and `]`

.

P′′ was the first "goto-less" or "structured programming" language proved^{2} to be functionally equivalent to languages that use gotos.

## Implementation

A Haskell implementation:

{-# LANGUAGE TypeOperators #-} module P'' where import Control.Category ((>>>)) import Control.Lens hiding (Tape) import Control.Monad data Term = R | L | Seq Term Term | Loop Term type Tape = Top :>> [Int] :>> Int -- Run a P'' term over a tape, in an alphabet of size n. -- Returns Nothing if the program moves off the tape. Note -- that directions are flipped; the left-infinite tape is -- implemented as a right-infinite list zipper. runTerm :: Int -> Term -> Tape -> Maybe Tape runTerm n R = leftward runTerm n L = focus %~ (\x -> succ x `mod` n) >>> rightward runTerm n (Seq p q) = runTerm n p >=> runTerm n q runTerm n (Loop p) = \tape -> case tape ^. focus of 0 -> Just tape _ -> runTerm n p >=> runTerm n (Loop p) $ tape -- Run a P'' program over an empty tape. runP'' :: Int -> Term -> Maybe Tape runP'' n p = runTerm n p blankTape where blankTape = zipper (repeat 0) & fromWithin traverse

Example usage: define a program that calculates `n-1`

, then run it and print the first 10 tape elements.

prog :: Term prog = let s = foldr1 Seq in s [L, R, Loop $ s [L, L, R, R]] main :: IO () main = print $ runP'' 256 prog <&> rezip <&> take 10

## References

- Böhm, C.: "On a family of Turing machines and the related programming language", ICC Bull. 3, (July 1964), 187-194.
- 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 seminal paper on the
*structured program theorem*.)

## External resources

- P′′ at Wikipedia describes an explicit example program from Böhm.
^{1} - [
**P′′**online interpreter] demonstrating '99 bottles of beer' in 337568 instructions.