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