P′′

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

P′′
Парадигма	Імперативне програмування і структурне програмування
Дата появи	1964
Творці	Corrado Böhm^d

Визначення

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

Синтаксис

1. R і λ — слова.
2. Якщо p і q — слова, то pq — слово.
3. Якщо q — слово, то (q) — слово.
4. Решта послідовностей символів не є словами.

Семантика

1. {a0, a1, ..., an} (n ≥ 1) — алфавіт нескінченної стрічки (аналогічної стрічці машини Тюрінга), a0 — порожній символ.
2. R — перенесення головки стрічки на одну клітинку вправо.
3. λ — замінити поточний символ ai на ai+1 (an замінюється на a0) і перемістити головку на одну клітинку вліво.
4. (q) — повторювати операцію (операції) q, поки значення поточної комірки не дорівнює a0.
5. Операції виконуються зліва направо в порядку їх запису, поки справа нічого не залишиться.

Додаткові факти

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

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