Car(maserati, green, 25000).

Car(corvette, black, 24000).

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 делает программу эффективнее, но она теряет прозрачность логической семантики, остаётся только процедурной, что отвечает выбранной стратегии просмотра дерева.