ОБЛАСТЬ ДЕЙСТВИЯ ПЕРЕМЕННЫХ

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

Единственным исключением из правила определения области действия переменных является анонимная переменная, например, «_» в цели любит(Х,_). Каждая анонимная переменная есть отдель­ная сущность. Она применяется тогда, когда конкретное значение переменной несущественно для данного утверждения. Таким обра­зом, каждая анонимная переменная четко отличается от всех других анонимных переменных в утверждении.

Переменные, отличные от анонимных, называются именованны­ми, а неконкретизированные (переменные, которым не было присво­ено значение) называются свободными.

СЛОЖНЫЕ ТЕРМЫ, ИЛИ СТРУКТУРЫ

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

Приведем примеры структурированных термов:

собака(рекс), родитель(Х,У).

Число компонент в структуре называется арностью структуры. Так, в данном примере структура собака имеет арность 1 (записыва­ется как собака/1), а структура родитель - арность 2 (родитель/2). Заметим, что атом можно рассматривать как структуру арности 0.

Для некоторых типов структур допустимо использование альтер­нативных форм синтаксиса. Это синтаксис операторов для структур арности 1 и 2, синтаксис списков для структур в форме списков и син­таксис строк для структур, являющихся списками кодов символов.

СИНТАКСИС ОПЕРАТОРОВ

Структуры арности 1 и 2 могут быть записаны в операторной форме, если атом, используемый как главный функтор в структуре, объявить оператором (см. гл. 6).

СИНТАКСИС СПИСКОВ

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

СИНТАКСИС СТРОК

Строка определяется как список кодов символов. Коды символов имеют особое значение в языках программирования. Они выступают как средство связи компьютера с внешним миром. В большинстве ре­ализации Пролога существует специальный синтаксис для записи строк. Он подобен синтаксису атомов. Строкой является любая по­следовательность символов, которые могут быть напечатаны (кроме двойных кавычек), заключенная в двойные кавычки. Двойные ка­вычки в пределах строки записываются дважды «».

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

УТВЕРЖДЕНИЯ

Программа на Прологе есть совокупность утверждений. Утверж­дения состоят из целей и хранятся в базе данных Пролога. Таким об­разом, база данных Пролога может рассматриваться как программа на Прологе. В конце утверждения ставится точка «.». Иногда утверж­дение называется предложением.

Основная операция Пролога - доказательство целей, входящих в утверждение.

Существуют два типа утверждений:

факт: это одиночная цель, которая, безусловно, истинна;

правило: состоит из одной головной цели и одной или более хво­стовых целей, которые истинны при некоторых условиях.

Правило обычно имеет несколько хвостовых целей в форме конъ­юнкции целей.

Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хво­стовые цели.

Примеры фактов:

собака(реке). родитель(голди.рекс).

Примеры правил:

собака (X) :- родитель (X.Y),собака (Y). человек(Х) :-мужчина(Х).

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

Так, правило

собака (X) :- родитель(Х,У),собака(У). может быть задано как

:-собака (X) ',' родитель(Х.У) .собака (Y).

Запись верна, поскольку :- является оператором «при условии, что», а ',' - это оператор конъюнкции. Однако удобнее записывать это как

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

и читать следующим образом: « Х - собака при условии, что родите­лем Х является Y и Y - собака».

Структуру иногда изображают в виде дерева, число ветвей кото­рого равно арности структуры.

ЗАПРОСЫ

После записи утверждений в базу данных вычисления могут быть инициированы вводом запроса.

Запрос выглядит так же, как и целевое утверждение, образуется и обрабатывается по тем же правилам, но он не входит в базу данных (программу). В Прологе вычислительная часть программы и данные имеют одинаковый синтаксис. Программа обладает как декларатив­ной, так и процедурной семантикой. Мы отложим обсуждение этого вопроса до последующих глав. Запрос обозначается в Прологе утвер­ждением ?-, имеющим арность 1. Обычно запрос записывается в опе­раторной форме: за знаком ?- следует ряд хвостовых целевых утвер­ждений (чаще всего в виде конъюнкции).

Приведем примеры запросов:

?-собака(X). ?- родитель(Х.У),собака (Y).

или, иначе,

'?-'(собака(Х)) С?-') ','(родитель(Х„У»,собака (Y)).

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

Запрос иногда называют управляющей командой (директивой), так как он требует от Пролог-системы выполнения некоторых дейст­вий. Во многих реализациях Пролога для управляющей команды ис­пользуется альтернативный символ, а символ ?- обозначает приглашение верхнего уровня интерпретатора Пролога. Альтернативным символом является :-. Таким образом,

:-write(co6aкa).

- это управляющая команда, в результате выполнения которой печа­тается атом собака. Управляющие команды будут рассмотрены ниже при описании ввода программ.

ВВОД программ

