Рекурсии)

Рис. 8.5. Рекурсивная схема слова 2СОЕД. При каждом рекурсивном вызове передаются два элемента (оба списка). Списки (А В С) и (D) после соединения образуют (А В С D). Список (D) обозначен буквой L

AND), так как для равенства списковых структур оба они должны быть истинными. Общее действие в данном случае заключается в

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

Последнии пример рекурсии, несомненно, сложнее двух пре- дыдущих. На рис. 8.5 показана схема рекурсии, аналогичная схе-

мам из первых двух примеров, но для слова 2СОЕД. Здесь при каждом рекурсивном вызове в стеке находится не один элемент, а

несколько. 2СОЕД (текст приводится на экране 42) берет со стека список (@СПИСОК) и присоединяет его к началу другого списка с именем I. Главная идея алгоритма состоит в усечении @СПИСОК и одновременно передачи копии СПЙСОК2. Эти копии пригодятся

185

184

во время рекурсивного подъема. Когда @СПИСОК становится НУЛЕМ, завершающий вызов 2СОЕД удаляет из стека пустой @СПИСОК, а также соответствующий ему список I и осуществля- ет возврат, как показано в нижней части рис. 8.5.

При рекурсивном подъеме на стек воздействует фрагмент 2СОЕД, находящийся непосредственно за словом РЕКУРСИЯ. Го- лова каждого варианта @СПИСОК связывается в I. Таким обра- зом, всякий раз один элемент из исходного варианта @СПИСОК начиная с конечного хвоста ©СПИСОК, последовательно присое- диняется к I.

Эти три примера помогут вам детально изучить рекурсивный вызов отдельной функции, и лишь после того, как вы окончатель- но разберетесь в нем, можно приступить к более абстрактному представлению проблемы. Если для понимания происходящего до- статочно следить за ходом рекурсии по диаграмме,то для написа- ния рекурсивных процедур требуются уже определенные знания. Попытаемся проиллюстрировать функционирование слова 2СОЕД на некотором абстрактом уровне мышления. Так как при рекурсии вызываются копии какого-либо слова, они должны выполнять в точности ту же функцию, что и исходное слово при его первона- чальном вызове.

В функциональной записи обращение к 2СОЕД выглядит так:

2СОЕД(Х,У)

Слово 2СОЕД берет два аргумента, X и Y, и присоединяет X к Y путем присоединения хвоста списка @СПИСОК к I, или:

2СОЕД(ХВОСТ ©СПИСОК, I)

Затем к результату добавляется голова списка ©СПИСОК:

2СОЕД(ПЕРВЫЙ ©СПИСОК, 2СОЕД (ХВОСТ ©СПИСОК, I))

Обратите внимание на то, что слово 2СОЕД рекурсивно, поскольку используется в качестве аргумента к самому себе. Второй аргумент 2СОЕД можно развернуть следующим образом:

2СОЕД(ПЕРВЫЙ ©СПИСОК, 2СОЕД(ПЕРВЫЙ ХВОСТ ©СПИСОК, I), I)

Слово 2СОЕД внутри последнего выражения также может быть i свою очередь развернуто. Эти последовательные расширения могут продолжаться до тех пор, пока не встретится некоторое условие завершения.

Рассматриваемое слово 2СОЕД является реализацией такок функционального подхода. В подобном представлении остается

186

неясным, что же процедура завершения передает самой вложенной копии слова 2СОЕД. На нижнем уровне рекурсивной схемы пос- ледний вызов должен выполнить подготовку к подъему, поскольку условие завершения инициирует переход только один раз. Напри- мер в случае 2СОЕД при подготовке к подъему необходимо уда- лить из стека два верхних элемента, оставшихся в нем после спуска.

Возможен и другой путь представления процесса рекурсии - как пары последовательных итерационных процедур с процедурой завершения, разделяющей их в нижней части рекурсивной схемы.

Если вы следите за состоянием стека по ходу рекурсивного выполнения какого-то слова, то, подходя к слову РЕКУРСИЯ, нужно учитывать, что состояние стека должно в точности соответ- ствовать его состоянию перед исходным выполнением этого слова (как это определено стековой нотацией для данного слова).

При выполнении слова 2СОЕД РЕКУРСИЯ выбирает из стека два элемента, но не помещает в стек ни одного. Два списка, переданные слову 2СОЕД при исходном обращении, остаются в стеке, а затем копируются посредством OVER ХВОСТ OVER для передачи слову РЕКУРСИЯ. После возврата из слова РЕКУРСИЯ очевидно, что завершилось выполнение

2СОЕД(ХВОСТ ©СПИСОК, I)

