P′′ — низькорівнева мова програмування, яку створив 1964 року Коррадо Бьом.
Визначення
P′′ формально визначено як набір слів алфавіту з 4 інструкцій {R, λ, (, )} так:
Синтаксис
- R і λ — слова.
- Якщо p і q — слова, то pq — слово.
- Якщо q — слово, то (q) — слово.
- Решта послідовностей символів не є словами.
Семантика
{a0, a1, ..., an} (n ≥ 1)
— алфавіт нескінченної стрічки (аналогічної стрічці машини Тюрінга), a0
— порожній символ. - R — перенесення головки стрічки на одну клітинку вправо.
- λ — замінити поточний символ
ai
на ai+1
(an
замінюється на a0
) і перемістити головку на одну клітинку вліво. - (q) — повторювати операцію (операції) q, поки значення поточної комірки не дорівнює
a0
. - Операції виконуються зліва направо в порядку їх запису, поки справа нічого не залишиться.
Додаткові факти
- P′′ — перша повна за Тюрінгом мова програмування без оператора GOTO.
- Команди мови Brainfuck (за винятком введення і виведення) можна перекласти на P′′ і навпаки:
Brainfuck | P′′ |
> | R |
< | L=r'λ |
+ | r=λR |
- | r'=rrrrr...rr (n разів) |
[ | ( |
] | ) |