Термы, функторы и арность

Урок про то, что в Prolog данные и программа — это одно и то же: и факт, и список, и дерево вычислений — всё построено из термов.

Терм — единственный вид данных в Prolog. Любое выражение — атом, число, переменная или составной терм — это терм.

Понимание термов превращает Prolog из набора магических заклинаний в стройную систему. Когда вы видите, что likes(ann, malina), [1, 2, 3] и 2 + 3 — это всё составные термы одной природы, многое встаёт на места. Этот урок раскладывает термы по полочкам.

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

Prolog умеет рассматривать сам код как данные: разбирать терм на части, строить новый терм на лету, сравнивать структуры. Это основа метапрограммирования и многих стандартных предикатов. Чтобы этим пользоваться, надо знать словарь: что такое функтор, арность, как устроены составные термы и какими инструментами их препарировать.

Четыре вида термов

Атомы и числа вместе называют простыми (атомарными) термами. Составной терм — это «структура»: имя плюс скобки с аргументами.

Функтор и арность: name/N

У составного терма есть две характеристики: функтор (имя, атом перед скобками) и арность (число аргументов). Их записывают вместе как имя/арность.

likes(ann, malina)     → функтор likes, арность 2  → likes/2
point(1, 2, 3)         → функтор point, арность 3  → point/3
foo(a)                 → foo/1

Это не формальность. Для Prolog foo/2 и foo/3 — РАЗНЫЕ предикаты, как будто у них разные имена. Факт foo(a, b) никак не отвечает на запрос foo(a, b, c) — арность не совпала, термы не унифицируются.

foo(a, b).             % это факт про foo/2

?- foo(a, b).
true.

?- foo(a, b, c).       % это запрос про foo/3 — другого предиката нет
false.

Составной терм — это дерево

Любой составной терм удобно представлять как дерево: функтор — корень/узел, аргументы — ветви. Аргументы сами могут быть составными термами, образуя поддеревья.

Возьмём route(point(0, 0), point(3, 4)). Его дерево:

            route/2
            /     \
      point/2    point/2
       /  \        /  \
      0    0      3    4

Кстати, привычный список [1, 2, 3] — это тоже дерево из вложенных составных термов '[|]'/2 (исторически '.'/2): на самом деле это '[|]'(1, '[|]'(2, '[|]'(3, []))), где [] — атом пустого списка. А 2 + 3 — это терм +(2, 3), записанный в инфиксной форме. Операторы — лишь удобный синтаксис поверх обычных составных термов.

Разбор и сборка термов

Оператор =.. (univ)

Оператор =.. (читается «univ») превращает составной терм в список [Функтор | Аргументы] и наоборот.

?- point(1, 2) =.. L.
L = [point, 1, 2].          % разобрали терм в список

?- T =.. [circle, 5].
T = circle(5).              % собрали терм из списка

?- foo(a, b, c) =.. [F | Args].
F = foo,
Args = [a, b, c].

Это и есть метапрограммирование: можно собрать вызов предиката, имя которого вычислено во время работы программы.

Предикаты functor/3 и arg/3

Часто =.. избыточен, и хватает точечных инструментов. functor(Term, Name, Arity) достаёт имя и арность; arg(N, Term, A) достаёт N-й аргумент.

?- functor(point(1, 2), Name, Arity).
Name = point,
Arity = 2.

?- arg(2, point(1, 2), A).
A = 2.                      % второй аргумент

?- functor(T, circle, 1).
T = circle(_).              % собрали «болванку» терма с свежей переменной

Сравнение термов по стандартному порядку

Помимо унификации термы можно сравнивать по фиксированному стандартному порядку. Это синтаксическое сравнение структур, не вычисление.

Важно отличать == от =. = ПЫТАЕТСЯ унифицировать (и может связать переменные). == просто проверяет, идентичны ли термы УЖЕ сейчас, ничего не связывая.

?- X == 5.
false.            % X не связан, он не идентичен 5

?- X = 5, X == 5.
X = 5.            % сначала связали, теперь идентичны — true

?- a @< b.
true.             % атомы сравниваются по алфавиту: a раньше b

?- 1 @< a.
true.             % числа в стандартном порядке идут раньше атомов

Стандартный порядок такой: переменные < числа < атомы < строки < составные термы (составные — сначала по арности, затем по функтору, затем по аргументам слева направо). Этот порядок используют, например, при сортировке предикатом sort/2.

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

Внутри интерпретатора КАЖДЫЙ объект — это терм-структура: тег (что это — переменная, число, атом, составной) и данные. Составной терм хранится как «функтор + массив указателей на аргументы». Поэтому functor/3, arg/3 и =.. — это просто чтение полей этой структуры, операции дешёвые. А унификация, паттерн-матчинг и сравнение работают единообразно именно потому, что под всем — одно представление. В этом красота Prolog: нет отдельных «типов данных» с особым поведением, есть один универсальный терм.

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

• Путать = и ==. = унифицирует и связывает; == лишь проверяет идентичность. X == 5 при несвязанном X — это false, а не связывание.
• Игнорировать арность. foo/2 и foo/3 — разные предикаты. Лишний или недостающий аргумент — и факт «не виден».
• Считать @< числовым сравнением. Это сравнение по стандартному порядку термов, а не по величине. Для чисел по значению используйте <, > (с is/арифметикой).
• Забывать экранировать в записи. При чтении документации помните: @< — это оператор «меньше в стандартном порядке», а не разметка.
• Применять =.. к несвязанному с обеих сторон. Хотя бы одна сторона (терм или список с известным функтором) должна быть достаточно определена, иначе — ошибка инстанцирования.

Итоги

• В Prolog ВСЁ — терм: атомы, числа, переменные и составные термы.
• Составной терм описывается функтором и арностью: name/N; foo/2 ≠ foo/3.
• Составные термы — это деревья; списки и 2 + 3 — тоже составные термы под удобным синтаксисом.
• =.. (univ), functor/3, arg/3 разбирают и собирают термы — основа метапрограммирования.
• == и \== проверяют идентичность без связывания; @<, @> сравнивают по стандартному порядку.
• Под капотом единое представление термов делает унификацию и сравнение единообразными.