Автор: Сотник С.Л.

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

Синтаксис

ТЕРМЫ

Объекты данных в Прологе называются термами. Терм может быть константой, пе-ременной или составным термом (структурой). Константами являются целые и действительные числа, например:

0, -l, 123.4, 0.23E-5,

(некоторые реализации Пролога не поддерживают действительные числа).

К константам относятся также атомы, такие, как:

голди, а, атом, +, :, 'Фред Блогс', [].

Атом есть любая последовательность символов, заключенная в одинарные кавычки. Ка-вычки опускаются, если и без них атом мож¬но отличить от символов, используемых для обозна-чения перемен¬ных. Приведем еще несколько примеров атомов:

abcd, фред, ':', Джо.

Полный синтаксис атомов описан ниже.

Как и в других языках программирования, константы обознача¬ют конкретные элемен-тарные объекты, а все другие типы данных в Прологе составлены из сочетаний констант и пере-менных.

Имена переменных начинаются с заглавных букв или с символа подчеркивания "_". Примеры переменных:

X, Переменная, _3, _переменная.

Если переменная используется только один раз, необязательно называть ее. Она может быть записана как анонимная переменная, состоящая из одного символа подчеркивания "_". Переменные, подо¬бно атомам, являются элементарными объектами языка Пролог.

Завершает список синтаксических единиц сложный терм, или структура. Все, что не может быть отнесено к переменной или кон¬станте, называется сложным термом. Следовательно, сложный терм состоит из констант и переменных.

Теперь перейдем к более детальному описанию термов.

КОНСТАНТЫ

Константы известны всем программистам. В Прологе константа может быть атомом или числом.

ATOM

Атом представляет собой произвольную последовательность сим¬волов, заключенную в одинарные кавычки. Одинарный символ ка¬вычки, встречающийся внутри атома, записывается дважды. Когда атом выводится на печать, внешние символы кавычек обычно не пе¬чатаются. Существует несколько исключений, когда атомы необяза¬тельно записывать в кавычках. Вот эти исключения:

1) атом, состоящий только из чисел, букв и символа подчеркива¬ния и начинающийся со строчной буквы;

2) атом, состоящий целиком из специальных символов. К специ¬альным символам отно-сятся:

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

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

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

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

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

ЧИСЛА

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

ПЕРЕМЕННЫЕ

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

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

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

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

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

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

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

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

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

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

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

Число компонент в структуре называется арностью структуры. Так, в данном примере структура собака имеет арность 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. Иллюстрация унификации.

Терм1
-----
джек(Х) 
джек (личность) 
джек(Х,Х) 
джек(Х.Х) 
джек( . ) 
f(Y,Z) 
Х	

Терм2
-----
джек (человек) 
джек (человек) 
джек(23,23) 
джек (12,23) 
джек(12,23) 
Х 
Z	

Отождествимы ?
--------------
да: Х=человек 
нет 
да: Х=23 
нет 
да 
да: X=f(Y,Z) 
да: X=Z

Заметим, что Пролог находит наиболее общий унификатор тер¬мов. В последнем приме-ре (рис.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)).

дает ответ

да

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

Арифметические выражения

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

Введение

Язык Пролог не предназначен для программирования задач с большим количеством арифметических операций. Для этого ис¬пользуются процедурные языки программирования. Од-нако в лю¬бую Пролог-систему включаются все обычные арифметические операторы:

+ сложение

— вычитание

* умножение

/ деление

mod остаток от деления целых чисел

div целочисленное деление

В некоторых реализациях языка Пролог присутствует более ши¬рокий набор встроенных арифметических операторов.

Пролог позволяет также сравнивать арифметические выраже¬ния, используя следующие встроенные предикаты:

Диапазоны чисел, входящих в арифметические выражения, за¬висят от реализации Про-лога. Например, система ICLPROLOG опе¬рирует с целыми числами со знаком в диапазоне

–8388606 ... 8388607

Арифметические выражения

Арифметическое выражение является числом или структурой. В структуру может вхо-дить одна или более компонент, таких, как чис¬ла, арифметические операторы, арифметические списковые выраже¬ния, переменная, конкретизированная арифметическим выражени¬ем, унарные функторы, функторы преобразования и арифметиче¬ские функторы.

