1_Начало работы со средой SWI-Prolog_Теория. Лабораторная работа 1 Основы логического программирования. Начало работы со средой swiprolog
 Скачать 149.82 Kb.
|
|
Лабораторная работа № 1 Основы логического программирования. Начало работы со средой SWI-Prolog. Цель работы: рассмотреть основные конструкции рекурсивно-логического программирования: термы и утверждения, унификацию термов, механизмы управления выполнением программы (прямая трассировка, прямой перебор с возвратом) на Прологе и изучить приемы работы с интерпретатором SWI Prolog. Задачи: знакомство с элементами интерфейса интерпретатора SWI Prolog: окно запросов; встроенный редактор текстов. создание программ в среде SWI Prolog; приобретение практических навыков составления, отладки и выполнения простейшей программы на Прологе в системе SWI Prolog. Теоретическая часть. Языки логического программирования – основные понятия. В настоящее время в теории и практике программирования сложилось два основных стиля разработки программ: процедурный и декларативный. Процедурный (или алгоритмический) стиль наиболее распространён и поддерживается большей частью существующих языков программирования (ЯП), таких, например, как Паскаль, С++, Java и др. При этом подходе программа - это процедура, алгоритм, т.е. детально расписанная программистом последовательность шагов исполнителя, направленная на решение поставленной задачи в заданной системе обозначений используемого языка. В отличие от этого, языки логического программирования (ЯЛП) к которым относится, например, PROLOG, основаны на системе обозначений и понятий, принятых в математической логике и, соответственно, поддерживают, так называемый, декларативный (описательный) стиль программирования. Это означает, что вместо записи алгоритма решения задачи, как того требует процедурный стиль, предполагают формальное описание условия исходной задачи и формальное же описание ожидаемого решения, в виде некоторой системы логических утверждений (предикатов) как относительно исходных, так и относительно результирующих объектов рассматриваемой предметной области. Цепочка же необходимых преобразований входных данных в конкретные значения выходных объектов (т.е., собственно говоря, алгоритм извлечения решения) строится, как логический вывод, реализуемый интерпретатором (обрабатывающим модулем) рассматриваемого языка. Базовыми элементами языков логического программирования являются термы – ими выражаются объекты данных и упомянутые выше предикаты – они выражают существенные (с точки зрения условия решаемой задачи) свойства объектов и отношения между объектами. Как было сказано выше, термами выражаются объекты данных. Терм может быть простым или составным. Простыми термами являются константы и переменные. Классификация объектов данных приведена на рис. 1. [Братко стр. 48]:  Рис. 1.1. Классификация объектов данных Пролога. К константам относятся следующие типы данных: атомы, числа, строки. Атом – это строка символов, которая начинается со строчной буквы и обозначает некоторый неделимый абстрактный объект. Он может содержать буквы, цифры или специальные символы типа дефис, знак доллара и т.п. Если строка атома начинается с прописной буквы или содержит специальные символы, то она заключается в одинарные кавычки. Если внутри одинарных кавычек используется апостроф, его следует записывать как два апострофа. Примеры атомов: prolog, 'prolog', 'Prolog', '123', 'Paris', 'Mary''s' Здесь prolog и 'prolog' – это один и тот же атом, но prolog и 'Prolog'– разные. Числа понимаются в традиционном смысле. Они могут быть целыми и вещественными. Их диапазон определяются в конкретной реализации Пролога. Целыми являются любые положительные и отрицательные целые числа, ASCII -коды символов также являются целыми. Вещественные числа позволяют Прологу выполнять арифметику на дробных числах. Они могут быть представлены в форме с фиксированной точкой и с плавающей точкой, например, 135.712 и 0.135712E+3, соответственно. Числа с плавающей точкой имеют следующий вид: за необязательным знаком следует, по крайней мере, одна цифра за которой следует десятичная точка. За десятичной точкой следует, по крайней мере, одна цифра, вслед за которой следует необязательная экспонента. Экспонента это символ Е (или е) за которым следует необязательный знак, вслед за которым следует число в диапазоне от -308 до 308. Примеры чисел с плавающей точкой: 0.5, 55.3, –83.0Е21, 2134.2, 122.345е25 Строки представляют собой символьные константы, которые используются для эффективного манипулирования текстовой информацией. В SWI-Prolog они записываются в виде последовательностей ASCII-символов, заключенных в кавычки (" "). Например: "Студент изучает язык Пролог". Пустая строка записывается в виде "". Переменная. Понятие переменной в Прологе отличается от принятого во многих языках программирования. Переменная не рассматривается как выделенный участок памяти. Она служит для обозначения объекта, на который нельзя сослаться по имени. Переменную можно считать локальным именем для некоторого объекта. Имя переменной в Прологе может состоять из букв латинского алфавита, цифр, знаков подчеркивания и должно начинаться с прописной буквы или знака подчеркивания. Переменная, состоящая только из символа подчеркивания ( _ ), называется анонимной и используется в том случае, если имя переменной несущественно. Примеры переменных: X, Y, X5, Sum, _. Последняя из переменных – анонимная переменная, т.е. безымянная. Составные термы, или структуры. Составной терм (структура) состоит из атома, называемого главным функтором, и последовательности термов, называемых компонентами (или аргументами) структуры. Компоненты разделяются запятыми и заключаются в круглые скобки. Число компонент в структуре называется арностью структуры. Примеры структур: book(Author,Title,Year). Списки являются специфическим типом структур данных, используемых в Прологе. Список – это последовательность элементов (возможно, пустая!), расположенных в определенном порядке. Элементами списка могут быть атомы, целые числа или другие списки. Удобным способом записи списка является т.н. списковая нотация. В списковой нотации весь набор элементов списка помещается в квадратные скобки, а каждый элемент списка отделяется от соседнего элемента запятой. Пустым называется список, который не содержит никаких элементов. Примеры списков в списковой нотации: [a, b, c, d, e], [собака, кошка], [[4,5,3], [4,4,5], [2], [ ], 2]. [ ] – пустой список Учитывая важность списковой структуры данных тема представления и обработки списковых структур данных будет рассмотрено в отдельной лабораторной. Основными утверждениями Пролога являются факт и правило. Факт – это простейший вид утверждения. Он констатирует, что между объектами выполнено некоторое отношение и это отношение считается, безусловно, истиной. В математической логике отношения называются предикатами. Предикат состоит либо только из имени, либо из имени и следующей за ним последовательности аргументов, заключенной в скобки. Аргументом или параметром предиката может быть константа, переменная или составной объект. Число аргументов предиката называется его арностью или местностью. Факты могут описывать свойства объектов или отношения между объектами. Например, утверждение "Барсик – это кошка" выступает как свойства и на Прологе запишется в виде: кошка(барсик), утверждение "Иванов изучает язык Пролог" рассматривается как предикат отношение и на Прологе можно записать в виде: изучает(иванов, пролог). Имя предиката должно состоять из последовательности латинских букв, цифр, знаков подчеркивания и начинаться с буквы или знака подчеркивания. Соответственно, приведенные выше примеры фактов можно записать, например, так: cat(barsik). learn(ivanov, prolog). Некоторые предикаты уже известны системе, они называются стандартными или встроенными. Правило – это конструкция вида «A: – B, C, D.» , где A, B, C, D - предикаты. A называется заголовком или целью, B, C, D - телом или подцелями. Цель правила – всегда единственна, число подцелей -произвольно. Интерпретация правила выглядит следующим образом: A истинно, если одновременно истинны B, C и D. Пример. Известно, что дедушка человека – это папа его мамы или папа его папы. Определим соответствующее правило задающий отношение дедушка: X является дедушкой Y, если существует такой Z, что X является папой Z, а Z – мамой или папой Y. Данное суждение можно записать в виде следующих правил: дедушка(X, Y):- папа(X, Z), мама(Z, Y). дедушка(X, Y):- папа(X, Z), папа(Z, Y). Символ ":–" – это связка между головой правила и его телом, может читаться как "если" и трактоваться как аналог условного оператора из традиционных языков программирования. Символ "запятая" означает коньюнкцию подцелей (логическая операция “И”). В данном примере, для определения правила "дедушка" мы ввели переменные X, Y и Z. Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная. Каждая анонимная переменная – это отдельный объект. Совокупность всех утверждений программы обычно называется базой данных Пролога. Унификация – операция сопоставления термов. Понятия сопоставления – это один из наиболее важных аспектов логического программирования. Механизм доказательства целей в пролог – программе строится на основе сопоставлении термов и их унификации. Сопоставление – это процесс, на вход которого подаются два терма, а он проверяет, соответствуют ли эти термы друг другу. Переменные, входящие в утверждения, сопоставляется особым образом. Факт доказывается для всех значений переменной или переменных. Правило доказывается для всех значений переменных в головном целевом утверждении при условии, что хвостовые целевые утверждения доказаны. При этом предполагается, что переменные в фактах и головных целевых утверждениях связаны квантором всеобщности. Переменные принимают конкретные значения на время доказательства целевого утверждения. В том случае, когда переменные содержатся только в хвостовых целевых утверждениях, правило считается доказанным, если хвостовое целевое утверждение истинно для одного или более значений переменных. Переменные, содержащиеся только в хвостовых целевых утверждениях, связаны квантором существования. Они принимают конкретные значения на то время, когда целевое утверждение, в котором переменные были согласованы, остается доказанным. Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной. Если переменная была конкретизирована каким-то значением, и ей сопоставлена некоторый объект, то эта переменная уже не может быть изменена. Переменная, которая еще не получила значения называется свободной переменной. Она не равняется ни нулю, ни пробелу. У нее нет никакого значения. Такие переменные еще называют неконкретизированными. Терм S сопоставляется с термом T по следующим правилам. Если S и Т константы, то S и Т сопоставимы, только, в том случае если они являются одним и тем же объектом, т.е. одинаковы. Если S переменная, а Т – произвольный объект, то они всегда сопоставимы и S приписывается значение T. Наоборот, если Т – переменная, а S – произвольный объект, то T приписывается значение S. В этом случае говорят, что T конкретизируется значением S. если S и T – неконкретизированные (свободные) переменные, то они сопоставимы. Если S и Т – структуры, то они сопоставимы, если S и Т имеют одинаковый главный функтор и арность, и все их соответствующие компоненты сопоставимы. Результирующая конкретизация определяется сопоставлением компонент. Возможность сопоставления двух термов в пролог – программе проверяется с помощью специального оператора равно =, а отрицание сопоставления – \=. В таблице 1 приведены примеры сопоставимых и не сопоставимых термов. Таблица 1. Примеры унификации термов.
Управление выполнением программы на Прологе Механизм прямой трассировки. При согласовании целевого утверждения в Прологе используется специальный метод, называемый механизмом возврата. При попытке согласования целевого утверждения Пролог выбирает первое из тех утверждений, голова которых сопоставима с целевым утверждением. Если удается согласовать тело утверждения, то целевое утверждение согласовано. Если нет, то Пролог переходит к следующему утверждению, голова которого сопоставима с целевым утверждением, и так далее до тех пор, пока целевое утверждение не будет согласовано или не будет доказано, что оно не согласуется с базой данных. Рассмотрим простую задачу. Из игроков в настольный теннис надо выбрать школьников одного возраста. Программа может выглядеть как на рисунке 1.2.  Рис. 1.2. Проограмма playing_tennisюpl Для того чтобы решить задачу и проследить механизм прямого полного перебора, зададим внешнию цель: ?- игрок(X,9). Система начинает прямой перебор фактов, начиная с первого из имеющихся в базе знаний, и сопоставляет попарно объекты целевого утверждения и факта последовательно слева направо. Эту работу выполняют так называемые внутренние подпрограммы унификации, осуществляющие означивание переменных. Объект 'Петя' сопоставляется с переменной X , а объект '9' – с '9'. Говорят, что объекты сопоставляются удачно, если они удовлетворяют одному из следующих правил: 1. Объекты сопоставимы, если они равны (у нас это “9” и “9”). 2. Объект сопоставим со свободной переменной. Свободная переменная приобретает значение этого объекта. В нашем примере переменная X принимает значение 'Петя'. 3. Объект сопоставим с занятой переменной, если значение занятой переменной совпадает со значением объекта. 4. Две свободные переменные всегда сопоставимы. Как только одна из сопоставимых переменных получит значение, другая тоже получит это значение. X=Y, X = 2. Если все объекты сопоставлены удачно, то выполнение предиката целевого утверждения заканчивается успешно. В нашем примере сопоставление объектов целевого утверждения и первого факта произойдет успешно и система Пролог выдаст первое решение: X = 'Петя' На этом поиск решений не заканчивается. Чтобы продолжить поиск введем символ точка с запятой ";". После чего все переменные целевого утверждения освобождаются (переменная Х становится свободной) и система автоматически переходит на следующий по порядку факт игрок('Коля',10), сопоставляя свободную переменную Х со значением 'Коля' и '9' с '10'. Переменная Х получает значение 'Коля', но объекты '9' и '10' не сопоставляются. Поэтому выполнение целевого предиката заканчивается неудачно, решения не получено. И вновь переменные целевого утверждения освобождаются, осуществляется переход на очередной факт и осуществляется попарно сопоставление объектов. В соответствии с рассмотренными правилами система выдаст еще два решения и закончит работу: Такой процесс согласования целевого утверждения путем прямого продвижения по программе называется механизмом прямого полного перебора или прямой трассировкой (forward tracking). Механизм прямого перебора с возвратом. Пролог производит доказательства конъюнкции целевых утверждений слева направо. При этом может встретиться целевое утверждение, согласовать которое не удается. Если такое случается, то происходит смещение влево до тех пор, пока не будет найдено целевое, которое может быть вновь согласовано, или не будут исчерпаны все предшествующие целевые утверждения. Если слева нет целевых утверждений, то конъюнкцию целевых утверждений согласовать нельзя. Однако, если предшествующее целевое утверждение может быть согласовано вновь, Пролог возобновляет процесс доказательства целевых утверждений слева направо, начиная со следующего справа целевого утверждения. Такой процесс смещения влево для повторного согласования целевого утверждения и возврата называется механизмом прямого перебора с возвратом. Данный механизм поиска решений рассмотрим на примере задачи определения пар игроков двухкругового турнира в настольный теннис между всеми игроками (возраст в расчет не принимается). Воспользуемся имеющейся базой знаний и введем целевое утверждение:  Рис. 1.3. Проограмма playing_tennisюpl Цель турнир/2 составная, она включает три подцели. Пролог обращается к фактам, проверяя, удовлетворяют ли они каждой из подцелей, просматривая их слева направо. Общая цель считается достигнутой, если все подцели истинны. Сначала ищется факт, сопоставимый с первой подцелью. В данной задаче очевидно, что все факты будут успешно сопоставлены с первой и второй подцелью. Но нам важно проследить, как будет работать механизм прямого перебора с возвратом. После успешного сопоставления указатель первой подцели закрепляется за фактом игрок('Петя',9). Система переходит ко второй подцели и начинает сопоставлять ее с фактами, начиная с самого первого. Переменная X, как и переменная Y, принимает значение 'Петя'. Система переходит к третьей подцели. При этом обращения к фактам не происходит, поскольку данная подцель является вычисляемым высказыванием. Третья подцель оказывается ложной, поскольку требуется неравенство переменных Х и Y, а они равны. Следовательно, и все целевое утверждение является ложным. Но на этом процесс решения задачи не заканчивается. Происходит возврат к предыдущей подцели – второй. Этот переход называется автоматическим возвратом (backtraking). В процессе автоматического возврата на предыдущую подцель все переменные этой подцели освобождаются (т.е. Y опять свободна), указатель первой подцели по-прежнему закреплен за первым фактом, а указатель второй подцели смещается на второй факт игрок('Коля',10). Теперь переменная Y успешно сопоставляется со значением 'Коля', вторая подцель снова оказывается истинной. Система переходит к третьей подцели Х\=Y. Переменная Х сохраняет значение 'Петя', и третья подцель оказывается истинной. И, следовательно, вся цепочка подцелей истинна. Полученное решение выводится на экран: X = 'Петя', Y = 'Коля' ; Поскольку мы задали внешнюю цель (в режиме диалога), поиск решений на этом не заканчивается. Используя механизм возврата, система вновь переходит на предыдущую подцель, передвигая ее указатель на следующий факт игрок('Вася',9). Переменная Y получает новое значение и после проверки на истинность третьей подцели на экран выводится очередное решение. Когда все факты для второй подцели будут исчерпаны, на экране будет представлено четыре решения: ?- турнир(X,Y). X = 'Петя', Y = 'Коля' ; X = 'Петя', Y = 'Вася' ; X = 'Петя', Y = 'Ваня' ; X = 'Петя', Y = 'Юра' ; Исчерпав все факты второй подцели, система возвращается к первой подцели. Переменные и этой подцели освобождаются (Х и Y становятся свободными). Указатель первой подцели смещается на второй факт. Указатель второй цели установится на первый факт, и на экран последовательно будут выводится решения: X = 'Коля', Y = 'Петя' ; X = 'Коля', Y = 'Вася' ; X = 'Коля', Y = 'Ваня' ; X = 'Коля', Y = 'Юра' ; . . . . . . . . X = 'Вася', Y = 'Петя' ; X = 'Вася', Y = 'Коля' ; X = 'Вася', Y = 'Ваня' ; X = 'Вася', Y = 'Юра' ; X = 'Ваня', Y = 'Петя' ; X = 'Ваня', Y = 'Коля' ; X = 'Ваня', Y = 'Вася' ; X = 'Ваня', Y = 'Юра' ; X = 'Юра', Y = 'Петя' ; X = 'Юра', Y = 'Коля' ; X = 'Юра', Y = 'Вася' ; X = 'Юра', Y = 'Ваня' ; И т.д., пока не будут исчерпаны все факты для первой подцели: Таким образом, механизм полного прямого перебора с возвратом обеспечивает поиск всех фактов для всех подцелей целевого утверждения. Иначе говоря, процесс поиска решения заканчивается после просмотра всех фактов для всех подцелей. Можно сформулировать основные правила поиска с возвратом: Цели должны быть доказаны по порядку, слева, направо. Для доказательства некоторой цели предложения просматриваются в том порядке, в каком они появляются в тексте программы. Для того, чтобы доказать головную цель правила, необходимо доказать цели в теле правила. Тело правила состоит, в свою очередь из целей, которые должны быть доказаны. Цель считается доказанной, если с помощью соответствующих фактов доказаны все цели, находящиеся в листьевых вершинах дерева целей. Управление поиском с возвратом: предикаты ! и fail Управление поиском с возвратом заключается в решении двух задач: включении поиска с возвратом при его отсутствии, и отключении поиска с возвратом при его наличии. Для решения этих задач используются два стандартных предиката: предикат fail, включающий поиск с возвратом. предикат ! (этот предикат еще называют «отсечение»), предотвращающий поиск с возвратом. Рассмотрим, как работает предикат fail. Для начала следует напомнить, что поиск с возвратом начинает свою работу только в том случае, если не удается доказать какую-либо цель. Поэтому действует предикат fail очень просто – цель с использованием данного предиката никогда не доказывается, а, следовательно, всегда включается поиск с возвратом. Предикат fail используется в тех случаях, когда в программе есть внутренняя цель, и необходимо найти все возможные решений. Рассмотрим пример. Имеется база данных "hobby", содержащий об увлечениях некоторых людей. likes('Катя','книги'). likes('Петя','хоккей'). likes('Маша','теннис'). likes('Дима','футбол'). likes('Аня','театр'). Пусть требуется вывести на экран все факты базы знаний в удобочитаемом виде. Чтобы сделать это, можно задать цель: likes(X,Y).  Рис. 1.4. Проограмма hobby. Напишем предикат выводящий на экран все факты базы знаний print:- likes(X,Y), write(X),write(" любит "),write(Y),nl, fail. print:- write("Конец"),nl. После запуска на выполнение на экран будет выведено:  Рис. 1.5. Результат запроса print. Процедура вывода на экран в рассмотренном примере состоит из двух правил. Второе правило играет важную роль. Если его убрать, решение задачи формально окончится неудачей. И действительно, система выдаст сообщение false по окончании вывода, если попытка найти еще одно правило с головным предикатом print, которое приводит к успешному решению, ни к чему не привела. Сообщение false выглядит крайне нелогично, когда цель фактически достигнута. Не имеет значения, что будет записано в теле второго правила, лишь бы результат был заведомо истинным. Тот же результат можно получить, если в данном примере вместо предиката fail в конце цепочки записать вычисляемое высказывание: X='Аня'. Проблема состоит в том, что факт, касающийся 'Аня', может быть удален или оказаться не последним. Т.е. обыгрывать специфику данных всегда следует с большой осторожностью. Предикат fail устраняет указанную проблему. Другое средство управления механизмом автоматического возврата – это использование предиката "отсечение" cut, который в программах обычно изображается символом "!". Этот предикат называют также "преградой" или предикатом "сократить". Предикат "!" позволяет сократить или отсечь часть пространства поиска. Используя этот предикат, можно существенно ограничить автоматический перебор фактов в процессе поиска цели и, следовательно, ускорить решение задачи. Если преграда в виде предиката cut встроена в цепочку подцелей, то действуют следующие правила. 1. Невозможно осуществить возврат через преграду на предыдущую подцель правила. 2. Достижение цели за преградой приводит к прекращению перебора предикатов, соответствующих текущему головному предикату правила. Например, пусть предикату a соответствуют три факта а1, а2, а3: a(a1). a(a2). a(a3). Предикату b соответствует два факта b1, b2: b(b1). b(b2). Предикату c – четыре факта c1, c2 , c3, с4: c(c1). c(c2). c(c3). c(c4). Рассмотрим правило, состоящий из трех подцелей, включающий отсечение “!”: p :- a, b, !, c.  Рис. 1.6. Проограмма cut.pl. При отсутствии отсечения система попытается отыскать 3*2*4=24 решения. Наличие отсечения, например после подцели a(A) сужает поиск до 4 решений: один факт из a, один из b и, допустим, все четыре из c, поскольку после перебора фактов С система не сможет осуществить возврат через преграду. Более того, если есть еще один предикат p, он не будет выполняться, согласно второму правилу. |