Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
(1) Исходный список целевых утверждений:
темный(X), большой(X).
(2) Просмотр всей программы от начала к концу и поиск предложения, у которого голова сопоставима с первым целевым утверждением
темный(X).
Найдена формула 7:
темный(Z):- черный(Z).
Замена первого целевого утверждения конкретизированным телом предложения 7 — порождение нового списка целевых утверждений.
черный(X), большой(X)
(3) Просмотр программы для нахождения предложения, сопоставимого с черный(X). Найдено предложение 5: черный (кот). У этого предложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до
большой(кот)
(4) Просмотр программы в поисках цели большой(кот). Ни одно предложение не найдено. Поэтому происходит возврат к шагу (3) и отмена конкретизации X = кот. Список целей теперь снова
черный(X), большой(X)
Продолжение просмотра программы ниже предложения 5. Ни одно предложение не найдено. Поэтому возврат к шагу (2) и продолжение просмотра ниже предложения 7. Найдено предложение (8):
темный(Z):- коричневый(Z).
Замена первой цели в списке на коричневый(X), что дает
коричневый(X), большой(X)
(5) Просмотр программы для обнаружения предложения, сопоставимого коричневый(X). Найдено предложение коричневый(медведь). У этого предложения нет тела, поэтому список целей уменьшается до
большой(медведь)
(6) Просмотр программы и обнаружение предложения большой(медведь). У него нет тела, поэтому список целей становится пустым. Это указывает на успешное завершение, а соответствующая конкретизация переменных такова:
Рис. 2.10. Пример, иллюстрирующий процедурную семантику Пролога: шаги вычислений, выполняемых процедурой вычислить.
В главе 1 в разд. "Как пролог-система отвечает на вопросы" мы уже фактически рассмотрели, что делает процедура вычислить. В оставшейся части данного раздела приводится несколько более формальное и систематическое описание этого процесса, которое можно пропустить без серьезного ущерба для понимания остального материала книги.
Конкретные операции, выполняемые в процессе вычисления целевых утверждений, показаны на рис. 2.10. Возможно, следует изучить этот рисунок прежде, чем знакомиться с последующим общим описанием.
Чтобы вычислить список целевых утверждений
G1, G2, …, Gm
процедура вычислить делает следующее:
• Если список целей пуст - завершает работу успешно.
• Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'.
• ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.
Если С найдено и имеет вид
H:- B1,..., Вn.
то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком G1, …, Gm. Пусть С' — это
Н':- B1',..., Вn'.
Сопоставляется G1 с H'; пусть S — результирующая конкретизация переменных. В списке целей G1, G2, …, Gm, цель G1 заменяется на список В1', …, Вn', что порождает новый список целей:
В1', …, Вn', G2, …, Gm
(Заметим, что, если С — факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а следовательно, — привести к успешному завершению.)
Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей
В1'', …, Вn", G2', …, Gm'
• Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением С (С — предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.
Более компактная запись этой процедуры в обозначениях, близких к Паскалю, приведена на рис. 2.11.
Здесь следует сделать несколько дополнительных замечаний, касающихся процедуры вычислить в том виде, в котором она приводится. Во-первых, в ней явно не указано, как порождается окончательная результирующая конкретизация переменных. Речь идет о конкретизации S, которая приводит к успешному завершению и которая, возможно, уточнялась последующими конкретизациями во время вложенных рекурсивных вызовов вычислить.
procedure вычислить (Прогр, СписокЦелей, Успех)
Входные параметры:
Прогр: список предложений
СписокЦелей: список целей
Выходной параметр:
Успех: истинностное значение; Успех принимает значение
истина, если список целевых утверждений
(их конъюнкция) истиннен с точки зрения Прогр
Локальные переменные:
Цель: цель
ДругиеЦели: список целей
Достигнуты: истинностное значение
Сопоставились: истинностное значение
Конкрет: конкретизация переменных
H, Н', B1, B1', …, Вn, Вn': цели
Вспомогательные функции:
пycтой(L): возвращает истину, если L — пустой список
голoвa(L): возвращает первый элемент списка L
хвост(L): возвращает остальную часть списка L
конкат(L1, L2): создает конкатенацию списков — присоединяет
список L2 к концу списка L1
сопоставление(T1, T2, Сопоставились, Конкрет): пытается
сопоставить термы Т1 и T2; если они сопоставимы, то
Сопоставились — истина, а Конкрет представляет
собой конкретизацию переменных
подставить(Конкрет, Цели): производит подстановку переменных
в Цели согласно Конкрет
Begin
if пустой(СписокЦелей) then Успех: = истина
Else
Begin
Цель: = голова(СписокЦелей);
ДругиеЦели: = хвост(СписокЦелей);
Достигнута: = ложь;
while not Достигнута and
"в программе есть еще предложения" do
Begin
Пусть следующее предложение в Прогр есть
H:- B1, …, Вn.
Создать вариант этого предложения
Н':- В1', …, Вn'.
сопоставление(Цель, Н',
Сопоставились, Конкрет)
if Сопоставились then
Begin
НовыеЦели:=
конкат( [ В1', …, Вn' ], Другие Цели);
НовыеЦели: =
подставить(Конкрет, НовыеЦели);
вычислить(Прогр, НовыеЦели, Достигнуты)
End
End;
Успех: = Достигнуты
End
End;
Рис. 2.11. Вычисление целевых утверждений Пролога.
Всякий раз, как рекурсивный вызов процедуры вычислить приводят к неуспеху, процесс вычислений возвращается к ПРОСМОТРУ и продолжается с того предложения С, которое использовалось последним. Поскольку применение предложения С не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет возврат в ту точку (предложение С), в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки, аннулируются. Такой порядок обеспечивает систематическую проверку пролог-системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.
Мы уже знаем, что даже после успешного завершения пользователь может заставить систему совершить возврат для поиска новых решений. В нашем описании процедуры вычислить эта деталь была опущена.
Конечно, в настоящих реализациях Пролога в процедуру вычислить добавлены и еще некоторые усовершенствования. Одно из них — сокращение работы по просмотрам программы с целью повышения эффективности. Поэтому на практике пролог-система не просматривает все предложения программы, а вместо этого рассматривает только те из них, которые касаются текущего целевого утверждения.
Дата публикования: 2015-10-09; Прочитано: 252 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!