P′′

\mathcal{P}^{\prime\prime} (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 ==
* {a0, a1, ..., an}(n ≥ 1) is the tape-alphabet of a Turing machine with left-infinite tape, a0 being the blank symbol.
* R means move the tape-head rightward one cell (if any).
* λ means replace the current symbol ai by ai+1 (taking an+1 = a0), and then move the tape-head leftward one cell.
* (q) means iterate q in a while-loop, with condition that the current symbol is not a0.
* 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öhm1 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 proved2 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
* [interpreter] demonstrating '99 bottles of beer' in 337568 instructions.
Category:Languages
Category:Turing complete
Category:Turing tarpits
Category:Low-level
Category:Cell-based
Category:Implemented
Category:Brainfuck
Category:Before 1993