P′′

P′′ — низкоуровневый язык программирования, созданный в 1964 году Коррадо Бёмом.

Определение

P′′ формально определяется как набор слов алфавита из 4 инструкций {R, λ, (, )} следующим образом:

Синтаксис

1. R и λ — слова.
2. Если p и q — слова, то pq — слово.
3. Если q — слово, то (q) — слово.
4. Остальные последовательности символов не являются словами.

Семантика

1. R — переместить указатель на 1 ячейку вправо (всего существует n+1 ячеек с индексами от 0 до n; начальное положение указателя на ячейке 0; n+1=0).
2. λ — увеличить значение текущей ячейки на 1 и переместить указатель на 1 ячейку влево (0-1=n).
3. (q) — повторять операцию (операции) q, пока значение текущей ячейки не равно 0.
4. Операции выполняются слева направо в том порядке, в котором они записаны, до тех пор, пока справа ничего не останется.

Дополнительные факты

1. P′′ — первый полный по Тьюрингу язык программирования без оператора GOTO.
2. Команды языка Brainfuck (за исключением ввода и вывода) могут быть переведены на P′′ и обратно:

Brainfuck	P′′
>	R
<	L=r'λ
+	r=λR
-	r'=rrrrr...rr (n раз)
[	(
]	)