Далее последовательность SWAP ПЕРВЫЙ SWAP СВЯЗЬ вычисля- ет ПЕРВЫЙ ©СПИСОК, а СВЯЗЬ осуществляет присоединение. То, что РЕКУРСИЯ оставляет в стеке, определяет характер выполнения процедуры завершения. В нашем случае по крайней мере два элемента должны быть удалены из стека. Никаких иных действий не требуется, следовательно, ветвь IF содержит 2DROP. В предыдущем примере со словом ДЛИНА все необходимое для процедуры завершения можно было выяснить путем анализа содер- жимого стека до и после выполнения слова РЕКУРСИЯ. Список следовало вывести из стека, а число внести, что ветвь IF слова ДЛИНА и делала. Она удаляла посредством DROP из стека указа- тель списка и помещала в него начальное значение (0).

Двойную рекурсию можно организовать так же, как и обыч- ную хвостовую рекурсию, которая использовалась в приведенных выше примерах. Стандартная схема действий такова: проверка ус- ловия завершения, затем выбор головы и хвоста списка, рекурсия по каждому из них и затем объединение результата по какому-ни- будь принципу. Для слова РАВНО (рис. 8.4) условием завершения Рекурсии является проверка на атомы, а значения флагов, оставля- емые в стеке после двух рекурсивных вызовов, логически умножа- ется посредством AND.

Тщательно изучите приведенные выше примеры рекурсии, постарайтесь выработать свои приемы и понятие рекурсии станет для вас таким же привычным, как и понятие цикла. Слова Лиспа на

187

экранах с 40 по 49 (см. гл. 7 или листинга исходных текстов) тоже могут служить примерами слов, реализованных с помощью рекурсии.

СБОРКА МУСОРА

Важной составляющей общей реализации Лиспа является уп- равление списковой памятью - областью памяти, выделенной под списки. В нашей несколько упрощенной реализации память под списки выделяется статически (во время компиляции), а не дина- мически. Но в силу того, что управление списковой памятью, как уже отмечалось, играет не последнюю роль для Лиспа в частности и для языков ИИ вообще, мы рассмотрим ее здесь.

Так как ячейки связи, из которых строятся списки, могут ос- вобождаться, требуется некоторый механизм, позволяющий опре- делить, какие ячейки свободны для использования их словом СВЯЗЬ, а какие из них уже заняты. Существуют различные схе- мы управления списковой памятью, обеспечивающие решение за- дачи динамического распределения памяти. Основная проблема за- ключается в распознавании свободных ячеек связи. Этот процесс называется сборкой мусора. В большинстве реализаций Лиспа применяется техника отметить и удалить (mark and sweep). Другая схема, описываемая ниже более подробно, называется учетом ссылок (reference counting).

Прежде чем объяснить различие между этими методами, мы должны упомянуть о двух нежелательных эффектах при работе с памятью - висячих ссылках и мусоре, причем первый из них пред- ставляет наибольшую опасность. Висячие ссылки появляются в тех случаях, когда некоторая ячейка считается свободной, хотя факти- чески остается все еще занятой. Если ячейки, входящие как сос- тавные части в активные (используемые) списки, ссылаются на ячейку, которая стала считаться свободной, то это не мешает слову СВЯЗЬ данную ячейку задействовать вновь и сделать ее частью нового списка. В результате появляются "висячие" указатели из активных ячеек, так как их значения фактически не определены. Отсюда следует, что нельзя активную ячейку связи делать свобод- ной. Второй эффект противоположен первому. Мы полагаем, что ячейка активна, а она на самом деле свободна. Такая ячейка на- зывается мусором, поскольку не может быть повторно использова- на, и нет способа узнать, что она не занята.

При отметке и удалении мы можем избежать неприятностей так как разрешаем использовать всю свободную память, а затем собираем мусор. Специальная программа просматривает списки, на которые есть ссылки от идентификаторов, и, поскольку такие списки являются активными, в "бите сборки мусора" каждой а тивной ячейки делается отметка, показывающая, что данна ячейка не может быть освобождена. Далее просматривается вся

списковая память и непомеченные ячейки собираются в отдельный свободный список, откуда будут вновь выделяться словом СВЯЗЬ. Но для задач реального времени схема отметки и удаления не сов- сем подходит, так как сборка мусора занимает очень много време- ни, а задача при этом не может выполняться. На больших компью- терах пауза для сборки мусора может занимать секунды. Не дай бог связываться с длительными циклами по непрерывному обнов- лению памяти!

