Основы логического программирования

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1.

Основы логического программирования

 

Цель практического занятия – знакомство с принципами логического программирования.

Основные парадигмы программирования

Разработка языка Prolog (Пролог) началась в 1970 г. Аланом Колмероэ и Филиппом Русселом. Они хотели создать язык, который мог бы делать логические заключения на основе заданного текста. Название является сокращением от "PROgramming in LOGic". Этот язык был разработан в Марселе в 1972г.

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

При использовании ЭВМ для решения задач можно выделить два взаимосвязанных способа представления знания:

1) процедурное представление, т. е. определение алгоритма обработки данных;

2) декларативное представление, т. е. определение отдельных понятий, их состояния в конкретные моменты времени и связей между ними.

Традиционные алгоритмические языки (Бэйсик, Паскаль, Си, Фортран) являются процедурными, поскольку их цель – описание алгоритма. Но они содержат и декларативные компоненты (описание переменных).

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

Факты представляют собой логические формулы. База знаний (БЗ) задается совокупностью таких формул. Логические методы обеспечивают получение новых фактов из фактов, представленных в БЗ.

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

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

– доказательства теорем и вывода решений в задачах;

– создания пакетов символьной обработки при решении уравнений,

дифференцировании, интегрировании и т. д.;

– разработки упрощенных версий систем ИИ;

– создания естественно-языковых интерфейсов для существующих

программ;

– перевода текстов с одного языка на другой, в том числе – с одного

языка программирования на другой.

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

• объявления некоторых фактов об объектах и отношениях между ними,

• определения некоторых правил об объектах и отношениях между ними;

• формулировки вопросов об объектах и отношениях между ними.

Понятие предиката

Теоретической основой Пролога является раздел символьной логики, называемый исчислением предикатов. Предикат - это логическая функция, которая выражает некоторое отношение между своими аргументами и принимает значение "истина", если это отношение имеется или "ложь", если оно отсутствует.

Рассмотрим понятие предиката в Прологе на примере родословной Рюриковичей.

Вначале запишем отношения типа родитель – ребенок. В синтаксисе Пролога выражение «Игорь является родителем Святослава» выглядит следующим образом:

parent (игорь, святослав).

 

Здесь родитель parent – это имя предиката, а «игорь» и «святослав» – аргументы. Аргументы игорь и святослав являются константами, поэтому записаны строчными буквами. С прописной буквы в Прологе начинаются переменные. Точка означает конец предиката, так же, как и конец предложения на естественном языке.

 

Рис. 1.1. Родословная Рюриковичей

 

 

Запишем также родительские отношения для других членов генеалогического дерева:

parent(рюрик, игорь). parent(ефанда, игорь).

parent(ольга, святослав). parent (игорь, святослав).

parent(святослав, святополк).parent(куно, святополк). и т.д.

Полученный набор предикатов образует базу знаний.

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

? parent(ефанда, игорь).

Эта цель может быть прочитана следующим образом: Является ли Ефанда родителем Игоря? Сопоставив эту цель с содержимым базы знаний, Пролог установит, что данное утверждение истинно и сообщит об этом.

Запрос «Кто является родителями Игоря?» в Прологе выглядит следующим образом:

? parent(X, игорь).

Здесь X является переменной, которой должны быть присвоены искомые значения. Переменная в Прологе является аналогом местоимения или вопросительного слова. Из приведенной выше базы знаний Пролог извлечет два ответа:

X = рюрик

X = ефанда

Мы можем сформулировать вопрос следующим образом: Есть ли у Игоря родители?

parent(_, игорь).

Пролог выдаст ответ: Yes.

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

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

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

? parent(X, ярослав), parent(Y, X).

Данная запись означает: Найти Y, являющийся родителем X, который, в свою очередь, является родителем Ярослава. Запятая в прологе идентична союзу "И" или конъюнкции. В ответ на такой запрос Пролог выдаст следующий ответ:

X = святослав

Y = малуша

Можно выдать следующий запрос:

? parent(ольга, _).

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

Этот запрос можно прочитать следующим образом: Есть ли у Ольги дети?

