Мышление в терминах состояний

Эссе Маркуса Триски (часть книги The Power of Prolog) разбирает стену, в которую упираются новички при переходе от императивных языков к декларативным: "как вообще увеличить переменную?", "как удалить элемент из списка?" Ответ всегда одной формы: перестать думать об изменении состояния и начать думать об отношениях между состояниями.

Переход от мутаций к отношениям

В императивном стиле переменная инкрементируется через i = i + 1. Состояние i меняется, старое состояние исчезает, а декларативно уравнение i = i + 1 бессмысленно - ни одно целое число не равно самому себе плюс один. В Prolog та же мысль превращается в I #= I0 + 1: I и I0 - две разные переменные в отношении эквивалентности. Отношение работает во всех направлениях: связать I0 - получить следующее целое число; связать I - получить предыдущее; оставить обе несвязанными - перечислить варианты.

Мыслительный скачок: две переменные вместо одной в императивном языке, поскольку одна переменная не может отражать два состояния одновременно.

Удаление элемента из списка

Наивная императивная постановка - remove(list, e). Декларативная постановка - это отношение между тремя вещами: списком, элементом и другим списком. Оно выполняется, когда второй список совпадает с первым за вычетом всех вхождений элемента:

list1_element_list2([], _, []).
list1_element_list2([E|Ls1], E, Ls2) :-
        list1_element_list2(Ls1, E, Ls2).
list1_element_list2([L|Ls1], E, [L|Ls2]) :-
        dif(L, E),
        list1_element_list2(Ls1, E, Ls2).

Отношение отвечает на любые запросы: какой элемент был удалён? как выглядит входной список, если выходной - X? для каких троек отношение выполняется? Название remove/3 скрыло бы эту общность. Использование library(reif) и tfilter/3 сворачивает этот предикат в одну декларативную строку.

Состояния в головоломках

Головоломка с кувшинами для воды (8/5/3, налить по 4 в кувшины A и B) делает выбор представления состояния наглядным. Триска показывает версию на Haskell с тройками (Int, Int, Int) и версию на Prolog с использованием термов jug(Name, Fill) с итеративным углублением. Версия на Prolog короче, потому что ходы можно описать единообразно: From и To - переменные, арифметику берёт на себя constraint solver, а структуре не требуется явно перечислять все шесть возможных переливаний.

Тот же шаблон обобщается на другие задачи: волк и коза, головоломка 8-puzzle, Escape from Zurg, миссионеры и каннибалы. Выбор представления состояния, допускающего небольшое отношение между состояниями, важнее выбора стратегии поиска.

Состояния в программах (интерпретатор)

В эссе строится интерпретатор на Prolog для небольшого императивного языка над целыми числами. AST представляют собой термы Prolog: function(Name, Parameter, Body), assign(Variable, Expression), if(Condition, Then, Else), while(Condition, Body) и так далее. Состояние интерпретатора - пара ассоциативных списков (привязки переменных и определения функций), а предикат interpret/3 протаскивает это состояние через вызовы, по одному предложению на каждую форму AST. Каждое предложение определяет отношение между входным и выходным окружением.

Две интересные детали:

• print создаёт побочный эффект, не укладывающийся в модель чистых отношений. Чтобы решить это корректно, пришлось бы протаскивать через окружение представление внешнего мира.
• return выделяется тем, что его результирующее "окружение" - это единственное значение, которое eval/3 забирает при вычислении вызовов функций.

Состояния в компиляторах

Далее в эссе строится компилятор для того же языка, нацеленный на стек-ориентированную VM с инструкциями pushc, pushv, pop, арифметикой, jne/jge/jle, call, ret, print, halt. Состояние компиляции - это кортеж из четырёх элементов s(Is, Fs, Vs, PC): сгенерированные инструкции, смещения функций, смещения переменных в текущей функции и счётчик команд (program counter). Компилятор написан в нотации DCG с полуконтекстом (semicontext notation), благодаря чему состояние передаётся неявно:

state(S), [S] --> [S].
state(S0, S), [S] --> [S0].

state(S) читается как "текущее состояние - S"; state(S0, S) - как "сейчас S0, в дальнейшем S". С этой обвязкой предложения компиляции для каждой конструкции языка становятся почти дословной транслитерацией семантики: vminstr/1 эмитит одну инструкцию и увеличивает PC.

Пример с факториалом показан вместе со скомпилированным байткодом (38 инструкций, включая трамплин jmp 33, перепрыгивающий через тело функции к точке входа).

Почему это важно

Аргументация эссе идёт от вопроса "как мне увеличить переменную" до "как написать компилятор" через один и тот же приём на каждом шаге: выбрать представление состояния, допускающее компактное и общее отношение. Полуконтекстная нотация DCG в Prolog делает протаскивание состояния через отношение почти незаметным, что максимально приближает декларативный код по ощущениям к императивному.

Тема перекликается с no-silver-bullet-llms и обсуждениями декларативного против императивного в message-passing-shared-mutable-state - разные углы одного и того же наблюдения: рассуждать в терминах состояний в масштабе сложнее, чем в терминах отношений.