Логическое программирование. Элементы и конструкции языка Турбо-Пролог. Средства отладки Турбо-Пролога, страница 8

Замечание: порядок расположения целей в разделе goal и подцелей в правилах определяет действия Турбо-Пролога.

4. Унификация и поиск с возвратом

Рассмотрим пример описания схемы родственных отношений, представленной на рис.2.

Рис.2. Схема родственных отношений.

Стрелкой на схеме выражено отношение “родитель”. Обозначим это отношение предикатом roditel. Тогда факт того, что vita является родителем kata, будет выражен на ТурбоПрологе следующим образом:

roditel(vita,kata).

Составим теперь небольшую программу, описывающую всю схему родственных отношений, представленную на рисунке:

/* Программа 1 */ domains    person = symbol predicates    roditel(person, person) clauses    roditel(ola,sasha).    roditel(vita,sasha).    roditel(vita,kata).    roditel(sasha,ana).    roditel(sasha,vera).    roditel(vera,kola).

Программа содержит три раздела: domains, predicatesи clauses. В разделе domains описывается домен person как символическое          имя(symbol).     В       разделе       predicates описывается бинарный предикат roditel с двумя доменами символьного типа. В разделе clauses содержится шесть утверждений, каждое из которых объявляет об одном факте наличия отношения roditel.

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

Goal:

Теперь можно задавать программе вопросы, касающиеся отношения roditel. Например, вопрос “Является ли sasha родителем vera? ” выражается на Турбо-Прологе следующим образом:

Goal: roditel(sasha, vera)

Если данный факт в разделе clauses программы имеется (что имеет место в нашем случае), то система, найдя его, ответит YES(ДА). Если такого факта в программе нет, то ответом будет NO(НЕТ).

После ответа (а точнее под ним) в диалоговом окне вновь появится сообщение:

Goal:

Зададим более сложный вопрос “Кто является родителем

kata? ”:

Goal:roditel(X, kata)

Для формулировки данного вопроса была использована свободная переменная X. Решая поставленную задачу, ТурбоПролог просматривает сверху вниз все факты раздела clauses до тех пор, пока не будет найден факт, в котором вторым аргументом будет kata. Переменная X при этом получит значение vita (т.е. станет связанной с этим значением), что и будет ответом системы:

X=vita

1  Solution

Сообщение системы 1 Solution определяет количество решений (выводов), т.е. понимается здесь как один вывод.

Используя отношение roditel, можно задать и такой вопрос,  “Кто дети sasha? ”:

Goal: roditel(sasha, X)

В этом случае, просматривая факты, система найдет два совпадения с первым аргументом sasha и выдаст два следующих ответа:

X=ana

X=vera

2  Solutions

Нашей программе можно задать и более сложный вопрос, например, “Кто чей родитель? ”, который определяет, что нужно найти такие X и Y, чтобы X являлся родителем Y:

Goal:roditel(X, Y)

Решая эту задачу, система найдет все пары данного вида в разделе clauses программы и выдаст соответственно шесть пар решений:

X=ola, Y=sasha

X=vita,Y=sasha

. . .

6 Solutions

Таким образом, поиск решений в Турбо-Прологе, как можно видеть, состоит в сопоставлении вопросов (внешних целей) с утверждениями раздела clauses программы. Этот процесс называют унификацией.

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