Структура программы на языке Prolog

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

СТРУКТУРА ПРОГРАММЫ НА ЯЗЫКЕ PROLOG

 

Обычно программа Visual Prolog включает три или четыре основных раздела. Это раздел выражений clauses, раздел описания предикатов predicates, раздел доменов domains и раздел цели goal.

Раздел clauses

В разделе выражений clauses программист размещает все включаемые в программу факты и правила.

Выражения, относящиеся к определенному предикату, должны размещаться в разделе clauses вместе. Последовательность определяющих предикат выражений называется ПРОЦЕДУРОЙ.

Фактом называют отношение или свойство, о котором известно, что оно имеет значение истина. Например:

Pred1(1).

pred2(3,"Start").

pred3(computer(ibm,ps_2)).

Правилом же является конструкция, содержащая некоторые условия:

pred4(Arg1,Arg2,...,ArgN) if

pred5(...) and pred6(...) and... predN(...).

или:

pred4(Arg1,Arg2,...,ArgN):- pred5(...), pred6(...),..., predN(...).

где «:-» соответствует «if», а «,» соответствует «and».

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

Раздел predicates

Если программист определяет в разделе clauses свой собственный предикат, то он ДОЛЖЕН объявить его в разделе predicates. В противном случае Visual Prolog не будет знать, о чем идет речь. Когда объявляется предикат, Прологу сообщается о том, к каким доменам принадлежат аргументы этого предиката.

Предикаты определяются фактами и правилами. В разделе predicates просто перечисляется каждый предикат с указанием доменов аргументов.

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

Общий вид определения предиката:

pred(dom1,dom2,...,domN)

