Переменные и унификация

Урок про то, почему X = 5 в Prolog — это вопрос «можно ли сделать X и 5 одинаковыми?», а не команда «положи 5 в X».

Унификация — это процесс поиска такой подстановки значений вместо переменных, при которой два терма становятся синтаксически одинаковыми.

Если вы пришли из Python, Java или C, слово «переменная» обманет вас. Там переменная — это ящик, в который кладут значение, а оператор = командует «положи». В Prolog всё иначе, и пока вы это не прочувствуете, язык будет казаться нелогичным. Этот урок — про самый важный механизм Prolog. Понять его — значит понять половину языка.

Зачем это нужно

Prolog не выполняет команды по шагам — он доказывает утверждения. Когда вы задаёте цель, система пытается сделать её истинной, подбирая значения переменных так, чтобы всё сошлось. Этот подбор и есть унификация. Она работает и при сопоставлении вопроса с фактами в базе, и при передаче аргументов в правила, и в обычных целях вроде X = 5. Один механизм пронизывает весь язык — поэтому разобраться в нём стоит основательно.

Переменные пишутся с большой буквы

В Prolog имя, начинающееся с заглавной буквы или с подчёркивания, — это переменная. Имя со строчной буквы — это атом (константа). Это синтаксическое правило, без исключений.

X        % переменная
Result   % переменная
_x       % переменная (начинается с _)
malina   % атом (константа)
ann      % атом
42       % число

Поэтому likes(ann, malina) — это факт о двух конкретных константах, а likes(X, malina) — это шаблон «кто-то любит малину», где X ещё предстоит найти.

Унификация — это не присваивание

Оператор = в Prolog НЕ присваивает. Он спрашивает: «можно ли сделать левый и правый термы одинаковыми, подобрав значения переменным?» Если да — переменные связываются и цель успешна; если нет — цель проваливается.

?- X = 5.
X = 5.            % да: связали X с 5

?- 5 = 5.
true.            % да: уже одинаковы, связывать нечего

?- 5 = 6.
false.           % нет: разные константы, никак не уравнять

Последняя строка показывает суть: 5 = 6 — это не ошибка и не присваивание, это ложное утверждение. Унификация просто не нашла способа уравнять термы.

Две переменные тоже унифицируются

Можно унифицировать переменную с переменной. Тогда они становятся «связанными вместе»: что узнаем про одну, то узнаем и про другую.

?- X = Y.
X = Y.           % теперь X и Y — это одно и то же неизвестное

?- X = Y, Y = 7.
X = 7,
Y = 7.           % связали Y с 7 — и X автоматически стал 7

Заметьте: мы нигде не «присваивали X = 7». Значение «протекло» в X через то, что X и Y были унифицированы раньше. Это и значит — связывание, а не присваивание.

Унификация по структуре

Самое мощное — унификация составных термов. Два составных терма унифицируются, если у них одинаковый функтор, одинаковое число аргументов, и аргументы попарно унифицируются.

?- f(X) = f(a).
X = a.           % функторы f/1 совпали, осталось X = a

?- point(X, 3) = point(1, Y).
X = 1,
Y = 3.           % сопоставили по позициям

?- f(a) = g(a).
false.           % разные функторы f и g — не уравнять

Так Prolog «распаковывает» данные: одной строкой point(X, 3) = point(1, Y) мы и проверили форму терма, и вытащили из него значения.

Оператор \= — «не унифицируются»

Парный оператор \= успешен, когда два терма не могут быть унифицированы. Он ничего не связывает — только проверяет.

?- 5 \= 6.
true.            % верно: 5 и 6 уравнять нельзя

?- a \= a.
false.           % a и a унифицируются, значит \= ложно

?- X \= 5.
false.           % X можно унифицировать с 5, значит \= ложно

Последний пример коварен: свободную переменную всегда можно унифицировать с чем угодно, поэтому X \= 5 при несвязанном X ложно. \= проверяет возможность унификации прямо сейчас, а не «всегда ли они разные».

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

Внутри унификация — это рекурсивный алгоритм сопоставления двух термов. Упрощённо он работает так:

• Если один из термов — несвязанная переменная, она связывается с другим термом (запись об этом кладётся в trail, чтобы потом откатить при backtracking).
• Если оба — одинаковые атомы или одинаковые числа, успех.
• Если оба — составные термы, сравниваем функторы и арность; при совпадении рекурсивно унифицируем аргументы по позициям.
• Иначе — провал.

   point(X, 3)   =   point(1, Y)
        |                 |
   функтор point/2 == point/2  ✓
        |                 |
      X = 1   ──┐   ┌──  3 = Y
                ▼   ▼
            X=1, Y=3   (успех)

Важная деталь: классический Prolog по умолчанию НЕ делает «occurs check» (проверку, что переменная не входит в терм, с которым связывается). Поэтому X = f(X) создаёт бесконечный (циклический) терм вместо честного провала — это особенность реализации ради скорости.

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

• Считать = присваиванием. X = X + 1 НЕ увеличивает X. Это попытка унифицировать X с термом +(X, 1) — и она проваливается (или зацикливается). Для арифметики есть отдельный оператор is, о нём — в другом разделе.
• Ждать переприсваивания. Связанная переменная связана навсегда в рамках текущего доказательства. Если X = 3 уже сработало, то следующее X = 4 провалится — нельзя «перезаписать» X в 4.
• Путать имена. Область видимости переменной — одно правило/один запрос. X в одном правиле и X в другом — разные переменные.
• Думать, что \= «запоминает» неравенство. Он лишь проверяет текущую невозможность унификации, ничего не откладывая на будущее.

Итоги

• Переменные в Prolog начинаются с заглавной буквы или _; имена со строчной — это атомы.
• Унификация — поиск подстановки, делающей два терма одинаковыми. Это сопоставление, а не присваивание.
• = унифицирует и связывает переменные; 5 = 6 — просто ложь, а не ошибка.
• Составные термы унифицируются по функтору, арности и аргументам — так данные «распаковываются».
• Переменная связывается один раз в рамках доказательства; переприсваивания нет.
• \= успешен, когда термы нельзя унифицировать прямо сейчас.