Пролог выдаст ответ: Yes.

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

Таким образом, программа на Прологе состоит из предикатов.

Программа на Прологе и база знаний - синонимы. Цель формулируется также в виде предикатов. Выполнение программы на Прологе – это резолюция цели.

Факты и правила в Прологе

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

grandparent(X,Y) if parent(X,Z), parent(Z,Y).

Синонимом связки "if" в правиле являются символы ":-", поэтому правило может быть записано в виде.

grandparent(X,Y):- parent(X,Z), parent(Z,Y).

Читать это нужно следующим образом: X является прародителем Y, если X является родителем Z и Z является родителем Y. Предикат grandparent(X,Y) называется заголовком правила, а выражение справа от if – телом правила.

Таким образом, как и в базах данных, в базе знаний Пролога в виде фактов мы храним первичные знания, а производные от них записываем в виде правил, к которым обращаемся так же, как и к фактам.

Пример программы на Прологе

Существует множество реализации языка Пролог для разных классов вычислительных систем. Для выполнения лабораторных работ используется программный продукт Visual Prolog v.5.2 Personal Edition for Windows.

Программа на Прологе состоит из нескольких секций, каждая из которых идентифицируется ключевым словом и имеет следующую обобщенную структуру:

 

Domains

/* секция объявления доменов */

Database

/* секция объявления динамических баз данных */

Predicates

/* секция объявления предикатов */

Clauses

/* предложения (факты и правила) */

Goal

/* подцель_1, подцель_2, и т. д. */

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

Для набора фактов и правил, рассмотренных выше, один из возможных примеров программы на Прологе будет иметь вид:

Рис. 1.2. Пример программы на Прологе

Пролог-программа может использовать комментарии, которые не влияют на выполнение программы, но могут оказать помощь человеку, читающему программу. Пролог игнорирует произвольное число строк, заключенное между символами /* и */. Все, что находится между % и концом строки, также рассматривается как комментарий.

Практикум 1-1

:

Запустите систему Пролог. Создайте программу «Родственные отношения» в соответствии с рис.1.1., рис.1.2. Проверьте работу программы, ответив на вопросы: 1. Является ли Ольга родителем Игоря? 2. Кто родители князя Игоря? 3. Есть ли у Олега дети? 4. Чьим внуком является Ярослав Мудрый? 5. Сколько детей у Анны Византийской?

 

Практикум 1-2

:

Добавьте правила, для определения родственных связей · отец · мать · брат · сын · дядя Проверьте работу программы, ответив на вопросы: 1. Кто отец Владимира Красное Солнышко?? 2. Перечислить всех матерей? 3. Сколько братьев у Ярослава Мудрого? 4. Был ли сын у Ярополка? 5. Был ли дядя у Мстислава Храброго?

 

Практикум 1-3

:	Самостоятельно сформулируйте пять запросов к базе знаний Оформите Отчет по лабораторной работе

 

 

Контрольное задание 1

Исходные данные

Номер варианта индивидуального задания выбирается по последней цифре номера зачетной книжки (номера студенческого билета).

В индивидуальном задании студенту для описания базы фактов предлагается минимальный набор родственных отношений в соответствии с вариантом:

0.	отец/2. мать/2.
1.	сын/2. дочь/2.
2.	сын/3. дочь/3.
3.	родитель/2. мужчина/1.
4.	родитель/2. женщина/1.
5.	ребенок/2. мужчина/1.
6.	ребенок/2. женщина /1.
7.	ребенок/3.
8.	родители/3.
9.	ребенок/3. сын/2.

Значками «/1», «/2», «/3» задается арность отношения или, говоря в терминах предметной области, количество личностей в отношении.

Например:

· отношение «мужчина/1» характеризует такой факт как «Виктор является мужчиной» или на Пролог

мужчина (“Виктор”);

· отношение «отец/2» характеризует родственное отношение «Виктор отец Андрея» или на Пролог

отец (“Виктор”, “ Aндрей”);

· отношение «сын/3» характеризует родственной отношение «Андрей сын Виктора и Аллы» или на Пролог

сын (“Андрей”, “Виктор”, “Алла”);

