Delphi World - ИИ - Урок 6 - Пролог
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
ИИ - Урок 6 - Пролог

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

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

Синтаксис

ТЕРМЫ

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

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]

Т=[с]

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования