Prolog против императивного и функционального

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

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

Изучив Prolog, легко решить, что это «странный язык со своими правилами». Но дело не в синтаксисе: Prolog принадлежит к отдельной парадигме, и чтобы писать на нём хорошо, нужно перестроить мышление. Этот урок сравнивает три парадигмы по существу и показывает, когда какая уместна.

Три способа думать о вычислении

Возьмём одну задачу — «вычислить факториал» — и посмотрим, как её формулирует каждая парадигма.

Императивно (C, Python в процедурном стиле) вы описываете шаги: заведи переменную-аккумулятор, крути цикл, на каждом шаге меняй её значение.

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i   # переменная меняется
    return result

print(factorial(5))

Вывод:

120

Функционально (Haskell, чистый стиль) вы описываете что есть результат через функции и рекурсию, без изменяемых переменных: значение либо база, либо выражено через себя на меньшем аргументе.

factorial 0 = 1
factorial n = n * factorial (n - 1)

Логически (Prolog) вы описываете отношение «факториал числа N равен F» как набор правил, а интерпретатор ищет, при каких F отношение выполняется.

factorial(0, 1).
factorial(N, F) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, F1),
    F is N * F1.

Заметьте сдвиг: в Prolog factorial — не функция, возвращающая значение, а отношение между двумя аргументами. У него нет «возвращаемого значения» — есть второй аргумент, который связывается ответом.

Таблица отличий

Ключевые различия по существу

Присваивание против унификации

В императивном языке x = x + 1 — это команда: возьми старое значение, прибавь, перезапиши. Это разрушительное обновление. В Prolog X = 5 — это унификация: попытка сделать две стороны равными. Если X ещё свободна, она связывается с пятёркой; если уже связана с другим — провал. Переменная не «меняется», она получает значение один раз в пределах ветви доказательства.

Цикл против поиска

В императивном коде вы пишете цикл, чтобы перебрать варианты, и сами решаете, когда остановиться. В Prolog перебор вариантов встроен: если у предиката несколько подходящих клауз, интерпретатор пробует их по очереди (backtracking). Вы описываете, что считается решением, а механизм поиска находит все такие решения.

Связь с Haskell: две декларативности

Часто говорят, что и Haskell, и Prolog «декларативны». Это правда, но декларативность у них разная.

• Функциональная декларативность (Haskell): вы описываете что вычислить как композицию функций. Ленивые вычисления откладывают работу до момента, когда результат реально нужен. Но направление одно: из аргументов получается результат. Функция length по списку даёт число, но «по числу восстановить список» она не умеет.
• Логическая декларативность (Prolog): вы описываете отношение между объектами. Механизм — не вычисление функции, а поиск доказательства с унификацией и возвратом. Поэтому многие предикаты обратимы: append(X, Y, [a,b,c]) перечислит все способы разбить список на две части.

Грубо: Haskell — «декларативность через функции и ленивость», Prolog — «декларативность через отношения и поиск». Обе прячут от вас низкоуровневые шаги, но прячут разное.

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

Императивная модель опирается на состояние: память — это изменяемые ячейки, программа последовательно их перезаписывает (модель фон Неймана). Функциональная — на редукцию выражений: вычисление сводит выражение к нормальной форме, подставляя определения функций; неизменяемость гарантирует, что одно и то же выражение всегда даёт один результат. Логическая модель Prolog опирается на SLD-резолюцию: интерпретатор строит дерево доказательства, на каждом шаге унифицирует цель с головой клаузы и при провале откатывается к ближайшей развилке, пробуя следующую альтернативу. Это и есть «поиск», встроенный в язык, — то, что в императивном коде вы писали бы руками как стек и циклы.

Когда какая парадигма уместна

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

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

• Писать Prolog как Си. Попытка «присвоить переменной новое значение» через X = X + 1 всегда провалится — это унификация, а не присваивание.
• Считать предикат функцией. Ожидание «возвращаемого значения» мешает увидеть обратимость и множественные решения.
• Думать, что декларативное = медленное и одинаковое. Декларативность Haskell и Prolog устроена по-разному, и порядок клауз/целей в Prolog всё-таки влияет на эффективность и завершимость.
• Игнорировать backtracking. Новички пишут цикл там, где Prolog сам перебрал бы варианты, и борются с языком вместо того, чтобы его использовать.

Итог

• Три парадигмы — это три способа думать: команды над состоянием, вычисление функций, поиск по отношениям.
• В Prolog нет присваивания и нет «возврата значения»: есть унификация переменных и связывание аргументов.
• Повторение задаётся не циклом, а рекурсией и встроенным backtracking-поиском.
• Haskell и Prolog оба декларативны, но по-разному: функции и ленивость против отношений и поиска доказательства.
• Выбор парадигмы — вопрос задачи: контроль ресурсов, преобразование данных или логический вывод.