На помощь приходит команда "cut"

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

цедура является хвостовой рекурсией. Хотя, довольно просто сделать рекур-

сивный вызов в последней подцели последнего предложения. Но как гаранти-

ровать, что в любых других вызываемых процедурах нет альтернатив?

К счастью, внутренняя команда на завершение (!) позволяет отвергать

все существующие альтернативы. Чтобы установить ее, необходимо использо-

вать директиву компилятора check_determ. (Директивы компилятора описаны в

Справочном руководстве.)

Вы можите установить badcount3 следующим образом (изменяя его имя в

процессе) и оставляя check без изменений:

сutcount3(X) :-

write(X), nl,

NewX = X+1,

check(NewX),

!,

cutcount3(NewX).

Команда "cut" означает - "сжечь мосты между собой", или, точнее -

"однажды достигнув этой точки, не обращать внимание на альтернативные

предложения этого предиката и альтернативные решения предыдущих подцелей

включая данное предложение". Что точнее - решайте сами. Поскольку альтер-

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

дальше.

"Cut" также эффективен и в badcount2:

cutcount2(X) :-

X >= 0, !,

write(X), nl,

NewX = X+1,

cutcount2(NewX).

cutcount2(X) :-

write("X is negative.).

Если "cut" выполняется, компьютер предполагает, что непроверенных

альтернатив нет, и не создает стек.

/* Программа CH07EX06.PRO */

/* Показывает, как bedcount2 и bedcount3 может быть установлен объ-

явлением "cut" для исключения непроверенных предложений. Эти версии -

хвостовая рекурсия. */

predicates

cutcount2(real)

cutcount3(real)

check(real)

clauses

/* cutcount2:

Выполнение этого предложения не завершается во время ре-

курсивного вызова. */

cutcount2(X) :-

X >= 0, !,

write(X),

nl,

NewX = X+1,

cutcount2(NewX).

cutcount2(_) :-

write("X is negative.").

/* cutcount3:

Непроверенная альтернатива в предложении, вызванном перед

рекурсивным вызовом. */

cutcount3(X) :-

write(X),

nl,

NewX = X+1,

check(NewX),

!,

cutcount3(NewX).

check(Z) :- Z >= 0.

check(Z) :- Z > 0.

К сожалению, "cut" не сможет помочь с badcount1, которому необходи-

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

Единственный способ усовершенствовать badcount1 - представить вычисление

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

Использование аргументов в качестве переменных цикла

Сейчас, после освоения хвостовой рекурсии, как бы вы поступили с

циклическими переменными и счетчиками? Чтобы ответить на этот вопрос, вы

должны немного перевести с Паскаля на Пролог (допустим, что вы хорошо

знакомы с языком Паскаль).

В разделе "Рекурсия" мы показали вычисление факториала с помощью ре-

курсивной процедуры. В этом разделе мы используем для этого итерацию. В

Паскале это выглядело бы так:

P := 1;

for I := 1 to N do P := P*1;

FactN := P;

Здесь 4 переменных. N - число, факториал которого будет вычисляться;

FactN - результат вычисления; I - циклическая переменная, используемая от

1 до N; P - суммарная переменная. Конечно, опытный программист на Паскале

объединил бы FactN и P, но для Пролога так будет удобнее.

Первый шаг в переводе на Пролог - заменить for более простой форму-

лировкой для цикла, точнее определяющей, что происходит с I в каждом ша-

ге. Используем для этого определение while:

P := 1; /*инициализация P и I*/

I := 1;

while I <= N do /* задание цикла */

begin

P := P*1; /*обновление P и I*/

I := I+1

end;

FactN := P; /*показать результат*/

Программа CH07EX07.PRO показывает дальнейший перевод на Пролог:

/* CH07EX07.PRO - программа с хвостовой рекурсией для

вычисления факториала */

predicates

factorial(integer, real)

factorial(integer, real, integer, real)

/* Если числа превосходят 32767 - они объявляются веществен-

ными */

clauses

factorial(N, FactN) :-

factorial_aux(N, FactN, 1, 1).

factorial_aux(N, FactN, I, P) :-

I <= N, !,

NewP = P+1,

NewI = I+1,

factorial_aux(N, FactN, NewI, NewP).

factorial_aux(N, FactN, I, FactN) :-

I > N.

У предложения факториала есть только два аргумента - N и FactN. Они

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

вычисляет факториал. Второе предложение фактически обеспечивает рекурсию.

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

одного шага в другой. Поэтому factorial просто вызывает factorial_aux пе-

редавая дальше N и FactN с начальными значениями для I и P:

factorial(N, FactN) :-

factorial_aux(N, FactN, 1, 1).

Так I и P инициализируются.

Но, как factorial передает FactN, ведь у нее пока нет еще значения?

Ответ заключается в том, что Турбо Пролог здесь объединяет переменную,

названную FactN в одном предложении, и переменную, названную FactN в дру-

гом предложении. Таким же образом factorial_aux передает себе FactN в ка-

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

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

ней получат такое же значение.

Теперь о работе factorial_aux. Обычно этот предикат проверяет пред-

ложение для циклического вычисления - I меньше либо равно N - а затем,

рекурсивно вызывает себя с новыми значениями для I и P. Здесь проявляется

еще одна особенность Пролога. В Прологе, верное для арифметики выражение

P = P + 1

совсем не является определением присвоения (как это должно быть на других

основных языках программирования). ВЫ НЕ МОЖЕТЕ ИЗМЕНИТЬ ЗНАЧЕНИЕ ПЕРЕ-

МЕННОЙ В ПРОЛОГЕ. Вместо этого, вы должны создать новую переменную и при-

дать ей нужное значение. Например

NewP = P + 1.

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

factorial_aux(N, FactN, I, P) :-

I <= N,

NewP = P+1,

NewI = I+1,

!,

factorial_aux(N, FactN, NewI, NewP).

Как и в случае cutcount2, в этом предложении "cut" будет причиной

хвостовой рекурсии, хотя это и не последнее предложение.

В конце концов, I будет превышать N. Когда это происходит, текущие

значения P и FactN объединяются и рекурсия прекращается. Один из способов

выполнения этого выглядит следующим образом:

factorial_aux(N, FactN, I, P) :-

I > N,

FactN = P.

Здесь нет необходимости делать FactN = P отдельным шагом. Объедине-

ние может происходить в списке аргументов. Для этого подставляем одинако-

вые названия переменных в позиции, занятые требуемыми значениями FactN и

P. Аргументы в этих позициях уравняются. Это дает завершающее предложе-

ние:

factorial_aux(N, FactN, I, FactN) :-

I > N.

Запомните, что если I > N не выполнено, объединение второго и чет-

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

выходит из этого предложения, возвращая каждую переменную в исходное по-

ложение.