Три ипостаси машины Тьюринга: объект, граф, поведение

В @turing-machine-js/machine я сделал то, чего давно хотел: машину состояний можно сериализовать в Mermaid-диаграмму и собрать обратно. toGraph превращает машину в граф, toMermaid — в текст диаграммы; fromMermaid и fromGraph проходят путь назад. Диаграмма и машина стали взаимозаменяемы: можно нарисовать, отредактировать, сохранить — и восстановить рабочую машину.

И сразу захотелось регрессионный тест: прогнать машину через round-trip и проверить, что на выходе — та же машина. Вот на слове «та же» всё и завертелось.

Побайтово? Нет: id узлов — это runtime-id инстансов, и fromGraph назначает их заново. Той же структуры? Иногда да, иногда нет — смотря как устроена композиция. Так же себя ведёт? Это вообще другая проверка, графа она не касается.

Оказалось, «та же» — не один вопрос, а три, и на каждый отвечает своё API. Эти три ответа я добавлял в библиотеку годами, по одному, и долго не проговаривал себе, что это три отдельные границы, а не один растяжимый «equals». Объект, граф, поведение — три ипостаси одной машины, и в плоской машине они дают один и тот же ответ. Композиция — место, где ответы расходятся. Дальше — про то, что у движка для этого есть, где проходят границы и как v7 уложила две ипостаси из трёх в форму графа, оставив для третьей отдельную функцию equivalentOn.

Что у движка вообще есть?

Прежде чем разводить три ипостаси, нужен инвентарь.

В движке три слоя, на которые ложится вопрос «а та же ли машина?»:

Объекты времени исполнения. State — узел графа машины. У него есть имя, переходы (на каждый возможный символ ленты — следующее состояние, что писать, куда двигаться), и идентичность: два разных State — это два разных объекта, как бы ни выглядели их таблицы переходов.

Граф как сериализация. State.toGraph(state, tapeBlock) обходит достижимые состояния и возвращает Graph — обычные данные: узлы с именами и переходами, индексированные числовыми id. State.fromGraph(graph) принимает граф и собирает машину обратно: {start, tapeBlock, states}. Поверх графа — toMermaid(graph) и fromMermaid(text), отображение в синтаксис Mermaid flowchart и обратно. Парсер строгий: принимает только то, что эмиттер выпускает.

Поведенческая эквивалентность. equivalentOn(reference, candidate, cases) в utilities/equivalence.ts — запускает обе машины на тестовых лентах, сравнивает выходы и снимки на каждом шаге. Отдельный модуль, ничего не знает про граф.

Три слоя — три вопроса «те же ли?». Дальше — про то, как они расходятся.

Плоская машина: простой случай

У плоской машины — без композиции — все три ипостаси совпадают.

Объектно: один State равен другому, если это тот же экземпляр (===). Это базовая семантика JavaScript, ничего движок к ней не добавляет.

