У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

Рис. 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.1. Заметим, что два последних дерева имеют одинаковую форму, хотя корни и листья деревьев различны. Прежде чем читать дальше, вы должны быть уверены в том, что можете представить в виде дерева каждую из структур, с которыми вы уже сталкивались в предыдущих главах.

Предположим, у нас есть предложение «Джону нравится Мэри», и необходимо представить синтаксическую структуру этого предложения. В английском языке имеется очень простое синтаксическое правило построения предложений: предложение состоит из существительного, за которым следует глагольная группа. В свою очередь глагольная группа состоит из глагола и другого существительного. Это отношение между частями предложения может быть описано следующей структурой (которая представлена в виде дерева, приведенного на рис. 3.2): предложение(существительное, глагольная_группа(глагол, существительное)).

Рис. 3.1.

Если мы возьмем наше предложение («Джону нравится Мэри») и вставим слова из этого предложения в качестве аргументов функторов существительноеи глаголв структуру предложения, то мы получим (см. рис. 3.3):

предложение(существительное(джон), глагольная_группа(глагол(нравится), существительное(мэри)))

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