Назад | Содержание | Вперёд

2. 2.    Сопоставление

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

С другой стороны, дата( Д, М, 1983) и дата( Д1, Ml, 1944) не сопоставимы, как и термы дата( X, Y, Z) и точка( X, Y, Z).

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

       ?-  дата( Д, М, 1983)  =   дата( Д1, май, Y1),
             дата( Д, М, 1983)  =  дата( 15, М, Y).

Для достижения первой цели система припишет переменным такие значения:

        Д  = Д1
        М  =  май
        Y1  =  1983

После достижения второй цели, значения переменных станут более конкретными, а именно:

        Д  =  15
        Д1  =  15
        М  =  май
        Y1  =  1983
        Y  =  1983

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

Общие правила выяснения, сопоставимы ли два терма S и Т, таковы:

(1)    Если S и Т - константы, то S и Т сопоставимы, только если они являются одним и тем же объектом.

(2)    Если S - переменная, а Т - произвольный объект, то они сопоставимы, и S приписывается значение Т. Наоборот, если Т -переменная, а S -произвольный объект, то Т приписывается значение S.

(3)    Если S и Т - структуры, то они сопоставимы, только если

(а)    S и Т имеют одинаковый главный функтор
        и
(б)    все их соответствующие компоненты сопоставимы.

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

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

        треугольник  =   треугольник,
        точка( 1, 1)  =  X,
        А  =  точка( 4, Y),
        точка( 2, 3)  =  точка( 2, Z).

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

        Х  =  точка( 1, 1)
        А  =  точка( 4, Y)
        Z  =  3

В приведенном ниже примере показано, как сопоставление само по себе можно использовать для содержательных вычислений. Давайте вернемся к простым геометрическим объектам с рис. 2.4 и напишем фрагмент программы для распознавания горизонтальных и вертикальных отрезков. "Вертикальность" - это свойство отрезка, поэтому его можно формализовать в Прологе в виде унарного отношения. Рис. 2.8 помогает сформулировать это отношение. Отрезок

Рис.  2. 7.    Сопоставление треугольник(( точка( 1, 1), А, точка( 2, 3)) = треугольник( Х, точка( 4, Y),
точка( 2, Z))

является вертикальным, если x-координаты его точек-концов совпадают; никаких других ограничений на отрезок не накладывается. Свойство "горизонтальности" формулируется аналогично, нужно только в этой формулировке х и y поменять местами. Следующая программа, содержащая два факта, реализует эти формулировки:

        верт( отр( точка( Х, Y), точка( Х, Y1) ) ).
        гор( отр( точка( Х, Y), точка( Х1, Y) ) ).

С этой программой возможен такой диалог:

        ?-  верт( отр( точка( 1, 1), точка( 1, 2) ) ).
        да

        ?-  верт( отр( точка( 1, 1), точка( 2, Y) ) ).
        нет

        ?-  гор( отр( точка( 1, 1), точка( 2, Y) ) ).
        Y  =  1

На первый вопрос система ответила "да", потому. что цель, поставленная в вопросе, сопоставима с одним из фактов программы. Для второго вопроса сопоставимых фактов не нашлось. Во время ответа на третий вопрос при сопоставлении с фактом о горизонтальных отрезках Y получил значение 1.

Рис. 2. 8.  Пример вертикальных и горизонтальных отрезков прямых.

Сформулируем более общий вопрос к программе: "Существуют ли какие-либо вертикальные отрезки, начало которых лежит в точке (2,3)?"

        ?-  верт( отр( точка( 2, 3), Р) ).
        Р  =  точка( 2, Y)

Такой ответ означает: "Да, это любой отрезок, с концом в точке (2,Y), т. е. в произвольной точке вертикальной прямой х = 2". Следует заметить, что ответ пролог-системы возможно будет выглядеть не так красиво, как только что описано, а (в зависимости от реализации) приблизительно следующим образом:

        Р  =  точка( 2, _136)

Впрочем, разница здесь чисто внешняя. В данном случае _136 - это неинициализированная переменная. Имя _136 - законное имя прологовской переменной, которое система построила сама во время вычислений. Ей приходится генерировать новые имена, для того чтобы переименовывать введенные пользователем переменные в программе. Это необходимо по двум причинам: первая - одинаковые имена обозначают в разных предложениях разные переменные; и вторая - при последовательном применении одного и того же предложения используется каждый раз его "копия" с новым набором переменных.

Другим содержательным вопросом к нашей программe является следующий: "Существует ли отрезок, который одновременно и горизонтален в вертикален?"

        ?-  верт( S), гор( S).
        S  =  отр( точка( Х, Y), точка( Х, Y) )

Такой ответ пролог-системы следует, понимать так: "да, любой отрезок, выродившийся в точку, обладает как свойством вертикальности, так и свойством горизонтальности одновременно". Этот ответ снова получен лишь из сопоставления. Как и раньше, в ответе вместо Х и Y могут появиться некоторые имена, сгенерированные системой.

Упражнения

2. 3.    Будут ли следующие операции сопоставления успешными или неуспешными? Если они будут успешными, то какова будет результирующая конкретизация переменных?

    (а)        точка( А, В) = точка( 1, 2)
    (b)        точка( А, В) = точка( X, Y, Z)
    (c)        плюс( 2, 2) = 4
    (d)        +( 2, D)= +( Е, 2)
    (е)        треугольник( точка( -1, 0), Р2, Р3) =
                 треугольник( Р1, точка( 1, 0), точка( 0, Y)

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

Посмотреть ответ

2. 4    Используя представление отрезков, применявшееся в данной разделе, напишите терм, соответствующий любому отрезку на вертикальной прямой x = 5.

Посмотреть ответ

2. 5.    Предположим, что прямоугольник представлен термом прямоугольник( P1, P2, P3, Р4), где Р - вершины прямоугольника, положительно упорядоченные. Определите отношение

        регулярный( R)

которое имеет место, если R - прямоугольник с вертикальными и горизонтальными сторонами.

Посмотреть ответ

Назад | Содержание | Вперёд