Декларативность: ЧТО против КАК

Урок показывает радикальное отличие декларативного стиля: вы задаёте отношения, а машина сама ищет, что им удовлетворяет.

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

В прошлом уроке мы увидели идею «ЧТО, а не КАК» на родственных связях. Теперь разберём это отличие предметно: возьмём одну и ту же задачу и решим её сначала в императивном стиле, потом в логическом. Контраст лучше всего показывает, что именно берёт на себя движок вывода.

Одна задача, два мышления

Задача: есть список чисел, нужно проверить, входит ли в него заданное число. В императивном языке мы мыслим процессом: завести индекс, пройтись по элементам, сравнить каждый, вернуть результат. Вот как это выглядит на Python (этот блок исполним — нажмите «Запустить»):

def vhodit(x, spisok):
    for element in spisok:   # КАК: явно перебираем
        if element == x:
            return True
    return False

print(vhodit(3, [1, 2, 3, 4]))
print(vhodit(9, [1, 2, 3, 4]))

Вывод:

True
False

Мы расписали как: цикл, сравнение, ранний выход. А теперь то же отношение «элемент входит в список» на Prolog. Здесь мы описываем что значит «входить»: число входит в список, если оно стоит в голове списка, ИЛИ входит в хвост.

% X входит в список, если X — первый элемент
vhodit(X, [X | _]).
% либо X входит в хвост списка
vhodit(X, [_ | Hvost]) :- vhodit(X, Hvost).

Здесь [X | _] — это шаблон «список, у которого голова X, а хвост нас не интересует» (символ _ — анонимная переменная). Двух коротких правил достаточно. Спросим:

?- vhodit(3, [1, 2, 3, 4]).

Вывод:

true

Мы нигде не написали цикл и индекс. Мы лишь сказали, при каких условиях элемент считается входящим, а перебор хвоста за хвостом сделал движок вывода. Более того, ту же программу можно использовать в другую сторону — попросить выдать все элементы списка по очереди:

?- vhodit(Element, [10, 20, 30]).

Вывод:

Element = 10 ;
Element = 20 ;
Element = 30.

Императивная функция vhodit так не умеет — она отвечает только «да/нет» для конкретного числа. Логическое отношение богаче: оно описывает связь, и спрашивать о ней можно с любой стороны.

Роль движка вывода

Ключевой персонаж декларативного подхода — движок вывода (inference engine). Это встроенная в Prolog машина, которая по вашим фактам и правилам пытается доказать запрос. Вы не управляете ею напрямую; вы лишь поставляете ей знания. Движок делает три вещи: сопоставляет запрос с подходящими правилами (унификация), разбивает цель на подцели и перебирает варианты с откатом назад при неудаче (backtracking).

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

Где декларативность выигрывает

Как работает под капотом

Когда вы спрашиваете vhodit(3, [1,2,3,4]), движок сначала пробует первое правило: можно ли сопоставить 3 с головой списка 1? Нет, 1 \= 3. Тогда он пробует второе правило: «3 входит в хвост [2,3,4]». Это новая, меньшая подцель — рекурсия. Снова первое правило: голова 2 не равна 3. Снова в хвост [3,4]. Теперь голова 3 совпадает — первое правило срабатывает, доказательство завершено. Вот эта «лесенка» спуска в хвост и есть тот цикл, который вы НЕ писали: его породил сам механизм вывода из ваших двух правил.

vhodit(3, [1,2,3,4])
  -> голова 1 != 3, идём в хвост
vhodit(3, [2,3,4])
  -> голова 2 != 3, идём в хвост
vhodit(3, [3,4])
  -> голова 3 == 3, ДОКАЗАНО (true)

Частые ошибки

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

Забывать про базовый случай рекурсии. В отношении vhodit первое правило (элемент — это голова) — база; без него рекурсия по хвосту никогда не остановится на успехе.

Думать, что декларативность бесплатна по скорости. Движок выполняет реальный перебор. Плохо сформулированное отношение заставит его перебирать слишком много вариантов. Декларативность упрощает запись, но не отменяет вычислительную стоимость.

Итог

• Императивный стиль описывает как; декларативный — что должно быть истинно.
• Одно и то же отношение в Prolog работает в обе стороны, а императивная функция — обычно в одну.
• Поиск решения берёт на себя движок вывода: унификация, разбиение на подцели, backtracking.
• Декларативность упрощает запись, но не отменяет стоимость перебора.