основы. Лабораторная работа №2 - Основы языка Visual Prolog 8 (2). Лабораторная работа 2 Основы языка Visual Prolog
 Скачать 126.09 Kb.
|
|
Лабораторная работа №2 «Основы языка Visual Prolog» Цель: Изучение основ логического программирования, основные принципы языка Пролог, включая предложения, предикаты, переменные, цели и сопоставления. Оформить отчет. Общие сведения 1 ПРОграммирование в ЛОГике В Прологе (Prolog — PROgramming LOGic) вы получаете решение задачи логическимвыводом из ранее известных положений. Обычно программа на Прологе не является последовательностью действий, — она представляет собой набор фактов с правилами, обеспечивающими получение заключений на основе этих фактов. Поэтому Пролог известен как декларативный язык. Пролог базируется на предложениях Хорна, являющихся подмножеством формальной системы, называемой логикой предикатов. Пролог включает механизм вывода, который основан на сопоставлении образцов. С помощью подбора ответов на запросы он извлекает хранящуюся (известную) информацию, т.е. знание Пролога о мире — это ограниченный набор фактов (и правил), заданных в программе. Одной из важнейших особенностей Пролога является то, что, в дополнение к логическому поиску ответов на поставленные вами вопросы, он может иметь дело с альтернативами и находить все возможные решения. Вместо обычной работы от начала программы до ее конца, Пролог может возвращаться назад и просматривать более одного «пути» при решении всех составляющих задачу частей. Программист на Прологе описывает объекты (objects) и отношения (relations), а затем описывает правила (rules), при которых эти отношения являются истинные. 2 Основные разделы Visual Prolog-программ Обычно программа на Visual Prolog состоит из четырех основных программных разделов. К ним относятся: раздел clauses (предложений); раздел predicates (предикатов); раздел domains (доменов); раздел goal (целей). 2.1 Раздел предложений (clauses) В раздел clauses (предложений) помещаются все факты и правила, составляющие программу. Факты — это отношения или свойства, о которых известно, что они имеют значение «истина». Факт представляет либо свойство объекта, либо отношение между объектами. Факт самодостаточен. Для подтверждения факта не требуется дополнительных сведений, и факт может быть использован как основа для логического вывода. Факт в Visual Prolog состоит из имени отношения и объекта или объектов, заключенных в круглые скобки. Факт завершается точкой («.»). Т.е. предложение на естественном языке «Билл любит собак.» (Bill likes dogs) на синтаксисе Visual Prolog будет выглядеть likes ("Bill", "dogs"). Факты, помимо отношений, могут выражать и свойства. Так, например, предложение естественного языка «Кермит зеленый» (Kermit is green) на Visual Prolog, выражая те же свойства, выглядит следующим образом: green ("kermit"). Правила — это связанные отношения; они позволяют логически выводить одну порцию информации из другой. Правило принимает значение «истина», если доказано, что заданный набор условий является истинным. Правило — это свойство или отношение, которое достоверно, когда известно, что ряд других отношений достоверен. Синтаксически эти отношения разделены запятыми. Все правила имеют 2 части: заголовок и тело, разделенные специальным знаком «:-». Заголовок — это факт, который был бы истинным, если бы были истинными несколько условий. Это называется выводом или зависимым отношением. Тело — это ряд условий, которые должны быть истинными, чтобы можно было доказать, что заголовок правила истинен. Ниже представлен обобщенный синтаксис правила в Visual Prolog: заголовок:- <Подцель>, <Подцель>,..., <Подцель>. Тело правила состоит из одной или более подцелей. Подцели разделяются запятыми, определяя конъюнкцию, а за последней подцелью правила следует точка. Каждая подцель выполняет вызов другого предиката Visual Prolog, который может быть истинным или ложным. После того, как программа осуществила этот вызов, Visual Prolog проверяет истинность вызванного предиката, и если это так, то работа продолжается, но уже со следующей подцелью. Если же в процессе такой работы была достигнута точка, то все правило считается истинным; если хоть одна из подцелей ложна, то все правило ложно. Ниже представлены правила, соответствующие связи «любить» (likes): Синди любит все, что любит Билл. (Cindy likes everything that Bill likes) Кейтлин любит все зеленое. (Caitlin likes everything that is green) Используя эти правила, вы можете из предыдущих фактов найти некоторые вещи, которые любят Синди и Кейтлин: Синди любит собак. (Cindy likes dogs) Кейтлин любит Кермит. (Caitlin likes Kermit) Чтобы перевести эти правила на Пролог, вам нужно немного изменить синтаксис, подобно этому: likes ("Сindy", Something):- likes ("Bill", Something). likes ("Сaitlin", Something):- green (Something). Символ «:–» имеет смысл «если» (if). Однако if Пролога отличается от if, написанного в других языках, например, в Pascal, где условие, содержащееся в операторе if, должно быть указано перед телом оператора, который может быть выполнен. Данный тип оператора известен как условный оператор если/тогда (if/then). Visual Prolog использует другую форму логики в таких правилах. Вывод об истинности заголовка правила Пролога делается, если (после того, как) тело этого правила истинно, т.е правило Пролога соответствует условной форме тогда, если (then/if). Все предложения для каждого конкретного предиката в разделе clauses должны располагаться вместе. Последовательность предложений, описывающих один предикат, называется процедурой. Вы можете рассматривать правило и как процедуру. Другими словами, эти правила likes ("Сindy", Something):- likes ("Bill", Something). likes ("Сaitlin", Something):- green (Something). также означают: "Чтобы доказать, что Синди любит что-то, докажите, что Билл любит это" и "Чтобы доказать, что Кейтлин любит что-то, докажите, что это что-то зеленое". 2.2 Раздел предикатов ((class) predicates) Если вразделе clauses программы на Visual Prolog вы описали собственный предикат, то вы обязаны объявить его в разделе predicates (предикатов); в противном случае Visual Prolog не поймет, о чем вы ему «говорите». В результате объявления предиката вы сообщаете, к каким доменам (типам) принадлежат аргументы этого предиката. Visual Prolog поставляется с большим набором встроенных предикатов (их не нужно объявлять), а интерактивное справочное руководство предоставляет полное их описание. Предикаты задают факты и правила. В разделе же predicates все предикаты просто перечисляются с указанием типов (доменов) их аргументов. Объявление предиката начинается с имени этого предиката, за которым идет двоеточие («:»), далее следует открывающая (левая) круглая скобка, затем ноль или больше доменов (типов) аргументов предиката: predicatesName : (argument_typel OptionalNamel, argument_type2 OptionalName2,..., argument_typeN OptionalNameN). После каждого домена (типа) аргумента следует запятая, а после последнего типа аргумента ‒ закрывающая (правая) скобка. Декларация предиката завершается точкой. Доменами (типами) аргументов предиката могут быть либо стандартные домены, либо домены объявленные вами в разделе domains. Имя предиката должно начинаться с буквы, за которой может располагаться последовательность букв, цифр и символов подчеркивания. Не следует использовать заглавные буквы в качестве первой буквы имени предиката. Оно должно начинаться на прописную букву. Имя предиката может иметь длину до 250 символов. В именах предикатов запрещается использовать пробел, символ минус, звездочку и другие алфавитно-цифровые символы. Аргументы предикатов должны принадлежать доменам, известным Visual Prolog. Эти домены могут быть либо стандартными доменами, либо некоторыми из тех, что вы объявили вразделе доменов. Т.е. если предикат my_predicate (string, integer) объявлен в разделе predicates следующим образом: class predicates my_predicate : (string, integer). то не нужно в разделе domains декларировать домены его аргументов, т. к. symbol и integer — стандартные домены. Однако если этот же предикат вы объявляете так: class predicates my_predicate : (name, number). то необходимо объявить, что name (строковый тип) и number (целый тип) принадлежат к стандартным доменам string и integer: domains name = string. number = integer. class predicates my_predicate : (name, number). 2.3 Раздел доменов (domains) В традиционном Прологе есть только один тип — терм. В Visual Prolog мы объявляем домены всех аргументов предикатов. Домены позволяют задавать разные имена различным видам данных, которые, в противном случае, будут выглядеть абсолютно одинаково. В программах Visual Prolog объекты в отношениях (аргументы предикатов) принадлежат доменам, причем это могут быть как стандартные (табл. 2.1), так и описанные вами специальные домены. Таблица 2.1 ‒ Основные стандартные домены
Раздел domains служит двум полезным целям. Во-первых, вы можете задать доменам осмысленные имена, даже если внутренне эти домены аналогичны уже имеющимся стандартным. Во-вторых, объявление специальных доменов используется для описания структур данных, отсутствующих в стандартных доменах. Иногда очень полезно описать новый домен — особенно, когда вы хотите прояснить отдельные части раздела predicates. Объявление собственных доменов, благодаря присваиванию осмысленных имен типам аргументов, помогает документировать описываемые вами предикаты. Покажем, как объявление доменов помогает документировать предикаты: Франк — мужчина, которому 45 лет. Используя следующие домены, можно так объявить соответствующий предикат: domains name = symbol. sex = symbol. age = integer. class predicates person : (name, sex, age). 2.4 Раздел цели (goal) Этот раздел аналогичен телу правила: это просто список подцелей. Цель отличается от правила лишь следующим: за ключевым словом goal не следует «:-»; при запуске программы Visual Prolog автоматически выполняет цель. Это происходит так, как будто Visual Prolog вызывает goal, запуская тем самым программу, которая пытается разрешить тело правила goal. Если все подцели в разделе goal истинны, — программа завершается успешно. Если же какая-то подцель из раздела goal ложна, то считается, что программа завершается неуспешно (хотя чисто внешне никакой разницы в этих случаях нет, — программа просто завершит свою работу). Пример: Однократно дав языку Visual Prolog несколько фактов, мы можем задавать вопросы, касающиеся отношений между ними. На естественном языке мы спрашиваем: Does Bill like dogs? (Билл любит собак?). По правилам Пролога мы спрашиваем: likes ("Bill", "dogs"). Получив такой запрос, Visual Prolog ответит: yes (да), потому что Visual Prolog имеет факт, подтверждающий, что это так. 3. Другие разделы программ Теперь, когда вы ознакомились с такими разделами программ Visual Prolog, как clauses, (class) predicates, domains и goal, поговорим о некоторых других, часто используемых разделах программ: (class) facts, constants. 3.1 Раздел фактов ((class) facts) Программа на Visual Prolog представляет собой набор фактов и правил. Иногда в процессе работы программы бывает необходимо модифицировать (изменить, удалить или добавить) некоторые из фактов, с которыми она работает. В этом случае факты рассматриваются как динамическая или внутренняя база данных, которая при выполнении программы может изменяться. Для объявления фактов программы, рассматривающихся как части динамической (или изменяющейся) базы данных, Visual Prolog включает специальный раздел — (class) facts. Ключевые слова (class) facts объявляют раздел фактов. Именно в этой секции вы объявляете факты, включаемые в динамическую базу данных. В Visual Prolog есть несколько встроенных предикатов, облегчающих использование динамических фактов. 3.2 Раздел констант (constants) В программах на Visual Prolog можно объявлять и использовать символические константы. Раздел для объявления констант обозначается ключевым словом constants, за которым следуют сами объявления, использующие следующий синтаксис: <Id> = <Макроопределение>. Рассмотрим следующий фрагмент программы: constants zero = 0. pi = 3.141592653. Перед компиляцией программы Visual Prolog заменит каждую константу на соответствующую ей строку. На использование символических констант накладываются следующие ограничения: описание константы не может ссылаться само на себя: my_number = 2*my_number/2 % не допускается Это приведет к сообщению об ошибке «Recursive declaration» (Рекурсивное определение); в описаниях констант система не различает верхний и нижний регистры. Следовательно, при использовании в разделе программы clauses идентификатора типа constants, его первая буква должна быть строчной для того, чтобы избежать путаницы между константами и переменными. в программе может быть несколько разделов constants, однако объявление константы должно производиться перед ее использованием; идентификаторы констант являются глобальными и могут объявляться только один раз. Множественное объявление одного и того же идентификатора приведет к сообщению об ошибке «The declaration conflicts with another declaration in the scope» (Объявление вызывает конфликт с другим объявлением в области видимости). 4 Переменные В Visual Prolog переменные позволяют записывать общие факты и правила и задавать общие вопросы. Имена переменных в Visual Prolog должны начинаться с заглавной буквы (или с символа подчеркивания), после которой может стоять любое количество букв (заглавных или строчных), цифр или символов подчеркивания. Удобно использовать в названии переменной буквы разного регистра: IncomeAndExpenditureAccount. В простом запросе, чтобы найти того, кто любит теннис, можно использовать переменные. Например: likes(X, "tennis"). В этом запросе буква «X» используется как переменная для нахождения неизвестного человека. Осмысленный выбор имен переменных делает программу более удобной для чтения. Например: likes(Person, "tennis"). лучше, чем likes(X, "tennis"). потому что Person имеет больше смысла, чем X. Предложение на английском языке Bill likes the same thing as Kim. (Билл любит то же, что и Ким), может быть записано на Visual Prolog следующим образом: likes ("Bill", Thing) :- likes ("Kim", Thing). Thing — это переменная. Если вам нужна только определенная информация запроса, можно использовать анонимные переменные для игнорирования ненужных значений. В Visual Prolog анонимные переменные обозначаются символом подчеркивания («_»). Анонимная переменная может быть использована на месте любой другой переменной, и ей никогда не присваивается значение. Анонимные переменные также можно использовать в фактах. Следующие факты Пролога: owns(_, "shoes"). eats(_). могли быть использованы для выражения утверждений на естественном языке: У каждого есть туфли. (Everyone owns shoes.) Каждый ест. (Everyone eats.) Анонимные переменные сопоставляются с любыми данными. 5 Комментарии Хорошим стилем программирования является включение в программу комментариев, объясняющих все то, что может быть непонятно кому-то другому (или даже вам, спустя полгода). Многострочные комментарии должны начинаться с символов /* и завершаться символами */. Для установки однострочных комментариев можно использовать либо эти же символы, либо начинать комментарий символом процента (%). 6 Сопоставление (matching). В Visual Prolog имеется несколько примеров сопоставления одной вещи с другой. Ясно, что идентичные структуры сопоставимы (сравнимы) друг с другом: parent ("Joe", "Tammy") сопоставимо с parent ("Joe", "Tammy"). Однако сопоставление (сравнение) обычно использует одну или несколько свободных переменных. Например, если X свободна, то parent ("Joe", X) сопоставимо с parent ("Joe", "Tammy") и X принимает значение (связывается с) "Tammy". Если же X уже связана, то она действует так же, как обычная константа. Таким образом, если X связана со значением "Tammy", то parent ("Joe", X) сопоставимо с parent ("Joe", "Tammy"), но parent ("Joe", X) не сопоставимо с parent ("Joe", "Millie") . Две свободные переменные могут сопоставляться друг с другом. Например, parent ("Joe", X) сопоставляется с parent ("Joe", Y), связывая при этом переменные X и Y между собой. С момента связывания X и Y трактуются как одна переменная, и в любое изменение значения одной из них приводит к немедленному соответствующему изменению другой. В случае подобного «связывания» между собой нескольким свободных переменных все они называются совмещенными свободными переменными. В Прологе связывание переменных (со значениями) производится двумя способами: на входе и выходе. Направление, в котором передаются значения, указываете в шаблоне потока параметров (flow pattern). В дальнейшем (для краткости) будем опускать слово «шаблон» и говорить просто «поток параметров». Когда переменная передается в предложение, она считается входным аргументом и обозначается символом (i). Когда же переменная возвращается из предложения, она является выходным аргументом и обозначается символом (о). Объявление предиката выглядит в этом случае следующим образом: phone_number : (string Name, string Phone) (i, o). Указанные в скобках символы (i, o) говорят о том, что первый аргумент будет входным, второй – выходным. При компиляции Visual Prolog 8 автоматически заменяет такое объявление на строку следующего вида: phone_number : (string Name, string Phone [out]). Пример программы Представленный листинг 2.1 представляет собой законченную программу на Visual Prolog 8, служащую небольшим телефонным справочником. Так как используются только стандартные домены, раздел domains в этой программе не нужен. Листинг 2.1.
В качестве цели вызывается стандартный предикат run(), определяя точку входа в программу. Поместим следующие предикаты в описание run(): phone_number("Carol", Number). phone_number(Who, "438-8400"). phone_number("Albert", Number). phone_number(Who, Number). Тогда результат выполнения будет выглядеть следующим образом (рис. 2.1):  Рисунок 2.1 – Результат выполнения программы листинга 2.1 Теперь измените предложения. Предположим, что Kim и Dorothy имеют одинномер телефона. Добавим этот факт в раздел clauses и введем цель: phone_number(Who, "438-8400"). Листинг 2.2
На этот запрос вы должны получить два решения(рис. 2.2):  Рисунок 2.2 – Результат выполнения программы листинга 2.2 7 Разветвление Язык Prolog не содержит операторов, аналогичных операторам разветвления и повторения в других языках программирования. Реализация этих процессов происходит в соответствии с правилами логического вывода. Поэтому для программирования нескольких реализаций одного и того же предиката следует построить несколько правил. При этом у всех ветвей головой правил служит один и тот же предикат. Для примера рассмотрим программу определения типа образовательного учреждения, которое посещает ребенок, в зависимости от его возраста, вводимого с клавиатуры (листинг 2.3). Листинг 2.3.
Результат выполнения программы (рис. 2.3):  Рисунок 2.3 – Результат выполнения программы листинга 2.3 8 Режимы детерминизма предикатов В предыдущих листингах можно было заметить слова determ, nondeterm, multi при объявлении предикатов. Для того чтобы компилятор языка Visual Prolog проводил более быстрые вычисления, при объявлении предикатов указывается режим детерминизма. Объявление режимов детерминизма позволяет организовывать вычисления более экономно. Так, если для вычислений откат не нужен, то нет необходимости ставить точки возврата. Эта особенность предиката отмечается с помощью специального ключевого слова. В результате экономится память, и вычисления становятся быстрее. Режим детерминизма определяется количеством возможных решений при вызове предиката (т. е. тем, нужен ли откат) и тем, может ли он быть неуспешным. Ключевые слова, с помощью которых указываются режимы детерминизма, перечислены в табл. 2.2. Таблица 2.2 ‒ Режимы детерминизма
Компилятор Visual Prolog автоматически вычисляет режим детерминизма предиката с помощью его определения в программе и сообщает пользователю об ошибке, если объявленный режим детерминизма предиката не соответствует фактическому определению предиката. Иногда он ограничивается предупреждением. Предикат succeed() является примером предиката с режимом procedure, предикат fail имеет режим failure. Предикаты с режимом детерминизма procedure, называют процедурами. Если предикат не может порождать более одного решения, то он называются детерминированным, а если может, то недетерминированным. По умолчанию используется режим procedure, если предикат объявляется в разделе (class) predicates, и режим nondeterm, если предикат объявляется в разделе (class) facts. 9 Задания на выполнение 9.1 Упражнения 1. Переведите следующие предложения на естественный язык (помните, что для компьютера эти факты являются просто порциями информации, которые могут быть использованы для согласования ответов с вопросами). 1. likes ("Jeff", "painting"). 2. male ("John"). 3. building("Empire State Building", "New York"). 4. person("Roslin", "Jeanie", "1429 East Sutter St.", "Scotts Valley", "CA", 5066). 2. Напишите предложения на естественном языке, соответствующие следующим правилам Visual Prolog: eats(Who, What):- food(What), likes(Who, What). рass_class (Who) :- did_homework (Who), good_attendance (Who). оwns(Who, What):- bought(Who, What). 3. По данным предложениям составьте правила Visual Prolog: человек голоден, если его желудок пуст; каждому нравится работа, если она веселая и хорошо оплачиваемая; обладает автомобилем тот, кто купил его, платит за него и управляет им; Мари вегетарианка и ест только то, что выписал доктор; Компьютер нужен только программисту; 9.2 По имеющимся фактам и правилам: Иван, Елена, Татьяна, Игорь – студенты. Студент получает зачет, если он отчитается по лабораторным занятиям. Иван отчитается по лабораторным занятиям только вместе с Игорем. Елена и Татьяна отчитались по лабораторным занятиям и пойдут вечером на дискотеку. Если Игорь пойдет на дискотеку вместе с Татьяной, то он отчитается по лабораторным занятиям. Игорь пойдет вечером на дискотеку, если у него будет свободное время. Сегодня вечером Игорь свободен. сформировать следующие запросы: Кто пойдет вечером на дискотеку? Кто получит зачет? 9.3 Задание: Пусть имеется генеалогическое дерево некоторой семьи (см. рис. 2.4). При этом мужчины обозначены прямоугольниками, женщины – овалами. Согласно данному дереву задайте отношение принадлежности к полу и отношение «родитель-ребенок». Опишите с помощью правил следующие отношения: а) «А является отцом В»; b) «А является матерью В»; с) «А является сыном В»; d) «А является дочерью В». Используя описанные факты и правила, найдите ответы на следующие вопросы: a) У кого из перечисленных людей есть сын? b) У кого из перечисленных людей есть дочь? c) У кого есть сын и дочь? d) Кто является дедом Александра? e) Кто является внучкой Дарьи? f) Кто является сестрой Петра? g) Кто является братом Елены? h) Кто является мужем и женой?  Рисунок 2.4 ‒ Генеалогическое дерево 9.4 Задание: Задайте отношение между числами a, b и x, так чтобы х являлось корнем уравнения ax+b=0. Используя полученное отношение, найдите решение уравнений: a) 3х-6=0; b) 1,5х+7,5=0; c) 2,2х-11=0. 9.5 Задание: Опишите предикат, позволяющий находить сумму двух чисел в том случае, если они имеют одинаковые знаки и их произведение, если они имеют разные знаки. Проверьте работу предиката на примерах: a) -3 и 2; b) 1 и 5; c) -6 и -2. 10 Содержание отчета: Тема и цель работы. Основные разделы программы на языке Visual Prolog. Выполненные задания Листинги программ. |