Лабораторная работа №1

Синтаксис языка Prolog. Объявление фактов и правил. Реализация логического вывода

1. Основные синтаксические правила

Программа на языке Пролог состоит из следующих разделов:

DOMAINS – определения доменов (классов объектов);

DATABASE (необязательный) – предикаты базы данных;

PREDICATES – остальные предикаты;

GOAL (необязательный) – внутренняя цель;

CLAUSES – правила.

В разделе DOMAINS описываются собственные типы, создаваемые на основе базовых (табл. 1).

Соответственно правомерны собственные объявления типов следующего вида:

DOMAINS

         name, party, state = symbol

         birth_year, year_in, year_out = integer

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

PREDICATES

         president (symbol, symbol, symbol, integer, integer, integer)

PREDICATES

         president (name, party, state, birth_year, year_in, year_out)

В разделе PREDICATES описываются предикаты (логические функции). Иными словами, данный раздел содержит объявления функций.

Пролог является языком декларативного типа или, используя более «говорящее» название, ЧТО-языком (в отличие от КАК-языков), т.е. при программировании на этом языке разработчик описывает ЧТО нужно сделать, а КАК будет выполняться описанное – остается на совести исполнительной системы средства разработки. Исполнительная система Пролога называется процедурами унификации [1]. Является очевидным, что для эффективной разработки и отладки программ на Прологе разработчик должен представлять принципы функционирования процедур унификации.

Утверждения (факты, правила) описываются в разделе CLAUSES в соответствии со следующим синтаксисом:

<Описание_утверждения> ::=

<Предикат1> [(<Список_термов1>)] [:-

                   <Предикат2> [(<Список_термов2>)],

                   <Предикат3> [(<Список_термов3>)],

                   …

                   <ПредикатN> [(<Список_термовN>)]].

Знак “:-“ соответствует условному выражению ЕСЛИ, знак “,” – логическому выражению И. ИЛИ в Прологе практически не используют, заменяя его многократным определением правила с разными конъюнкциями. Соответственно знак “:-“ отделяет констатирующую часть продукционного правила (первую), называемую также заключением или консеквентом, от условной части (второй), называемой также посылкой или антецедентом. Утверждения с отсутствующим антецедентом являются тождественно истинными и называются фактами. Утверждения с присутствующим антецедентом являются продукционными правилами, истинность которых устанавливается путем логического вывода, т.е. путем проверки истинности утверждений условной части. Для любого предиката, реализуемого разработчиком, может быть разработано несколько утверждений, включая как факты, так и правила.

Термами из списка термов могут быть символические имена, переменные и функторы.

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

В качестве цели (GOAL) может указываться как конъюнкция предикатов, так и одиночный предикат, обусловленный конъюнкцией в разделе CLAUSES.

2. Принципы реализации цели и их использование

Процедуры унификации Пролога ориентированы на выявление истинности поставленной внешней или внутренней (при наличии раздела GOAL) цели. В процессе выяснения истинности цели Пролог осуществляет проверку условной части целевого утверждения, проверяя при этом истинность утверждений, входящих в целевую часть, истинность утверждений, входящих в их целевые части и т.д. Программист при этом решает свои задачи, используя принципы функционирования процедур унификации Пролога.

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

На использовании точек отката основаны методы отката после неудачи (ОПН) и отсечения и отката (ОО).

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

         all_cities_wo_capitol (State) :-

                   city_of ( State, X ),

                   not ( capitol ( State, X ) ),

                   write (X), nl,

                   fail.

Предположим, что в качестве цели используется утверждение all_cities_wo_capitol(«Россия»). Поскольку утверждение, использующее предикат all_cities_wo_capitol в констатирующей части, единственное, то не будет организована точка отката, связанная с различными такими утверждениями. Пусть на основе предиката city_of реализована встроенная база данных следующего вида:

         city_of ( "Россия", "Москва" ).

         city_of ( "Россия", "Киров" ).

         city_of ( "Россия", "СПб" ).

         city_of ( "Польша", "Познань" ).

         city_of ( "Китай", "Нанкин" ).