Учет ссылок не требует длительных пауз для подчистки спис- ковой памяти. Однако такой подход имеет недостаток: програм- мисту приходится вести точный учет использования ячеек памяти, а потому каждая ячейка связи должна иметь дополнительную па- мять для счетчика ссылок. Последний содержит число активных указателей, ссылающихся на данную ячейку. Всякий раз, когда указатель удаляется, счетчик ссылок ячейки, на которую ссыла- ется указатель, уменьшается (посредством RC- ), а когда активный указатель начинает ссылаться на эту ячейку, - увеличивается (по- средством RC+ ). Нулевое значение счетчика ссылок свидетель- ствует о том, что ячейка свободна. Если над списками выполняются неразрушительные операции, то они в процессе выполнения производят копии исходных списков с помощью слова СВЯЗЬ. Счетчики ссылок ячеек таких списков не увеличиваются, так как эти ячейки не приписываются идентификатору и по определению не активны.

Управление счетчиками ссылок осуществляется операторами RC+ и RC-. Они различаются только тем, что RC+ увеличивает значение счетчиков, a RC- их уменьшает. Эти операторы прос- матривают всю структуру некоторого списка целиком и модифи- цируют счетчики ячеек каждой ячейки связи данного списка.

Для того чтобы сохранить только ячейки связи, являющиеся частью списка, на который ссылается идентификатор списка, при- меняется слово УСТАНОВИТЬ (или SETQ в Лиспе). Оно выполня- ет большую часть работы счетчиков ссылок по обновлению. Слово УСТАНОВИТЬ запускает RC+ на список, когда на тот начинает ссылаться идентификатор списка, и RC- , когда тот же самый идентификатор прекращает ссылки. Таким образом, управление ячейками осуществляется просто словом УСТАНОВИТЬ. Применя- емые в настоящее время методы сборки мусора, конечно, более сложны, чем две предложенные вам здесь схемы, и, как правило, представляют их комбинации. Кроме того, современные языки ИИ для эффективного хранения массивов, символьных строк и чисел используют структуры данных, отличные от ячеек связи.

189

РЕАЛИЗАЦИЯ ФУНКЦИЙ ПРЕОБРАЗОВАНИЯ СПИСКОВ

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

ЗАМЕНЕ инициирует RC- для конкретного списка, а затем вызывает слово ЗАМЕНГ*, которое фактически осуществляет его изменение. Оно замещает заголовок списка заданным С-выражени ем. ЗАМЕНХ же замещает хвост. Остальные слова преобразования списков используют ЗАМЕНГ* и ЗАМЕНХ* , поскольку каждое слово для того, чтобы привести в соответствие счетчики ссылок обращается к RC-. Слова ЗАМЕНГ* и ЗАМЕНХ* являются прими тивами преобразования списков, поскольку они, в отличие от ЗАМЕНГ и ЗАМЕНХ, -не затрагивают счетчики ссылок.

НОБРАТНЫЙ циклически просматривает заданный список СП1 и замещает прежние значения хвостов ячеек связи указателя ми на предыдущие ячейки, как показано на рис. 8.6. Хвост первого элемента СП1 устанавливается в НУЛЬ, чтобы обозначить конец преобразованного списка. СП2 является указателем обратного спи- ска, поскольку ссылается на его заголовок.

Рис. 8.6. Список СП2, реорганизованный в обратном порядке. Хво- стовые значения ячеек связи исходного списка СП1 (вариант А) заменены указателями на предыдущие ячейки (вариант В)

*НКОНК (*NCONC), а также слово НКОНК (NCONC) осу- ществляет конкатенацию списков СШ и СП2, замещая НУЛЬ пос- леднего элемента СШ указателем на СП2. Слово ПРИСОЕД (ATTACH) выбирает из стека аргументы С - С-выражение и СП- список. Если С представляет собой атом, то с помощью слова СВЯЗЬ оно присоединяет С к СП, а если - список, то так же, как и слово *НКОНК, замещает хвост С указателем на СП. С стано- вится начальной частью нового списка.

НУДАЛИТЬ (DREMOVE) использует слово НУДАЛИТЫ, ко- торое, подобно НУДАЛИТЬ, выбирает С и СП как аргументы и удаляет из СП все ячейки с головами, равными (РАВ) С. Ре- зультат выполнения НУДАЛИТЬ показан на рис. 8.7. Хвост ячей- ки, указывающий на ячейку, голова которой РАВ С, модифициру- ется таким образом, что указываемая ячейка обходится, ее место

Рис. 8.7. Удаление элемента из списка с помощью слова

НУДАЛИТЫ. Элемент В удаляется из исходного списка СП1 (вариант

А), в результате получается список СП2 (вариант В)

занимает следующая-и тем самым средняя ячейка исключается из списка. НУДАЛИТЬ проверяет голову первой ячейки СП на равен- ство (РАВ) С. Если равенство не обнаруживается, то вызывается слово НУДАЛИТЫ, которое перемещается дальше по СП, обходя ячейки с головами, равными (РАВ) С, путем изменения хвостовых указателей. Однако если должен быть удален первый элемент СП, то его голова и хвост замещаются содержимым этих полей из второго элемента - таким образом осуществляется эффективный обход второго элемента, поскольку хвост первой ячейки теперь указывает на третью ячейку, так как вторую ячейку мы предвари- тельно удалили. Затем для преобразования этого списка можно вызвать слово НУДАЛИТЫ. Схема выполнения слова НУДА- ЛИТЬ показана на рис. 8.8.

