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

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

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

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!4t 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)

Рандомно подобранные статьи с сайта:

B3. Типы подчинительной связи: согласование, управление, примыкание.


Похожие статьи:

admin