Для ответа на вопрос, поступивший от программиста, Пролог выполняет решение некоторой задачи. Вопрос содержит конъюнкциюцелевых утверждений, которые необходимо попытаться доказать, т. е. проверить на согласованность с базой данных. Для доказательства целевых утверждений Пролог использует известные утверждения.Факт может привести к немедленному доказательству (согласованию) целевого утверждения, в то время как правило может только свести данную задачу к конъюнкции предикатов-подцелей. Однако использование некоторого утверждения возможно только, когда оно «подходит» к рассматриваемому целевому утверждению, т. е. соответствует ему (сопоставимо с ним). Если целевое утверждение не доказано, возбуждается процесс возврата.Процесс возврата заключается в пересмотре проделанной работы и попытках передоказать (вновь согласовать) целевые утверждения путем поиска альтернативных путей доказательства. Более того, если программист неудовлетворен ответом на свой вопрос, он может сам инициировать процесс возврата, нажав на клавиатуре клавишу ';', после того как Пролог информирует его о найденном решении. В данном разделе будут представлены диаграммы, показывающие, как Пролог пытается доказать и передоказать целевые утверждения.
Пролог пытается согласовать с базой данных входящие в конъюнкцию целевые утверждения в том порядке, в каком они написаны (слева направо), где бы они ни появились – в теле правила или в вопросе. Это означает, что Пролог не будет проверять некоторое утверждение, пока не будет доказан его сосед слева. А сосед справа будет рассматриваться только после доказательства данного целевого утверждения. Рассмотрим следующую простую программу о семейных связях:
родители (С,M,F):- мать(С,М), отец(C,F).
мать(джон,анна).
мать(мэри,анна).
отец(мэри,фред). отец(джон,фред).
Давайте рассмотрим последовательность событий, позволяющую дать ответ на вопрос:
?-женщина(мэри), родители(мэри,М,Р), родители(джон,М,Р).
Данный вопрос позволяет определить, является ли мэрисестрой джона. Для того чтобы дать ответ Прологу, необходимо согласовать с базой данных последовательность подцелей, приведенных на рис. 2.1.
Представим целевые утверждения в виде прямоугольников, распределенных по странице. Стрелка, начинающаяся в верхней части страницы, указывает, какие целевые утверждения уже согласованы. Прямоугольники, через которые стрелка уже прошла, соответствуют согласованным целевым утверждениям. Прямоугольники, лежащие ниже острия стрелки, соответствуют целевым утверждениям, которые Пролог еще не рассматривал. При выполнении программы стрелка движется вверх и вниз по странице в соответствии с переходом Пролога от одного целевого утверждения к другому. Будем называть ее цепочкой доказательств.В данном примере стрелка начинается в верхней части страницы, как показано выше. По мере согласования трех целевых утверждений она будет удлиняться вниз, проходя через соответствующие прямоугольники. Конечная ситуация представлена на рис. 2.2. Отметим, что в ходе доказательства согласованности целевых утверждений с базой данных были найдены значения для переменных Ми F.
Такая диаграмма иллюстрирует общую структуру происходящего, но она не показывает, какдоказывались эти три целевых утверждения. Для того чтобы показать это, поместим внутрь прямоугольников больше информации. Давайте посмотрим, как доказывалось второе целевое утверждение. Доказательство согласованности целевого утверждения с базой данных включает в себя поиск в базе данных соответствующих(сопоставимых) утверждений, пометку этого места базы данных и затем доказательств возникших подцелей. Этот процесс для второго целевого утверждения можно проиллюстрировать, включив в прямоугольник родителииндикацию выбранного утверждения и возникшие подцели. Выбранное утверждение обозначается числом в скобках, в данном случае (1). Это число указывает номер выбранного утверждения в наборе утверждений с соответствующим предикатом.Таким образом, число 1означает, что было выбрано первое утверждение с данным предикатом. Эта информация достаточна для отметки места в базе данных. Подцели заключены в маленькие прямоугольники, помещенные в прямоугольник данного целевого утверждения. В момент, когда выбрано утверждение родители,ситуация выглядит так, как показано на рис. 2.3.
Рис. 2.3.
Стрелка вошла в прямоугольник родителии прошла через скобки, указывая, что выбрано некоторое утверждение. Данное утверждение создало две подцели – матьи отец. Вданный момент для получения ответа на вопрос необходимо, чтобы стрелка прошла через два маленьких прямоугольника, вышла из прямоугольника родителии затем прошла через второй прямоугольник родители.Когда стрелка проходит через маленькие прямоугольники, необходимо выполнить те же самые шаги: выбор соответствующего утверждения и доказательство порождаемых им подцелей. В данном примере для каждого из этих двух целевых утверждений в базе данных находится соответствующий факт, и их согласованность с базой данных доказывается. На рис. 2.4 приведено более детальное изображение ситуации в момент получения ответа на вопрос.
Рис. 2.4.
Отметим, что для полноты картины нам необходимо было бы показать, как доказываются целевые утверждения женщина(мэри)и родители(джон,анна,фред).Однако столь подробная диаграмма не поместилась бы на одной странице.
Данный пример иллюстрирует общую схему рассмотрения целевых утверждений, объединенных в конъюнкцию, для случая, когда все цели согласуются с базой данных. Стрелка перемещается вниз по странице, по очереди проходя через прямоугольники. Когда стрелка входит в какой-либо прямоугольник, выбирается некоторое утверждение и отмечается его позиция. Если данное утверждение сопоставимо с целью и является фактом, стрелка может покинуть прямоугольник (такая ситуация имела место для целевых утверждений матьи отец).Если же утверждение сопоставимо с целью, но является правилом, создаются прямоугольники для подцелей, и стрелка должна пройти через них, прежде чем она сможет покинуть первоначальный прямоугольник.
Когда целевое утверждение недоказуемо (проверены все возможные утверждения или пользователь нажал клавишу ';'), «цепочка доказательств» проходит назад тот путь, по которому она пришла в данную точку. Она возвращается в покинутые перед этим прямоугольники для того, чтобы попытаться передоказать(вновь согласовать) соответствующие целевые утверждения. Когда стрелка возвращается в то место, где было выбрано какое-то утверждение (это событие изображается числом в скобках), Пролог пытается найти альтернативное утверждение, соответствующее данной цели. Сначала делаются неопределенными все переменные, которые были конкретизированы в ходе доказательства данного целевого утверждения. Затем возобновляется поиск в базе данных, начиная с того места, где был оставлен маркер. Если будет найдено другое утверждение, соответствующее целевому, Пролог помечает это место, и дальше события развиваются, как было описано выше в разд. 2.6.1. Отметим, что рассмотрение любых целевых утверждений, находящихся «ниже» данного (даже если они были пройдены в ходе рассмотрения предыдущей альтернативы), всегда начинается с самого начала. Пролог пытается доказать их без учета положения маркера (т. е. это не передоказательство). Если не удается найти другое подходящее утверждение, данное целевое утверждение считается недоказуемым и стрелка продолжает возвращаться назад до следующего маркера. В нашем примере, если целевое утверждение родители(джон,анна,фред)недоказуемо, стрелка уйдет назад из прямоугольника родители(джон,анна,фред)и войдет в прямоугольник родители (мэри,анна,фред)снизу для того, чтобы попытаться передоказать данное целевое утверждение (см. рис. 2.5).
Рис. 2.5.
Отступая дальше, стрелка достигнет места, где было выбрано утверждение, соответствующее целевому утверждению отец. В первую очередь освобождаются все переменные, которые были конкретизированы в результате использования данного утверждения. Это означает, что переменная Fвновь становится неконкретизированной. Затем Пролог просматривает базу данных, начиная с утверждения, следующего за первым утверждением с предикатом отец(здесь находится маркер), пытаясь найти альтернативное утверждение. Если предположить, что мэриимеет только одного отца, то этот процесс успехом не завершится. Поэтому стрелка продолжит отступление. Она покинет прямоугольник отец(мэри, F)(это целевое утверждение недоказуемо) и вернется в прямоугольник мать(мэри,анна)(для того, чтобы попытаться передоказать данное целевое утверждение) (см. рис. 2.6).
Рис. 2.6.
Отступление стрелки будет продолжаться до успешного доказательства соответствующего целевого утверждения.
Эти примеры иллюстрируют общую схему повторного рассмотрения целевых утверждений в процессе возврата. Когда некоторое целевое утверждение недоказуемо, стрелка возвращается из соответствующего прямоугольника в прямоугольник с предшествующим целевым утверждением. Стрелка отступает до тех пор, пока не встретится маркер. Все переменные, которые были конкретизированы в результате предыдущего выбора сопоставимого утверждения, становятся неконкретизированными. Затем Пролог возобновляет поиск в базе данных сопоставимого утверждения, начиная с маркера. Если сопоставимое утверждение будет найдено, новое место помечается маркером, создаются прямоугольники для целевых подутверждений и стрелка опять начинает движение вниз. В противном случае стрелка продолжает отступать вверх в поисках другого маркера.
Правила, определяющие, подходит ли некоторое утверждение для согласования с целевым утверждением, выглядят следующим образом. Отметим, что при выборе утверждения все переменные сначала неконкретизированы.
• Неконкретизированная переменная соответствует любому объекту. Этот объект становится значением переменной.
• Целое число или атом соответствуют только самим себе.
• Между структурами можно установить соответствие, только если они имеют одинаковый функтор, одинаковое число параметров и соответствующие параметры соответствуют друг другу.
Особым случаем является установление соответствия между двумя неконкретизированными переменными. В этом случае мы говорим, что переменные сцеплены.Две сцепленные переменные обладают следующим свойством: как только одна из них принимает конкретное значение, то же самое конкретное значение принимает и другая.
Если читатель заметил сходство между установлением соответствия и приравниванием аргументов (разд. 2.4), то он совершенно прав. Дело в том, что предикат '=' пытается сделать свои аргументы равными путем установления соответствия между ними.
Попытаемся применить на практике наши знания об операторах, арифметических действиях и установлении соответствия. Предположим, что в базе данных находятся следующие факты:
сумма(5).
сумма(З).
сумма(X+Y).
Рассмотрим вопрос:
?- сумма(2+3).
Какой из вышеприведенных фактов будет соответствовать данному запросу? Если вы думаете, что таковым будет первый факт, вам следует вернуться назад и еще раз прочесть разделы о структурах и операторах. В вопросе аргументом структуры суммаявляется структурас функтором + и компонентами 2 и 3. На самом деле указанной цели соответствует третий факт, при этом переменные Xи Yпринимают конкретные значения 2 и 3.
С другой стороны, если программист действительно хочет вычислить сумму, ему следовало бы воспользоваться предикатом is. Он должен был бы написать
?- X is 2+3.
или (в качестве развлечения) он мог бы определить предикат сложить, связывающий два целых числа и их сумму:
сложить (X, Y, Z):- Z is X+Y.
В этом определении Xи Yдолжны быть конкретизированы, а Zнеконкретизирована.
ГЛАВА 3. ИСПОЛЬЗОВАНИЕ СТРУКТУР ДАННЫХ
Оксфордский толковый словарь английского языка определяет слово «рекурсия» следующим образом:
РЕКУРСИЯ. [Теперь употребляется редко, устаревшее.] Обратное движение, возвращение.
Это определение загадочно и, по-видимому, устаревшее. В настоящее время рекурсия является очень популярным и мощным средством в области нечислового программирования. Она используется в двух случаях: для описания структур, имеющих другие структуры в качестве компонент, и для описания программ, выполнению которых предшествует выполнение их собственной копии. Иногда начинающие программисты относятся к рекурсии с подозрением, не понимая, как это можно определить некоторое отношение через само себя? В Прологе рекурсия – это нормальный и естественный способ представления структур данных и программ. Мы надеемся, что тема этой главы – рекурсия – обретает ясность удобным и ненавязчивым образом.
3.1. Структуры и деревья
Чтобы легче было понять сложную структуру, ее обычно представляют в виде дерева,в котором каждому функтору соответствует вершина, а компонентам соответствуют ветви дерева. Каждая ветвь может указывать на другую структуру, так что мы можем иметь структуры внутри структур. Обычно принято изображать дерево таким образом, чтобы корень дерева находился вверху, а ветви были направлены вниз, как это показано на рис. 3.1. Заметим, что два последних дерева имеют одинаковую форму, хотя корни и листья деревьев различны. Прежде чем читать дальше, вы должны быть уверены в том, что можете представить в виде дерева каждую из структур, с которыми вы уже сталкивались в предыдущих главах.
Предположим, у нас есть предложение «Джону нравится Мэри», и необходимо представить синтаксическую структуру этого предложения. В английском языке имеется очень простое синтаксическое правило построения предложений: предложение состоит из существительного, за которым следует глагольная группа. В свою очередь глагольная группа состоит из глагола и другого существительного. Это отношение между частями предложения может быть описано следующей структурой (которая представлена в виде дерева, приведенного на рис. 3.2): предложение(существительное, глагольная_группа(глагол, существительное)).
Рис. 3.1.
Если мы возьмем наше предложение («Джону нравится Мэри») и вставим слова из этого предложения в качестве аргументов функторов существительноеи глаголв структуру предложения, то мы получим (см. рис. 3.3):
предложение(существительное(джон), глагольная_группа(глагол(нравится), существительное(мэри)))
Этот пример показывает, как можно использовать структуры в языке Пролог для представления синтаксиса очень простых предложений. В общем случае если мы знаем, какой частью речи является каждое слово в предложении, то можно записать структуру на Прологе, которая в явном виде описывает отношения между различными словами в предложении. Эта задача сама по себе представляет интересную тему исследования, и далее мы еще вернемся к вопросу о том, как, используя Пролог, заставить ЭВМ «понимать» некоторые простые предложения.
Деревья могут также применяться для графического описания переменных внутри структуры, в частности показывая, как сцеплены переменные, имеющие одинаковые имена (см. рис. 3.4).
Рис. 3.2.
Рис. 3.3.
Рис. 3.4.
3.2. Списки
Список- довольно широко используемая структура данных в области числового программирования. Список -это упорядоченная последовательность элементов,которая может иметь произвольную длину. Признак упорядоченныйуказывает на то, что порядок элементов в последовательности является существенным. Элементамисписка могут быть любые термы – константы, переменные, структуры, которые включают, конечно, и другие списки. Указанные свойства очень полезны в ситуации, когда мы не в состоянии заранее предсказать, насколько большим должен быть список и какую информацию он будет содержать. Более того, списки позволяют представить практически любой тип структуры, который может потребоваться при символьных вычислениях. Списки широко используются для представления деревьев синтаксического разбора, грамматик, карт городов, программ для ЭВМ и математических объектов, таких как графы, формулы и функции. Существует язык программирования – Лисп, в котором единственными доступными структурами данных являются константа и список. Однако в Прологе список – это просто один из частных видов структуры.
Списки могут быть представлены как специального вида дерево. Список – это любой пустой список,не содержащий ни одного элемента, либо структура, имеющая две компоненты: голову и хвост списка. Конец списка обычно представляют как хвост, который является пустым списком. Пустой список записывают как [] – открывающая квадратная скобка, за которой следует закрывающая квадратная скобка. Голова и хвост списка являются компонентами функтора, обозначаемого точкой '.'. Так, список, состоящий из одного элемента ' а' есть .(а, []), а его представление в виде дерева имеет вид
Аналогично список, состоящий из атомов a, bи с, мог бы быть записан как .(а,.(b,.(с,[]))), что изображается следующим образом:
Иногда функтор точка ('.') определяется как оператор, так что допустимо для Пролога два последних списка записать как а.[]и а.(b.(с.[]))). Второй список можно было бы записать просто как а.b.с.[], так как функтор точка – правоассоциативный оператор. Списки являются упорядоченными последовательностями элементов, так что список а.bотличается от списка b.а.
Некоторые любят записывать древовидные диаграммы списков в виде дерева, «растущего» слева направо, ветви которого направлены вниз. Приведенный выше список, представленный диаграммой в виде такой «виноградной лозы» выглядит так:
В этой диаграмме компонента функтора '.', соответствующая голове списка, «свисает» вниз, а компонента, соответствующая хвосту списка, «растет» вправо. Конец списка четко выделен тем, что последняя компонента – хвост списка – является пустым списком. Главное преимущество использования диаграммы для представления списка заключается в том, что она может быть записана справа налево на листе бумаги.
«Виноградная» диаграмма может оказаться удобной для записи списков на бумаге, когда нам необходимо видеть структуру списка, но в программах на Прологе для записи списков такие диаграммы не используются. Так как запись сложных списков с помощью функтора '.' часто оказывается неудобной, то в Прологе предусмотрена другая синтаксическая форма, которая может быть использована для записи списков в программе. Это так называемая скобочная форма записи списка.Она представляет собой заключенную в квадратные скобки последовательность элементов списка, разделенных запятыми. Например, упоминавшиеся выше списки могут быть записаны в скобочной форме в виде [а]и [а, b, с]. Списки могут содержать другие списки или переменные. Например, в Прологе допустимы следующие списки:
[]
[конкретный, человек, [любит, ловить, рыбу]]
[а, V1, b, [X, Y]]
Переменные, входящие в списки, ничем не отличаются от переменных в любой другой структуре. Они в любой момент могут быть конкретизированы, так что умелое использование переменных может обеспечить образование «пустых мест» в списке, которые впоследствии могут быть заполнены данными.
Чтобы продемонстрировать структуру списков, содержащих в качестве элементов другие списки, приведем «виноградную» диаграмму для последнего из рассмотренных списков:
Из приведенной диаграммы ясно видно, что каждый ее горизонтальный уровень является списком, состоящим из некоторого числа элементов. Верхний уровень на приведенной диаграмме представляет список, содержащий четыре элемента, один из которых сам является списком. Второй уровень, содержащий два элемента, представляет четвертый элемент списка верхнего уровня. Работа со списками основана на расщеплении их наголовуи хвостсписка. Голова списка – это первый аргумент функтора '.', который используется для конструирования списка. Хвост списка – это второй аргумент функтора '.'. В случае когда для записи списка используется скобочная форма записи, головой списка является первый его элемент. Хвост списка представляет список,состоящий из всех элементов исходного списка, за исключением первого его элемента. Следующие примеры демонстрируют расщепление списков на голову и хвост:
| Список | Голова | Хвост |
| [а, b, с] | а | [b, с] |
| [а,] | а | [] |
| [] | ||
| [[эта, кошка], сидела] | [эта, кошка] | [сидела] |
| [эта, [кошка, сидела]] | эта | [кошка, сидела]] |
| [эта, [кошка, села], на пол] | эта | [кошка, села], на пол] |
| [X+Y, х + y] | X + Y | [x + y] |
Заметим, что пустой список не имеет ни головы, ни хвоста. В последнем примере оператор ± используется как функтор для структур +(Х, Y)и +(х,у).
Так как операция расщепления списка на голову и хвост очень широко используется, то в Прологе введена специальная форма для представления списка с головой Xи хвостом Y. Это записывается как [X|Y], где для разделения Xи Yиспользуется вертикальная черта. При конкретизации структуры подобного вида Xсопоставляется с головой списка, a Y– с хвостом списка, как это показано в следующем примере:
p([1, 2, 3]).
p([эта, кошка, сидела, [на, этой, подстилке]]).
?- p([X|Y]).
X = 1 Y=[2,3] ;
X=эта Y=[кошка, сидела, [на, этой, подстилке]]
?- p([_,_,_,[_|X]]).
X=[этой, подстилке]
Ниже приведено еще несколько примеров с использованием различных синтаксических возможностей записи списков, показывающих, каким образом производится сопоставление списков. В этих примерах делается попытка сопоставить два заданных списка, конкретизируя переменные, если это возможно.
| Список 1 | Список 2 | Конкретизация |
| [X, Y, Z] | [джону,нравится,рыба] | X=джону Y= нравится Z = рыба |
| [кошка] | [X| Y] | X= кошка |
| [X, Y | Z] | [мэри,нравится,вино] | X = мэри Y = нравится Z = [вино] |
| [[этот, Y]|Z] | [[X, заяц], [находится, здесь]] | X = этот Y = заяц Z = [[находится_ здесь]] |
| [X, Y|Z, W] | (синтаксически некорректная конструкция списка) | |
| [золотистый | T] | [золотистый, норфолк] | T= [норфолк] |
| [лошадь, X] | [белая, лошадь] | (сопоставление невозможно) |
| [белая | Q] | [P | лошадь] | P= белая Q= лошадь |
Как видно из последнего примера, используя скобочную форму записи списков, можно создавать структуры, похожие на списки, но не заканчивающиеся пустым списком. Одна из таких структур, [белая|лошадь],обозначает структуру, головой которой является