 |
Оптимизация хвостовой рекурсии
|
|
|
|
У рекурсии есть один большой недостаток — она «съедает» память. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура) могла, после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно (состояния выполнения решения сохраняются в стековом фрейме). Максимальный размер стека у 16-битных платформ, таких как IBM PC, работающая под DOS, составляет 64 Кбайт, что позволяет разместить максимум 3000 или 4000 стековых фреймов. На 32-битных платформах стек теоретически может возрасти до нескольких гигабайт; но здесь проявятся другие системные ограничения, прежде чем стек переполнится. Что же можно сделать, чтобы избежать использования столь большого стекового пространства?
Рассмотрим специальный случай, когда процедура может вызвать себя без сохранения информации о своем состоянии. Что, если вызывающая процедура не собирается возобновлять свое выполнение после завершения вызванной процедуры?
Предположим, что процедура вызывается последний раз, т. е. когда вызванная процедура завершит работу, вызывающая процедура не возобновит свое выполнение. Это значит, что вызывающей процедуре не нужно сохранять свое состояние, потому что эта информация уже не понадобится. Как только вызванная процедура завершится, работа процессора должна идти в направлении, указанном для вызывающей процедуры после ее выполнения.
Например, допустим, что процедура А вызывает процедуру В, а В — С в качестве своего последнего шага. Когда В вызывает С, В не должна больше ничего делать. Поэтому, вместо того чтобы сохранить в стеке процедуры В информацию о текущем состоянии С, мы можем переписать старую сохраненную информацию о состоянии В (которая больше не нужна) на текущую информацию о С, сделав соответствующие изменения в хранимой информации. Когда С закончит выполнение, она будет считать, что она вызвана непосредственно процедурой А.
|
|
|
Предположим, что на последнем шаге выполнения процедура В вместо процедуры С вызывает себя. Получается, что когда В вызывает В, стек (состояние) для вызывающей в должен быть заменен стеком для вызванной В. Это очень простая операция, просто аргументам присваиваются новые значения и затем выполнение процесса возвращается на начало процедуры В. Поэтому, с процедурной точки зрения, происходящее очень похоже на всего лишь обновление управляющих переменных в цикле
Эта операция называется оптимизацией хвостовой рекурсии (tail recursion optimization) или оптимизацией последнего вызова (last-call optimization) Обратите внимание, что по техническим причинам оптимизация последнего вызова неприменима к рекурсивным функциям.
Как задать хвостовую рекурсию
Что означает фраза "одна процедура вызывает другую, выполняя свои самый последний шаг"? На языке Пролог это значит.
П вызов является самой последней подцелью предложения,
О ранее в предложении не было точек возврата
Ниже приводится удовлетворяющий обоим условиям пример
count (N): -write(N), nl, NewN = N+l, count(NewN).
Эта процедура является хвостовой рекурсией, которая вызывает себя без резервирования нового стекового фрейма, и поэтому не истощает запас памяти Как показывает программа ch06e04 pro (листинг 13 4), если вы дадите ей целевое утверждение
count (0).
то предикат count будет печатать целые числа, начиная с 0, и никогда не остановится В конечном счете произойдет целочисленное переполнение, но остановки из-за истощения памяти не произойдет
|
|
|
Листинг 13.4. Программа ch 06 e 04. pro
/* Программа с хвостовой рекурсией, которая не истощает память */ predicates count(ulong)
clauses
count(N):-
write('\r',N), NewN = N+l, count(NewN).
GOAL nl, count(0).
Определение списка
В Прологе список — это объект, который содержит конечное число других объектов. Списки можно грубо сравнить с массивами в других языках, но, в отличие от массивов, для списков нет необходимости заранее объявлять их размер.
Список, содержащий числа 1, 2 и 3, записывается так:
[1, 2, 3]
Каждая составляющая списка называется элементом. Чтобы оформить списочную структуру данных, надо отделить элементы списка запятыми и заключить их в квадратные скобки. Вот несколько примеров:
[dog, cat, canary]
["valerie ann", "jennifer caitlin", "benjamin thomas"]
Объявление списков
Чтобы объявить домен для списка целых, надо использовать декларацию домена, такую как:
domains
integerlist = integer*
Символ (*) означает "список чего-либо"; таким образом, integer* означает "список целых".
Элементы списка могут быть любыми, включая другие списки. Однако все его элементы должны принадлежать одному домену. Декларация домена для элементов должна быть следующего вида:
domains
elementlist = elements*
elements =....
Здесь elements имеют единый тип (например: integer, real или symbol) или являются набором отличных друг от друга элементов, отмеченных разными функторами. В Visual Prolog нельзя смешивать стандартные типы в списке. Например, следующая декларация неправильно определяет список, составленный из элементов, являющихся целыми и действительными числами или идентификаторами:
elementlist = elements*
elements = integer; real; symbol/* Неверно */
Чтобы объявить список, составленный из целых, действительных и идентификаторов, надо определить один тип, включающий все три типа с функторами, которые покажут, к какому типу относится тот или иной элемент. Например:
elementlist = elements*
elements = i(integer); r(real); s(symbol)% функторы здесь i,r и s
Головы и хвосты
Список является рекурсивным составным объектом. Он состоит из двух частей — головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка — всегда список, голова списка — всегда элемент. Например:
|
|
|
голова [а, b, с] есть а
хвост [а, b, с] есть [b, с]
Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:
голова [с] есть с
хвост [с] есть []
Если выбирать первый элемент списка достаточное количество раз, вы обязательно дойдете до пустого списка []. Пустой список нельзя разделить на голову и хвост.
В концептуальном плане это значит, что список имеет структуру дерева, как и другие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 1.
Рис. 1. Структура дерева
Одноэлементный список, как, например [а], не то же самое, что элемент, который в него входит, потому что [а] на самом деле — это составная структура данных.
Работа со списками
В Прологе есть способ явно отделить голову от хвоста. Вместо разделения элементов запятыми, это можно сделать вертикальной чертой "|". Например:
[а, b, с] эквивалентно [а| [b, с]] и, продолжая процесс,
[а| [b, с] ] эквивалентно [а| [b| [с] ]], что эквивалентно [а| [b| [с| [] ] ] ]
Можно использовать оба вида разделителей в одном и том же списке при условии, что вертикальная черта есть последний разделитель. При желании можно набрать
[а, b, с, d] как [а, b|[с, d]].
В табл. 1. приведены несколько примеров на присвоение в списках.
Таблица 1. Присвоение в списках
| Список 1 | Список 2 | Присвоение переменным |
| [X, Y, Z] | [эгберт, ест, мороженое] | Х=эгберг, У=ест, Z=мороженое |
| [7] | [X | Y] | Х=7, Y=[] |
| [1, 2, 3, 4] | [X, Y | Z] | X=l, Y=2, Z=[3,4] |
| [1, 2] | [3 | X] | fail% неудача |
Использование списков
Список является рекурсивной составной структурой данных, поэтому нужны алгоритмы для его обработки. Главный способ обработки списка — это просмотр и обработка каждого его элемента, пока не будет достигнут конец.
Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе — что делать с пустым списком.
Печать списков
Если нужно напечатать элементы списка, это делается так, как показано в листинге 1.
|
|
|
Листинг 1. Программа ch 07 e 01. pro;
domains
list = integer*% Или любой тип, какой вы хотите
predicates
write_a_list(list)
clauses
write_a_list([ ]),% Если список пустой — ничего не делать
write_a_list([Н|Т]):-% Присвоить Н-голова,Т-хвост, затем...
write(H),nl,
write_a_list(Т).
goal
write_a_list([1, 2, 3]).
Вот два целевых утверждения write_a_list, описанные на обычном языке:
Печатать пустой список — значит ничего не делать.
Иначе, печатать список — означает печатать его голову (которая является одним элементом), затем печатать его хвост (список).
Подсчет элементов списка
Рассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:
Длина [] — 0.
Длина любого другого списка — 1 плюс длина его хвоста.
Можно ли применить это? В Прологе — да. Для этого нужны два предложения (листинг 2).
|
|
|
