Лаб. Работа 3 использование отсечения в пролог-программах

1. Цель работы: приобретение практических навыков использования отсечения в программах на Турбо-Прологе.

2. Краткие справочные данные.

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

Отсечение реализуется следующим образом: после согласования целевого утверждения, стоящего перед отсечением, все предложения с тем же предикатом, расположенные после отсечения, не рассматриваются.

Можно выделить три основные случая использования отсечения:

1. для устранения бесконечного цикла;

Пример: вычисление суммы 1 + 2 + … + N.

сумма( 1, 1 ) :- !.

сумма( N, R ) :- N1=N-1, сумма( N1, R1 ), R = R1 + N.

Если граничное условие будет записано в виде

сумма( 1, 1 ).

без отсечения, то сопоставление головы правила с запросом в разделе goal (или в окне Dialog) будет происходить успешно и при N <= 0, т.е. делается попытка доказать цель сумма( 0, R ), что в свою очередь приводит к цели сумма( -1, R ) и т.д., т.е. образуется бесконечный цикл.

2. при программировании взаимоисключающих утверждений;

Пример: нахождение большего числа среди двух чисел X и Y можно запрограммировать в виде отношения

max( X, Y, Max ), где Max = X, если X >= Y и Max = Y, если Y > X.

Это соответствует двум предложениям программы:

max( X, Y, X ) :- X >= Y.

max( X, Y, Y ) :- X < Y.

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

max( X, Y, X ) :- X >= Y, !.

max( _, Y, Y ).

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

Пример: присвоение какому-либо объекту категории в зависимости от величины заданного критерия в соответствии с таблицей

Критерий	Категория
свыше 80 до 100	А
свыше 40 до 80	В
от 0 до 40	С

Возможный вариант программы:

категория( Кр, _ ) :- Кр > 100, !, fail; Кр < 0, !, fail.

категория( Кр, ‘A’) :- Кр > 80, !.

категория( Кр, ‘B’) :- Кр > 40, !.

категория( _, ‘C’).

При запросе категория( 200, Х ) произойдет сопоставление запроса с головой первого утверждения. Цель Кр > 100 будет достигнута. Затем будет доказана цель-отсечение. Но когда встретится предикат fail, который всегда вызывает состояние неудачи, то стоящий перед ним предикат отсечения остановит работу механизма возврата и в результате ответом на запрос будет No Solution (Нет решения).

Комбинация !, fail вводит возникновение неудачи.