2. Использование накапливающего параметра

Пример: реверс списка

1. исходный список, 2 – результирующий список

Базовый случай: если список пуст, то результат – пустой список.

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

rev([],[]).

rev([X|Xs],Y):-

rev(Xs,Z),

append(Z,[X]).

Алгоритм можно оптимизировать, добавив накапливающий параметр. Если завести стек, то можно в него на каждом шаге заносить голову списка, а когда он исчерпается, сразу выдать содержимое стека.

rev1([X|Xs],Acc,Ys):-

rev1(Xs,[X|Acc],Ys).

rev1([], Acc,Acc).

rev2(L1,L2):-rev1(L1,[],L2).

3. Управление перебором

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

Пример: ступенчатая функция

F(X,0):-X<3.

F(X,2):-X>=3, X<6.

F(X,4):-X>=6.

Когда система пробует второе правило, заранее известно, что ни его, ни 3е правило применить не удастся.

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

F(X,0):-X<3, !.

F(X,2):-X>=3, X<6, !.

F(X,4):-X>=6.

После проверки 1го случая последует отсечение, 2й и 3й будут вычеркнуты из списка. Такая программа будет работать эффективнее. Также программу можно упростить. Мы знаем, что 2е правило сработает лишь в случае неудачи 1го, и проверять условие X>=3 не требуется.

F(X,0):-X<3, !.

F(X,2):- X<6, !.

F(X,4).

Определим точный смысл оператора отсечения.

Пусть заданы правила:

C:- P,Q,R,!,S,T,U. (1)

C:-V. (2)

A:-B,C,D. (3)

B:-… (4)

Цель ?-A.

Процедура Просмотр находит (3) правило. Пусть подцель В успешно выполняется, затем начинает работать подцель С. Эта подцель обращена к правилу (1), в котором есть отсечение, для которого она будет родителем. Рассмотрим работу правила (1). Выполнение подцелей P,Q,R идет обычным образом. После их успешного выполнения работает оператор !. Он исключает из рассмотрения альтернативное правило (2). Затем запрещается перебор в предикатах P,Q,R, то есть им запрещается генерировать новые варианты. Предикаты S,T,U работают обычным образом. Когда срабатывает ! и потом возникает откат, то перебор возобновляется от цели-родителя.

elem1(X, [X|_]):- !.

elem1(X, [_|Xs]):- elem1(X, Xs).

Пример: Добавление без дублирования:

1. добавляемый элемент, 2 – исходный список, 3 – результирующий список.

Элемент будет добавлен, если его нет в исходном списке.

add1(X,L,L):- elem1(X,L),!.

add1(X,L,[X|L]).

Оператор отсечения позволяет внести в Пролог отрицание. В процедуре «Добавление без дублирования» его точный смысл был: если подцель не достигнута, то выполняется другая подцель, что совпадает по смыслу с неуспешным выполнением цели.

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

Пример: все птицы умеют летать, кроме пингвинов.

летает (Х):-пингвин(Х), !, fail.

летает (Х):-птица(Х).

пингвин (джим).

?- летает (Джим).

no

Порядок записи правил имеет значение. Первое правило предотвратит перебор, то есть исключит второе правило из рассмотрения, если Х – пингвин.

Определим специальный предикат not(цель):

Если цель успешна, то not(цель) неуспешна;

Иначе not(цель) успешна.

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

not(P).

Терм Р вызывается как процедура.