Числа. Числа и их диапазоны определяются в конкретной реали¬зации Пролога.

Арифметические операторы. + - * / mod div

Арифметические списковые выражения. Если Х - арифметиче¬ское выражение, то список [X ] также является арифметическим вы¬ражением, например [1,2,3]. Первый элемент списка используется как операнд в выражении. Скажем,

X is ([l,2,3]+5)

имеет значение 6.

Арифметические списковые выражения полезны и при обработке символов, поскольку последние могут рассматриваться как неболь¬шие целые числа. Например, символ "а" эквивален-тен [97 ] и, буду¬чи использован в выражении, вычисляется как 97. Поэтому значение выражения «р»+"А"-"а" равно 80, что соответствует коду ASCII для «Р».

Переменная, конкретизированная арифметическим выражени¬ем. Примеры:

Х-5+2 и У-3*(2+А)

Унарные функторы. Примеры:

+(Х) и -(У)

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

float (X) преобразует целое число Х в число с плавающей точкой.

Математические функторы. Пример: квадрат(Х) объявлен как оператор и эквивалентен арифметическому выражению (Х*Х).

Арифметические операторы

Атомы +, -, *, /, mod и div - обычные атомы Пролога и могут использоваться почти в любом контексте. Указанные атомы - не встроенные предикаты, а функторы, имеющие силу только в преде¬лах арифметических выражений. Они определены как инфиксные операторы. Эти атомы являются главными функторами в структуре, а сама структура может принимать только описанные выше формы.

Позиция, приоритет и ассоциативность арифметических опера¬торов четко заданы и пе-речислены в таблице операторов в гл. 6.

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

Арифметические операторы определяются Пролог-системой. Ес¬ли мы напишем преди-кат

среднее (X,Y,Z) :- Z is (X+Y)/2.

то хотя можно определить среднее как оператор

?- ор(250^х, среднее).

но Пролог выдаст сообщение об ошибке, если встретит выражение Z is X среднее Y.

Это произойдет потому, что Х среднее Y не образует арифметиче¬ского выражения, а среднее не является арифметическим операто¬ром, определенным в системе.

Вычисление арифметических выражений

В Прологе не допускаются присваивания вида Сумма=2+4.

Выражение такого типа вычисляется только с помощью систем¬ного предиката is, на-пример:

Сумма is 2 + 4.

Предикат is определен как инфиксный оператор. Его левый аргу¬мент - или число, или неконкретизированная переменная, а правый аргумент - арифметическое выражение.

Попытка доказательства целевого утверждения Х is Y заканчи¬вается успехом в одном из следующих случаев:

а) Х - неконкретизированная переменная, а результат вычисле¬ния выражения Y есть число;

б) Х - число, которое равно результату вычисления выражения Y. Цель Х is Y не имеет побочных эффектов и не может быть согла¬сована вновь. Если Х не является неконкретизиро-ванной переменной или числом, или если Y - не арифметическое выражение, возникает ошибка.

Примеры:

D is 10- 5 заканчивается успехом и D становится равным 5

4 is 2 * 4 - 4 заканчивается успехом

2 * 4 - 4 is 4 заканчивается неудачей

a is 3 + 3 заканчивается неудачей

X is 4 + а заканчивается неудачей

2 is 4 - X заканчивается неудачей

Обратите внимание, что предикат is требует, чтобы его первый аргумент был числом или неконкретизированной переменной. Поэтому М - 2 is 3 записано неверно. Предикат is не является встроен¬ным решателем уравнений.

Сравнение результатов арифметических выражений

Системные предикаты =:=, =\=, >, <, >= и <= определены как инфикс¬ные операторы и применяются для сравнения результатов двух арифметических выражений.

Для предиката @ доказательство целевого утверждения X@Y за¬канчивается успехом, если результаты вычисления арифметических выражений Х и Y находятся в таком отношении друг к другу, кото¬рое задается предикатом @.

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

С помощью предикатов описываются следующие отношения:

Х =:= Y Х равно Y

Х =\= Y Х не равно Y