Графово: возьмите toGraph, прогоните через JSON туда-обратно, восстановив через fromGraph — полу́чите двойник с теми же именами и переходами. Совпадение не байт-в-байт, а с точностью до переименования id: id узлов — это runtime-id инстансов, и при пересборке через fromGraph они назначаются заново. В репозитории есть регрессионный тест на это (turing-machine-js#139). Проверяет не «выглядит так же», а «имеет ту же структуру».

Поведенчески: equivalentOn прогонит обе машины по тестовым лентам и подтвердит «да, отработали одинаково».

Простой случай. Все три ипостаси совпадают, потому что нет места, где они могли бы разойтись. Но место расхождения есть — композиция.

Композиция: где становится интересно

Композиция в движке выглядит так:

const wrapper = baseState.withOverriddenHaltState(overrideState);

Новое состояние-обёртка wrapper делегирует поиск переходов своему baseState, но подменяет halt-выход: вместо остановки машины — переход в overrideState.

Концептуально обёртка — это «выполнить базовое состояние как подпрограмму, на выходе перейти в overrideState». Имя композиции строится по правилу: для базы с именем A и оверрайда с именем B обёртка получает имя A(B). О том, как и почему именно это имя — отдельная статья «Семь стрел, 429 деревьев» (1).

Здесь начинают расходиться три ипостаси.

Объектно: обёртка и база — два разных State. wrapper !== baseState. Это следствие того, что withOverriddenHaltState возвращает новый экземпляр.

Графово: обёртка своих переходов не имеет. Они живут на базе. Если визуализировать граф, обёртка — это узел с делегированием, не с переходами.

Поведенчески: обёртка и база не эквивалентны. У них разный halt-выход. На любом входе трейс совпадает шаг в шаг вплоть до halt-выхода базы — и расходится ровно в этот момент.

Обёртка существует как самостоятельный объект ровно для того, чтобы хранить эту подмену. Дальше вопрос: как уложить её в граф, чтобы fromGraph сумел её восстановить?

Как композиция попадает в граф

Мне нужно было, чтобы граф сам нёс композицию, — это убивало двух зайцев. Во-первых, fromGraph восстанавливает машину прямо из структуры, а не угадывает композицию по runtime-подсказке. Во-вторых, граф остаётся читаемым: композиция видна на самой диаграмме, а не растворяется в плоском списке переходов. В v7 (turing-machine-js#180) обёртка эмитируется двумя узлами:

• Узел-обёртка — call-site без переходов, форма [[wrapper-name]], поле bareStateId указывает на базу.
• Узел базы — обычный узел с переходами, форма [baseState-name], помещённый внутрь Mermaid subgraph «callable subtree of NAME».

Целиком, на примере scanToX(eraseHere):

Этого достаточно, чтобы fromGraph восстановил обёртку по структуре: вот call-site, вот база, на которую он ссылается. Граф кодирует композицию, а не намекает на неё.

Под капотом (можно пропустить). Halt-выход каждого frame-а — отдельный узел isHaltMarker с id = -frameId; в рантайме он сворачивается в синглтон haltState, но на графе живёт отдельно, иначе вся машина «втягивается» в один halt-узел. Когда одна база достижима из нескольких обёрток, frame-ы считаются union-find по достижимости баз (подпись subgraph — «callable subtree of A» или «callable scope: A ∪ B»). Начало машины помечено служебным idle([idle]) с пунктирной enter-стрелкой — якорь, по которому парсер находит стартовое состояние. Метки переходов записаны по простому шаблону [reads] → [writes]/[moves] — по ячейке на ленту.

Та же машина после round-trip?

Для простой композиции — одна обёртка, одна база, дерево не пересекается с другими — round-trip воспроизводи́м с точностью до переименования id. Граф хранит узлы, имена, переходы; fromGraph собирает ту же машину обратно. Композитное имя scanToX(eraseHere) в граф попадает — это подпись узла-обёртки, — но fromGraph его не читает: композитное имя он пересобирает заново из базы и оверрайда, через единственное разрешённое место мутации имени, Symbol-accessor STATE_INTERNAL (turing-machine-js#180). Поэтому накопления имён не происходит: на каждой пересборке имя считается из структуры, а не наращивается поверх предыдущего. Ровно это и проверяет регрессионный тест на простые обёртки.

Ломается воспроизводимость на общей базе — когда один и тот же State служит базой сразу нескольким обёрткам. Не выдумка: в library-binary-numbers алгоритм minusOne устроен так, что invertNumber оказывается базой двух обёрток, внешней и внутренней (полный граф). Один объект, два call-site.

Структуру это не ломает: toGraph обходит достижимые состояния ровно раз, по id инстанса, поэтому общая база — это один узел, а две обёртки просто ссылаются на него двумя стрелками; fromGraph восстанавливает ровно один общий инстанс на обе обёртки. Сама общая база переживает round-trip. А вот воспроизводимость сериализации — нет: повторная пересборка может дать граф, который не сводится к исходному, даже если закрыть глаза на id.

Та же форма в миниатюре, на scanToX — одна база под двумя обёртками:

Под капотом (можно пропустить). Id узлов — это runtime-id инстансов, fromGraph назначает их заново. «Воспроизводимо» здесь значит: сериализовать, пересобрать, сериализовать снова и сравнить два графа, игнорируя сами значения id. У простой обёртки повторный toGraph даёт ту же раскладку с точностью до переименования. В случае с общей базой, например одной на две обёртки, id после пересборки могут идти в другом порядке, а узлы эмитируются отсортированными по id — раскладка съезжает, и закрытие глаз на id уже не помогает.

И вот тут граф перестаёт быть тем ответом, на который стоит опираться. Зато equivalentOn на обеих машинах даёт allAgree: true: по поведению — та же. Граница простая: воспроизводимость сериализации — только на простых обёртках, поведенческая эквивалентность — всегда.

Где живёт equivalentOn

equivalentOn(reference, candidate, cases) живёт в utilities/equivalence.ts. reference и candidate — это Runnable ({ state, getTapeBlock }), cases — массив тестовых входов; функция запускает обе машины, сравнивает выходы и снимки на каждом шаге и возвращает отчёт { results, allAgree }: пошаговые результаты плюс итоговое «да/нет» в allAgree.

Важно, что он не живёт в utilities/stateGraph.ts, где собраны toGraph/fromGraph. Это разные модули, разные слои библиотеки. equivalentOn ничего не знает про граф; ему всё равно, эмитируется ли обёртка как call-site или как один узел, в каких frame-ах живут переходы. Он смотрит только на наблюдаемое поведение.

Это и есть его роль. Когда воспроизводимость toGraph/fromGraph зыбка (общая база на две обёртки), equivalentOn отвечает на вопрос, который потребителю на самом деле нужен: «после восстановления — это та же машина по поведению?». Граф — это инструмент сериализации; поведение — это контракт.

Ловушка, в которую легко попасть: проверять тождество через === над State-инстансами. После пересборки это даёт false — fromGraph всегда создаёт свежие инстансы, — хотя поведение совпадает. Ложная регрессия на ровном месте. equivalentOn нужен ровно для того, чтобы такого не происходило, — но для этого надо знать, что он есть.

Теги: данные едут с графом, идентичность остаётся локальной

Маленькая, но симптоматичная добавка v7 — теги (turing-machine-js#186). У State появился API: state.tag('hot', 'subroutine-entry'), state.tags, state.untag(...). Теги — это строковые метки на инстансе. Нужны они инструментам поверх машины: toMermaid раскрашивает и группирует по ним узлы через classDef, а потребители вроде post-machine-js помечают ими точки входа подпрограмм. На семантику машины теги не влияют.

Что про них важно для трёх ипостасей:

• Поведенчески — не считаются. equivalentOn теги не смотрит. Машина с тегами и без них на одних и тех же переходах — поведенчески одна и та же.
• Графово — переживают round-trip. GraphNode.tags сериализуется; toMermaid эмитирует теги в подписи узла через <br> и как classDef для цветовой группировки в рендере; fromMermaid читает из подписи (<br> — источник истины, classDef декоративный).
• Объектно — локальны инстансу. Теги живут на конкретном State, не на базе. Две обёртки делят одну базу, но набор тегов у каждой — свой. Пометь одну — и вторая, и сама база останутся без тега.

Хорошая граница: данные, описывающие узел графа, едут с графом; идентичность инстанса остаётся локальной для конкретной сборки. Теги оказываются посередине: для поведения их нет (equivalentOn к ним слеп), но они долговечнее ===-идентичности — та обнуляется на каждой пересборке, а теги едут с графом и переживают round-trip.

Что я в итоге понял

Три ипостаси я не задумывал разом — они набрались по одной, и только задним числом стало видно, что это разные проекции одной сущности, не один растяжимый «equals».

Объектную JavaScript даёт бесплатно: === и instanceof работают сами. Поведенческую я получил почти даром — equivalentOn это просто прогон двух машин на тестах. А графовую пришлось проектировать: без неё fromGraph не восстановил бы из сериализованной машины ничего, и именно ради неё v7 уложила композицию в данные графа.

Две вещи дошли до меня поздно. Биективное именование композиций — не украшение, а условие: пока имена неоднозначны, граф теряет один из видов проверки на «те же» ещё до того, как fromGraph запустится. Об этой же неоднозначности — статья (1). И поведенческая эквивалентность должна жить отдельно от графа: equivalentOn ничего не знает про toGraph, и это правильно — потребителю чаще нужен поведенческий ответ, а не побайтовый round-trip.

А ещё теги подсказали простую проверку: что переживает round-trip — описывает узел графа, что не переживает — описывает конкретный инстанс. Добавляю поле — смотрю, в какую ипостась оно попадает: от этого зависит, в каком смысле оно делает две машины «теми же».

Код: turing-machine-js (движок с v7-графовыми утилитами). Интерактивное демо на demo.machines.mellonis.ru рисует машины через toMermaid и подсвечивает текущий переход.