· отношение «родитель/3» характеризует родственной отношение «Виктор и Алла родители Андрея» или на Пролог

родители (“Виктор”, “Алла”, “Андрей”).

Примечание: Указанный в задании минимальный набор фактов родственных отношений может быть расширен дополнительными фактами, но необходимость подобного действия необходимо обосновать.

Задание 1. Генеалогическое дерево

Для определения фактов базы знаний необходимо составить генеалогическое дерево и изобразить его на бумаге в виде семантической сети. Пример генеалогического дерева приведен на рис.1.1. Личности, объединяемые генеалогическим деревом, могут быть как реальными (Иван Грозный, Петр I, Николай II, Пушкин А.С., и т.п.), так и виртуальными (родословные гномов и т.п. персонажей). Для проверки правильности составления всех правил родственных отношений дерево должно содержать не менее четырех уровней или, говоря языком предметной области, на дереве должны быть прадедушки (прабабушки) и правнуки (правнучки). Для упрощения задания не рекомендуется (но не возбраняется) вводить в генеалогическое дерево личностей порождающих циклические связи, являющимися, например, одновременно «супругой» и «двоюродной сестрой».

Задание 2. Представление правил

Используя исходные предикаты (в соответствии с вариантом) написать правила для установления родственных связей, таких как:

· отец, мать, сестра, брат, сын, дочь;

· двоюродная сестра (кузина), двоюродный брат (кузен), дядя, тетя, племянник, племянница;

· дедушка, бабушка, прадедушка, прабабушка, внук, внучка, правнук, правнучка.

Дополнительно (для желающих - задания повышенной трудности):

кровные (общий предок), сводные брат и сестра, шурин, деверь, золовка, тесть, теща, зять, невестка.

Для каждого родственного отношения первоначально необходимо записать правило на естественном языке (в виде продукции). Например:

ЕСЛИ есть такой X который является отцом Z

И Z является отцом ИЛИ матерью Y

ТОГДА X является дедом Y.

Затем переписать это же правило на языке Пролог:

grandfather (X,Y):- father (X,Z), father (Z,Y).

grandfather (X,Y):- father (X,Z), mother (Z,Y).

Задание 3. Программа на Прологе

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

Описать все правила родственных отношений.

Сформулировать запросы для проверки работы программы

Требования к оформлению

Преподавателю на проверку сдается файл Microsoft Word, содержащий следующую информацию:

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

2. Генеалогическое дерево

3. Составление правил искомых родственных связей в базе знаний

4. Листинг разработанной базы знаний на языке Пролог

5. Примеры запросов к базе знаний и ее ответов

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 2.

Структура Пролог-программы

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

В секции domains объявляются любые нестандартные домены, используемые для аргументов предикатов. Домены в Прологе являются аналогами типов в других языках. Основными стандартными доменами Пролога являются:

char - символ, заключенный в одиночные кавычки (например, 'а');

integer – целое число;

real – вещественное число;

string - последовательность символов, заключенных в двойные кавычки (например, "нажмите ввод");

symbol - либо набор латинских букв, цифр и символов подчеркивания, в котором первый символ - прописная буква (например, n_fax); либо последовательность символов, содержащая пробелы или начинающаяся со строчной буквы, заключенная в кавычки (например, "Список СУБД").

file - символическое имя файла, которое начинается с прописной буквы.

Кроме стандартных доменов пользователь может использовать свои.

Для этого в области объявления доменов можно использовать следующие форматы:

а) ИмяТипаПеременной = СтандартныйДомен.

domains

fio = symbol

year, height = integer

б) ИмяСписка = ИмяТипаПеременной*, где ИмяСписка - область, состоящая из списков элементов типа ИмяТипаПеременной, которая может быть определена пользователем или иметь стандартный тип.

domains

number = integer*

letter = char*

в) ИмяСтруктуры = functor1(d11,…,d1n); functor2(d21,..., d2n);... functorm(dm1,...,dmq), где ИмяСтруктуры - область, которая состоит из составных объектов, описываемых указанием функтора и областей для всех компонентов. Например,

