Материал: 3130

3.1.1. Атомы и числа

Атомы и числа представляют собой цепочки следующих символов:

прописные буквы А, В, ..., Z

строчные буквы а, b, ..., z

цифры 0, 1, 2, ..., 9

специальные символы, такие как + - * / = : . & _ ~ Атомы можно создавать тремя способами:

(1)из цепочки букв, цифр и символа подчеркивания _, начиная такую цепочку со строчной буквы

(2)из специальных символов: <--->, ======>, ..., ., ..., : : =

(3)из цепочки символов, заключенной в одинарные кавычки.

'Том', 'Южная_Америка', 'Сара Джонс'

Числа в Прологе бывают целыми и вещественными. Синтаксис целых чисел: 1, 1313, 0, -97, - допускается их диапазон от -16383 до 16383. Синтаксис вещественных чисел: 3.14, -0.0035, 100.2.

3.1.2. Переменные

Переменные - это цепочки, состоящие из букв, цифр и символов подчеркивания:

Х, Результат, Объект2, Список_участников, СписокПокупок, _х23, _23

Если переменная встречается в предложения только один раз, то можно использовать "анонимную" переменную, которая записывается в виде одного символа подчеркивания. Рассмотрим, например, следующее правило:

имеетребенка( X) :- родитель( X, Y).

Это правило гласит: "Для всех X, Х имеет ребенка, если X является родителем некоторого Y". Свойство имеетребенка определяется таким образом, что не зависит от имени ребенка. Следовательно, уместно использовать анонимную переменную. Вышеприведенное правило можно переписать так:

имеетребенка( X) :- родитель( X, _ ).

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

некто_имеет_ребенка :- родитель( _, _ ).

Это предложение эквивалентно следующему:

некто_имеет_ребенка :- родитель( X, Y).

Однако оно имеет совершенно другой смысл, нежели

11

некто_имеет_ребенка :- родитель( X, X).

Если анонимная переменная встречается в вопросе, то ее значение не выводится при ответе системы на этот вопрос. Если нас интересуют люди, имеющие детей, но не имена этих детей, мы можем просто спросить:

?- родитель( X, _ ).

Лексический диапазон имени - одно предложение. Это значит, что если, например, имя Х15 встречается в двух предложениях, то оно обозначает две разные переменные. Однако внутри одного предложения каждое его появлений обозначает одну и ту же переменную. Для констант ситуация другая: один и тот же атом обозначает один и тот же объект в любом предложении.

3.1.3. Структуры

Структурные объекты (или просто структуры) - это объекты, которые состоят из нескольких компонент. Компоненты, в свою очередь, могут быть структурами. Например, дату можно рассматривать как структуру, состоящую из трех компонент: день, месяц, год. Хотя они и составлены из нескольких компонент, структуры в программе ведут себя как единые объекты. Для того, чтобы объединить компоненты в структуру, требуется выбрать функтор. Для нашего примера подойдет функтор дата. Тогда дату 1 мая 1983 г. можно запи-

сать: дата(1, май, 1983).

Все компоненты в данном примере являются константами (две компоненты - целые числа и одна - атом). Компоненты могут быть также переменными или структурами. Произвольный день в мае можно представить структурой: дата(День, май, 1983). Заметим, что День является переменной и ей можно приписать произвольное значение на некотором более позднем этапе вычислений. Такой метод структурирования данных прост и эффективен. Это является одной из причин широкого использования Пролога для обработки символьной информации.

Синтаксически все объекты данных в Прологе представляют собой термы. Например, май и дата( 1, май, 1983) – суть термы.

Рис.3.2. Дата - пример структурного объекта: (а) его представление в виде дерева; (б) запись на Прологе.

12

Структурные объекты изображаются в виде деревьев. Корнем дерева служит функтор, ветвями, выходящими из него, - компоненты. Если некоторая компонента тоже является структурой, тогда ей соответствует поддерево в дереве, изображающем весь структурный объ-

ект.

Тогда объекты, приведенные на Рис.3.3, можно представить следующими термами: Р1 = точка( 1, 1)