Х < Y Х меньше Y

Х > Y Х больше Y

Х <= Y Х меньше или равно Y

Х >= Y Х больше или равно Y

Использование предикатов иллюстрируют такие примеры:

а > 5 заканчивается неудачей

5+2+7 > 5+2 заканчивается успехом

3+2 =:= 5 заканчивается успехом

3+2 < 5 заканчивается неудачей

2 + 1 =\= 1 заканчивается успехом

N > 3 заканчивается успехом, если N больше 3, и неудачей в противном слу-чае

Структуры данных

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

Списки

СПИСКОВАЯ ФОРМА ЗАПИСИ

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

[джек, джон, фред, джилл, джон]

[имя (джон, смит), возраст (джек, 24), X]

[Х.У.дата (12,январь, 1986) ,Х]

[]

Запись [H|T] определяет список, полученный добавлением Н в начало списка Т. Гово-рят, что Н - голова, а Т - хвост списка [HIT]. На вопрос

?-L=[a | [b, c, d]]. будет получен ответ

L=[a, b, c, d]

а на запрос

?-L= [a, b, c, d], L2=[2 | L]. - ответ

L=[a, b, c, d], L2- [2, a, b, c, d]

Запись [Н | Т] используется для того, чтобы определить голову и хвост списка. Так, за-прос

?- [X | Y]=[a, b, c]. дает

Х=а, Y=[b, c]

Заметим, что употребление имен переменных Н и Т необязательно. Кроме записи вида [H|T], для выборки термов используются пе¬ременные. Запрос

?-[a, X, Y]=[a, b, c].

определит значения

X=b

Y=c

а запрос

?- [личность(Х) | Т]=[личность(джон), а, b].

значения

Х=джон

Т=[а, Ь]

НЕКОТОРЫЕ СТАНДАРТНЫЕ ЦЕЛЕВЫЕ УТВЕРЖДЕНИЯ ДЛЯ ОБРАБОТКИ СПИ-СКОВ

Покажем на примерах, как можно использовать запись вида [Н | T] вместе с рекурсией для определения некоторых полезных це¬левых утверждений для работы со списками,

Принадлежность списку. Сформулируем задачу проверки при¬надлежности данного тер-ма списку.

Граничное условие:

Терм R содержится в списке [H|T], если R=H.

Рекурсивное условие:

Терм R содержится в списке [H|T], если R содержится в списке Т.

Первый вариант записи определения на Прологе имеет вид:

содержится (R, L) :-

L=[H I T],

H=R.

содержится(Р, L) :-

L=[H|T],

содержится (R, T).

Цель L=[H I T] в теле обоих утверждений служит для того, чтобы разделить список L на голову и хвост.

Можно улучшить программу, если учесть тот факт, что Пролог сначала сопоставляет с целью голову утверждения, а затем пытается согласовать его тело. Новая процедура, которую мы назовем принад¬лежит, определяется таким образом:

принадлежит (R, [R | Т]).

принадлежит (R, [H | Т]) :- принадлежит (R, T).

На запрос

?- принадлежит(а, [а, Ь, с]).

будет получен ответ

да

на запрос

?- принадлежит(b, [a, b, с]).

- ответ

да

но на запрос

?- принадлежит(d, (a, b, c)).

Пролог дает ответ

нет

В большинстве реализации Пролога предикат принадлежит яв¬ляется встроенным.

Соединение двух списков. Задача присоединения списка Q к списку Р, в результате чего получается список R, формулируется следующим образом:

Граничное условие:

Присоединение списка Q к [] дает Q.

Рекурсивное условие:

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

Определение можно непосредственно написать на Прологе:

соединить([],0,0).

соединить(Р,Q,Р) :-

Р=[НР | ТР],

соединить(TP, Q, TR),

R=[HP | TR].

Однако, как и в предыдущем примере, воспользуемся тем, что Пролог сопоставляет с целью голову утверждения, прежде чем пы¬таться согласовать тело:

присоединить([] ,Q,Q).

присоединить(HP | TP], Q, [HP | TR]) :-

присоединить (TP, Q, TR).

На запрос

?- присоединить [а, b, с], [d, e], L).