auto = car(symbol,integer),

packing = box(integer, integer, integer)

+ [3, стр10]

г) file = name1; name2;... namen используется, когда пользователю необходимо ссылаться на файлы по их символическим именам.

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

domains

name, firm, type = symbol

freq, vol = integer

device = processor(name,freq); disk(firm,vol); monitor(type)

computer = device*

В этом описании домен computer является списком элементов типа device, то есть каждый элемент этого списка может иметь структуру типа либо processor, либо disk, либо monitor, содержащих одну или две компоненты, каждая из которых имеет стандартный символьный или целый тип.

Все структурированные объекты можно представить графически в виде деревьев. Корнем дерева является функтор, а ветвями — компоненты. Если компонент представляет собой структуру, он становится поддеревом этого дерева, которое соответствует всему структурированному объекту.

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

predicates

predicateName₁ (domen₁₁, domen₁₂,..., domen_1m)

…

predicateName_n (domen_n1, domen_n2,..., domen_nk)

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

Если предикат один, то он называется однозначным (derministic), а если в базе знаний может быть несколько экземпляров данного предиката, то такой предикат называется неоднозначным (non-derministic), и это необходимо указать в описании предиката.

Пример описания предикатов:

predicates

nondeterm student (string, real)

start /* это однозначный предикат;

determ можно не писать */

nondeterm good_student (string)

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

predicates

nondeterm add(integer,integer,integer)

nondeterm add(real,real,real)

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

В секции clauses размещаются факты и правила, с которыми будет работать - Пролог, пытаясь разрешить цель программы.

Пример фактов, определяющих отношение, заданное предикатом student, может иметь вид:

clauses

student ("Петров", 4.5).

student ("Сидоров",3.75).

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

Заголовок:- Подцель1, Подцель2,..., ПодцельN.

где обозначение:- читается как "если", а Заголовок имеет такую же форму, как и факт. Тело правила - это список подцелей, разделенных запятыми. Запятая понимается как конъюнкция и читается как "и". Пример записи правила

good_student(Name):- student(Name, В), В > 4.

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

Практикум 2-1

:

Создайте базу знаний (БЗ), хранящую сведения о студентах (не менее 10) и их средних баллах. Напишите правило, определяющее «хороших» (по среднему баллу) студентов. Практически у каждого студента есть какое-то хобби (возможно, не одно). Добавьте факты с информацией о хобби в БЗ. Создайте запросы для ответов на следующие вопросы: 1. Какие хобби у «хороших» студентов? 2. Кто-нибудь увлекается фотографией? 3. Какие средние баллы у студентов, увлекающихся футболом?

 

Множество правил, заголовки которых содержат одинаковые имена предикатов и одинаковое количество аргументов, называются процедурой. На рис. 2.1 представлены правила, которые реализуют процедуру нахождения наибольшего из двух действительных чисел, определяемую предикатом вида max(number1, number2, max_number). Считается, что между этими правилами неявно присутствует соединительный союз "или".

Рис. 2.1. Нахождение максимального числа

Практикум 2-2

:	Создайте программу вычисления максимального и минимального из трех целых чисел.

 

В секции goal задается внутренняя цель программы. Цель может состоять из нескольких предикатов (из нескольких подцелей). Если внутренняя цель не используется, то в процессе работы есть возможность вводить в диалоговом окне внешнюю цель.

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

Стандартные предикаты

В систему Пролог включено более 200 встроенных стандартных предикатов и более дюжины стандартных доменов. В случае использования этих предикатов и доменов нет необходимости объявлять их в программе.

Ввод и вывод

С помощью встроенных предикатов ввода-вывода программа, взаимодействуя с пользователем, может принимать от него данные и печатать результаты. Рассмотрим простейшие предикаты ввода\ вывода.

Ввод данных.

readln(X) – для ввода строки

readint(X) – для ввода целых чисел

readchar(X) – для ввода символов

readreal(X) – для ввода действительных чисел

По умолчанию данные вводятся с клавиатуры терминала, ввод завершается нажатием клавиши “Enter”.

Для вывода используется предикат

write(T1,T2,…,Tn).

