Рис. 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.2): предложение(существительное, глагольная_группа(глагол, существительное)).
Рис. 3.1.
Если мы возьмем наше предложение («Джону нравится Мэри») и вставим слова из этого предложения в качестве аргументов функторов существительноеи глаголв структуру предложения, то мы получим (см. рис. 3.3):
предложение(существительное(джон), глагольная_группа(глагол(нравится), существительное(мэри)))
Этот пример показывает, как можно использовать структуры в языке Пролог для представления синтаксиса очень простых предложений. В общем случае если мы знаем, какой частью речи является каждое слово в предложении, то можно записать структуру на Прологе, которая в явном виде описывает отношения между различными словами в предложении. Эта задача сама по себе представляет интересную тему исследования, и далее мы еще вернемся к вопросу о том, как, используя Пролог, заставить ЭВМ «понимать» некоторые простые предложения.