Согласование

В предыдущем разделе было показано, как могут использоваться термы для пред­ставления сложных объектов данных. Наиболее важной операцией с термами является согласование. Даже одно только согласование позволяет выполнять некото­рые интересные вычисления.

Если даны два терма, то можно утверждать, что они согласуются, если выполне­ны следующие условия.

1. Они являются идентичными.

2. Переменные в обоих термах можно конкретизировать значениями объектов таким образом, чтобы после подстановки этих объектов вместо переменных термы стали идентичными,

Например, термы date [ D,.4, 2001) ndate(Dl, may, Y1) согласуются. Ниже показана одна конкретизация, при которой оба терма становятся идентичными.

• D конкретизируется значением D1,

• К конкретизируется значениемтау.

• Y1 конкретизируется значением 2001.

Этот вариант конкретизации можно записать более компактно в знакомой форме, в которой Prolog выводит результаты:

D - D1

М = may Y1 = 2001

С другой стороны, термы date (D, М, 2001) и date (Di, Ml, 1444) не согла­суются; то же самое касается термов date [ X, Y, Z) и point (X, Y, Z),

Согласованием называется процесс, в котором в качестве входных данных берутся два терма и выполняется проверка того, являются ли они согласованными. Если термы не согласуются, это означает, что процесс согласования оканчивается неуда-

Часть I. Язык Prolog

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

Снова рассмотрим пример согласования двух дат. Запрос на выполнение этой опе­рации можно передать системе Prolog в виде следующего вопроса с использованием знака операции "=":

?- date; D, М, 2001) = datef Dl, may, Yl>.

Выше уже упоминалась конкретизация D = D1, У, = may, Yl = 2001, при ко­торой достигается согласование. Но есть и другие варианты конкретизации, при ко­торых оба терма становятся идентичными. Два из них приведены ниже.

D = 1 D1 = 1

М = may Yl = 2001 D - third Dl = third M = rociy Yl ■ £001

Принято считать, что эти две конкретизации являются менее общими по сравне­нию с первой, поскольку они ограничивают значения переменных D и D1 более жест­ко, чем это необходимо. Для того чтобы оба терма в данном примере стали идентич­ными, требуется лишь предусмотреть применение одинаковых значений D и D1, хотя в качестве этого значения можно использовать что угодно. Согласование в языке Prolog всегда приводит к наиболее общей коккретизации.Таковой является конкре­тизация, которая ограничивает переменные в минимально возможной степени и тем самым оставляет максимально возможную свободу для дальнейшей конкретизации (на тот случай, если потребуется дальнейшее согласование). В качестве примера рас­смотрим следующий вопрос:

?- date! n, н, 2001) = date (Dl, may, Yl), date! D, Ы, 2001) = date! 15, M, Y).

Для достижения первой цели система Prolog конкретизирует переменные сле­дующим образом:

D = D1 И = may П = 2001

После достижения второй цели конкретизация становится более определенной, как показано ниже.

D = 15 D1 = 15

М - may

Yl - 2001 Y = 2001

Этот пример также показывает, что в ходе последовательного достижения цели переменные обычно конкретизируются все более определенными значениями. Ниже приведены правила определения того, согласуются ли два терма, S и 1.

1. Если 3 и Т являются константами, то они согласуются, только если представ­ляют собой одинаковый объект.

2. Если S представляет собой переменную, а Т — нечто иное, то они согласуются и S конкретизируется значением Г. И наоборот, если переменной является Т, то Т конкретизируется значением S.

3. Если S и т являются структурами, то они согласуются, только если выполняют­ся следующие условия:

Глава 2. Синтаксис и значение программ Prolog

а) S и Т имеют одинаковый главный функтор;

б) все их соответствующие компоненты согласуются.

Результирующая конкретизация определяется путем согласования компонентов.

Последнее из этих правил можно проиллюстрировать графически, рассматривая древовидное представление термов, как в примере, показанном на рис. 2.7. Процесс согласования начинается с корня (с главных функторов). Если оба функтора согла­суются, процесс переходит к параметрам и осуществляется согласование пар соответ­ствующих параметров. Итак, весь процесс согласования можно рассматривать как состоящий из показанной ниже последовательности (простых) операций согласования.

triangle = triangle,

point(1,1) = X,

А = point (4 Л! •

point (2,3) = point(2,Z).

triangle

 

triangle

 

Рис. 2.7, Согласование термов запроса txiangletfoint (1,1), й, point (2,3)1 = triangle { X, poxnt!4_t Y), point (2, Z))

Весь процесс согласования завершается успешно, поскольку успешными оказы­ваются все операции согласования в этой последовательности. Результирующая кон­кретизация выглядит следующим образом:

х = point [1,1)

А = point (A,'i) Z = 3

Следующий пример показывает, что даже одна только операция согласования может использоваться для выполнения некоторых интересных вычислений. Вернем­ся к примеру простых геометрических объектов (см. рис, 2,4) и определим фрагмент программы для распознавания горизонтальных и вертикальных отрезков прямых. Вертикальность' является свойством отрезков, поэтому такое свойство можно фор­мализовать в языке Prolog как унарное отношение. Пример, приведенный на рис. 2.8, позволяет понять, как следует формализовать это отношение. Отрезок явля­ется вертикальным, если координаты х его конечных точек равны; никакие иные ог-

Часть I. Язык Prolog

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

vertical (seg (point (X,Y), point (X, YD).

horizontal(segl point (X,Y), point(XI,Y)).

po1nt{X,Y1)