Программирование на языке пролог

Рис. 2.5.

Отступая дальше, стрелка достигнет места, где было выбрано утверждение, соответствующее целевому утверждению отец. В первую очередь освобождаются все переменные, которые были конкретизированы в результате использования данного утверждения. Это означает, что переменная Fвновь становится неконкретизированной. Затем Пролог просматривает базу данных, начиная с утверждения, следующего за первым утверждением с предикатом отец(здесь находится маркер), пытаясь найти альтернативное утверждение. Если предположить, что мэриимеет только одного отца, то этот процесс успехом не завершится. Поэтому стрелка продолжит отступление. Она покинет прямоугольник отец(мэри, F)(это целевое утверждение недоказуемо) и вернется в прямоугольник мать(мэри,анна)(для того, чтобы попытаться передоказать данное целевое утверждение) (см. рис. 2.6).

Рис. 2.6.

Отступление стрелки будет продолжаться до успешного доказательства соответствующего целевого утверждения.

Эти примеры иллюстрируют общую схему повторного рассмотрения целевых утверждений в процессе возврата. Когда некоторое целевое утверждение недоказуемо, стрелка возвращается из соответствующего прямоугольника в прямоугольник с предшествующим целевым утверждением. Стрелка отступает до тех пор, пока не встретится маркер. Все переменные, которые были конкретизированы в результате предыдущего выбора сопоставимого утверждения, становятся неконкретизированными. Затем Пролог возобновляет поиск в базе данных сопоставимого утверждения, начиная с маркера. Если сопоставимое утверждение будет найдено, новое место помечается маркером, создаются прямоугольники для целевых подутверждений и стрелка опять начинает движение вниз. В противном случае стрелка продолжает отступать вверх в поисках другого маркера.

2.6.3. Установление соответствия

Правила, определяющие, подходит ли некоторое утверждение для согласования с целевым утверждением, выглядят следующим образом. Отметим, что при выборе утверждения все переменные сначала неконкретизированы.

• Неконкретизированная переменная соответствует любому объекту. Этот объект становится значением переменной.

• Целое число или атом соответствуют только самим себе.

• Между структурами можно установить соответствие, только если они имеют одинаковый функтор, одинаковое число параметров и соответствующие параметры соответствуют друг другу.

Особым случаем является установление соответствия между двумя неконкретизированными переменными. В этом случае мы говорим, что переменные сцеплены.Две сцепленные переменные обладают следующим свойством: как только одна из них принимает конкретное значение, то же самое конкретное значение принимает и другая.

Если читатель заметил сходство между установлением соответствия и приравниванием аргументов (разд. 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. Списки

Список– довольно широко используемая структура данных в области числового программирования. Список -это упорядоченная последовательность элементов,которая может иметь произвольную длину. Признак упорядоченныйуказывает на то, что порядок элементов в последовательности является существенным. Элементамисписка могут быть любые термы – константы, переменные, структуры, которые включают, конечно, и другие списки. Указанные свойства очень полезны в ситуации, когда мы не в состоянии заранее предсказать, насколько большим должен быть список и какую информацию он будет содержать. Более того, списки позволяют представить практически любой тип структуры, который может потребоваться при символьных вычислениях. Списки широко используются для представления деревьев синтаксического разбора, грамматик, карт городов, программ для ЭВМ и математических объектов, таких как графы, формулы и функции. Существует язык программирования – Лисп, в котором единственными доступными структурами данных являются константа и список. Однако в Прологе список – это просто один из частных видов структуры.