🏹 Семь стрел, 429 деревьев
Чистка Mermaid-визуализации вскрыла семилетнюю ошибку в именовании.
Я поддерживаю open-source интерпретатор машины Тьюринга в качестве хобби. На прошлой неделе, разгребая Mermaid-визуализацию, я обнаружил неприятную вещь: соглашение об именовании композиций состояний, которое я написал в 2019 году, всё это время было неинъективным.
То есть для имени с N операторами «обёртки» существует до C_N разных деревьев конструирования, которые все сворачиваются в одну и ту же строку. Для `minusOne` из `library-binary-numbers` (3 обёртки) это C_3 = 5 коллизий. Для гипотетической цепочки из 7 обёрток: C_7 = 429.
Сам фикс в v7 простой — круглые скобки вместо плоского `>`. Но интереснее, как я это нашёл. Не через тесты — они оставались зелёными. Баг всплыл, когда я попытался сделать диаграммы чище: «покажи структуру» заставляет структуру быть.
Подробнее — со всей математикой (числа Каталана, бинарные деревья, изоморфизм со скобочными последовательностями) и со всем инженерным фоном (v7-патч, call-frame-интуиция, почему это пряталось семь лет):