Введение списка утверждений в Пролог-систему осуществляется с помощью встроенного предиката consult. Аргументом предиката consult является атом, который обычно интерпретируется системой как имя файла, содержащего текст программы на Прологе. Файл от­крывается, и его содержимое записывается в базу данных. Если в файле встречаются управляющие команды, они сразу же выполня­ются. Возможен случай, когда файл не содержит ничего, кроме уп­равляющих команд для загрузки других файлов. Для ввода утверж­дений с терминала в большинстве реализации Пролога имеется спе­циальный атом, обычно user. С его помощью утверждения записыва­ются в базу данных, а управляющие команды выполняются немед­ленно.

Помимо предиката consult, в Прологе существует предикат reconsult. Он работает аналогичным образом. Но перед добавлени­ем утверждений к базе данных из нее автоматически удаляются те утверждения, головные цели которых сопоставимы с целями, со­держащимися в файле перезагрузки. Такой механизм позволяет вводить изменения в базу данных. В Прологе имеются и другие методы добавления и удаления утверждений из базы данных. Не­которые реализации языка поддерживают модульную структуру, позволяющую разрабатывать модульные программы.

В заключение раздела дадим формальное определение синтакси­са Пролога, используя форму записи Бэкуса-Наура, иногда называе­мую бэкусовской нормальной формой (БНФ).

запрос ::- голова утверждения

правило ::– голова утверждения :- хвост утверждения

факт ::- голова утверждения

голова утверждения ::-атом | структура

хвост утверждения ::- атом структура,

термы ::-терм [,термы]

терм ::- число | переменная | атом | структура

структура ::-атом (термы)

Данное определение синтаксиса не включает операторную, спи­сковую и строковую формы записи. Полное определение дано в при­ложении А. Однако, любая программа на Прологе может быть напи­сана с использованием вышеприведенного синтаксиса. Специальные формы только упрощают понимание программы. Как мы видим, син­таксис Пролога не требует пространного объяснения. Но для написа­ния хороших программ необходимо глубокое понимание языка.

Унификация

Одним из наиболее важных аспектов программирования на Про­логе являются понятия унификации (отождествления) и конкретиза­ции переменных.

Пролог пытается отождествить термы при доказательстве, или согласовании, целевого утверждения. Например, в программе из гл. 1 для согласования запроса ?- собака(Х) целевое утверждение соба­ка (X) было отождествлено с фактом собака (реке), в результате чего переменная Х стала конкретизированной: Х= рекc.

Переменные, входящие в утверждения, отождествляются особым образом - сопоставляются. Факт доказывается для всех значений пе­ременной (переменных). Правило доказывается для всех значений переменных в головном целевом утверждении при условии, что хво­стовые целевые утверждения доказаны. Предполагается, что пере­менные в фактах и головных целевых утверждениях связаны кван­тором всеобщности. Переменные принимают конкретные значения на время доказательства целевого утверждения.

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

Терм Х сопоставляется с термом Y по следующим правилам. Ес­ли Х и Y - константы, то они сопоставимы, только если они одинако­вы. Если Х является константой или структурой, а Y - неконкретизи­рованной переменной, то Х и Y сопоставимы и Y принимает значе­ние Х (и наоборот). Если Х и Y - структуры, то они сопоставимы тог­да и только тогда, когда у них одни и те же главный функтор и ар­ность и каждая из их соответствующих компонент сопоставима. Если Х и Y - неконкретизированные (свободные) переменные, то они со­поставимы, в этом случае говорят, что они сцеплены. В (Таблица 2) при­ведены примеры отождествимых и неотождествимых термов.

Таблица 2. Иллюстрация унификации.

Заметим, что Пролог находит наиболее общий унификатор тер­мов. В последнем примере (рис.2.1) существует бесконечное число унификаторов:

X-1, Z-2; X-2, Z-2; ....

но Пролог находит наиболее общий: Х=Z.

Следует сказать, что в большинстве реализации Пролога для по­вышения эффективности его работы допускается существование циклических унификаторов. Например, попытка отождествить тер­мы f(X) и Х приведет к циклическому унификатору X=f(X), кото­рый определяет бесконечный терм f(f(f(f(f(...))))). В программе это иногда вызывает бесконечный цикл.

Возможность отождествления двух термов проверяется с по­мощью оператора =.

Ответом на запрос

?- 3+2=5.

будет

нет

так как термы не отождествимы (оператор не вычисляет значения своих аргументов), но попытка доказать

?-строка(поз(Х)) -строка(поз(23)).

закончится успехом при

Х=23.

Унификация часто используется для доступа к подкомпонентам термов. Так, в вышеприведенном примере Х конкретизируется пер­вой компонентой терма поз(23), который в свою очередь является компонентой терма строка.

Бывают случаи, когда надо проверить, идентичны ли два терма. Выполнение оператора = = заканчивается успехом, если его аргумен­ты - идентичные термы. Следовательно, запрос

?-строка(поз(Х)) --строка (поз (23)).

дает ответ

нет

поскольку подтерм Х в левой части (X - свободная переменная) не идентичен подтерму 23 в правой части, Однако запрос

?- строка (поз (23)) --строка (поз (23)).

дает ответ

да

Отрицания операторов = и - = записываются как \= и \= = соот­ветственно.