Чтобы выяснить причину этой зависимости, необходимо более
детально рассмотреть работу Пролог-системы на однопроцессорной
ЭВМ. Для наглядности представим этот процесс в виде дерева реше-
ний. Вершина дерева будет соответствовать исходной цели, постав-
ленной в Пролог-программе, листья - множеству возможных вариан-
тов решения задачи. Все остальные вершины будут определять про-
межуточные состояния Пролог-системы в процессе решения задачи, а
дуги будут определять направления переходов от одного состояния
системы к другому. Для эффективной и безопасной работы компьютера вам может потребоваться антивирус. Отиличным вариантом будет установить антивирус Касперского. Kaspersky-Shop.ru - специализированный интернет-магазин компании ООО "Эникод", специализирующийся на продаже продуктов "Лаборатории Касперского". Мы предоставляем весь спектр лицензионного программного обеспечения "Лаборатории Касперского" и возможность быстро и удобно приобрести желаемый продукт в режиме онлайн. Клиентам предоставляются различные методы оплаты, коробочная и электронная поставки, оперативная обработка заказов, возможность отслеживания статуса заказа, а также скидки и подарки от магазина http://www.kaspersky-shop.ru/.
Рассмотрим процесс достижения цели на примере программы
родственных отношений из лабораторной работы N 1. Пусть заданы
следующие факты:
parent("Олег","Борис"). (1)
parent("Олег","Таня"). (2)
parent("Борис","Оля"). (3)
parent("Борис","Юра"). (4)
и определено правило для предиката "предок":
ancestor(X,Y):-parent(X,Y). (5)
ancestor(X,Z):-parent(X,Y),ancestor(Y,Z). (6)
Работая в оболочке Турбо-Пролога определим следующую цель:
Goal: ancestor("Олег","Юра"), (7)
которая на русском языке звучит следующим образом:
"Является ли Олег предком Юры?".
Дерево решений для данного примера приведено на рис.1.
Рассмотрим последовательность действий Пролог-системы. После
подачи на ее вход цели ancestor("Олег","Юра") система начинает
анализировать текст программы, начиная с первого предложения.
Предложения (1)-(4) представляют собой факты и ни один из них
не совпадает с целью (7). Следующим на пути Пролог-системы
встречается первое предложение правила ancestor, после чего
выполняется попытка замещения исходного предиката новым соглас-
но этому правилу. Результатом этой операции является предикат
parent("Олег","Юра").Для данного предиката определено множество
фактов, но ни один из них не удовлетворяет полученной цели.
Поэтому, в данной ветви дерева поиска решений не может быть
листьев и Пролог-система осуществляет автоматический возврат
по дереву на уровень выше и продолжает, если это возможно, поиск
в другом направлении. В нашем случае возврат на уровень выше
означает переход к просмотру исходной программы, начиная с пред-
ложения следующего за предложением (5), приведшим к отрицатель-
ному результату поиска. Предложение (6) определяет правило,
результат которого имеет следующий вид:
parent("Олег",Y), ancestor(Y,"Юра").
Для раскрытия предиката ancestor(Y,"Юра") повторяется та
же последовательность действий, что и для исходного предиката-
цели. Первое сопоставимое предложение в тексте программы - это
правило (5), согласно которому предикат ancestor заменяется на
предикат parent с аналогичными аргументами:
parent("Олег",Y),parent(Y,"Юра").
В полученном выражении все предикаты относятся к области
фактов, поэтому процесс преобразования предикатов заканчивается.
На следующем этапе выполняется конкретизация переменной Y. Эта
операция выполняется на базе имеющихся фактов (1)-(4). Первый же
вариант конкретизации (по предложению (1) Y="Борис") дает удов-
летворительный результат:
parent("Олег","Борис"),parent("Борис","Юра").
Последнее выражение содержит только константные объекты.
Оба предиката, входящие в это выражение представляют собой истин-
ные факты. Следовательно, данное выражение также истинно и цель
считается достигнутой. Пролог-система сообщит об этом появлением
в окне диалога слова "Yes". В результате анализа данного примера
можно сделать следующее заключение.
С программной точки зрения Пролог-система представляет со-
бой процедуру поиска по дереву решений. В ходе реализации этой
процедуры выполняются следующие операции:
- сопоставление термов языка Пролог;
- конкретизация переменных;
- автоматический возврат на предыдущий уровень дерева при
отсутствии решения в текущей ветви дерева.
Сопоставление, или унификация, представляет собой опера-
цию, операндами которой являются два терма языка. Результатом
операции является ИСТИНА, если операнды соответствуют друг дру-
гу, и ЛОЖЬ - в противном случае. Два терма сопоставимы в одном
из двух случаев:
- если они идентичны (объекты одного типа);
- если в термах есть переменные, которые могут быть иден-
тичны.
Например, две структуры dat(D,M,1994) и dat(X,june,Y)
сопоставимы (D=X,M=june,1994=Y), а структуры dat(15,M,Y) и
dat(28,M,1990) - не сопоставимы, т.к. первая пара объектов не
может быть идентичной.
Теперь изменим исходный текст программы следующим образом.
Поменяем местами предложения (5) и (6), а в новом предложении
(5) поменяем порядок следования предикатов в правой части. Таким
образом программа будет иметь следующий вид:
parent("Олег","Борис"). (1)
parent("Олег","Таня"). (2)
parent("Борис","Оля"). (3)
parent("Борис","Юра"). (4)
ancestor(X,Z):-ancestor(Y,Z),parent(X,Y). (5)
ancestor(X,Y):-parent(X,Y). (6)
Goal: ancestor("Олег","Юра"), (7)
Дерево решений для второго случая представлено на рис.2. В про-
цессе поиска решений для той же цели первым по тексту программы
попадается рекурсивное правило, а первым предикатом в нем - ре-
курсивный вызов. Поэтому дерево на рис.2 будет иметь вид беско-
нечной цепочки, а после запуска данной программы Пролог-система
с некоторой задержкой выдаст сообщение о переполнении стека
Таким образом, данный вариант программы подтверждает зависи-
мость процедурной семантики от порядка следования предложений и
предикатов в них. |
Главная
Каталог файлов
