На этом шаге мы рассмотрим оптимизацию хвостовой рекурсии.
У рекурсии есть один большой недостаток - она съедает память. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура) могла, после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно (состояния выполнения решения сохраняются в стековом фрейме). Максимальный размер стека у 16-битных платформ, работающая под DOS, составляет 64 Кбайт, что позволяет разместить максимум 3000 или 4000 стековых фреймов. На 32-битных платформах стек теоретически может возрасти до нескольких гигабайт; но здесь проявятся другие системные ограничения, прежде чем стек переполнится. Что же можно сделать, чтобы избежать использования столь большого стекового пространства?
Рассмотрим специальный случай, когда процедура может вызвать себя без сохранения информации о своем состоянии. Что, если вызывающая процедура не собирается возобновлять свое выполнение после завершения вызванной процедуры?
Предположим, что процедура вызывается последний раз, т. е. когда вызванная процедура завершит работу, вызывающая процедура не возобновит свое выполнение. Это значит, что вызывающей процедуре не нужно сохранять свое состояние, потому что эта информация уже не понадобится. Как только вызванная процедура завершится, работа процессора должна идти в направлении, указанном для вызывающей процедуры после ее выполнения.
Например, допустим, что процедура А вызывает процедуру B, а B - C в качестве своего последнего шага. Когда B вызывает C, B не должна больше ничего делать. Поэтому, вместо того чтобы сохранить в стеке процедуры B информацию о текущем состоянии C, вы можете переписать старую сохраненную информацию о состоянии B (которая больше не нужна) на текущую информацию о C, сделав соответствующие изменения в хранимой информации. Когда C закончит выполнение, она будет считать, что она вызвана непосредственно процедурой А.
Предположим, что на последнем шаге выполнения процедура B вместо процедуры C вызывает себя. Получается, что когда B вызывает B, стек (состояние) для вызывающей B должен быть заменен стеком для вызванной B. Это очень простая операция, просто аргументам присваиваются новые значения и затем выполнение процесса возвращается в начало процедуры B. Поэтому, с процедурном точки зрения, происходящее очень похоже на всего лишь обновление управляющих переменных в цикле.
Эта операция называется оптимизацией хвостовой рекурсии (tail recursion optimization) или оптимизацией последнего вызова (last-call optimization). Обратите внимание, что по техническим причинам оптимизация последнего вызова неприменима к рекурсивным функциям.
Как задать хвостовую рекурсию
Что значит фраза "одна процедура вызывает другую, выполняя свой самый последний шаг"? На языке Пролог это значит:
- вызов является самой последней подцелью предложения;
- ранее в предложении не было точек возврата.
count(N):-
write(N),
nl,
NewN=N+l,
count(NewN).
Эта процедура является хвостовой рекурсией, которая вызывает себя без резервирования нового стекового фрейма, и поэтому не истощает запас памяти. Как показывает программа pro40_1.pro, если вы дадите ей целевое утверждение
count(0).
то предикат count будет печатать целые числа, начиная с 0, и никогда не остановится. В конечном счете произойдет целочисленное переполнение, но остановки из-за истощения памяти не произойдет.
/* Программа с хвостовой рекурсией, которая не истощает память */
predicates
count(integer)
clauses
count(N):-
write(N),
NewN=N+1,
count(NewN).
goal
nl,
count(0).
Из-за чего возникает не оптимизированная хвостовая рекурсия
Выше был продемонстрирован правильный пример использования хвостовой рекурсии, программа pro40_2.pro показывает три ошибочных способа организации хвостовой рекурсии.
- Если рекурсивный вызов - не самый последний шаг, процедура не является хвостовой рекурсией. Например:
badcountl(X):- write(X), NewX=X+1, badcountl(NewX), nl.Каждый раз, когда badcount1 вызывает себя, стек должен быть сохранен для того, чтобы обработку можно было вернуть к вызывающей процедуре, которая должна выполняться до nl. Поэтому она сделает всего несколько тысяч рекурсивных вызовов до исчерпания памяти.
- Другой способ сделать хвостовую рекурсию не оптимизированной - оставить некоторую возможную альтернативу
непроверенной к моменту выполнения рекурсивного вызова. Тогда стек должен быть сохранен, т. к. в случае
неудачного завершения рекурсивного вызова вызывающая процедура может откатиться и начать проверять эту
альтернативу. Например:
badcount2(X):- write(X) , NewX=X+l, badcount2(NewX). badcount2(X):- X<0, write("X отрицательно.").Здесь первое предложение badcount2 вызывает себя, когда второе предложение еще не выполнено. Снова программа истощает память после определенного количества вызовов.
- Для потери оптимизации хвостовой рекурсии не обязательно иметь непроверенную альтернативу как отдельное
предложение рекурсивной процедуры. Непроверенная альтернатива может быть и в любом вызываемом предикате.
Например:
badcount3(X):- write(X), NewX=X+l,, check(NewX), badcount3(NewX). check(Z):- Z>=0. check(Z) :- Z<0.Предположим, что X - положительная величина, как это обычно бывает. Когда badcount3 вызывает себя, первое предложение check достигает цели, а второе предложение check еще не проверено. Поэтому badcount3 должен сохранить копию своего стекового фрейма, чтобы иметь возможность вернуться и начать проверять второе предложение check в случае, если рекурсивный вызов завершится неудачно.
Текст этой программы можно взять здесь./*32-битной архитектуре эти примеры будут выполняться достаточно долго, занимая много памяти и значительно уменьшая общую производительность системы.*/ predicates badcount1(integer) badcount2(integer) badcount3(integer) check(integer) clauses %badcountl: Рекурсивный вызов - не последний шаг. badcount1(X):- write(X), NewX=X+1, badcount1(NewX), nl. % badcount2: Это предложение, которое не выполняется во время % осуществления рекурсивного вызова badcount2(X):- write(X), NewX=X+1, badcount2(NewX). badcount2(X):- X<0, write("X отрицательно."). % badcount3: Непроверенная альтернатива в процедуре, % вызванной перед рекурсивным вызовом. badcount3(X):- write(X) , NewX=X+1, check(NewX), badcount3(NewX). check(Z):- Z>=0. check(Z):- Z<0.
Заметьте, что badcount2 и badcount3 хуже, чем badcount1, потому что они генерируют точки возврата.
Вероятно, вы сейчас думаете, что невозможно гарантировать, что процедура является оптимизированной хвостовой рекурсией. Хотя довольно просто сделать рекурсивный вызов в последней подцели заключительного предложения, но как гарантировать, что в любых других вызываемых предикатах нет альтернатив?
Отсечение позволяет отвергать все возможные излишние альтернативы. Чтобы установить cut, необходимо использовать директиву компилятора check_determ.
Вы можете исправить badcount3 следующим образом (модифицируя его имя):
cutcount3(X):-
write(X),
NewX=Х+1,
check(NewX),
!,
cutcount3(NewX).
Команда "отсечение" означает "сжечь мосты за собой", или, точнее, "однажды достигнув этой точки, не обращать внимания на альтернативные предложения этого предиката и альтернативные решения предыдущих подцелей в данном предложении". Что точнее - решайте сами. Поскольку альтернативы исключаются, фрейм стека не нужен и рекурсивный вызов может свободно идти дальше.
"Отсечение" также эффективно и в badcount2, если переместить проверку из второго предложения в первое:
cutcount2(X):-
X>=0,
!,
write(X) ,
NewX = Х+1,
cutcount2(NewX).
cutcount2(X) :-
write("X is negative.").
Отсечение - это действительно решение. Оно используется всякий раз, когда альтернативы нам не интересны. В исходной версии предыдущего примера второе предложение должно было оставлять выбор, т. к. первое предложение не содержало проверки X. Переместив проверку в первое предложение и отрицая ее, решение можно принять уже там, а отсечение установить в соответствии с утверждением: "Теперь я знаю, что я не должен писать, что X отрицателен".
То же касается cutcount3. Предикат check показывает ситуацию, когда вы хотите совершить некую дополнительную операцию над X, основанную на знаке. Однако код для check недетермирован, и отсечение после его вызова - это все, на что вам надо решиться. Однако вышесказанное немного искусственно - возможно, было бы правильнее, чтобы check был детерминиронан:
check(Z):-
Z>=0,
!,
... % использование Z
check(Z):-
Z<0,
... % использование Z
Проверка во втором предложении check - полное отрицание проверки в первом. Поэтому check можно переписать как:
check(Z):-
Z>=0,
Если отсечение выполняется, компьютер предполагает, что непроверенных альтернатив нет, и не создает стековый фрейм. Программа pro40_3.pro содержит измененные версии badcount2 и badcount3.
/*Показывает, как bedcount2 и bedcount3 могут быть
улучшены объявлением отсечения ("cut") для исключения
непроверенных предложений. Эти версии используют оптимизированную
хвостовую рекурсию.*/
predicates
cutcount2(integer)
cutcount3(integer)
check(integer)
clauses
cutcount2(X):-
X>=0,
!,
write(X),
NewX=X+1,
cutcount2(NewX).
cutcount2(_):-
write("X отрицательно.").
cutcount3(X):-
write(X) ,
NewX=X+1,
check(NewX),
!,
cutcount3(NewX).
check(Z):-
Z>=0.
check(Z):-
Z<0.
К сожалению, отсечение не сможет помочь с badcount1, в котором необходимость создания копий стековых фреймов не связана с непроверенными альтернативами. Единственный способ усовершенствовать badcount1 - произвести вычисления таким образом, чтобы рекурсивный вызов происходил в конце предложения.
Со следующего шага мы начнем рассматривать использование аргументов в качестве переменных цикла.
