Ненормальное марковское программирование

Какие программы могут быть по-настоящему достойны хаба "ненормальное программирование"?

Конечно же, программы для нормальных марковских алгорифмов! (Далее - НАМ).

Но, будем честны перед собой: абстрактные машины - очень просты в реализации. Зачастую вызов состоит в том, чтобы сделать какую-нибудь эзотерическую версию, язык для машины на минималках, и затем ещё и минимизировать транслятор для него.

Поэтому поставим задачу со звёздочкой: научимся писать для НАМ в компайл-тайме С++!
(Далее - компайл-тайм - КТ, рантайм - РТ)

Историческое отступление

Эту задачу я придумал себе ещё в прошлом году. Сразу же с примерным планом, как я буду её делать на безумном C++. Это был бы компактный иллюстратор простеньких магических техник.

Но по мере написания кода, и написания текстов, и написания тестов, и обсуждений с коллегами (на RSDN), и добавления фич, - проект стал претерпевать заметные изменения. Так, что мне несколько раз пришлось переписать документацию.

Я обнаружил, что некоторые "красивые" решения оказываются ужасно неэффективными. А некоторые советы коллег, из их рабочего кода, - пессимизируют мой код ещё жёстче.

Какие-то базовые извращения с кодом я сохранил в каталоге experimental, а какие-то безжалостно выкинул. Но можно посмотреть по истории коммитов на гитхабе https://github.com/nickolaym/nenormal.