Тогда точка отката будет устанавливаться на обращение к утверждению city_of, так как если при проверке значения условной части утверждения, связанного с предикатом all_cities_wo_capitol, будет выявлена неудача, то нужно будет проверить значение условной части для другого утверждения city_of. На предикаты not и write точки отката установлены быть не могут, т.к. для одного набора термов возможно только одно утверждение, использующее любой из этих предикатов. Поэтому в данном случае после вызова fail будет осуществлен переход к следующему утверждению city_of.

Метод ОО основан на применении предиката отсечения (cut), обозначаемого как символ «!». Этот предикат всегда оканчивается успешно и осуществляет отсечение (очистку) всех указателей отката. При организации цикла методом ОО предикат fail используется так же, как при ОПН. Использование cut в конце условной части правила позволяет устранить действие установленных ранее точек отката на выполнение программы после анализа правила.

Используемым в Прологе методом повторения является рекурсия:

<предикат>:-

           <повторяемая часть 1>,

           <условие продолжения>,

           <повторяемая часть 2>,

           <предикат>,

<повторяемая часть 3>.

Таким образом, здесь утверждение инициализирует проверку самого себя после успешного выполнения повторяемых частей 1 и 2. В случае организации бесконечной рекурсии условие продолжения будет отсутствовать. Как только условие продолжения ложно, происходит неудачное завершение утверждения, т.е. присвоение ему значения ЛОЖНО. Поэтому при последней проверке утверждения повторяемая часть 2 выполняться не будет. В случае успешного возврата из рекурсии осуществляется выполнение повторяемой части 3, и тогда эта часть выполниться столько же раз, сколько часть 2. В случае неуспешного возврата повторяемая часть 3 не будет выполнена ни разу, и первое («родительское») утверждение завершится неудачей. Успешное выполнение рекурсивного утверждения часто организуется путем создания двух связанных с предикатом утверждений, первое из которых соответствует приведенному выше, а второе выполняется с успешным завершением при невыполнении условия продолжения первого утверждения.

Данный метод построения рекурсивных правил называется           ОПР-методом (ОПР – обобщенное правило рекурсии). Метод ОПН, в отличие от него, используется в случаях, когда необходим просмотр всего диапазона правил, для чего производится возврат в точку отката.

Пример:

sum_series (1, 1).

sum_series (Number, Sum) :-

           Number > 0,

           Next_number = Number – 1,

           sum_series (Next_number, Partial_Sum),

           Sum = Number + Partial_Sum.

Этот предикат вычисляет сумму ряда 1, 2, …, Number. Условие Number>0 предназначено для контроля неотрицательности Number и не является условием продолжения. При каждой новой проверке утверждения sum_series производится сравнение величины Next_number с 1. Если результат сравнения неудачен, то производится переход к следующему утверждению sum_series. Если Next_number=1, то переменной Partial_Sum ставится в соответствие 1 и производится первое удачное завершение утверждения, после которого вычисляется значение Sum и т.д.

В случае отсутствия всех повторяемых частей и условия продолжения получаем следующую повторяемую конструкцию:

repeat.

repeat :- repeat.

Используется она следующим образом:

do_echo :-

           repeat,

           readln(Name),

           write(Name), nl,

           check(Name), !.

check (stop) :-

           nl, write (“ – OK, bye!”).

check (_) :- fail.

В данном случае при вводе строки Name ”stop” выполняется успешное завершение утверждения с очисткой всех точек отката при помощи предиката отсечения. В случае ввода другой строки при помощи предиката fail осуществляется повторная проверка утверждения. В случае отсутствия предиката repeat повторная проверка утверждения не выполняется, так как отсутствует точка отката, возникающая по причине двойственности утверждения repeat. Таким образом, при выполнении предиката fail без использования repeat осуществлялся бы неудачный выход из утверждения do_echo. Повторная проверка утверждения repeat выполняется следующим образом. Поскольку в предыдущий раз было успешно проверено первое утверждение, связанное с этим предикатом, производится выполнение второго утверждения, которое обращается к первому утверждению.

3. Варианты заданий

Задание. Набрать указанную программу. Опробовать использование внешней и внутренней цели. Внутреннюю цель реализовать методом отката после неудачи. Доработать программу в соответствии с заданием.