Он выводит значения T1,T2,…,Tn на текущее устройство вывода, по умолчанию, на экран. Предикат write(…) не допускает повторного согласования и выполняется лишь один раз. Переход на новую строку при печати данных обеспечивается встроенным предикатом nl, название которого образовано аббревиатурой (начальными буквами) слов «newline» новая строка. Как и write, предикат nl выполняется только один раз.

 

Перечень и назначение стандартных предикатов приведен в Приложении 1.

Рассмотрим пример программы, в которой используется обращение к стандартным предикатам (рис.2.2):

Рис. 2.2. Использование стандартных предикатов

В этой программе запрашивается Ваше имя, а затем оно выводится на экран.

Практикум 2-3

:

Добавьте в программу, представленную на рис.2.2 факты, хранящие пароли пользователей с параметрами (Имя, Пароль). Модифицируйте предикат hello (или создайте новый) - после ввода пользователем имени запросите пароль, если среди фактов будет обнаружено такое сочетание имени и пароля, то сообщить приветствие, а если нет – выдать сообщение: «Пользователь или пароль указан не верно. Повторить попытку (да или нет)?». Если пользователь ответил «да», то повторить запрос имени и пароль, если «нет», то закончить работу программы.

 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 3.

Использование предиката cut

Предикат отсечения[1] «cut» обозначается с помощью символа!. Он позволяет получить доступ только к части данных, устраняя дальнейшие поисковые действия. В общем виде можно записать, например:

R: – A,B,!, C.

Это означает, что если для целей А и В найдено хотя бы одно решение, то дальнейший перебор возможных вариантов значений А и В не нужен.

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

Существуют два основных случая применения отсечения.

· Если заранее известно, что определенные посылки никогда не приведут к осмысленным решениям (поиск решений в этом случае будет лишней тратой времени), Отсечение позволяет сделать программу быстрее и экономичнее. Такой прием называют зеленым отсечением.

· Если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей. Это - красное отсечение.

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

На рис. 3.3 приведена программа, составляющая все возможные пары мальчик+девочка.

Рис 3.3. Пример программы без отсечения

Практикум 3-2

:	1. Проверьте работу программы, приведенной на рис.3.3. 2. Проверьте, как изменятся результаты, если в предикат show вставлять предикат отсечения: Объясните каждый из получившихся результатов. Определите в каждом случае цвет отсечения

Отсечение - это мощный, но и опасный оператор Пролога: он многое позволяет, но делает программу более трудной для понимания.

 

Использование рекурсии

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

Рассмотрим преимущества использования рекурсии на примере.

Пусть имеются следующие факты о том, какая валюта котируется выше (рис.3.4):

Рис 3.4. Пример программы

Результатом запроса на рис.3.4 будет yes, потому что такой факт явно описан в программе.

Если же сделать запрос,

GOAL

doroge(евро, йена).

или

doroge (фунт, рубль).

 

То ответ будет отрицательный (no), поскольку такие факты отсутствуют.

Избежать противоречий здесь можно введением правила, в котором допустимо сравнение между собой не только двух, но и трех объектов:

doroge_3(X, Y):- doroge(X, Y). /* два объекта */

doroge_3(X, Y):- doroge(X, Z), doroge(Z, Y). /* три объекта */

Второе правило описывает правило транзитивности, если X>Z, и Z>Y, то делается вывод, что X>Y.

Однако цепочка взаимных сравнений может быть более длинной. Например, при четырех сравнениях потребуется конструкция:

doroge_4(X, Y):- doroge(X, M), doroge(M, K), doroge(K, Z), doroge(Z, Y).

Описывать такие длинные правила неудобно. Здесь выгоднее применить рекурсию, обратившись к правилу из самого этого правила:

val_doroge(X, Y):- doroge(X, Y).

val_doroge(X, Y):- doroge(X, Z), val_doroge(Z, Y).

 

Первое предложение в этой конструкции определяет момент прекращения рекурсивных вызовов, если существует такой факт.

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

Практикум 3-3

