Так как другие утверждения для likes следуют за этим правилом, то Турбо-Пролог помещает указатель отката на начало следующего правила для likes.
Первой подцелью является likes(mary, X). Это новая подцель, поэтому Турбо-Пролог снова начинает просмотр с вершины списка предикатов для likes и находит likes(mary, X). Этот факт сопоставим с подцелью ikes(mary, X), так как все ее термы сопоставимы, поскольку X получила значение pears во время унификации. Теперь подцель likes(mary, X) успешно вычислена, но правило, которое сгенерировало эту подцель сгенерировало также и другие подцели, которые еще должны быть доказаны. Поэтому внутренние унификационные подпрограммы ставят указатель на следующий факт для likes. Этот указатель показывает, что существует по крайней мере еще одно утверждение для likes, которое может быть использовано для вычисления текущей подцели. В случае, если следующая подцель окажется неуспешной, механизм отката будет иметь точку для поиска другого кандидата для вычисления цели.
К этому моменту цель likes(beth, X) была сопоставлена с головой правила likes(beth, X). Внутренние унификационные подпрограммы установили указатель на голову следующего правила likes(beth, X) и начали попытки вычисления утверждений в правой части правила. В результате была сгенерирована подцель likes(mary, X). Пытаясь вычислить эту подцель, унификационные подпрограммы обнаружили сопоставимое утверждение likes(mary, pears). Теперь X получил значение pears, а значение подцели стало likes(beth, pears). Существуют и другие утверждения, которые могут быть использованы для вычисления подцели, поэтому указатель отката был установлен на likes(mary, popcorn).
Следующая подцель справа есть fruit(X). Так как сейчас X имеет значение pears, то подцель означает fruit(pears). Внутренние унификационные подпрограммы находят сопоставление с первым утверждением для fruit. Так как существуют другие утверждения, которые могут быть использованы для вычисления подцели, то создается еще один указатель отката на это утверждение.
Теперь два указателя отката отмечают альтернативные пути к решению правила:
likes(beth,X) :- likes(mary, X), fruit(X), color(X, red).
Это точки 2 и 3. (Точка 1 это альтернативный путь к решению основной цели). Последняя отмеченная точка всегда является точкой, с которой будет начат поиск альтернативного решения. Последняя подцель правила есть color(X, red). Внутренние подпрограммы унификации, всегда просматривая утверждения слева направо, пытаются сопоставить подцель с утверждением color(pears,yellow). Так как X имеет значение pears, то текущая под-
цель есть color(pears,red).
31
Все попытки вычислить эту подцель неуспешны, так как программа не содержит утверждения color(pears,red). Подцель вычислена неуспешно.
Внутренние унификационные подпрограммы выполняют откат к последнему указателю, который установлен на fruit(pears). Это сопоставление неуспешно, так что механизм отката повторяет откат к ближайшему предыдущему указателю, который установлен на likes(mary,popcorn).
Переменная X опять становится свободной из-за неуспешного вычисления подцели во время попытки сопоставления с pears. В точке, определяемой указателем отката, Турбо-Пролог находит факт likes(mary,popcorn). Указатель отката, отмеченный цифрой 4, устанавливается на следующее утверждение для likes. Переменная X имеет значение popcorn, так что теперь подцели эквивалентны "Мэри любит кукурузные зерна и кукурузные зерна фрукт красного цвета".
Подцель fruit(popcorn) не может быть доказана при помощи фактов и правил, имеющихся в программе, так что подцель likes(mary,X) неуспешна. Переменная X освобождается, и подцель likes(mary,X) в правиле likes(beth,X) имеет еще один шанс на успех, так как был отмечен для отката еще один факт, о том что любит Мэри. Внутренние унификационные подпрограммы выполняют откат в точку 4.
Теперь подцель сопоставляется с likes(mary, apples), и X получает значение apples. Выполняется попытка для следующей подцели ruit(apples). Первое утверждение для fruit имеет объект pears. Объекты не сопоставимы, так что внутренние унификационные подпрограммы переходят к следующему факту fruit(apples), который сопоставим с подцелью.
Наконец, последняя подцель первого правила проверена. Снова делается попытка сопоставить ее с фактом для color. В этот момент подцель есть color(apples, red). Начав с вершины списка фактов для color, внутренние унификационные подпрограммы пытаются сопоставить эту подцель с фак-
тами color(pears, yellow), color(oranges, orange) и color(apples, red). Во вре-
мя этой последней попытки объект apples (присвоенный переменной X) сопоставляется с объектом apples в факте, но последние объекты red и yellow не сопоставимы, так что попытка неудачна. Последний факт, связанный с цветом это color(apples, red), который сопоставим с подцелью color(apples, red).
С успешным сопоставлением последней подцели правило доказано. Переменная X, получив значение apples, тем самым доказывает правую часть. Все правило с переменной X, означенной объектом apples, c точки зрения внутренних унификационных подпрограмм выглядит как
likes(beth, apples) :- likes(mary, apples), fruit(apples), color(apples, red).
Выдав сообщение X=apples, Турбо-Пролог показывает, что для цели найдено по крайней мере одно решение.
Снова используется последняя подцель. Теперь co значением
32
color(apples,red).
Еще раз все утверждения для color проверяются по очереди для сопоставления с новой подцелью. Сопоставление найдено в последнем утверждении color(apples, red). Теперь все три подцели правила доказаны. Переменная X имеет значение apples. Следовательно, сейчас голова правила имеет вид: likes(beth, apples). Эта голова правила сопоставима с утверждением цели
likes(beth, X).
так что цель успешна, и Турбо-Пролог выдает сообщение X=apples. Поскольку внешняя цель была использована с программой, являющейся "черным ящиком" для Турбо-Пролога, то он продолжает поиск других решений для цели. Цель была успешной, так что переменная X освобождена и может быть снова означена подпрограммами внутренней унификации.
Поиск решений снова начинается с указателя отката, который теперь является последним. Это указатель точки 1. Указатель точки 2 был удален, так как в конце пути было найдено решение.
Теперь внутренние унификационные подпрограммы начинают поиск с правила
likes(beth, X) :- likes(mary, X), X=popcorn.
Снова первая подцель есть likes(mary, X), и внутренние унификационные подпрограммы осуществляют поиск утверждений likes для сопоставления. Утверждение
likes(mary, pears).
сопоставимо с подцелью, так что X получает значение pears. Указатель для отката устанавливается на следующее утверждение likes(mary, popcorn).
Вычислив текущую подцель и означив X объектом pears, ТурбоПролог пытается вычислить оставшуюся подцель, которая есть
X=popcorn.
Как было объяснено ранее в этой главе, оператор = работает как оператор сравнения, поскольку значения обоих термов известны: переменная X имеет значение pears, а popcorn есть константа. Операция сравнения будет неуспешной:
pears=popcorn.
Термы не сопоставимы, поэтому подцель неуспешна, и X снова освобождена.
Теперь внутренние унификационные подпрограммы выполняют откат к последнему указателю, с тем, чтобы попробовать альтернативный путь решения. Последний указатель отката установлен на утверждение
likes(mary, popcorn).
Ранее X была освобождена, поэтому сейчас она получает значение popcorn. Установив указатель отката на следующее утверждение likes(mary,apples), внутренние унификационные подпрограммы снова пытаются вычислить подцель X=popcorn. Внутренние значения подтермов есть
33
popcorn=popcorn.
Сопоставление успешно, и последняя подцель правила успешно вычислена. Переменная X в голове правила имеет значение popcorn. Таким образом, выведенный факт есть likes(beth, popcorn). Турбо-Пролог сообщает об этом, выдавая X=popcorn. Теперь найдены два решения, а указатель отката остался на утверждении
likes(beth, popcorn).
Турбо-Пролог возвращается в указанную точку и пытается найти еще одно решение.
Вспомним, что данный путь является альтернативным для второй подцели второго правила для likes. Следовательно, имеем подцель
likes(mary, X).
Так как X снова освобождена, то она получает значение apples и подцель снова успешна. Хотя среди утверждений для likes и не осталось фактов, но еще остались два правила, так что указатель устанавливается на факт likes(mary,apples). Возвратившись к следующей подцели, Турбо-Пролог сравнивает X=popcorn или apples=popcorn. Иными словами, подцель неуспешна.
Снова внутренние унификационные подпрограммы выполняют откат к голове правила likes(beth, X). Эта голова правила не сопоставима с подцелью likes(mary, X), управляющей данной попыткой использовать данный альтернативный путь, поэтому унификационный механизм проверяет сопоставимость головы следующего правила. Эта голова правила также есть likes(beth, X), поэтому снова из-за несопоставимости beth и mary, сопоставление оказывается неудачным.
На этот раз правило не смогло дать решение, и цель оказалась неуспешной. Ранее найдены два решения. Чтобы показать, что на этом процесс завершен, Турбо-Пролог выдает сообщение Two solutions (Два решения).
2.5 Заключение
В данной главе Турбо-Пролог рассматривался на концептуальном уровне. Как вы узнали, Турбо-Пролог является декларативным языком, основанным на логике предикатов. Предикаты в общем случае определяют отношения между объектами.
Факты и правила являются утверждениями, которые образуют данные программы на Турбо-Прологе. Правила имеют левую часть (голову) и правую часть(тело). Левая часть правила истинна, если истинна правая часть правила. Правила генерируют новые факты, когда все утверждения в теле оказываются вычисленными.
Цели - это конструкции на основе предикатов, которые объявляют, что должна доказать программа на Турбо-Прологе. Связки в целях и правилах выполняют генерацию подцелей в качестве шага процесса доказательства цели.
34
Внутренние унификационные подпрограммы означивают переменные. Означенные переменные и константы имеют значения, "известные" ТурбоПрологу. Свободные переменные значений не имеют. Турбо-Пролог использует откаты для определения альтернативных путей вычисления цели или подцели. Если подцель оказалась неуспешной, а указатели отката были установлены, то для предыдущей подцели будет сделана попытка добиться успеха, начиная с точки отката.
Понимание поведения переменных, унификации и отката может оказаться весьма сложным для начинающих знакомиться с Турбо-Прологом. Эта глава дала возможность познакомиться с несколькими примерами, иллюстрирующими связь между переменными, унификацией и откатом во время работы системы. После того, как вы продолжите знакомство со следующими главами, вы почувствуете себя более уверенными в скрытых операциях, выполняемых программами на Турбо-Прологе.
Глава 3. Основы программирования на Турбо-Прологе
3.1 Введение
Синтаксис и структура программ Турбо-Пролога, описанию которых посвящена данная глава, отражают концепции логики предикатов, преставленье в гл. 2.
В целях упрощения организации фактов и правил Турбо-Пролог поддерживает составные доменные структуры; кирпичиками для их создания служат базисные типы доменов Турбо-Пролога. В настоящей главе рассматривается вопрос создания составных объектов и доменных структур на основе этих базисных типов.
Примеры программ главы ставят целью продемонстрировать новые концепции и методы программирования, а упражнения дают возможность поэкспериментировать с программами. Прочитав главу, Вы уже будете иметь достаточно знаний об использовании некоторых полезных приемов программирования на Турбо-Прологе.
3.2 Структура программ Турбо-Пролога
Любая программа, написанная на Турбо-Прологе, состоит из пяти разделов. Таковыми являются раздел описания доменов, раздел базы данных, раздел описания предикатов, раздел описания цели и раздел описания утверждений. Ключевые слова domains, database, predicates, goal и clauses
отмечают начала соответствующих разделов. Назначение этих разделов таково:
-раздел domains содержит определения доменов, которые описывают различные классы объектов, используемых в программе;
-раздел database содержит утверждения базы данных, которые являются предикатами динамической базы данных. Если программа такой базы дан-
35