Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 162
Текст из файла (страница 162)
Есть два противоположных подхода к сравнению заданной цели и факта в базе данных. Система может начать поиск с фактов и правил, хранящихся в базе данных, и попытаться найти послеловательность совпадений, ведущую к цели. Этот подход называется резолюцией снизу-вверх, или прямым выводом (Гогзгагг( сйа(п(пк). Альтернативный подход заключается в том, что система начинает поиск с цели и пытается найти последовательность соответствующих высказываний, ведущую к некоторому множеству исходных фактов, хранящихся в базе данных.
Этот подход называется резолюцией сверху- вниз. или обратным выводом (Ьас(свагд сйа)п(пй). В целом, обратный вывол хорошо работает, когда существует небольшой набор возможных ответов. Прямой вывод работает лучше, когда количество возможных правильных ответов велико; в этой ситуации при обратном выводе для получения ответа может потребоваться очень большое количество сопоставлений.
Реализации языка Рго)оя используют для резолюции обратный вывод, предположительно потому, что их разработчики думали, будто обратный вывод подходит для более широкого класса задач, чем прямой вывод. Снова рассмотрим пример запроса: пап!ЬоЬ). 623 Глава 15. Языки логического программирования Предположим, что база данных содержит следующий факт и правило вывода: айаг)зег (ЬоЬ) . пап(Х) : — ЙаГЬег(Х). При прямом выводе система должна была бы отыскать первое высказывание.
Тогда логический вывод цели осуществляется следующим образом: переменная Х конкретизируется значением ЬоЬ, первое высказывание сопоставляется с правой частью второго правила (гагЬег (х) ), а затем левая часть второго высказывания сопоставляется с целью. При обратном выводе следует сначала сопоставить цель с левой частью второго высказывания ( (тап (Х) ), конкретизировав переменную Х значением ЬоЬ. На последнем этапе система должна сопоставить правую часть второго высказывания (теперь 1 а грег (ЬоЬ] ) с первым высказыванием. Следующий вопрос, относящийся к разработке языка, возникает всякий раз, когда цель имеет несколько структур, как в примере, приведенном выше.
В этом случае вопрос заключается а том, как выполнять поиск: сначала в глубину или в ширину". При поиске сначала- вглубь (бергйчбкэ! зеагсЬ) система находит полную цепочку высказываний — доказательство — дпя первой подцепи прежле, чем приступить к работе над остальными. При поиске сначала-вширь (Ьгеагйй-Лгз! зеагсЬ) система работает над всеми подцелями параллельно. Разработчики языка Рго)оя выбрали в качестве основного поиск сначала-вглубь, поскольлу он требует меньше компьютерных ресурсов.
Подход сначала-вширь представляет собой параллельный поиск, который может потребовать большого объема памяти. Последнее свойство механизма резолюции в языке Рго)оя, которое следует обсудить, — бектрекинг (Ьасйгас)г)пй). При обработке цели с несколькими подцелями, если система не способна доказать истинность одной из подцелей. она отказывается от обработки подцепи, которую не способна доказать. Вместо этого система заново рассматривает предыдущую подцель, если она является единственной, и пытается найти ее альтернативное решение.
Это восстановление предшествующего состояния цели для пересмотра ранее доказанной подпели называется бектрекингом. Новое решение находится а результате поиска. предпринятого с того места, где остановился прелыдуший поиск лля этой подцепи. Множественность решений дпя подпели является результатом начичия различных конкретизаций ее переменных. Бектрекннг требует больших затрат времени и объема памяти, поскольку он может найти все возможные решения для каждой подпели. Эти доказательства подцелей могут оказаться не достаточно организованными для того. чтобы минимизировать объем времени, которое требуется для поиска окончательного решения. что еше больше обостряет проблему.
Чтобы укрепить наше понимание бектрекинга, рассмотрим следующий пример. Допустим, что в базе данных есть совокупность фактов и правил, и системе языка Рго!од представлена следующая составная цель: п~а1е(Х), рагепг (Х, эце11еу] . В этой нели спрашивается, существует ли какая-либо конкретизация переменной Х. определяющая, что х является мужчиной (жа1е) и родителем (рагепс) шелли (вце11еу). Система языка Рго)од сначала ищет в базе данных первый факт с функтором жа1е.
Затем она конкретизирует переменную Х параметром найденного факта, скажем, параметром ж1)се. Далее она пытается доказать, что высказывание рагепг (т1)ге, аце11еу) является истинным. Если это не удается сделать, она возвращается к первой подцепи, жа1е (Х), и пробует снова удовлетворить ее с помощью некоторой ачьтерна- 15.6. Основные элементм языка Рго!оа 62Р тивной конкретизации переменной Х. Может оказаться, что, выполняя процесс резолюции. система должна будет найти каждого мужчину в базе данных, прежде чем она найдет одного из них, являющегося родителем Шелли. Она определенно должна найти всех мужчин, лля того чтобы доказать, что цель не может быть удовлетворена.
Заметим, что наш пример цели можно решить более эффективно, если порядок следования двух подцелей поменять местами. Тогда только после того, как система с помощью резолюции найлет родителя Шелли, она попытается найти лицо с подцелью жа1е. Этот способ эффективен, если у Шелли меньше родителей, чем мужчин в базе данных, что вполне правдополобно. В разделе 15.7.1 мы обсудим метод ограничения бектрекинга, выполняемый системой языка Рго!об.
Система языка Рго)оя всегда выполняет поиск в базе данных в направлении от первого элемента к последнему. В двух следующих подразделах описываются примеры на языке Рго)оя, иллюстрирующие процесс резолюции. 15.6.6. Простая арифметика Язык Рго1оя поддерживает целые числа и целую арифметику. Первоначально арифметические операторы были функторами, так что сумма числа 7 и переменной Х формировалась выражением (7, Х) В настоящее время язык Рго)об допускает более краткий синтаксис арифметических операций с использованием оператора зе. Этот оператор имеет арифметическое выражение в качестве своего правого операнда, а переменную — в качестве левого операнда.
Все переменные в выражении должны быть предварительно конкретизированы, но переменная в левой части выражения не должна конкретизироваться заранее. Рассмотрим следующее выражение: А зе В / 17 + С. Если переменные В и С конкретизированы, а переменная А — нет, то этот дизъюнкт приведет к тому, что переменная А будет конкретизирована значением данного выражения. Когда это случится. дизъюикт оказывается удовлетворенным. Если либо переменная В, либо переменная С являются неконкретизированными, либо переменная А является конкретизированной, дизъюнкт не удовлетворяется и конкретизация переменной А не происходит.
Семантика высказывания, содержащего оператор зе, значительно отличается о! семантики оператора присваивания в императивном языке. Это отличие может привести к интересной ситуации. Поскольку оператор де делает дизъюнкт, в котором он появляется.
похожим на оператор присваивания, начинающие программисты на языке Рго!оя могут попытаться написать оператор, приведенный ниже: Ецж зе Вцж ь )ЧипЬег. Такой оператор ннкогла не станет осмысленным (и даже допустимым) в языке Рго!од. Если переменная Яига не конкретизирована, ссылка на иее в правой части оператора является неопрелелеиной, и дизъюнкт теряет смысл. Если переменная Зцп уже конкретизировани дизъюнкт также теряет смысл, поскольку левая часть оператора не может имсгь тслушей конкретизации при вычислении оператора зв.
В любом случае конкрети- 630 Глава 15. Языки логического программирования зация переменной Яшп новым значением никогда не произойдет. (Если требуется вычислить значение выражения Яшп + (яопбэег, его слелует связать с новым именем.) В отличие от императивных языков, язык Рго!ой не имеет операторов присваивания. Онн просто не нужны в большинстве задач, для решения которых был разработан язык Рго!ой.
Полезность операторов присваивания в императивных языках зависит от возможности программиста контролировать поток управления выполнением программы, содержашей эти операторы. Поскольку контроль типов в языке Рго!ой не всегда возможен, такие операторы становятся намного менее полезными. В качестве простого примера использования количественных вычислений в языке Рго!од рассмотрим следующую задачу: допустим, что мы знаем срелнюю скорость нескольких автомобилей на конкретном гоночном треке и объем времени их пребывания на треке. Эту основную информацию можно закодировать в виде фактов, а отношение между скоростью, временем и расстоянием можно записать в виде правила, как показано ниже: ярееб(Хогб, 100).
ярееб(с)зету, 105) . ярееб(бобде, 95). ярееб(то1то,80). П1те(Тогб, 20). пзлпе(с)тету, 21). пыпе(бобае, 24). пппе(то1чо, 24). бдягапсе(Х, Х] : — ярееб(Х, Ярееб), пьп~е(Х, Т1жЕ), Х Де Ярееб * Тьгпе. Теперь запросы могут потребовать вычисления расстояния, пройденного конкретной машиной. Например, рассмотрим запрос б1ягапсе(с)зету, С)зету 01ягапсе). Он конкретизирует переменную Соету 01япапсе значением 2205. Первые два дизъюнкга в правой части оператора, вычисляющего расстояние, просто конкретизируют переменные Ярееб и Тйже соответствуюшими значениями заданного автомобильного функтора. После удовлетворения цели система языка Рго!ой также выводит имя переменной С)течу 01ягапсе и ее значение. Здесь поучительно посмотреть с точки зрения выполнения операторов, как именно система языка Рго!од вырабатывает результаты.
Система языка Рго!оа имеет встроенную структуру с именем стасе, отображаюшую конкретизации переменных их значениями на каждом этапе попытки удовлетворения заданной цели. Структура стасе используется для анализа и отладки программ, написанных на языке Рго!оа. Для того чтобы понять, как работает структура стасе, лучше всего ввести другую модель выполнения программ на языке Рго!ой, называемую моделью трассировки ((гас!пк пюбе1). Молель трассировки описывает выполнение программы, написанной на языке Рго!од, в терминах четырех событий: (!) вызов, возникающий в начале попытки удовлетворить цель; (2) выход, возникаюший, когда цель удовлетворена; (3) повтор (гебо), возникаюший, когда бектрекинг вынуждает систему возобновить попытку снова удовлетворить цель; (4) отказ, возникаюший, когда цель удовлетворить невозможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