pred – имя предиката (имя отношения) (формально оно относится к типу symbol), dom – тип данных конкретного аргумента (всего аргументов в предикате N – это число аргументов предиката, его называют арностью предиката (от термина arity, и иногда пишут pred/N).

Например:

Predicates

Run

Sum(real,real,real).

Parent(string,string).

Student(string).

В этом же разделе можно задать тип детерминизма предиката, вставляя перед объявлением предиката ключевые слова procedure, determ, failure или erroneous. С другой стороны, можно определить недетерминированный предикат – вставляя перед его объявлением ключевые слова nondeterm или multy. Если предикат объявляется как детерминированный, то компилятор выдает предупреждение или ошибку, если найдет недетерминированные предложения для этого предиката. Режимом детерминизма для предикатов по умолчанию является determ.

Раздел domains

Домены в Прологе подобны типам в Паскале. Они дают возможность присваивать различным видам информации, которая в противном случае выглядела бы одинаково, отличные имена. В программе Visual Prolog объекты в отношении (аргументы предиката) принадлежат доменам; это могут быть домены стандартные или специальные, определяемые программистами.

Раздел domains служит двум очень важным целям. Во-первых, можно определить для доменов осмысленные имена, причем даже в том случае, если внутренне они совпадают с именами уже существующих доменов. Во-вторых, объявления специальных доменов используются для объявления структур данных, которые стандартными доменами не определяются.

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

Например:

Domains

selector = integer % тип selector для целых чисел

list_str = string* % список со строковыми данными

computer = name(string,list_sel,selector,integer) % описание структуры

Раздел goal

В Visual Prolog предусмотрен раздел goal, который должен включаться в программу.

Важно отметить то, что содержание раздела goal аналогично правилу. Это попросту список подцелей. Но между разделом goal и правилом есть два отличия:

1. После ключевого слова goal не следует знак:- (если).

2. При запуске программы на выполнение Visual Prolog отрабатывает цель автоматически.

Visual Prolog как бы вызывает цель (обращается к разделу goal), а программа выполняется, пытаясь удовлетворить тело целевого правила. Если достигаются все подцели раздела goal, то программа успешно завершается. Если же в процессе выполнения программы какая-либо подцель не достигается, то и программа заканчивает работу неудачно. Хотя, если смотреть на программу извне, разница между этими двумя случаями не обязательно должна быть видна; программа просто завершается.

Другие разделы программы

Раздел facts

Программа на Visual Prolog представляет собой совокупность фактов и правил. Иногда в процессе выполнения программы может возникнуть потребность видоизменения (модификации, удаления или добавления) некоторых фактов, с которыми работает программа. В таком случае факты образуют ДИНАМИЧЕСКУЮ или ВНУТРЕННЮЮ базу данных; она может изменяться в процессе выполнения программы. В Visual Prolog для объявления в программе фактов, которые должны стать частью динамической (или изменяющейся) базы данных, предусмотрен специальный раздел - facts.

Такой раздел базы данных объявляется с помощью ключевого слова facts, куда включаются объявления фактов, предназначенных для организации динамической базы данных (БД). В Visual Prolog имеется несколько встроенных предикатов, существенно облегчающих использование динамической БД.

Раздел constants

В программе на Visual Prolog можно объявить и использовать символические константы. Раздел объявления констант начинается ключевым словом constants, после которого следуют сами объявления с соблюдением следующего синтаксиса:

<Идентификатор> = <Макроопределение>

<Идентификатор> – это имя константы, а <Макроопределение> – это то, что этому имени соответствует. Каждое <Макроопределение> заканчивается символом новой строки, так что в одной строке может размещаться только одно описание константы. На объявленные таким образом константы можно затем ссылаться в программе.

Рассмотрим следующий пример:

Constants

нуль = 0

один = 1

два = 2

сотня = (10*(10-1)+10)

пи = 3.141592653

еда = мясо

красный = 4

Перед компиляцией программы Visual Prolog заменит каждую константу действительной строкой, которую она представляет.

На использование констант накладываются следующие ограничения:

- определение константы не может ссылаться само на себя;

- в программе может быть несколько разделов constants, но константы должны объявляться до их использования;

- идентификаторы констант являются глобальными и могут объявляться только один раз. Несколько объявлений одного и того же идентификатора приведут к выдаче сообщения Constant identifier can only be declared once (Идентификатор константы может быть объявлен только один раз).

Разделы global

Visual Prolog позволяет объявить в программе некоторые домены, предикаты и выражения ГЛОБАЛЬНЫМИ (в отличие от ЛОКАЛЬНЫХ). Это можно сделать, сформировав в самом начале программы отдельные разделы globaldomains, globalpredicates и globalfacts.

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

 

1. Наберите в окне редактора следующую программу:

Domains

num1, num2, rez = real

Predicates

Sum(num1,num2,rez)

Clauses

sum(Num1,Num2,Rez):-Rez=Num1+Num2.

Как видно, данная программа предлагает найти сумму двух чисел. Входящими параметрами здесь являются Num1, Num2, а выходящим – Rez.

Добавьте в программу правило нахождения суммы трёх чисел – sum(Num1,Num2,Num3,Rez). Не забудьте при этом объявить новый предикат.

 

2. Опишите на Прологе свое дерево родственных отношений на примере рис.1:

Маша Витя

Петя Света Таня Ваня

Юра Катя

 

Рис.1. Дерево родственных отношений.

 

Факты должны быть:

parent/2 (т.е. 2-й арности)

man/1

woman/1

Добавьте правило:

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какова структура Пролог-программ?
2. Какие разделы программ относятся к основным?
3. Что содержится в разделе DOMAINS?
4. Что содержится в разделе PREDICATES?
5. Что такое «арность»?
6. Для чего предназначен раздел CLAUSES?
7. Опишите раздел GOAL.
8. Перечислите дополнительные разделы программ. Дайте их краткую характеристику.

 

 

ЛАБОРАТОРНАЯ РАБОТА №2

Тема: Создание программ на логическом языке в среде Visual Prolog.

Цель: Научиться писать простейшие программы на языке Пролог.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

ОПИСАНИЕ БАЗЫ ЗНАНИЙ

 

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

Описание фактов – достаточно простая задача, так как факт определяет свойство объекта или отношение (связь) между объектами. Любое имя, используемое в Прологе, должно состоять не более чем из 250 символов, первый из которых при этом должен обязательно быть строчной буквой (кроме имён переменных) желательно латинского алфавита (от a до z). Пробелы в записи имени недопустимы, однако можно использовать подчерк (_) в качестве разделителя компонент.

Наибольшую трудность представляет описание правил. Правила используются в тех случаях, если необходимо показать, что некоторый факт зависит от других фактов (условий). Правила обладают большей общностью, чем факты. Это объясняется тем, что в правилах обычно содержаться переменные. Важно помнить, что переменная используется для обозначения не одного конкретного объекта, а различных объектов. Область действия переменной – одно правило. Кроме того, переменная обозначает один и тот же объект по всему правилу. Вот почему в процессе логического вывода все вхождения одной переменной в правиле заменяются одним и тем же значением. Имена переменных должны задаваться с заглавной буквы или с символа подчёркивания «_». Существует и особый вид переменной, которая называется анонимной и обозначается символом «_» (и только!). Она используется в качестве аргумента предиката в случае, когда конкретное значение переменной несущественно. Значения таких переменных не выводятся на печать. Следует заметить, что если в одном правиле используется несколько анонимных переменных, то все они разные.

Например, если нас интересует, является ли кто-либо мамой, но нам не нужно знать их детей (см. лабораторную работу №1), то нужно задать цель:

mother(Х,_).

Пролог при этом выдаст имена всех матерей, которые найдёт в базе данных согласно правилу:

mother(X,Y):-parent(X,Y),woman(X).

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

ФОРМУЛИРОВКА ЦЕЛЕЙ

 

Существует два вида целей:

Ø подтвердить справедливость факта. Ответом системы на такие запросы выступает логическое Yes или No. В естественном языке такие цели соответствуют конструкции вопроса типа: «Действительно ли, что …?»;

Ø перечислить все значения переменных, указанных в запросе. В естественном языке аналогом этих целей выступают вопросы, начинающиеся со слов Что? Кто? Сколько? Где? и т.д., ответы на которые требуют уточнения кое-каких деталей касательно объекта, указанного в вопросе.

При формулировке правил и целей допускается использование отрицания, конъюнкции, дизъюнкции, а также операций сравнения (<,<=,>,>=,<>,=).

 

МОДЕЛИРОВАНИЕ РАССУЖДЕНИЙ

 

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

Пусть программа на Прологе содержит следующие утверждения (факты и правила) (фразы, заключенные в «/*..….*/», воспринимаются Прологом как коментарий):

знает(мария,хор). /* Мария знает хор*/

(1) знает(мария,сольфеджио). /* Мария знает сольфеджио*/

(2) знает(мария,информатика). /* Мария знает информатику*/

(3) знает(мария,алгебра). /* Мария знает алгебру*/

знает(мария,геометрия). /* Мария знает геометрию*/

/*Иван знает те же курсы, что и Мария, при условии, что эти курсы изучаются в университете */

знает(иван,X):- знает(мария,X),университет_курс(X).

университет_курс(информатика). /*информатика изучается в университете*/

университет_курс(алгебра). /*алгебра изучается в университете*/

университет_курс(геометрия). /*геометрия изучается в университете*/

музыка_курс(сольфеджио). /*сольфеджио изучается в музучилище*/

музыка_курс(хор). /*хор изучается в музучилище*/

и цель:

знает(иван,X). /*какие курсы знает Иван?*/

Пролог ищет факты и головы правил, сопоставимые с целью. Два факта сопоставимы (или соответствуют друг другу), если выполняются следующие три условия сопоставления фактов:

1. имена отношений одинаковы (побуквенное совпадение);

2. отношения имеют равное количество аргументов;

3. аргументы, расположенные в одинаковых позициях, сопоставимы.

Правила сопоставления аргументов:

3.1. Имена конкретных объектов сопоставимы, если они совпадают;

3.2. Переменная сопоставима с именем конкретного объекта;

3.3. Переменная сопоставима с другой переменной.

Пролог просматривает утверждения в том порядке, в каком они вводились в БЗ. Поэтому сначала сравниваются цель

знает(иван,Х)

и факт

знает(мария,хор).

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

знает(мария,Х).

Это новая подцель, поэтому Пролог снова начинает просмотр БЗ с первого факта для отношения «знает» и находит

знает(мария,хор).

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

Вторая подцель есть:

университет_курс(Х),

так как переменная Х имеет значение «хор». Все сопоставления этой подцели с фактами БЗ неуспешны. Поэтому первая попытка доказать цель завершилась неудачей.

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

знает(мария,сольфеджио)

и устанавливает указатель отката (2) на следующий факт для предиката «знает». Переменная Х принимает значение «сольфеджио».

Подцель

университет_курс(солфеджио)

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

знает(мария,информатика),

Х получает значение «информатика», а указатель отката устанавливается в точку (3). Вторая подцель принимает вид:

университет_курс(информатика).

Успешное сопоставление этой подцели доказывает цель. Следовательно, ответ на поставленный вопрос формулируется так: «Иван знает информатику». Цель успешно доказана, поэтому переменная Х становится свободной и может быть вновь означена при поиске других решений.

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

 

1. Описать БЗ «Библиотека», содержащую факты:

Ø О читателях – студентах:

Фамилия	Курс	Фамилия	Курс
Иванов		Анисимов
Петров		Тихонов
Сидоров		Травкин
Ковалёв		Жданов
Антонов		Галкин

Ø О книгах, невозвращённых читателями в срок

Название книги	Номер книги	Год издания	Фамилия студента
Физика			Иванов
Химия			Петров
Физика			Антонов
Химия			Тихонов
Химия			Галкин
Математика			Галкин

 

Ø Добавить к БЗ правило, позволяющее определить:

1. какие книги (название, номер) не возвращены студентами заданного курса;
2. кто из студентов не вернул книги, изданные до 1990 года;
3. кто из студентов не вернул книги заданной тематики (например, по химии).

 

Ø Сформулировать цели:

1. перечислить фамилии студентов 3-го курса, которые пользуются услугами библиотеки;

2. перечислить фамилии студентов 2-го и 4-го курсов, которые пользуются услугами библиотеки;

3. какие книги (название и номер) не возвращены студентами 2-го курса?

4. Кто из студентов не вернул книги, изданные до 1990 года?

5. Кто из студентов не вернул книги по физике?

 

2. Описать БЗ «Компьютеры».

Факты базы знаний содержат следующую информацию.

- какие фирмы изготавливают вычислительные системы и их составные части:

Фирмы-изготовители	Название изделия
Mem1, Mem2	Внутренняя память
Disk1, Disk2	Диски
Pr1	Процессоры
Comp1, Comp2	Компьютеры
Net1, Net2	Вычислительные сети

 

- услугами каких фирм-поставщиков пользуются фирмы-изготовители. (Одна и та же фирма может быть изготовителем и поставщиком, например, Comp1.) (рис.2)

Определить отношение «конкурент». Две фирмы конкурируют, если они выпускают одинаковые устройства.

Определить отношение «использует изделие», которое устанавливает связь между фирмами-поставщиками и фирмами-изготовителями. Например, фирма Comp1 использует изделия от фирм Mem1, Disk1, Disk2, Pr1, а фирма Net1 – от Mem1, Disk1, Disk2, Pr1, Comp1 (рис.2).

 

 

Disk1 Disk2

 

 

Comp1 Mem1 Comp2 Mem2

 

Pr1

 

 

Net1 Net2

 

Рис.1. Взаимодействие фирм-поставщиков и фирм-изготовителей.

 

Получить ответы на следующие вопросы:

1. Какие фирмы производят внутреннюю память?

2. Изделиями каких фирм пользуется фирма Net2?

3. Какие фирмы конкурируют между собой?

4. Какие фирмы по изготовлению компьютеров конкурируют между собой?

5. Диски каких фирм использует фирма Comp1?

6. Какие фирмы поставляют изделия для фирмы Comp2?

7. Внутреннюю память каких фирм использует фирма Net2?

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

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

Таблица 1.

№ варианта	Наименование предметной области	Количество объектов	Количество учитываемых параметров
	«Поиск жилья» (для фирмы по торговле недвижимостью)
	«Поиск преступника» (для органов внутренних дел)
	«Выбор места для отдыха» (для бюро путешествий)
	«Выбор подарка» (для супермаркета)
	«Поиск работы» (для службы занятости)
	«Подбор книг» (для библиотеки)
	«Выбор автомобиля»
	«Выбор компьютера»
	«Поиск преступника»
	«Выбор подарка»
	«Выбор места для проведения отпуска»
	«Выбор жилья»
	«Выбор авиакомпании для путешествия по заданному маршруту»
	«Выбор загородного дома»
	«Выбор подарка»
	«Поиск преступника»
	«Выбор автомобиля»
	«Выбор компьютера»
	«Подбор книг» (для библиотеки)
	«Выбор загородного дома»
	«Поиск работы»
	«Отбор кинофильма для предварительного показа на кинофестивале»
	«Выбор места для отдыха»
	«Выбор загородного дома»
	«Выбор облицовочных материалов для ремонта квартиры»

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что входит в базу знаний Пролога?
2. Что описывают факты в Прологе?
3. Как формируются правила на Прологе?
4. Как задаются имена в Прологе?
5. Объясните суть переменных в Прологе.
6. Что такое «анонимная переменная»?
7. Как классифицируются в Прологе вопросы в зависимости от получаемого результата?
8. Каковы условия сопоставимости фактов в Прологе?
9. Каковы правила сопоставления?
10. Объясните принцип отката в Прологе.

 

 

ЛАБОРАТОРНАЯ РАБОТА №3

Тема: Контроль механизма бэктрекинга при поиске решений.

Цель: Научиться использовать встроенные предикаты fail,cut и not.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

В Прологе существуют два специальных предиката, которые позволяют контролировать механизм бэктрекинга: предикат fail, заставляющий запускать механизм бэктрекинга, и cut (обозначается с помощью символа “!”), предназначенный для отмены бэктрекинга.

Domains

name = symbol

Predicates

Father(name, name)

Everybody

Clauses

Father(leonard, katherine).

Father(carl, jason).

Father(carl, marilyn).

Everybody:-

Father(X, Y),

write(X, " is ", Y, "'s father\n"),

Fail.

Goal

Everybody.

После запуска программы, система попытается удовлетворить все цели, находящиеся в разделе goal. Таким образом, в нашей базе знаний будет организован поиск фактов, соответствующих предикату everybody, либо правил, голова которых сопоставима с данным предикатом.

Заметим, что не имеет смысла использовать в теле правила подцель после fail. Учитывая тот факт, что значением предиката fail выступает «ложь», то нет путей, которые смогли бы удовлетворить подцель, находящуюся после fail.

 

1. ОТМЕНА БЭКТРЕКИНГА. ПРЕДИКАТ cut

Предикат cut генерирует значение «истина», что означает успех, и обозначается «!». Он размещается в теле правила как подцель. Когда обработка подцелей достигает cut, он всегда является успешным, а поэтому вызывается следующая за ним подцель. Из-за того, что cut был пройден, невозможно провести бэктрекинг подцелей, которые были расположены перед cut в обрабатываемом предложении, и поэтому невозможно перейти к другим вариантам, соответствующим текущему предикату.

Существует два основных правила использования предиката cut:

1. Если известно заранее, что полный перебор вариантов никогда не будет способствовать рациональному поиску решения, то использование cut («зелёное» отсечение) останавливает просмотр альтернативных значений.

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

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

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

- если х<10, то у=10;

- если 10<=х и х<20, то у=20;

- если 20<=х, то у=30.

На Прологе её можно выразить программой:

Predicates

F(integer,integer).

Clauses

f(X,10):- X < 10.

f(X,20):- X >= 10, X < 20.

f(X,30):- X >= 20.

Проанализируем, что будет делать программа, если задать вопрос:

Цель: f(5,Y), Y > 20.

При обработке первой цели f(5,Y), Y примет значение 10, поэтому другая подцель станет 10>20. она завершается неудачей. Однако очевидно, что и весь список подцелей, который будет проверяться благодаря бэктрекингу, тоже будет завершаться неудачей.

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

Predicates

F(integer,integer).

Clauses

f(X,10):- X < 10,!.

f(X,20):- X >= 10, X < 20,!.

f(X,30):- X >= 20.

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

Цель: f(22,Y),

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

Predicates

F(integer,integer).

Clauses

f(X,10):- X < 10,!.

f(X,20):- X < 20,!.

F(X,30).

Предикат cut по-разному воздействует на сложный вопрос и на множество фраз. Рассмотрим случай, когда предикат отсечения является одной из подцелей составного вопроса:

цель: a(X),b(Y),!,c(X,Y,Z).

При исполнении этого типа запроса Пролог-система пройдет через предикат cut только в том случае, когда подцели a(X) и b(Y) будут удовлетворены. После того, как подцель cut будет выполнена, система не сможет вернуться назад для повторного просмотра подцелей «а» и «b», если подцель «с» не удовлетвориться при текущих значениях X и Y.

Приведём ещё один пример использования cut:

Predicates

buy_car(symbol, symbol)

Car(symbol, symbol,integer)

Colors(symbol, symbol)

Clauses

buy_car(Model, Color):- car(Model, Color, Price),

colors(Color, sexy),!,

Price < 25000.

Car(corvette, red, 26000).

Car(porsche, red, 24000).

Colors(red, sexy).

Colors(black, mean).

Colors(green,preppy).

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

Для пояснения работы предиката cut вернёмся к процессу управления выводом в Прологе. Пусть Пролог-программа выглядит следующим образом:

Р: - a,b.

P: - c,d.

Эту программу, используя понятие процедуры, можно прочитать так. При выполнении процедуры р выполняются процедуры a и b. Если они завершаются успешно, тогда и процедура р считается успешно завершённой. В случае, если это не так, выполняются процедуры c и d. Иначе процедура р завершается неуспехом.

Такой алгоритм обработки можно реализовать на дереве типа И/ИЛИ (рис.1), где /\ обозначает «ИЛИ», а A означает узел типа «И»:

Р

 

а b c d

Рис.1 Иллюстрация дерева типа «И/ИЛИ»

Вершина типа «И» будет успешной только в том случае, когда её вершины-потомки успешны. Вершина типа «ИЛИ» будет успешной тогда, когда хотя бы одна из её вершин- потомков успешна.

Согласно со стратегией поиска в глубину, которая используется в Прологе, проводиться последовательный перебор дерева «И/ИЛИ» сверху-вниз, слева-направо. Это соответствует отделению самой левой подцели запроса и выполнению правил программы сверху-вниз.

Если при просмотре дерева какой-то из потомков вершины «ИЛИ» является успешным, то обработка других вершин-потомков (поддерева, которое находится правее) приостанавливается и считается, что эта вершина типа «ИЛИ» стала успешной.

Если какая-нибудь из вершин-потомков вершины типа «И» становится неуспешной, то и обработка других вершин-потомков завершается неуспешно.

Следует отметить, что обработка вершины «ИЛИ» не завершается, а только приостанавливается. Это связано с тем, что со временем возможно повторное обращение к этой вершине, и тогда ветви, которые не анализировались, могут снова привести к успеху в этой вершине (бэктрекинг).

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

Одним из способов устранения указанного недостатка является использование предиката cut.

Рассмотрим программу:

а(x): - b(x),!, c(x).

A(x): - d(x).

b(c).

B(f).

C(e).

C(f).

D(g).

Это типичное «красное» отсечение.

На запрос а(Z) программа даст только один ответ – Z=e, так как она не будет возвращаться к вариантам, возникшим до обращения к cut (при обработке подцелей a(Z) и b(Z)).

Если же извлечь предикат cut из первого правила и создать запрос a(Z), то получим три ответа Z=e, Z=f, Z=g.

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

Like(wanja,X):-game(X).

Однако необходимо исключить баскетбол. Это можно сделать, воспользовавшись иной формулировкой:

Если Х – баскетбол, тогда „Ваня любит Х” не будет истиной, иначе, если Х – игра, то „Ваня любит Х”.

Для реализации этого на Прологе воспользуемся предикатом fail, который всегда завершается неуспешно и при этом влечёт неуспешное завершение и той фразы, являющейся для него родительской.

like(wanja, X):- basketball(X),!,fail.

Like(wanja, X):- game(X).

Тут отсечение отбросит рассмотрение другого правила, если игра – баскетбол, а fail вызовет неуспех.

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

not(P):- P,!, fail;

True.

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

Тогда пример можно переписать следующим образом:

Like(wahja,X):- game(X),

Not(basketball(X))

Важно отметить: предикат not выполняется успешно, когда подцель не является истиной, т.е. тогда, когда ассоциированная с ним подцель не может дать истину.

Следующая программа показывает использование предиката not.

Domains

name = symbol

gpa = real

 

Predicates

honor_student(name)

student(name, gpa)

Probation(name)

 

Clauses

honor_student(Name):-

Student(Name, GPA),

GPA>=3.5,

Not(probation(Name)).

student("Betty Blue", 3.5).

student("David Smith", 2.0).

student("John Johnson", 3.7).

probation("Betty Blue").

probation("David Smith").

 

На запрос honor_student(Name) она выдаст список студентов, средний балл которых больше или равен 3,5 за исключением студентов Betty Blue и David Smith, которые проходят практику.

Цель: not(dog(baks)),

она возможно ответит „да”. Однако этот ответ нельзя рассматривать как утверждение о том, что „Бакс не собака”. Просто системе не достаточно информации для подтверждения высказывания „Бакс - собака”. Такой подход берёт своё начало от предположения о замкнутости мира. Согласно данному предположению мир замкнут в том смысле, что всё существующее в нем либо указано в программе, либо может быть выведено из неё. И в другом случае, когда чего-то нет в программе (или не может быть выведено), то оно является ложным, и следовательно будет истинным его отрицание.

Мы же традиционно не считаем мир замкнутым: если в программе явно не указано, что dog(baks), то это не означает, что мы хотим сказать: Бакс не собака.

Приведём ещё один пример осторожного применения not:

Predicates

R(symbol)