P2 = точка(2, 3)

S = отрезок(P1, P2) = отрезок(точка(1, 1), точка(2, 3) ) Т = треугольник(точка(4, 2), точка(6, 4), точка(7, 1) )

Представление этих объектов в виде деревьев приводится на Рис.3.4. Функтор, служащий корнем дерева, называется главным функтором терма.

Если бы в такой же программе фигурировали точки трехмерного пространства, то можно было бы

13

для их представления использовать другой функтор, скажем точка3: точка3(X, Y, Z). Можно воспользоваться одним и тем же именем точка одновременно для точек двумерного и трехмерного пространств, например: точка(XI, Y1) и точка (X, Y, Z). Если одно и то же имя появляется в программе в двух различных смыслах, как в вышеупомянутом примере с точкой, то пролог-система будет различать их по числу аргументов и интерпретировать это имя как два функтора: один - двухаргументный; второй - трех. Т.е. каждый функтор определяется двумя параметрами:

(1)именем, синтаксис которого совпадает с синтаксисом атомов;

(2)n-арностью - т. е. числом аргументов.

Все структурные объекты в Прологе - это деревья, представленные в программе термами. Рассмотрим пример: на Рис.3.5 показана древовидная структура, соответствующая порядку вычисления

арифметического выражения (а+в)*(с-5) Рис.3.5. Древовидная структура, соответ-

Наиболее важной операцией над термами является сопоставление. Сопоставление само по себе может производить содержательные вы-

числения. Пусть даны два терма. Они сопоставимы, если: (1) они идентичны или (2) переменным в обоих термах можно приписать в качестве значений объекты (т.е. конкретизировать их) таким образом, чтобы после подстановки этих объектов в термы вместо переменных, последние стали идентичными.

Например, термы дата(Д, М, 1983) и дата(Д1, май, Y1) сопоставимы, так как Д заменяется на Д1, М заменяется на май, Y1 заменяется на 1983. Более компактно такая подстановка записывается в форме, в которой пролог-система выводит результаты: Д=Д1, М=май, Y1=1983. С другой стороны, дата(Д, М, 1983) и дата(Д1, Ml, 1944) не сопоставимы, как и термы дата(X, Y, Z) и точка(X, Y, Z).

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

Рассмотрим еще раз сопоставление двух дат. Запрос на проведение такой операции можно передать системе, используя оператор '=':

14

?- дата(Д, М, 1983)= дата(Д1, май, Y1).

Мы уже упоминали конкретизацию Д=Д1, М=май, Y1=1983, на которой достигается сопоставление. Существуют, однако, и другие конкретизации, делающие оба терма идентичными. Вот две из них:

Д=1, Д1=1, М=май, Y1=1983

Д=третий, Д1=третий, М=май, Y1=1983

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

?- дата(Д, М, 1983)= дата(Д1, май, Y1). дата(Д, М, 1983)=дата(15, М, Y).

Для достижения первой цели система припишет переменным такие значения: Д=Д1, М=май, Y1=1983. После достижения второй цели, значения переменных станут более конкретными: Д=15, Д1=15, М=май, Y1=1983, Y=1983.

Общие правила выяснения, сопоставимы ли два терма S и Т, таковы:

(1)Если S и Т - константы, то S и Т сопоставимы, только если они являются одним и тем же объектом.

(2)Если S - переменная, а Т - произвольный объект, то они сопоставимы, и S приписывается значение Т. Наоборот, если Т - переменная, а S - произвольный объект, то Т приписывается значение S.

(3)Если S и Т - структуры, то они сопоставимы, только если (а) S и Т имеют одинаковый глав-

ный функтор и (б) все их соответствующие компо-

ненты сопоставимы.

Результирующая конкретизация определяется сопоставлением компонент.

Последнее из этих правил можно наглядно представить себе, рассмотрев древовидное изображение термов, такое, например, как на Рис.3.6. Процесс сопоставления начинается от корня (главных функторов). Поскольку оба

15