Оптимизация последнего вызова и накапливающие параметры

Рекурсивные вызовы обычно занимают значительное пространство памяти, кото­рое освобождается только после возврата иэ последнего вызова. Большое количество вложенных рекурсивных вызовов может привести к нехватке памяти. Но в некото­рых случаях существует возможность выполнять вложенные рекурсивные вызовы без потребности в дополнительной памяти. В подобных случаях рекурсивная проце­дура имеет специальную форму, которая обеспечивает хвостовую рекурсию. В проце­дуре с хвостовой рекурсией имеется только один рекурсивный вызов, который оформляется как последняя цель последнего предложения в процедуре. Кроме того, цели, предшествующие рекурсивному вызову, должны быть детерминированными, для того чтобы после этого последнего вызова не происходил перебор с возвратами. Такой детерминированности можно добиться, например, поместив оператор отсече-

Часть 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.