Динамическое отсечение

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

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

на предикаты, расположенные за символом !, и только в тех предложениях,

куда этот символ был помещен (в исходном тексте программы). При этом от-

сутствует возможность передачи отсечения в качестве аргумента в другой

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

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

невозможность отсечь поиск дальнейших решений подцели в предложении, не

отсекая при этом точки слежения с возвратом для последующих предложений

данного предиката.

В версии 2.0 Турбо Пролога введен механизм динамического отсечения,

который реализован при помощи двух стандартных предикатов getbacktrack и

cutbacktrack. Этот механизм позволяет решить обе указанные выше проблемы.

Предикат getbacktrack устанавливает текущий указатель в вершину стека то-

чек слежения с возвратом. В дальнейшем вы можете удалить все полученные

таким образом точки слежения с возвратом с помощью предиката

cutbacktrack.

Примеры

В данном разделе приведен ряд примеров, иллюстрирующих применение

этих двух предикатов.

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

сведения о конкретных людях и их доходе, а также о наличии у

них друзей.

database

person(symbol,income)

friends(symbol,symbol)

Если вы определите счастливого человека, как человека, у кото-

рого либо много друзей, либо много денег, то это можно записать

в виде следующих предложений:

happy_person(has_friends(P)):-person(P,_),friends(P,_).

happy_person(is_rich(P)):-person(P,Income),rich(Income).

Если человек имеет более чем одного друга, то первое предложе-

ние будет выдавать несколько решений. В данном случае вы можете

добавить еще один предикат have_friends(P,P), в котором будет

использоваться отсечение или, вместо этого, применить динами-

ческое отсечение

happy_person(has_friends(P)):-

person(P,_),

getbacktrack(BTOP),

friends(P,_),

cutbacktrack(BTOP).

Хотя предикат friends может выдавать несколько решений, эта

возможность отсекается с помощью вызова cutbacktrack. В даль-

нейшем, при неудачном завершении в предикате person будет вы-

полняться слежение с возвратом.

2. Наиболее полезное применение динамическое отсечение находит

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

в другой предикат, который выполняет отсечение по условию. Ука-

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

аргументов целого типа.

В качестве иллюстрации рассмотрим программу, которая выдает

числа до тех пор, пока не будет нажата какая-либо клавиша.

predicates

number(integer)

return_members(integer)

checkuser(integer)

clauses

number(O)

number(N):-number(N1),N=N1+1.

return_numbers(N):-getbacktrack(BTOP),number(N),

checkuser(BTOP).

checkuser(BTOP):-keypressed,cutbacktrack(BTOP).

checkuser(_).

В основном динамическое отсечение применяется при реализации

экспертных систем, когда необходимо применять отсечение. Это

демонстрируется в Машине Логического Вывода (Prolog Inference

Engine) в разделе "Метапрограммирование".

Компилятор не распознает предикат cutbacktrack, когда выполняет

проход, связанный с анализом предложений на детерминизм. Это

означает, что вы можете получить предупреждающее сообщение

Non-deterministic clause при использовании директивы

check_determ, даже если вы используете cutbacktrack.