будет получен ответ

L = [a, b, c, d].

но на запрос

?- присоединить([a, b], [c, d], [e, f]).

ответом будет

нет

Часто процедура присоединить используется для получения спи¬сков, находящихся слева и справа от данного элемента:

присоединить (L [джим, р], [джек,.билл, джим, тим, джим, боб] ) .

L = [джек, билл]

R = [тим, джим, боб]

другие решения (да/нет)? да

L=[джек, билл, джим, тим]

R=[боб]

другие решения (да/нет)? да

других решений нет

Индексирование списка. Задача получения N-ro терма в списке определяется следую-щим образом:

Граничное условие:

Первый терм в списке [Н | Т] есть Н.

Рекурсивное условие:

N-й терм в списке [Н | Т] является (N-I)-м термом в списке Т.

Данному определению соответствует программа:

/* Граничное условие:

получить ([H | Т], 1, Н). /* Рекурсивное условие:

получить([Н | Т], N, У) :-

М is N - 1,

получить (Т, М ,Y).

Построение списков из фактов. Иногда бывает полезно предста¬вить в виде списка ин-формацию, содержащуюся в известных фактах. В большинстве реализации Пролога есть необ-ходимые для этого пре¬дикаты:

bagof(X,Y,L) определяет список термов L, конкретизирующих переменную Х как ар-гумент предиката Y, которые делают истинным предикат Y

setof(X,Y,L) все сказанное о предикате bagof относится и к setof, за исключением того, что список L отсортирован и из него удалены все повторения.

Если имеются факты:

собака(рекс).

собака (голди).

собака (фидо).

собака(реке).

то на запрос

?- bagof(D, co6aкa(D), L),

будет получен ответ

L=[реке, голди, фидо, рекс]

в то время как

?-setof(D, co6aкa(D), L). дает значение

L=[фидо, голди, рекc]

Пример: сложение многочленов

Теперь мы достаточно подготовлены к тому, чтобы использовать списки для решения задач. Вопрос, которым мы займемся, - пред¬ставление и сложение многочленов.

Представление многочленов. Посмотрим, как можно предста¬вить многочлен вида

Р(х)=3+3х-4х^3+2х^9

Q(х)=4х+х^2-3х^3+7х^4+8х^5

Заметим, что каждое подвыражение (такое, как Зх ^3, Зх, 3) имеет самое большее две переменные компоненты: число, стоящее перед х, называемое коэффициентом, и число, стоящее после ^ - сте¬пень. Следовательно, подвыражение представляется термом

х(Коэффициент, Степень)

Так, 5х^2 записывается как х(5,2), х^З представляется как х(1,3), а поскольку х^0 равно 1, подвыражению 5 соответствует терм х(5,0).

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

[x(3, 0), '+', x(3, l), '-', x(4, 3), '+', x(2, 9)]

Воспользуемся тем, что многочлен

3 + 3х - 4х^3 + 2х^9

допускает замену на эквивалентный

3 + 3х + (-4)х^3 + 2х^9 Тогда он выражается списком:

[х(3, 0), '+', х(3, 1), '+', х(-4, 3), '+', х(2, 9)]

В такой записи между термами всегда стоят знаки '+'. Следователь¬но, их можно опус-тить, и многочлен принимает окончательный вид:

[х(3, 0), х(3, 1), х(-4, 3), х(2, 9)]

Подразумевается, что между всеми термами списка стоят знаки '+'. Представлением многочлена Q(x) будет

[х(4, 1), х(1, 2), х(-3, 3), х(7, 4), х(8, 5)]

Сложение многочленов. Теперь напишем целевые утверждения для сложения двух мно-гочленов. Сложение многочленов

3-2х^2+4х^3+6х^6

-1+3х^2-4х^3

в результате дает

2+х^2+6х^6

Аргументами целевого утверждения являются многочлены, пред¬ставленные в виде спи-сков. Ответ будет получен также в виде списка.

Сложение многочлена Р с многочленом Q осуществляется следу¬ющим образом:

Граничное условие:

Р, складываемый с [], дает Р.

[], складываемый с Q, дает Q.

Рекурсивное условие:

При сложении Р с Q, в результате чего получается многочлен R, возможны 4 случая:

а) степень первого терма в Р меньше, чем степень первого терма в Q. В этом случае пер-вый терм многочлена Р образует первый терм в R, а хвост R получается при прибавлении хвоста Р к Q. Например, если Р и Q имеют вид

Р(х)=3х^2+5х^3

Q(x)=4x^3+3x^4

то первый терм R(x) равен 3х^2 (первому терму в Р(х)). Хвост R(x) равен 9х^3+3х^4, т.е. результату сложения Q(x) и хвоста Р(х);

б) степень первого терма в Р больше степени первого терма в Q. В данном случае пер-вый терм в Q образует первый терм в R, а хвост R получается при прибавлении Р к хвосту Q. Например, если

Р(х)=2х^3+5х^'4

Q(x)=3x^3-x^4

то первый терм R(x) равен 3х^2 (первому терму в Q(x)), а хвост R(x) равен 2х^3+4х^4 (результату сложения Р(х) и хвоста Q(x));

в) степени первых термов в Р и Q равны, а сумма их коэффици¬ентов отлична от нуля. В таком случае первый терм в R имеет коэф¬фициент, равный сумме коэффициентов первых тер-мов в Р и Q. Сте¬пень первого терма в R равна степени первого терма в Р (или Q). Хвост R полу-чается при сложении хвоста Р и хвоста Q. Например, если Р и Q имеют вид

Р(х)=2х+3х^3

Q(x)=3x+4x^4

то первый терм многочлена R (х) равен 5х (результату сложения пер¬вого терма в Р(х) с первым термом в Q(x)). Хвост R(x) равен 3х^3+4х^4 (результату сложения хвоста Р(х) и хвоста Q(x));

г) степени первых термов в Р и Q одинаковы, но сумма коэффи¬циентов равна нулю. В данном случае многочлен R равен результату сложения хвоста Р с хвостом Q. Например, если

р(х)=2+2х

Q(x)=2-3x^2

то

R(x)=2x-3x^2

(это результат сложения хвостов многочленов Р (х) и Q (х)).

Рассмотренный процесс сложения многочленов можно непосред¬ственно записать на языке Пролог:

/* Граничные условия

слож_мн([], Q Q).

слож_мн(P, [], P).

/* Рекурсивное условие

/* (a)

слож_мн([x(Pc, Pp)|Pt], [x(Qc, Qp)|Qt],

[x(Pc,Pp)IRt]) :-

PpQp,

слож_мн(Рt, [х(Qс,Qр) | Qt], Rt).

/*(б)

слож_мн([x(Pc, Pp) | Pt], [x(Qc, Qp) | Qt],

[x(Qc, Qp) | Rt]) :-

PpQp,

слож_мн([x(Pc, Pp) | Pt], Qt, Rt).

/*(в)

слож_мн([x(Pc, Pp) | Pt], [х(Qc,Pp) | Qt],

[x(Rc, Pp) | Rt]) :-

Rc is Pc+Qc,

Rc =\= 0,

слож_мн(Pt, Qt,Rt).

/*(r)

слож_мн([х(Рс, Рр) | Pt],

[x(Qc.Pp) | Qt], Rt) :-

Re is Pc+Qc,

Rc =:= 0,

слож_мн(Pt, Qt, Rt).

Заметим, что в двух последних утверждениях проверка на равен¬ство осуществляется следующим образом: степени первых термов складываемых утверждений обозначает одна и та же переменная Pp.

Списки как термы. В начале главы мы упомянули о том, что спи¬сок представляется с помощью терма. Такой терм имеет функтор '.', Два аргумента и определяется рекурсивно. Пер-вый аргумент являет¬ся головой списка, а второй - термом, обозначающим хвост списка. Пустой список обозначается []. Тогда список [а, b] эквивалентен терму.(а,.(b, [])).

Таким образом, из списков, как и из термов, можно создавать вложенные структуры. Поэтому выражение

[[a, b], [c, d], [a], a]

есть правильно записанный список, и на запрос

?- [Н | Т]=[[а, b], с].

Пролог дает ответ

Н=[а, b]

Т=[с]