Лекции в ворде (1156536), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

+ - * / ^ = : ; ? @ $ &

Заметим, что атом, начинающийся с /*, будет воспринят как на­чало комментария, если он не заключен в одинарные кавычки.

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

Атом, который необязательно заключать в кавычки, может быть записан и в кавычках. Запись с внешними кавычками и без них опре­деляет один и тот же атом.

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

ЧИСЛА

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

ПЕРЕМЕННЫЕ

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

Синтаксис переменной довольно прост. Она должна начинаться с прописной буквы или символа подчеркивания и содержать только символы букв, цифр и подчеркивания.

Переменная, состоящая только из символа подчеркивания, назы­вается анонимной и используется в том случае, если имя переменной несущественно.

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

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

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

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

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

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

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

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

Число компонент в структуре называется арностью структуры. Так, в данном примере структура собака имеет арность 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(...))))). В программе это иногда вызывает бесконечный цикл.

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

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

Характеристики

Список файлов лекций