Вариант 1. Программа из приложения 1. Указать цель: вывести всех демократов старше, чем 1915 г.р. Формат вывода: <Фамилия>: <начало правления> – <конец правления>.

Вариант 2. Программа из приложения 1. Указать цель: вывести всех техасцев. Формат вывода: <Фамилия> (<год рождения> г.р.): <начало правления> - <конец правления>.

Вариант 3. Программа из приложения 1. Указать цель: вывести всех демократов, правивших после 1969 г. Формат вывода: <Фамилия> (<год рождения> г.р.).

Вариант 4. Программа из приложения 2. Добавить утверждения: Бет любит пельмени, Бет любит пиццу. Указать цель: вывести все продукты, которые любит Бет, но не любит Мэри.

Вариант 5. Программа из приложения 2. Добавить новый предикат "Полезно" и утверждения: Бет полезно молоко, Бет полезно мясо, Бет полезны апельсины. Указать цель: вывести все продукты, которые любит Мэри и полезны Бет. Указать цель: вывести все продукты, которые не любит Мэри, но полезны Бет.

Вариант 6. Программа из приложения 2. Добавить новый предикат "Полезно" и утверждения: Бет полезно молоко, Бет полезно мясо, Бет полезны апельсины. Добавить предикат "Вредно" и утверждения: Элис вредны все красные фрукты, Элис вреден попкорн, Элис вредны апельсины. Указать цель: вывести все продукты, полезные Бет и не вредны Элис. Указать цель: вывести все продукты, которые любит Мэри, при этом вредные Элис и не полезные Бет.

Вариант 7. Программа из приложения 3. Добавить условие: "City есть город государства State, если City есть город штата Substate И Substate есть штат государства State". Указать цель: Вывести все города страны.

Вариант 8. Программа из приложения 3. Добавить условие: City есть город государства State, если City есть город штата Substate И Substate есть штат государства State. Ввести новый предикат "Граничат" и указать пары пограничных стран. Указать цель: вывести все города стран, не пограничных заданной.

Вариант 9. Программа из приложения 3. Добавить условие: City есть город государства State, если City есть город штата Substate И Substate есть штат государства State. Ввести новый предикат "Граничат" и указать пары пограничных стран. Указать цель: вывести все города стран, не пограничных заданной, кроме столиц.

Вариант 10. Программа из приложения 4. Взяв в качестве базовых предикаты mother и father, реализовать предикаты: son, daughter, parents, brother, sister, grandmother, grandfather. Указать цель: вывести все пары "бабушка - внук (внучка)". Указать цель: вывести все пары "дед - внук (внучка)".

Вариант 11. Программа из приложения 4. Взяв в качестве базовых предикаты mother и father, реализовать предикаты: son, daughter, parents, brother, sister, grandmother, grandfather. Ввести новые предикаты "Дядя" и "Тетя". Указать цель: вывести все пары "дядя - племянник (племянница)". Указать цель: вывести все пары "тетя - племянник (племянница)".

Вариант 12. Программа из приложения 4. Взяв в качестве базовых предикаты mother и father, реализовать предикаты: son, daughter, parents, brother, sister, grandmother, grandfather. Ввести новые предикаты "Теща (свекровь)" и "Тесть (свекор)". Указать цель: Вывести все пары "теща (свекровь) - зять (сноха)". Указать цель: вывести все пары "тесть (свекор) - зять (сноха)".

Структура отчета по лабораторной работе

1.     Титульный лист.

2.     Цель работы.

3.     Описание выполнения задания:

3.1.    Формулировка задания.

3.2.    Текст программы.

3.3.    Результаты достижения цели.

4.     Выводы.

Библиографический список

1. Ин, Цин Маун. Использование Турбо-Пролога / Ин, Цин Маун, Соломон, Дэвид; Пер. с англ. Д.Ю. Буланже, О.Л. Кондратьева; Под ред. Б.Г. Сушкова. – М.:Мир, 1993. – 606 с.: ил.

2. Грэй, П. Логика, алгебра и базы данных / Грэй, П.; Пер. с англ. Х.И. Кислова, Г.Е. Минца; Под ред. Г.В. Орловского, А.О. Слисенко. – М.: Машиностроение, 1989. – 359с.