В процесс написания статьи я понял, что, если рассказывать все нюансы, то получается невообразимо длинный текст. Поэтому здесь расскажу только самое главное, и то разобью на несколько частей. А остальная писанина (включая черновики, режиссёрские версии и неудачные дубли) - на гитхабе. Извините :( Иначе мой перфекционист сожрёт моего революционера.

План следующий:

1. познакомимся с НАМ и научимся писать на них программы (в этой части)

2. превозможем неприятности, которые нас ждут в КТ

3. унифицируем с РТ

Нормальные Марковские Алгорифмы

Машина НАМ устроена следующим образом.

• Программа - это последовательность правил подстановки - троек

  • строка поиска

  • строка замены

  • признак "обычное/финальное правило" (то есть: продолжать/остановиться)

• Данные - это строка, над которой выполняется программа

Синтаксис НАМ

Традиционно, правила записываются в такой нотации:

"search" ->  "replace" # обычное правило
"search" ->. "replace" # финальное правило

(или без кавычек, если строки непустые и без пробелов и стрелок)

Расширение синтаксиса

Для наглядности, я введу понятие подпрограмм. По сути, это прото макросы, группирующие одно или несколько правил под произвольным именем.

В окончательную программу они входят как подстановка этого списка правил в соответствующее место единственного общего списка.

Ну и комментарии в классическом стиле # .....

abc:
    "a" -> "b"
    "b" -> "c"

cde:
    "c" -> "d"
    "d" -> "e"

main: # если уж завели подпрограммы, то заведём и главную среди них
    cde
    abc

# общий список
main

Рекурсии не предполагается! Да и смысла в ней нет, потому что это лишь создаст дубликаты правил.

DISCLAIMER

Этот синтаксис - чисто для статьи. В коде на C++ всё построено на обычном синтаксическом дереве C++, где уже сразу есть и строки, и элементарные правила, и подпрограммы любой вложенности. Но без колдунства со стрелочками и точками, просто  RULE("s", "r") и т.п.

(TODO: ещё и парсер забабахать в КТ... ну, это была бы вообще жесть).

Логика работы

За один такт машина

• ищет первое подходящее правило (искомая строка входит в строку данных),

• выполняет замену подстроки (только самое первое вхожение),

• и если правило финальное - завершает работу, а если обычное - уходит на следующий такт

Машина останавливается,

• когда было применено любое финальное правило

• когда ничего не удалось найти (и заменить).

Можно считать, что в конце программы всегда есть правило аварийной остановки "" ->. ""

Попробуем что-нибудь попрограммировать.

Hello world

Программа из единственного правила

"" ->. "hello, world!"

для любой исходной строки просто добавит в её начало "hello, world!" и остановится.

(для любой, потому что, очевидно, пустая строка входит в любую строку, прямо с первой позиции).

Privet mir

Пусть у нас данные - это "hello, world!".

"world" -> "mir"
"hello" -> "privet"

На первом такте будет выполнено самое первое подходящее правило, а не самое левое найденное вхождение. То есть,

1. "hello, world!"

2. "hello, mir!"

3. "privet, mir!"

Порядок имеет значение

Выше нам было неважно, в каком порядке правила сработали, ведь они не влияют друг на друга. Но вот пример, когда это окажется важно.

Применим программу к строке "eeecccaaa":

"a" ->  "B"
"c" ->. "D"
"e" ->  "F"

1. "eeecccaaa" - a/B

2. "eeecccBaa" - a/B

3. "eeecccBBa" - a/B

4. "eeecccBBB" - c/D, стоп

5. "eeeDccBBB"

Оказалось, что третье правило вообще не достигнуто.

Разумеется, это не означает "будем до упора применять первое правило, затем до упора второе, и так далее..."

Вот тут у нас будет цикл

"BB"  -> "stop"
"aaa" -> "B"
"a"   -> "aa"

1. "aaaa" - aaa/B - второе правило

2. "Ba" - a/aa - третье

3. "Baa" - a/aa

4. "Baaa" - aaa/B - снова второе

5. "BB" - BB/stop - первое

6. "stop"

Это даёт нам подсказку, как программировать на НАМ.

• Мы должны расставлять правила в порядке их приоритетов

• и можем делать циклы, добавляя-убирая куски строк так, что вышестоящие правила снова подойдут

Правильная скобочная последовательность

Пусть на входе строка, содержащая скобки в произвольном порядке (и ничего, кроме скобок).

Если они сбалансированы, то надо вывести "GOOD", а если нет - то "BAD".

Алгоритм работы:

• сперва сократим все парные скобки: "()" -> ""

• затем приведём все непарные к одному виду:

  • "(" -> "_"

  • ")" -> "_"

• затем сократим всю серию непарных:

  • "__" -> "_"

• затем, если осталась непарная (единственная) - выведем и остановимся

  • "_" ->. "BAD"

• наконец, если ничего не осталось - выведем и остановимся

  • "" ->. "GOOD"

Здесь правила идут в том же порядке, что и наш план работы.

"()" ->  ""
"("  ->  "_"
")"  ->  "_"
"__" ->  "_"
"_"  ->. "BAD"
""   ->. "GOOD"

По сути, программа распалась на последовательность циклов:

• пока есть пары, срабатывает первое правило, дальше не идём

• пока есть открывающие скобки (теперь только непарные), первое правило не срабатывает, но срабатывает второе

• аналогично, пока есть закрывающие

• пока есть несколько подчёркиваний (а скобок больше не осталось), срабатывает четвёртое

• ну и два финала

Мы не можем перемешать правила, но и не хотим.

А что там с проблемой останова?

Ведь НАМ эквивалентны машине Тьюринга.

А на чём бы её проверить? Конечно же, на всеми любимой гипотезе Коллаца!

Последовательность Коллаца

Пусть на входе строка из N единичек, N >= 1. (То есть, будем в единеричной системе счисления работать).

• Если N=1, остановимся.

• Если N чётно, то сократим их вдвое

• Если нечётно - утроим и прибавим единицу.

Последовательный алгоритм выглядит так:

1. Если в строке ровно одна единичка, остановимся "1" ->. "STOP"

2. Проверим чётность (а заодно и поделим пополам)

• добавим в начало строки маркер деления "" -> "[div]"

• и побежим вправо "[div]11" -> "1[div]"

3. Когда маркер добежал до конца строки, там либо ничего не осталось, либо осталась одна единичка.

• если ничего, то просто удалим маркер, "[div]" -> "" и вернёмся к началу

• если единичка, то перейдём к шагу 3 - выполним N*3+1

4. Выполним утроение, с учётом того, что слева (N-1)/2 единичек, а справа 1

• учтём, что N*3+1 = (N-1)/2*6 + 4

• запустим новый маркер "[div]1" -> "[mul]1111"

• и побежим влево "1[mul]" -> "[mul]111111"

5. Когда маркер добежал до начала строки, просто удалим его "[mul]" -> "" и вернёмся к началу

stop:         "1"       ->. "STOP"
div_start:    ""        ->  "[div]"
div_continue: "[div]11" ->  "1[div]"
div_end:      "[div]"   ->  ""
mul_start:    "[div]1"  ->  "[mul]1111"
mul_continue: "1[mul]"  ->  "[mul]111111"
mul_end:      "[mul]"   ->  ""

но очевидно же, что если собрать их в таком порядке, то мы мгновенно остановимся и получим строку вида "STOP111111одинодинодин!!!" (шучу, просто "STOP11111")

Поэтому stop должно быть в самом конце.

Тогда очевидно, что div_start нельзя делать первым, иначе получим взрыв "[div][div][div].....111"

И так далее. Фактически, нам нужно перевернуть весь алгоритм задом наперёд.

Но не совсем! Например, если мы поместим mul_end перед mul_continue, то просто удалим маркер умножения, не добежав до левого края.

По сути, нам надо упорядочить правила так, чтобы искомые НАД-строки предшествовали ПОД-строкам.

mul_continue: "1[mul]"  ->  "[mul]111111"
mul_end:      "[mul]"   ->  ""

div_continue: "[div]11" ->  "1[div]"
mul_start:    "[div]1"  ->  "[mul]1111"
div_end:      "[div]"   ->  ""

stop:         "1"       ->. "STOP"
div_start:    ""        ->  "[div]"

Но вот незадача:

• если мы поместим stop перед div_start, то получим старое доброе "STOP111111одинодинодин!"

• а если наоборот, то зациклимся в 1-4-2-1, потому что всегда будет работать div_start.

  • "1" -> "[div]1" -> "[mul]1111" -> "1111"

  • "1111" -> "[div]1111" -> "1[div]11" -> "11[div]" -> "11"

  • "11" -> "[div]11" -> "1[div]" -> "1"

Решение - запускать деление не с 0, а с 2.

mul_continue: "1[mul]"  ->  "[mul]111111"
mul_end:      "[mul]"   ->  ""

div_continue: "[div]11" ->  "1[div]"
mul_start:    "[div]1"  ->  "[mul]1111"
div_end:      "[div]"   ->  ""

div_start:    "11"      ->  "1[div]"
stop:         "1"       ->. "STOP"
zero:         ""        ->. "ZERO"

Теперь мы даже можем расширить последовательность до неотрицательных чисел! Просто добавим правило zero, соответствующее вырожденному циклу 0 / 2 => 0

Программа заметно перемешалась, и без комментариев и имён в ней сложно разобраться. (Вот поэтому я и добавил метки и подпрограммы...)

Давайте теперь мысленно оттрассируем.

3 - 10 - 5 - 16 - 8 - 4 - 2 - 1 - STOP

Мы умеем делать вычисления в единеричной системе счисления!

Как ещё можно программировать?

Определённую головную боль доставляет распознавание начала и конца строки.

У НАМ нет метасимволов ^ и $, но программисту подконтрольна спецификация на формат входных данных.

Для каких-либо наших нужд мы можем потребовать, чтобы текст был обрамлён этими символами.

Тот же мини-Коллац: если строка обрамлена, то мы можем вместо хитрого порядка правил ввести уникальные тэги для каждого состояния алгоритма.

Тогда в каждый момент времени подойдёт ровно одно правило, а значит, их порядок неважен!

^$        ->. ZERO
^1$       ->. STOP

^11       -> ^[0][*2+]11 # изолировали маркер начала и запустили цикл деления
[*2+]11   -> 1[*2+]      # цикл деления (слева направо)

[*2+]$    -> [+]$        # закончили деление: чётное - запустили цикл сложения
1[+]      -> [+]1        # цикл сложения (справа налево)
^[0][+]   -> ^           # закончили сложение и убрали изолятор

[*2+]1$   -> [*6+]1111$  # закончили деление: нечётное - запустили цикл умножения
1[*6+]    -> [*6+]111111 # цикл умножения (справа налево)
^[0][*6+] -> ^           # закончили умножение и убрали изолятор

(Я намеренно не стал оптимизировать эту программу).

Строка данных в общем случае принимает один из следующих видов

• ^11111$ - N единиц - основное состояние

• ^[0]1111[*2+]11111$ - N = 0 + D*2 + R

• ^[0]1111[*6+]11111$ - N' = 0 + D*6 + R 

то есть, мы как бы уже выполнили деление или умножение, и просто занимаемся эквивалентными преобразованиями.

Красиво же?

Десятичный Коллац

Научившись арифметике в единеричной системе, можем попробовать свои силы и в десятичной.

Например, умножение на константу - это такой же забег справа налево, с переносом.

Но программа при этом заметно распухнет, потому что нам нужно обработать все сочетания (цифра, перенос).

0[*3+0] -> [*3+0]0  # 00
1[*3+0] -> [*3+0]3  # 01
2[*3+0] -> [*3+0]6  # 01
3[*3+0] -> [*3+0]9  # 01
4[*3+0] -> [*3+1]2  # 12
5[*3+0] -> [*3+1]5  # 15
6[*3+0] -> [*3+1]8  # 18
7[*3+0] -> [*3+2]1  # 21
8[*3+0] -> [*3+2]4  # 24
9[*3+0] -> [*3+2]7  # 27

0[*3+1] -> [*3+0]0  # 01
...
9[*3+1] -> [*3+2]8  # 28

1[*3+2] -> [*3+0]5  # 05
...
9[*3+2] -> [*3+2]9  # 29

# когда кончились старшие разряды, - оставляем перенос
[*3+0]  ->
[*3+1]  -> 1
[*3+2]  -> 2

Деление на константу должно происходить "лесенкой", слева направо, но к счастью, в десятичной системе деление на 2 - это умножение на 5 с одним сдвигом.

0[/2]   -> [*5+0]   # частное кладём в перенос
2[/2]   -> [*5+1]
4[/2]   -> [*5+2]
6[/2]   -> [*5+3]
8[/2]   -> [*5+4]

0[*5+0] -> [*5+0]0  # обычное умножение на 5 с переносом
1[*5+0] -> [*5+0]5
.....
8[*5+4] -> [*5+4]4
9[*5+4] -> [*5+4]9

Полностью это выглядит так.
Пусть на каждом шаге последовательности строка имеет вид "111^12345$", где 111 - это счётчик шагов последовательности, а 12345 - текущее значение.
Начинаем вообще без счётчика, "^12345$".
Когда дойдём до финиша, уберём "^1$" и оставим только счётчик - за сколько шагов достигли 1.

# начало - изолируем конец строки символом !, чтобы не было гонки стартов
# и по признаку чётности решаем, будем ли мы делить на 2 или умножать на 3 +1
start:
  0$ -> 0[/2]!$
  1$ -> 1[*3+1]!$
  2$ -> 2[/2]!$
  3$ -> 3[*3+1]$
  ...
  9$ -> 9[*3+1]!$

# деление на 2
div2:
  0[/2] -> [*5+0]
  2[/2] -> [*5+1]
  ...
  8[/2] -> [*5+4]

# умножение на 3 и 5 с переносом
mul3:
  0[*3+0] -> [*3+0]0
  0[*3+1] -> [*3+0]1
  ...
  9[*3+1] -> [*3+2]8
  9[*3+2] -> [*3+2]9

mul3stop:
  ^[*3+0] -> (inc)^
  ^[*3+1] -> (inc)^1
  ^[*3+2] -> (inc)^2

mul5:
  0[*5+0] -> [*5+0]0
  0[*5+1] -> [*5+0]1
  ...
  9[*5+3] -> [*5+4]8
  9[*5+4] -> [*5+4]9

mul5stop:
  ^[*5+0] -> [+1]^
  ^[*5+1] -> [+1]^1
  ...
  ^[*5+4] -> [+1]^4

# когда умножение закончено, инкрементируем счётчик
inc:
  0[+1] -> 1
  1[+1] -> 2
  ...
  8[+1] -> 9
  9[+1] -> [+1]0
  # если нуля вообще не было (на первом шаге)
  [+1]  -> 1

# когда все действия одного шага выполнены, убираем изолятор
restart:
  !$ -> $

# в конце концов, стираем значение и останавливаем работу
finish:
  # если счётчик уже есть (проверяем по наличию младшего разряда) 
  0^1$ ->. 0
  1^1$ ->. 1
  ...
  9^1$ ->. 9
  # тот случай, если мы сразу начинали с 0 или 1 и не успели создать счётчик
  ^1$ ->. "0"
  ^0$ ->. "0"

main:
  # проверка конца последовательности идёт первой
  finish
  # правила рабочего цикла независимы, можем расположить как угодно
  start
  div2
  mul3
  mul3stop
  mul5
  mul5stop
  inc
  # рестарт цикла - строго в конце
  restart

Некоторые шаги можно склеить (начало умножения-деления), но я оставил их для наглядности.

Десятичное сложение

Научившись делать одноместные операции (а умножение на константу - одноместное), попробуем двуместные. Например, сложение.

Пусть входные данные выглядят так: "xxxxx+yyyyy=" (произвольной и необязательно одинаковой разрядности), и мы хотим получить "zzzzz".

Алгоритм

Пусть исходная строка "Xx+Yy=", где X и Y - цепочки старших разрядов, а x и y - одиночные младшие разряды

1. Возьмём младший разряд x и перенесём его рядом к y

2. Найдём (x+y) = z или 1z (то есть, с переносом)

3. Вынесем z направо, и распространим перенос влево по Y, если это нужно

(кстати, мы же понимаем, что перенос - это частный случай умножения, на 1).

Будем повторять, пока не кончатся X и-или Y.

Один такт сложения разрядов - это преобразование строк

• было "Xx+Yy=R" где R - ранее вынесенные разряды суммы

• стало "X+U=zR" где z = (x+y) mod 10, c = (x+y) div 10, U = Y+c

Математически это означает следующее

"XXXXXx           +  YYYYYy           =              RRR" - было
(X*10+x)*10^n     + (Y*10+y)*10^n     +              RRR
 X      *10^(n+1) +  Y      *10^(n+1) + (x+y)*10^n + RRR
 X      *10^(n+1) + (Y+c   )*10^(n+1) +  z   *10^n + RRR
"XXXXX            + uUUUUU            =  z           RRR" - стало

В конце у нас возможны три ситуации:

• "+=ZZZZZ" - числа одинаковой разрядности (с учётом переноса в Y) были сложены

• "XXX+=ZZZZZ" - Y кончился, слева старшие разряды X, справа - младшие разряды Z

• "+YYY=ZZZZZ" - X кончился, слева старшие разряды Y, справа - младшие разряды Z

Просто выбросим знаки + и =, тем самым, склеим (X+0)*10^n + Z или (0+Y)*10^n + Z.

Реализация

Не буду здесь расписывать всю программу, покажу лишь эскиз. С метасимволами x, y и т.п., обозначающими цифры.

take_digit:
    "x+"   ->  "+[x]"

move_digit_to_the_right:
    "[x]y" ->  "y[x]"

add_digits:
    "y[x]=" ->  "=z"  # если x+y < 10, z = (x+y)
    "y[x]+" ->  "^=z" # если x+y >= 10, z = (x+y) mod 10

add_carry:
    "y^"    ->  "u"   # если y+1 < 10, u = u+1
    "y^"    ->  "^u"  # если y+1 >= 10, u = (u+1) mod 10
    "+^"    ->  "+1"  # добежали до левого края, там мысленный старший 0

plus_nothing:
    "x+="  -> ""      # особый случай: справа кончились разряды

cleanup:
    "+"     ->  ""
    "="     ->  ""

that_s_all:
    ""      ->. ""    # для приличия, добавим явную остановку

main:  # правила должны идти в таком порядке, чтобы не устраивать гонки!
    # эти три группы независимы, их можно перетасовать как угодно
    move_digits_to_the_right
    add_digits
    add_carry

    # начало сложения очередного разряда (только когда закончили с предыдущим)
    plus_nothing   # сперва обработаем особый случай
    take_digit

    # к этому моменту мы сложили все разряды, осталось склеить голову и хвост
    # (убрать лишние значки)
    cleanup

    # когда всё сделано, перейдём в финальное состояние
    that_s_all

Продолжение следует!...

В следующей части - магия компайл-тайма.