:	Проверьте, как работает программа c рекурсией (с фактами о том, какая валюта котируется выше, рис.3.4), получите ответы на вопросы – выбрать все валюты, которые котируется выше рубля, – выбрать все валюты, которые котируется ниже рубля.

 

Любая рекурсивная процедура должна включать в себя базис и шаг рекурсии.

Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения

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

База правил просматривается всегда сверху вниз. Сначала делается попытка выполнения нерекурсивной фразы (базиса). Если условие окончания рекурсии не указано, то правило может работать бесконечно.

Например:

write_string:- write(“*****”),nl, write_string.

будет бесконечно печатать звездочки на экране компьютера.

Рассмотрим применение рекурсии на примере вычисления факториала натурального числа N!=1*2*3*…*N. Рекурсивная математическая запись:

1!=1 N!=(N-1)!*N

На рис. 3.5 представлена программа вычисления факториала, однако эта программа не будет работать правильно, а будет вызывать бесконечный цикл и переполнение памяти. Это происходит потому, что в программе произошел выход в отрицательную часть целых чисел, что не было предусмотрено формулой, на которой была основана эта процедура.

 

Рис 3.5. Пример неправильной программы

 

Для исправления этой ошибки возможны два варианта

1. Можно проверить, что число, для которого применяется правило, больше единицы (рис. 3.6-а).

2. Добавить в первое предложение (в базис рекурсии) отсечение. При достижении истинности высказывания, предложения процедуры, расположенные ниже той, из которой оно было вызвано, не рассматриваются (рис.3.6-б)

а)

б)

Рис 3.6. Примеры исправления программы

Практикум 3-4

:	Проверьте, как работает программа вычисления факториала, добавив вывод промежуточных результатов с помощью предикатов write("N1=",N1) после вычисления N1 и write("N1=",N1," F1=",F1) после вычисления fact(N1,F1).

 

Программа, представленная на рис. 3.7. должна печатать на экране компьютера цифры от 1 до 10.

Рис 3.7. Программа печати чисел

Практикум 3-5

:	а) Проверьте, действительно ли программа, представленная на рис. 3.7 печатает числа от 1 до 10? Исправьте программу, чтобы она работала правильно. б) Создайте программу печати чисел в обратном порядке от 10 до 1.

Программа, представленная на рис. 3.8 печатает сумму всех цифр введенного с клавиатуры числа.

 

Рис 3.8. Программа вычисления суммы цифр целого числа

Использование предиката! в описании базиса рекурсии позволяет избежать здесь переполнения стека.

Практикум 3-6

:	а) Проверьте, действительно ли программа, представленная на рис. 3.8 правильно считает сумму цифр. б) Создайте программу перевода десятичного числа в двоичное. (Двоичное число можно представить как строку из 0 и 1)

 

Хвостовая рекурсия

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

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

Пример. На рис. 3.9. представлен пример использования хвостовой рекурсии для вычисления факториала.

Вычисления осуществляются с помощью дополнительного предиката, в который передаются исходные данные и начальные значения. В дополнительном предикате третий параметр – это натуральные числа 1, 2, …, N, а в четвертом последовательно вычисляются значения 1!, 2!, …, N!

Процесс останавливается, когда третий параметр достигнет значения N.

Рис 3.9. Программа вычисления N! с использованием хвостовой рекурсии

 

Практикум 3-7

:	С использованием хвостовой рекурсии вычислить Y=X^N

Самостоятельные задания

1. На рис. 3.10 представлен пример Пролог - программы. Какого цвета использовано отсечение – красное или зеленое?

Рис 3.10. Программа с использованием отсечения

2. Даны а,n. Вычислить S=a+a²+a³+…+aⁿ

3. Даны а,n. Вычислить S=a+a(a+1)+a(a+1)(a+2)+…+a(a+1)*…*(a+n)

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 4.

Понятие списков в Прологе

 

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

При записи список заключают в квадратные скобки, а элементы списка разделяют запятыми, например:

[1,2,3]

[1.1,1.2,3.6]

[“вчера”,”сегодня”,”завтра”]

Элементами в списке может быть что угодно, включая другие списки, но все элементы в списке должны принадлежать одному домену.