3. Марселлус, Д.Н. Программирование экспертных систем на языке Турбо-Пролог / Марселлус, Д.Н.; Пер. с англ. И.И. Чижикова; Предисл. С.В. Трубицына. – М.: Финансы и статистика, 1994. – 256 с.

Приложение 1

Программа «Президенты США»

DOMAINS

         name, party, state = symbol

         birth_year, year_in, year_out = integer

PREDICATES

         president ( name, party, state, birth_year, year_in, year_out )

CLAUSES

         president ( eisenhower, republican, texas, 1890, 1953, 1961 ).

         president ( kennedy, democrat, massachusetts, 1917, 1961, 1963 ).

         president ( johnson, democrat, texas, 1908, 1963, 1969 ).

         president ( nixon, republican, california, 1913, 1969, 1974 ).

         president ( ford, republican, nebraska, 1913, 1974, 1977 ).

         president ( carter, democrat, georgia, 1924, 1977, 1981 ).

Приложение 2

Программа «Описание гастрономических предпочтений персон»

DOMAINS

         person = symbol

         food = symbol

         color = symbol

PREDICATES

         likes ( person, food )

         fruit (food)

         color ( food, color )

CLAUSES

         likes ( mary, pears ).

         likes ( mary, popcorn ).

         likes ( mary, apples ).

         likes ( beth, X ) :-

                   likes ( mary, X ),

                   fruit (X),

                   color ( X, red ).

         likes ( beth, X ) :-

                   likes ( mary, X ),

                   X = popcorn.

         fruit (pears).

         fruit (apples).

         color ( pears, yellow ).

         color ( oranges, orange ).

         color ( apples, red ).

         color ( apples, yellow ).

Приложение 3

Программа «Города и страны»

DOMAINS

         city, state = symbol

PREDICATES

         city (city)

         state (state)

         substate ( state, state )

         capitol ( state, city )

         city_of ( state, city )

CLAUSES

         city ( "Москва" ).

         city ( "Киров" ).

         city ( "Пекин" ).

         city ( "СПб" ).

         city ( "Казань" ).

         city ( "Варшава" ).

         city ( "Познань" ).

         city ( "Нанкин" ).

         state ( "Россия" ).

         state ( "Польша" ).

         state ( "Китай" ).

         substate ( "Россия", "Татарстан").

         capitol ( "Россия", "Москва" ).

         capitol ( "Польша", "Варшава" ).

         capitol ( "Китай", "Пекин" ).

         capitol ( "Татарстан", "Казань" ).

         city_of ( "Россия", "Москва" ).

         city_of ( "Россия", "Киров" ).

         city_of ( "Россия", "СПб" ).

         city_of ( "Польша", "Познань" ).

         city_of ( "Китай", "Нанкин" ).

         city_of ( State, City ) :- capitol ( State, City ).

Приложение 4

Программа «Родственники»

DOMAINS

         person = symbol

PREDICATES

         male (person)

         female (person)

         mother ( person, person )

         father ( person, person )

         dautcher ( person, person )

         son ( person, person )

         sister ( person, person )

         brother ( person, person )

         husband ( person, person )

         wife ( person, person )

         parents ( person, person, person )

         aunt ( person, person )

         uncle ( person, person )

         gmother ( person, person )

         gfather ( person, person )

         father_in_law ( person, person )

         mother_in_law ( person, person )

CLAUSES

         male ("Frank").

         male ("Sam").

         male ("Thomas").

         male ("Donald").

         male ("Robert").

         male ("Roger").

         female ("Mary").

         female ("Debbie").

         female ("Constance").

         female ("Alice").

         female ("Elisabeth").

         female ("Susanne").

         mother ( "Sam", "Mary" ).

         mother ( "Debbie", "Mary" ).

         mother ( "Mary", "Alice" ).

         mother ( "Frank", "Constance" ).

         father ( "Sam", "Frank" ).

         father ( "Debbie", "Frank" ).

         father ( "Mary", "Donald" ).

         father ( "Frank", "Thomas" ).