Материал: Волченков Логическое программирование язык пролог 2015

Берём первый по списку хороший фильм, например «Амаркорд» Феллини. После 2-го шага логического вывода получим

?– посмотрю(Амаркорд).

После 3-го шага логического вывода (после применения второго из приведённых выше правил) получим

?– нравится(A, Амаркорд), в_программе( Амаркорд, B).

Допустим, фильм «Амаркорд» нравится всем моим друзьям, но не демонстрируется ни в одном московском кинотеатре. Пролог по возврату будет делать множество лишних шагов – как бы обзванивать одного за другим всех моих друзей, чтобы после очередного звонка каждый раз заново безуспешно просматривать большой список кинотеатров.

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

посмотрю(X) :– в_программе(X, B), нравится(A, X).

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

А правильное решение заключается в том, чтобы поместить предикат «отсечения» между указанными подцелями:

посмотрю(X) :– нравится(A, X), !, в_программе(X, B).

Если фильм нравится хотя бы одному моему другу, то «отсечение» заблокирует возвраты к «записной книжке» и, если фильм нигде не демонстрируется, то сразу, без возвратов, будет взят следующий факт из «энциклопедического» списка хороший_фильм(X). И снова Пролог начнёт «звонить моим друзьям». Очевидно, что предикат отсечения обеспечил существенное уменьшение числа бесполезных просмотров базы данных.

Ещё один предикат управления – это заведомо невыполнимый предикат fail. Его используют для создания «искусственного тупи-

46

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

К предикатам управления следует отнести также предикат call/1. Его аргументом является переменная, значением которой является цель – предикат. Предикат call отправляет свой аргумент на выполнение, а выполнимость его аргумента означает выполнимость и самого предиката call. Данный предикат необходим, так как переменную в качестве подцели утверждения использовать нельзя.

Пример 3.2. Все три перечисленных выше предиката управления можно использовать в определении предиката not/1 – логического отрицания (реально, – это встроенный предикат):

not(P) :– call(P), !, fail. not(P).

Пусть в базе данных есть всего два факта о «хороших фильмах»:

хороший_фильм(КрестныйОтец). хороший_фильм(Матрица).

Рассмотрим запрос:

?– not(хороший_фильм(Матрица)).

Сработает 1-е правило определения. После успешного вызова подцели call(P) сработает «отсечение» (!) и «тупик» (fail). Возврат к цели not(P) – использованию 2-го правила определения – будет заблокирован. Ответ на запрос отрицательный.

Рассмотрим запрос:

? – not(хороший_фильм(ФоррестГамп)).

После безуспешного вызова подцели call(P) до «отсечения» дело не дойдёт, поэтому оно не будет выполнено. Возврат к цели not(P) – использованию 2-го правила определения – не будет заблокирован. Ответ на запрос будет положительным. Хорошо ли это

– по большому счёту? Ох уж эти системы с ограниченным миром! Ещё один пример использования предиката «отсечения» – дос-

тижение эксклюзивности при применении альтернативных правил.

47

Пример 3.3. Рассмотрим следующую программу:

Код 3.1

pension :– write(’Сколько Вам лет?’), nl, read(X), answer(X). answer(X) :– write(’Вы мужчина (м) или женщина (ж)?’), nl,

read(Y), answer(X, Y). answer(X, Y) :– Y == ж, условие_ж(X). answer(X, Y) :– Y == м, условие_м(X). усл_ж(X) :- X >= 55,

write(’Вы, сударыня, уже пенсионерка.’), nl.

усл_ж(X) :- X < 55,

write(’Вы, девушка, ещё не пенсионерка.’), nl. усл_м(X) :- X >= 60, write(’Вы, сударь, уже пенсионер.’), nl.

усл_м(X) :- X < 60, write(’Вы, юноша, ещё не пенсионер.’), nl.

Программа работает следующим образом («фотография» консоли):

| ?- pension.

Сколько Вам лет? |: 57.

Вы мужчина (м) или женщина (ж)?

|: ж.

Вы, сударыня, уже пенсионерка. yes

В этой программе делается лишняя работа. В 4-м правиле проверяется, мужчина ли пользователь, хотя невыполнение предыдущего правила говорит о том, что он не женщина. В 6-м и 8-м правилах проверяется, не меньше ли значение переменной X заданных чисел, хотя невыполнение предыдущих правил (5-го и 7-го) делает излишней эту проверку.

Как избавиться от этих проверок? Просто отбросить их нельзя, так как процедура pension может вызываться внутри другой проце-

дуры, в которой может возникнуть «внешний» возврат. Тогда по возврату может ошибочно сработать 4-е правило вместо 3-го, хотя пользователь – женщина. И может также ошибочно сработать 6-е правило вместо 5-го или 8-е правило вместо 7-го.

Решение этой проблемы во включении в правую часть указанных правил отсечения:

48

answer(X, Y) :– Y == ж, !, условие_ж(X). answer(X, Y) :– !, условие_м(X).

усл_ж(X) :- X >= 55, !, write(’Вы, сударыня, уже пенсионерка.’), nl.

усл_ж(X) :- !, write(’Вы, девушка, ещё не пенсионерка.’), nl. усл_м(X) :- X >= 60, !, write(’Вы, сударь, уже пенсионер.’), nl. усл_м(X) :- !, write(’Вы, юноша, ещё не пенсионер.’), nl.

Эксклюзивность каждого из этих правил соблюдена! И ещё одна область применения отсечения.

Предикат отсечения позволяет реализовать характерные для традиционных языков программирования условные конструкции (if then else), а также циклические конструкции (например, циклы с условием).

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

p :– a1, !, b1. p :– a2, !, b2.

…

p :– an-1, !, bn-1. p :– bn.

Эта программа реализует функцию на языке Бейсик:

Function p(…) As Boolean p = False

If a1 Then

p = b1 ElseIf a2 Then

p = b2

…

ElseIf an-1 Then

p = bn-1 Else

p = bn End If

End Function

49

Программирование повторений

Реализовать циклы (повторения) в Прологе можно разными способами. Рассмотрим четыре из них.

Метод обхода (без возвратов)

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

Пример 3.4. Печатаются «в столбик» все элементы списка:

выдать_по_очереди([]).

выдать_по_очереди([H|T]) :– write(H), nl, выдать_по_очереди(T).

Недостаток метода: рекурсивные вызовы «забивают» так называемый «резолюционный» стек; его очищали бы возвраты, но здесь их нет.

Метод поиска (возвратный метод)

Элементы какого-нибудь множества (для его представления можно использовать список) выбираются с помощью возвратной процедуры, например с помощью предиката member/2, о которой будет идти речь в следующей лекции. Над выбранным элементом производится какое-нибудь действие, после чего реализуется «искусственный» возврат с помощью предиката fail.

Пример 3.5. Печатаются «в столбик» все элементы списка:

выдать_по_очереди(List) :– member(X, List), write(X), nl, fail.

выдать_по_очереди(_).

Достоинство метода: «резолюционный» стек очищается с помощью «искусственных» возвратов.

CAF-метод (метод «cut and fail»)

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

50