Данную лекцию нужно рассматривать не как учебник по языку Пролог, а только как краткий "ликбез", который служит для иллюстрации принципов продукционного программирования, описанных выше.
0, -l, 123.4, 0.23E-5,
(некоторые реализации Пролога не поддерживают действительные числа).
К константам относятся также атомы, такие, как:
голди, а, атом, +, :, 'Фред Блогс', [].
abcd, фред, ':', Джо.
Полный синтаксис атомов описан ниже.
Как и в других языках программирования, константы обозначают конкретные элементарные объекты, а все другие типы данных в Прологе составлены из сочетаний констант и переменных.
Имена переменных начинаются с заглавных букв или с символа подчеркивания "_". Примеры переменных:
X, Переменная, _3, _переменная.
Если переменная используется только один раз, необязательно называть ее. Она может быть записана как анонимная переменная, состоящая из одного символа подчеркивания "_". Переменные, подобно атомам, являются элементарными объектами языка Пролог.
Завершает список синтаксических единиц сложный терм, или структура. Все, что не может быть отнесено к переменной или константе, называется сложным термом. Следовательно, сложный терм состоит из констант и переменных.
Теперь перейдем к более детальному описанию термов.
Константы известны всем программистам. В Прологе константа может быть атомом или числом.
Атом представляет собой произвольную последовательность символов, заключенную в одинарные кавычки. Одинарный символ кавычки, встречающийся внутри атома, записывается дважды. Когда атом выводится на печать, внешние символы кавычек обычно не печатаются. Существует несколько исключений, когда атомы необязательно записывать в кавычках. Вот эти исключения:
+ - * / ^ = : ; ? @ $ Заметим, что атом, начинающийся с /*, будет воспринят как начало комментария, если он не заключен в одинарные кавычки.
Как правило, в программах на Прологе используются атомы без кавычек.
Атом, который необязательно заключать в кавычки, может быть записан и в кавычках. Запись с внешними кавычками и без них определяет один и тот же атом.
Внимание: допустимы случаи, когда атом не содержит ни одного символа (так называемый 'нулевой атом') или содержит непечатаемые символы. (В Прологе имеются предикаты для построения атомов, содержащих непечатаемые или управляющие символы.) При выводе таких атомов на печать могут возникнуть ошибки.
Большинство реализации Пролога поддерживают целые и действительные числа. Чтобы выяснить, каковы диапазоны и точность чисел, следует обратиться к руководству по конкретной реализации.
Понятие переменной в Прологе отличается от принятого во многих языках программирования. Переменная не рассматривается как выделенный участок памяти. Она служит для обозначения объекта, на который нельзя сослаться по имени. Переменную можно считать локальным именем для некоторого объекта.
Синтаксис переменной довольно прост. Она должна начинаться с прописной буквы или символа подчеркивания и содержать только символы букв, цифр и подчеркивания.
Переменная, состоящая только из символа подчеркивания, называется анонимной и используется в том случае, если имя переменной несущественно.
Областью действия переменной является утверждение. В пределах утверждения одно и то же имя принадлежит одной и той же переменной. Два утверждения могут использовать одно имя переменной совершенно различным образом. Правило определения области действия переменной справедливо также в случае рекурсии и в том случае, когда несколько утверждений имеют одну и ту же головную цель. Этот вопрос будет рассмотрен далее.
Единственным исключением из правила определения области действия переменных является анонимная переменная, например, "_" в цели любит (Х,_). Каждая анонимная переменная есть отдельная сущность. Она применяется тогда, когда конкретное значение переменной несущественно для данного утверждения. Таким образом, каждая анонимная переменная четко отличается от всех других анонимных переменных в утверждении.
Структура состоит из атома, называемого главным
Приведем примеры структурированных термов:
собака(рекс), родитель(Х,У).
Число компонент в структуре называется арностью структуры. Так, в данном примере структура собака имеет собака/1 ), а структура родитель — родитель/2 ). Заметим, что атом можно рассматривать как структуру арности 0.
Для некоторых типов структур допустимо использование альтернативных форм синтаксиса. Это синтаксис операторов для структур арности 1 и 2, синтаксис списков для структур в форме списков и синтаксис строк для структур, являющихся списками кодов символов.
Структуры арности 1 и 2 могут быть записаны в операторной форме, если атом, используемый как главный
В сущности, список есть не что иное, как некоторая структура арности 2. Данная структура становится интересной и чрезвычайно полезной в случае, когда вторая компонента тоже является списком. Вследствие важности таких структур в Прологе имеются специальные средства для записи списков.
Строка определяется как список кодов символов. Коды символов имеют особое значение в языках программирования. Они выступают как средство связи компьютера с внешним миром. В большинстве реализации Пролога существует специальный синтаксис для записи строк. Он подобен синтаксису атомов. Строкой является любая последовательность символов, которые могут быть напечатаны (кроме двойных кавычек), заключенная в двойные кавычки. Двойные кавычки в пределах строки записываются дважды "".
В некоторых реализациях Пролога строки рассматриваются как определенный тип объектов подобно атомам или спискам. Для их обработки вводятся специальные встроенные предикаты. В других реализациях строки обрабатываются в точности так же, как списки, при этом используются встроенные предикаты для обработки списков. Поскольку все строки могут быть определены как атомы или как списки целых чисел, и понятие строки является чисто синтаксическим, мы не будем более к нему возвращаться.
Программа на Прологе есть совокупность утверждений. Утверждения состоят из целей и хранятся в базе данных Пролога. Таким образом, база данных Пролога может рассматриваться как программа на Прологе. В конце утверждения ставится точка ".". Иногда утверждение называется предложением.
Основная операция Пролога — доказательство целей, входящих в утверждение.
Существуют два типа утверждений:
Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.
Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.
Примеры фактов:
собака(рекс). родитель(голди.рекс).
Примеры правил:
собака (X) :- родитель (X.Y),собака (Y). человек(Х) :-мужчина(Х).
Разница между правилами и фактами чисто семантическая. Хотя для правил мы используем синтаксис операторов (более подробное рассмотрение операторного и процедурного синтаксисов выходит за рамки нашего курса), нет никакого синтаксического различия между правилом и фактом.
Так, правило
собака (X) :- родитель(Х,У),собака(У). может быть задано как
:-собака (X) ',' родитель(Х.У) .собака (Y).
Запись верна, поскольку :- является оператором "при условии, что", а ',' — это оператор конъюнкции. Однако удобнее записывать это как
собака ( X ) :-родитель ( X.Y ),собака ( Y ).
и читать следующим образом: " Х — собака при условии, что родителем Х является Y и Y — собака".
Структуру иногда изображают в виде дерева, число ветвей КОТОРОГО равно арности структуры.
После записи утверждений в базу данных вычисления могут быть инициированы вводом запроса.
Запрос выглядит так же, как и целевое утверждение, образуется и обрабатывается по тем же правилам, но он не входит в базу данных (программу). В Прологе вычислительная часть программы и данные имеют одинаковый синтаксис. Программа обладает как декларативной, так и ?-, имеющим ?- следует ряд хвостовых целевых утверждений (чаще всего в виде конъюнкции).
Приведем примеры запросов:
?-собака(X). ?- родитель(Х.У),собака (Y).
или, иначе,
'?-'(собака(Х)) С?-') ','(родитель(Х„У",собака (Y)).
Последняя запись неудобна тем, что разделитель аргументов в структуре совпадает с символом конъюнкции. Программисту нужно помнить о различных значениях символа ','.
Запрос иногда называют управляющей командой (директивой), так как он требует от Пролог-системы выполнения некоторых действий. Во многих реализациях Пролога для управляющей команды используется альтернативный символ, а символ ?- обозначает приглашение верхнего уровня интерпретатора Пролога. Альтернативным символом является :-. Таким образом,
:-write(co6aкa).
- это управляющая команда, в результате выполнения которой печатается атом собака. Управляющие команды будут рассмотрены ниже при описании ввода программ.
Введение списка утверждений в Пролог-систему осуществляется с помощью встроенного предиката
Помимо предиката reconsult. Он работает аналогичным образом. Но перед добавлением утверждений к базе данных из нее автоматически удаляются те утверждения, головные цели которых сопоставимы с целями, содержащимися в файле перезагрузки. Такой механизм позволяет вводить изменения в базу данных. В Прологе имеются и другие методы добавления и удаления утверждений из базы данных. Некоторые реализации языка поддерживают модульную структуру, позволяющую разрабатывать модульные программы.
В заключение раздела дадим формальное определение синтаксиса Пролога, используя форму записи Бэкуса-Наура, иногда называемую бэкусовской нормальной формой (
запрос ::- голова утверждения правило ::– голова утверждения :- хвост утверждения факт ::- голова утверждения голова утверждения ::-атом | структура хвост утверждения ::- атом структура, термы ::-терм [,термы] терм ::- число | переменная | атом | структура структура ::-атом (термы)
Данное определение синтаксиса не включает операторную, списковую и строковую формы записи. Полное определение дано в приложении А. Однако, любая программа на Прологе может быть написана с использованием вышеприведенного синтаксиса. Специальные формы только упрощают понимание программы. Как мы видим, синтаксис Пролога не требует пространного объяснения. Но для написания хороших программ необходимо глубокое понимание языка.
Одним из наиболее важных аспектов программирования на Прологе являются понятия унификации (
Пролог пытается отождествить термы при доказательстве, или согласовании, целевого утверждения. Например, в программе из лек. 1 для согласования запроса ?- собака(Х) целевое утверждение собака (X) было отождествлено с фактом собака (Рекс), в результате чего переменная Х стала конкретизированной: Х= рекc.
Переменные, входящие в утверждения, отождествляются особым образом — сопоставляются. Факт доказывается для всех значений переменной (переменных). Правило доказывается для всех значений переменных в головном целевом утверждении при условии, что хвостовые целевые утверждения доказаны. Предполагается, что переменные в фактах и головных целевых утверждениях связаны
В том случае, когда переменные содержатся только в хвостовых целевых утверждениях, правило считается доказанным, если хвостовое целевое утверждение истинно для одного или более значений переменных. Переменные, содержащиеся только в хвостовых целевых утверждениях, связаны
Терм Х сопоставляется с термом Y по следующим правилам. Если Х и Y — константы, то они сопоставимы, только если они одинаковы. Если Х является константой или структурой, а Y — неконкретизированной переменной, то Х и Y сопоставимы и Y принимает значение Х (и наоборот). Если Х и Y — структуры, то они сопоставимы тогда и только тогда, когда у них одни и те же главный Х и Y — неконкретизированные (
| Терм1 | Терм2 | Отождествимы ? |
|---|---|---|
| джек(Х) | джек (человек) | да: Х=человек |
| джек (личность) | джек (человек) | нет |
| джек(Х,Х) | джек(23,23) | да: Х=23 |
| джек(Х.Х) | джек (12,23) | нет |
| джек( . ) | джек(12,23) | да |
| f(Y,Z) | Х | да: X=f(Y,Z) |
| Х | Z | да: X=Z |
Заметим, что Пролог находит наиболее общий унификатор термов. В последнем примере (табл.7.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 — обычные атомы Пролога и могут использоваться почти в любом контексте. Указанные атомы — не встроенные предикаты, а
Арифметический оператор выполняется следующим образом. Во-первых, вычисляются арифметические выражения по обе стороны оператора. Во-вторых, над результатом вычислений выполняется нужная операция.
среднее (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] определяет список, полученный добавлением Н в начало списка Т. Говорят, что Н — голова, а Т — [. На вопрос
?-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,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х^3 (первому терму в 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]
Т=[с]
Данную лекцию нужно рассматривать не как учебник по языку Пролог, а только как краткий "ликбез", который служит для иллюстрации принципов продукционного программирования, описанных выше.
0, -l, 123.4, 0.23E-5,
(некоторые реализации Пролога не поддерживают действительные числа).
К константам относятся также атомы, такие, как:
голди, а, атом, +, :, 'Фред Блогс', [].
abcd, фред, ':', Джо.
Полный синтаксис атомов описан ниже.
Как и в других языках программирования, константы обозначают конкретные элементарные объекты, а все другие типы данных в Прологе составлены из сочетаний констант и переменных.
Имена переменных начинаются с заглавных букв или с символа подчеркивания "_". Примеры переменных:
X, Переменная, _3, _переменная.
Если переменная используется только один раз, необязательно называть ее. Она может быть записана как анонимная переменная, состоящая из одного символа подчеркивания "_". Переменные, подобно атомам, являются элементарными объектами языка Пролог.
Завершает список синтаксических единиц сложный терм, или структура. Все, что не может быть отнесено к переменной или константе, называется сложным термом. Следовательно, сложный терм состоит из констант и переменных.
Теперь перейдем к более детальному описанию термов.
Константы известны всем программистам. В Прологе константа может быть атомом или числом.
Атом представляет собой произвольную последовательность символов, заключенную в одинарные кавычки. Одинарный символ кавычки, встречающийся внутри атома, записывается дважды. Когда атом выводится на печать, внешние символы кавычек обычно не печатаются. Существует несколько исключений, когда атомы необязательно записывать в кавычках. Вот эти исключения:
+ - * / ^ = : ; ? @ $ Заметим, что атом, начинающийся с /*, будет воспринят как начало комментария, если он не заключен в одинарные кавычки.
Как правило, в программах на Прологе используются атомы без кавычек.
Атом, который необязательно заключать в кавычки, может быть записан и в кавычках. Запись с внешними кавычками и без них определяет один и тот же атом.
Внимание: допустимы случаи, когда атом не содержит ни одного символа (так называемый 'нулевой атом') или содержит непечатаемые символы. (В Прологе имеются предикаты для построения атомов, содержащих непечатаемые или управляющие символы.) При выводе таких атомов на печать могут возникнуть ошибки.
Большинство реализации Пролога поддерживают целые и действительные числа. Чтобы выяснить, каковы диапазоны и точность чисел, следует обратиться к руководству по конкретной реализации.
Понятие переменной в Прологе отличается от принятого во многих языках программирования. Переменная не рассматривается как выделенный участок памяти. Она служит для обозначения объекта, на который нельзя сослаться по имени. Переменную можно считать локальным именем для некоторого объекта.
Синтаксис переменной довольно прост. Она должна начинаться с прописной буквы или символа подчеркивания и содержать только символы букв, цифр и подчеркивания.
Переменная, состоящая только из символа подчеркивания, называется анонимной и используется в том случае, если имя переменной несущественно.
Областью действия переменной является утверждение. В пределах утверждения одно и то же имя принадлежит одной и той же переменной. Два утверждения могут использовать одно имя переменной совершенно различным образом. Правило определения области действия переменной справедливо также в случае рекурсии и в том случае, когда несколько утверждений имеют одну и ту же головную цель. Этот вопрос будет рассмотрен далее.
Единственным исключением из правила определения области действия переменных является анонимная переменная, например, "_" в цели любит (Х,_). Каждая анонимная переменная есть отдельная сущность. Она применяется тогда, когда конкретное значение переменной несущественно для данного утверждения. Таким образом, каждая анонимная переменная четко отличается от всех других анонимных переменных в утверждении.
Структура состоит из атома, называемого главным
Приведем примеры структурированных термов:
собака(рекс), родитель(Х,У).
Число компонент в структуре называется арностью структуры. Так, в данном примере структура собака имеет собака/1 ), а структура родитель — родитель/2 ). Заметим, что атом можно рассматривать как структуру арности 0.
Для некоторых типов структур допустимо использование альтернативных форм синтаксиса. Это синтаксис операторов для структур арности 1 и 2, синтаксис списков для структур в форме списков и синтаксис строк для структур, являющихся списками кодов символов.
Структуры арности 1 и 2 могут быть записаны в операторной форме, если атом, используемый как главный
В сущности, список есть не что иное, как некоторая структура арности 2. Данная структура становится интересной и чрезвычайно полезной в случае, когда вторая компонента тоже является списком. Вследствие важности таких структур в Прологе имеются специальные средства для записи списков.
Строка определяется как список кодов символов. Коды символов имеют особое значение в языках программирования. Они выступают как средство связи компьютера с внешним миром. В большинстве реализации Пролога существует специальный синтаксис для записи строк. Он подобен синтаксису атомов. Строкой является любая последовательность символов, которые могут быть напечатаны (кроме двойных кавычек), заключенная в двойные кавычки. Двойные кавычки в пределах строки записываются дважды "".
В некоторых реализациях Пролога строки рассматриваются как определенный тип объектов подобно атомам или спискам. Для их обработки вводятся специальные встроенные предикаты. В других реализациях строки обрабатываются в точности так же, как списки, при этом используются встроенные предикаты для обработки списков. Поскольку все строки могут быть определены как атомы или как списки целых чисел, и понятие строки является чисто синтаксическим, мы не будем более к нему возвращаться.
Программа на Прологе есть совокупность утверждений. Утверждения состоят из целей и хранятся в базе данных Пролога. Таким образом, база данных Пролога может рассматриваться как программа на Прологе. В конце утверждения ставится точка ".". Иногда утверждение называется предложением.
Основная операция Пролога — доказательство целей, входящих в утверждение.
Существуют два типа утверждений:
Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.
Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.
Примеры фактов:
собака(рекс). родитель(голди.рекс).
Примеры правил:
собака (X) :- родитель (X.Y),собака (Y). человек(Х) :-мужчина(Х).
Разница между правилами и фактами чисто семантическая. Хотя для правил мы используем синтаксис операторов (более подробное рассмотрение операторного и процедурного синтаксисов выходит за рамки нашего курса), нет никакого синтаксического различия между правилом и фактом.
Так, правило
собака (X) :- родитель(Х,У),собака(У). может быть задано как
:-собака (X) ',' родитель(Х.У) .собака (Y).
Запись верна, поскольку :- является оператором "при условии, что", а ',' — это оператор конъюнкции. Однако удобнее записывать это как
собака ( X ) :-родитель ( X.Y ),собака ( Y ).
и читать следующим образом: " Х — собака при условии, что родителем Х является Y и Y — собака".
Структуру иногда изображают в виде дерева, число ветвей КОТОРОГО равно арности структуры.
После записи утверждений в базу данных вычисления могут быть инициированы вводом запроса.
Запрос выглядит так же, как и целевое утверждение, образуется и обрабатывается по тем же правилам, но он не входит в базу данных (программу). В Прологе вычислительная часть программы и данные имеют одинаковый синтаксис. Программа обладает как декларативной, так и ?-, имеющим ?- следует ряд хвостовых целевых утверждений (чаще всего в виде конъюнкции).
Приведем примеры запросов:
?-собака(X). ?- родитель(Х.У),собака (Y).
или, иначе,
'?-'(собака(Х)) С?-') ','(родитель(Х„У",собака (Y)).
Последняя запись неудобна тем, что разделитель аргументов в структуре совпадает с символом конъюнкции. Программисту нужно помнить о различных значениях символа ','.
Запрос иногда называют управляющей командой (директивой), так как он требует от Пролог-системы выполнения некоторых действий. Во многих реализациях Пролога для управляющей команды используется альтернативный символ, а символ ?- обозначает приглашение верхнего уровня интерпретатора Пролога. Альтернативным символом является :-. Таким образом,
:-write(co6aкa).
- это управляющая команда, в результате выполнения которой печатается атом собака. Управляющие команды будут рассмотрены ниже при описании ввода программ.
Введение списка утверждений в Пролог-систему осуществляется с помощью встроенного предиката
Помимо предиката reconsult. Он работает аналогичным образом. Но перед добавлением утверждений к базе данных из нее автоматически удаляются те утверждения, головные цели которых сопоставимы с целями, содержащимися в файле перезагрузки. Такой механизм позволяет вводить изменения в базу данных. В Прологе имеются и другие методы добавления и удаления утверждений из базы данных. Некоторые реализации языка поддерживают модульную структуру, позволяющую разрабатывать модульные программы.
В заключение раздела дадим формальное определение синтаксиса Пролога, используя форму записи Бэкуса-Наура, иногда называемую бэкусовской нормальной формой (
запрос ::- голова утверждения правило ::– голова утверждения :- хвост утверждения факт ::- голова утверждения голова утверждения ::-атом | структура хвост утверждения ::- атом структура, термы ::-терм [,термы] терм ::- число | переменная | атом | структура структура ::-атом (термы)
Данное определение синтаксиса не включает операторную, списковую и строковую формы записи. Полное определение дано в приложении А. Однако, любая программа на Прологе может быть написана с использованием вышеприведенного синтаксиса. Специальные формы только упрощают понимание программы. Как мы видим, синтаксис Пролога не требует пространного объяснения. Но для написания хороших программ необходимо глубокое понимание языка.
Одним из наиболее важных аспектов программирования на Прологе являются понятия унификации (
Пролог пытается отождествить термы при доказательстве, или согласовании, целевого утверждения. Например, в программе из лек. 1 для согласования запроса ?- собака(Х) целевое утверждение собака (X) было отождествлено с фактом собака (Рекс), в результате чего переменная Х стала конкретизированной: Х= рекc.
Переменные, входящие в утверждения, отождествляются особым образом — сопоставляются. Факт доказывается для всех значений переменной (переменных). Правило доказывается для всех значений переменных в головном целевом утверждении при условии, что хвостовые целевые утверждения доказаны. Предполагается, что переменные в фактах и головных целевых утверждениях связаны
В том случае, когда переменные содержатся только в хвостовых целевых утверждениях, правило считается доказанным, если хвостовое целевое утверждение истинно для одного или более значений переменных. Переменные, содержащиеся только в хвостовых целевых утверждениях, связаны
Терм Х сопоставляется с термом Y по следующим правилам. Если Х и Y — константы, то они сопоставимы, только если они одинаковы. Если Х является константой или структурой, а Y — неконкретизированной переменной, то Х и Y сопоставимы и Y принимает значение Х (и наоборот). Если Х и Y — структуры, то они сопоставимы тогда и только тогда, когда у них одни и те же главный Х и Y — неконкретизированные (
| Терм1 | Терм2 | Отождествимы ? |
|---|---|---|
| джек(Х) | джек (человек) | да: Х=человек |
| джек (личность) | джек (человек) | нет |
| джек(Х,Х) | джек(23,23) | да: Х=23 |
| джек(Х.Х) | джек (12,23) | нет |
| джек( . ) | джек(12,23) | да |
| f(Y,Z) | Х | да: X=f(Y,Z) |
| Х | Z | да: X=Z |
Заметим, что Пролог находит наиболее общий унификатор термов. В последнем примере (табл.7.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 — обычные атомы Пролога и могут использоваться почти в любом контексте. Указанные атомы — не встроенные предикаты, а
Арифметический оператор выполняется следующим образом. Во-первых, вычисляются арифметические выражения по обе стороны оператора. Во-вторых, над результатом вычислений выполняется нужная операция.
среднее (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] определяет список, полученный добавлением Н в начало списка Т. Говорят, что Н — голова, а Т — [. На вопрос
?-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,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х^3 (первому терму в 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]
Т=[с]
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.