Функции преобразования списков нужно применять с осто- рожностью по следующим причинам:

1. Если на некоторый список ранее ссылался идентификатор списка, то после выполнения функции преобразования он может не ссылаться на гол ову этого списка, так как списки реорганизуют- ся- Например, слово НОБРАТНЫЙ возвратит указатель на голову обратного списка, но идентификатор списка, который указывал на исходный список, теперь ссылается на последний элемент вновь полученного списка. После выполнения функций непосредственно- го преобразования списков все ссылающиеся на них идентификато- ры должны быть переназначены.

190

191

2. Поскольку происходит переупорядочение элементов списка сведения о том, какие ячейки связи освободились, не получаются автоматически. Должно быть выполнено динамическое перераспре- деление списковой памяти.

О

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

5 4 \ ПРИМЕР РЕКУРСИИ: ВЫЧИСЛЕНИЕ ФАКТОРИАЛА

( N М -> ) : ФАКТОРИАЛ OVER 0=

IF NIP

ELSE OVER * SWAP 1- SWAP РЕКУРСИЯ

THEN

( M ->M!)

: ФАКТОРИАЛ 1 "ФАКТОРИАЛ ;

Э кран 54. Определение рекурсивных слов ФАКТОРИАЛ и •ФАКТОРИАЛ

3. С помощью функций преобразования легко создать непра- вильные списки. Часто случайно образуются зацикленные списки. Как правило, они обнаруживаются при печати, инициируемой сло- вом ВЫДАТЬ, одного из них. Вывод таких списков продолжается бесконечно и требует аппаратного переключения или какого-ни- будь иного принудительного выхода из системы.

ФУНКЦИИ НЕПОСРЕДСТВЕННОГО ПРЕОБРАЗОВАНИЯ СПИСКОВ И УЧЕТ ССЫЛОК

Функции непосредственного преобразования списков усложня- ют управление памятью, так как изменяют структуру самого спис- ка, а не возвращают его видоизмененную копию. Если существует идентификатор, ссылающийся на список, который подвергался пре образованиям посредством слова НОБРАТНЫЙ или НУДАЛЕ- НИЕ, то неясно, что делать со счетчиками ссылок. Не известно вошли ли ячейки исходного списка в полученный список (в случае НУДАЛИТЬ) или добавлены новые ячейки (в случае ЗАМЕНГ ЗАМЕНХ). К счастью, есть простой способ справиться с этой проб

Рис. 8.8. Алгоритм слова НУДАЛЕНИЕ. Если из списка СП1, изобра- женного на рис. 8.7, должна быть удалена первая ячейка, то проис- ходит замещение головы и хвоста первой ячейки содержимым вто-. рой. В противном случае вызывается НУДАЛЕНИЕ1

лемой. Если перед модификацией списка преобразующие слова уменьшают счетчики ссылок списка, используя RC- , то впоследствии ни одна ячейка, изъятая из списка, не становится мусором. Затем выполняется модификация списка.

Здесь необходимо отметить (позднее мы обсудим этот вопрос подробнее), что любой идентификатор измененного списка сейчас неверен, поскольку он продолжает ссылаться на ячейку, которая была заголовком списка, но теперь может им не быть. Должна быть выполнена последовательность действий, переназначающая идентификатор новому списку. Сначала выполняется с новым спи- ском RC+ , а затем с помощью функций Форта указатель списка заносится в переменную идентификатора списка. Второй вопрос (более тонкий) состоит в определении влияния реорганизации списка на другие списки, содержащие подсписки вместе с реорга- низованным списком. Таких ситуаций желательно избегать, выполняя функции преобразования списков только над теми словами, которые не имеют общих нодсписков с другими словами.

УПРАЖНЕНИЯ

1. Используя рекурсию, напишите слово ФАКТОРИАЛ, которое вычисляло бы факториал п. Стековая нотация имеет вид: ( п —> п!)

2. Изобразите схему рекурсии слова ФАКТОРИАЛ из упр. 1.

3. Напишите слово ОБРАТНЫЙ из упр.5 гл.7 как рекурсивное слово.

4. Напишите слова ЗАМЕНГ и ЗАМЕНХ. Примените их для написания слова НОБРАТНЫЙ.

192

рирует отдельный факт. Программа на Прологе содержит перечень предложений (clause), которые суть либо факты, либо правила. Предложения записываются в форме:

заголовок :- цель,, цель₂, ... , цель_п