Оптимизация последнего вызова и накапливающие параметры
Рекурсивные вызовы обычно занимают значительное пространство памяти, которое освобождается только после возврата иэ последнего вызова. Большое количество вложенных рекурсивных вызовов может привести к нехватке памяти. Но в некоторых случаях существует возможность выполнять вложенные рекурсивные вызовы без потребности в дополнительной памяти. В подобных случаях рекурсивная процедура имеет специальную форму, которая обеспечивает хвостовую рекурсию. В процедуре с хвостовой рекурсией имеется только один рекурсивный вызов, который оформляется как последняя цель последнего предложения в процедуре. Кроме того, цели, предшествующие рекурсивному вызову, должны быть детерминированными, для того чтобы после этого последнего вызова не происходил перебор с возвратами. Такой детерминированности можно добиться, например, поместив оператор отсече-
Часть I. Язык Prolog
ния непосредственно перед рекурсивным вызовом. Обычно процедура с хвостовой рекурсией выглядит примерно так:
р{ . . . ; :- . . . . В теле этого предложения 7сутствуют рекурсивные вызовы р( ...) :- ... % теле этого предложения отсутствуют рекурсивные вызовы
Р( ■ ■ ■ ) :-
..., ! , % Оператор отсечения гарантирует исключение перебора с возвратами
р (...) ": Вызов с хвостовой рекурсией
В тех случаях, когда используются подобные процедуры с хвостовой рекурсией, не требуется какая-либо информация после возврата из вызова. Поэтому такая рекурсия может выполняться как итерация, в которой для каждого очередного прохода по циклу не требуется дополнительная память. Система Prolog, как правило, обнаруживает такую возможность экономии памяти и реализует хвостовую рекурсию как итерацию. Подобная ситуация называется оптимизацией хвостовой рекурсии или оптимизацией последнего вызова.
Если требования по экономии памяти приобретают исключительно важное значение, одно из возможных решений может состоять в использовании формулировок процедур с хвостовой рекурсией. Часто .действительно существует возможность легко преобразовать рекурсивную процедуру в процедуру с хвостовой рекурсией, В качестве примера рассмотрим следующий предикат вычисления суммы списка чисел: sumlist< List, Sum)
Ниже приведен первый, бесхитростный вариант его определения.
sumlist< [ ], 0).
sumlist( [ First ! Rest], Sum) :-sumlist ( Rest, SumO) , Sum is X + Su»0.
В этой процедуре не применяется хвостовая рекурсия, поэтому для суммирования очень большого списка требуется много рекурсивных вызовов, следовательно, много памяти. Но известно, что в любом типичном процедурном языке такое суммирование может осуществляться с помощью простого итерационного цикла. Как же в этом случае преобразовать sumlist в процедуру с хвостовой рекурсией и дать возможность системе Prolog осуществлять суммирование с помощью итерации? К сожалению, нельзя просто переставить местами цели в теле второго предложения, поскольку цель is может выполняться лишь после вычисления значения SumO. Но ниже показан широко распространенный прием, которым позволяет выполнить такую замену.
sumlist ( List, Sum) :-
%TSffi L i s t , 0, Su -m). В ы з о в s-l—
I TotalSum - PartialSum + сумма чисел в списке List sumlistt [], Sum, Sum). % Общая сумма равна частной сумме sumlisti First i Rest ], PartialSum, TotalSum) :-
MewPartialSm is PartialSum + First,
sumlistt Rest, NewPartialSum, TotalSum).
Теперь эта процедура становится процедурой с хвостовой рекурсией, и система Prolog может осуществить оптимизацию последнего вызова.
Показанный выше на примере процедуры sur.J прием, обеспечивающий пре-
образование обычной рекурсивной процедуры в процедуру с хвостовой рекурсией, используется очень широко. Чтобы определить целевой предикат sumlist , мы ввели вспомогательный предикат sumlist/З. Дополнительный параметр, PartialSum, обеспечил возможность применить формулировку с хвостовой рекурсией. Такие дополнительные параметры используются часто и известны под названием накапливающих параметров (accumulator argument). Окончательный результат постепенно накапливается в таком накапливающем параметре во время последователь-, ных рекурсивных вызовов.
Глава 8. Стиль и методы программирования
Ниже приведен еще один известный пример преобразования процедуры в форму с хвостовой рекурсией с помощью введения накапливающего параметра.
reverse; List, ReversedList)
В списке ReversedList представлены такие же элементы, как и в списке List, но в обратном порядке. Далее процедура является примером первой, прямолинейной попытки:
reverse ( ;] , I ] ) ,
reverse [X Rest], Reversed) :-
reverse Rest, RevRest),
conc< RevRest, [X], Reversed). % добавить элемент Х к концу
Это - не процедура с хвостовой рекурсией. Кроме того, она является также очень неэффективной из-за наличия в ней цели conc( RevRest, [X], Reversed), для которой требуется время, пропорциональное длине списка RevRest. Поэтому для изменения порядка следования элементов на противоположный в списке с длиной п приведенная выше процедура потребует время, пропорциональное а , Но, безусловно, обращение списка может быть выполнено за линейное время. Поэтому из-за ее неэффективности приведенную выше процедуру (которая уже стала классическим примером) часто называют также "наивной попыткой выполнить обращение списка". В следующей, намного более эффективной версии процедуры введен накапливающий параметр:
reverse ( List, Reversed) :-
reverse( List, [ ], Reversed!. % reverse! List, PartReversed, Reversed):
% Для получения списка Reversed добавление элементов списка List в к списку PartReversed осуществляется в обратном порядке reverse ( [ ], Reversed, Reversed). revise ( [X i Rest], PartReversed, Totalizers ed) :-
reverse! Rest, [X PartReversed], TotalReversed) . % Добавить элемент Х
\ к накапливающему параметру
Эта процедура является эффективной (она требует затрат времени, пропорциональных длине списка), и в ней применяется хвостовая рекурсия.
8.5.5. Моделирование массивов с помощью предикатаагд
Структура списка является самым удобным средством представления множеств в языке Prolog, но доступ к любому элементу в списке осуществляется путем просмотра списка. Такая операция требует времени, пропорционального длине списка, поэтому, если списки имеют большую длину, она становится очень неэффективной. Древовидные структуры, представленные в главах 9 и 10, обеспечивают намного более эффективный доступ. Но часто имеется возможность обращаться к элементам структуры спомощью индексов элементов. В подобных случаях, наиболее эффективными являются структуры массивов, предусмотренные в других языках программирования, поскольку они обеспечивают непосредственный доступ к нужному элементу.
В языке Prolog отсутствуют средства поддержки массивов, по массивы в определенной степени можно моделировать с помощью встроенных предикатов агд и functor. Примеры использования этих предикатов приведены ниже. Цель functor< A, f, i::o; создает структуру со 100 элементами:
■Pi
В других языках типичный пример оператора, в котором осуществляется непосредственный доступ кэлементу массива, выглядит так:
А[6Э] = 1
184 Часть!, Язык Prolog
В этом операторе значение 60-го элемента массива А инициализируется числом 1. Аналогичный эффект в языке Prolog может быть достигнут с помощью следующей цели: агд( 60, Л, 1)
При этом происходит непосредственный доступ к 60-му компоненту составного терма А, который в результате конкретизируется следующим образом: А - f {_,...,_, 1,_, ...,_) % 60-й элемент равен 1
Особенность этой конструкции состоит в том, что время, необходимое для доступа к ы-му компоненту структуры, не зависит от N. Еще один типичный пример оператора из другого языка программирования состоит в следующем:
X = А[60]
Этот оператор можно представить с помощью моделируемой конструкции массива на языке Prolog следующим образом: агд[ 60, А, X)
Такая операция является гораздо более аффективной, чем развертывание списка из 100 элементов и обращение к 60-му элементу с помощью вложенной рекурсии по элементам списка. Но операция обновления значения элемента в моделируемом массиве является громоздкой. В других языках после инициализации значений в массиве их можно обновлять, например, следующим образом: А[60] - А[60] +1
Прямолинейный подход к моделированию такого обновления отдельного значения в массиве на языке Prolog может состоять в следующем: сформировать полностью новую структуру со 100 компонентами с помощью предиката functor, вставить новое значение в соответствующее место в этой структуре и заполнить все остальные компоненты значениями соответствующих компонентов из предыдущей структуры. Вся эта операция является громоздкой и очень неэффективной. Одна из идей по усовершенствованию данной операции состоит в том, что должны быть предусмотрены неконкретизированные вакансии (незаполненные места) в компонентах структуры, чтобы можно было в будущем размещать в этих вакансиях новые значения элементов массива. Поэтому можно, например, хранить значения последовательных обновлений в списке, хвост которого представляет собой неконкретизированную переменную — вакансию для будущих значений. В качестве примера рассмотрим следующие операции обновления значения переменной х в программе на процедурном языке: К ;= 1,- X :- 2; X := 3
Этиобновления можно моделировать на языке Prolog с помощью метода вакансий следующим образом:
X - [1 | Restl]% Соответствует X = 1,Restl - вакансия для будущихзначений
Restl = [2 | Kest2] Ъ СоответствуетX = 2, Rest2 - вакансия для будущих значений Rest2 = [3 I Rest3] % Соответствует X = 3
К этому моменту X - [1, 2, 3 | Rest3]. Очевидно, что хранятся все предыдущие значения X, а текущим является значение, непосредственно предшествующее вакансии. Но если количество последовательных обновлений велико, текущее значение становится глубоко вложенным и этот метод снова теряет эффективность. Еще одна идея, позволяющая исключить указанную причину снижения эффективности, состоит в том, что нужно отбрасывать предыдущие значения в тот момент, когда список становится слишком длинным, и снова начинать со списка, состоящего только из головы и неконкретйзирйванного хвоста.
Несмотря на эти возможные осложнения, метод моделирования массивов с помощью предиката «гд во многих случаях является достаточно простым и действует вполне успешно, В качестве одного из таких примеров можно привести решение 3 для задачи с восемью ферзями из главы 4 (см. листинг 4.4). Эта программа помещает очередного ферзя на вертикальный ряд (координата X), горизонтальный ряд {координата Y), восходящую диагональ (координата и) и нисходящую диагональ (координа-
Ппава 8. Стиль и методы программирования
та V), которые в данный момент свободны. В программе сопровождаются множества координат, свободных в настоящее время, и после размещения нового ферзя на клетке с соответствующими координатами эти занятые координаты удаляются из указанных множеств. Для удаления координат U и V в листинге 4.4 применяется просмотр соответствующих списков, но эта операция является неэффективной. Эффективность можно легко повысить путем моделирования массивов. Поэтому множество, состоящее из всех 15 восходящих диагоналей, можно представить с помощью следующего терма с 15 компонентами: Du - u{_,_,_,_,_,_,_,_,_,_,_,_.,_,„,_;
Предположим, что ферзь помещен на клетку (X,Yj = (1,1!. Эта клетка находится на 8-й восходящей диагонали. Тот факт, что данная диагональ теперь занята, может быть отмечен путем конкретизации 8-го компонента структуры Du значением 1 (т.е. значением соответствующей координаты X) следующим образом: arg( 8, Du, 1)
Теперь Du приобретает вид Du - и <_,_,_, _,_,_,_.!,_, _,_,_, _,_,_)
Если в дальнейшем будет предпринята попытка поместить ферзя на клетку
(X, Y) = (3,3), также лежащую на 8-й диагонали, то для этого потребуется выпол
нить следующую операцию:
arg( 3, Du, 3) I Здесь х = 3
Такая попытка окончится неудачей, поскольку 8-й компонент структуры Ш уже равен 1. Поэтому программа не позволит поместить на одну и ту же диагональ еще одного ферзя. Эта реализация множеств восходящих и нисходящих диагоналей приводит к созданию намного более эффективной программы по сравнению с приведенной в листинге 4.4.