a.Рекурсивная count-leaves:

(define (count-leaves tree) (cond ((null? tree) 0)

((not (pair? tree)) 1)

(else (+ (count-leaves (car tree))

(count-leaves (cdr tree))))))

b.Рекурсивная count-leaves с явным счетчиком:

(define (count-leaves tree) (define (count-iter tree n) (cond ((null? tree) n)

((not (pair? tree)) (+ n 1)) (else (count-iter (cdr tree)

(count-iter (car tree) n)))))

(count-iter tree 0))

Упражнение 5.22.

В упражнении 3.12 из раздела 3.3.1 были представлены процедура append, которая добавляет два списка друг к другу и получает третий, и процедура append! , которая склеивает два списка вместе. Спроектируйте регистровые машины, которые реализуют каждую из этих процедур. Предполагайте, что операции с памятью, реализующие списковую структуру, являются примитивами.

5.3.2 Иллюзия бесконечной памяти

Метод представления, намеченный в разделе 5.3.1, решает задачу реализации списковой структуры при условии, что у нас бесконечное количество памяти. В настоящем компьютере у нас в конце концов кончится свободное место, где можно строить новые пары.13 Однако большинство пар, порождаемых во время типичного вычисления, используются только для хранения промежуточных результатов. После того, как эти результаты обработаны, пары больше не нужны - они становятся мусором (garbage). Например, при выполнении

(accumulate + 0 (filter odd? (enumerate-interval 0 n)))

создается два списка: перечисление и результат его фильтрации. После того, как проводится накопление, эти списки больше не нужны, и выделенную под них память можно освободить. Если нам удастся периодически собирать весь мусор, и память будет таким образом освобождаться приблизительно с той же скоростью, с которой мы строим новые пары, мы сможем поддерживать иллюзию, что у нас бесконечное количество памяти.

13На самом деле и это может быть неправдой, поскольку размеры памяти могут стать настолько большими, что свободная память просто не успеет исчерпаться за время жизни компьютера. Например, в году примерно 3 х 1013 секунд, так что если мы будем вызывать cons один раз в микросекунду, и у нас будет примерно 1015 ячеек памяти, то мы построим машину, которая сможет работать 30 лет, пока память не кончится. По теперешним понятиям такое количество памяти кажется абсурдно большим, однако физически оно вполне возможно. С другой стороны, процессоры становятся быстрее, и может быть, что в компьютерах будущего будет по многу процессоров, работающих параллельно в единой памяти, так что память можно будет расходовать намного быстрее, чем мы сейчас предполагаем.

Для того, чтобы освобождать пары, нужен способ определять, какие из выделенных пар больше не нужны (в том смысле, что их содержимое не может уже повлиять на будущее вычисления). Метод, с помощью которого мы этого добиваемся, называется сборка мусора (garbage collection). Сборка мусора основана на наблюдении, что в каждый момент при интерпретации Лисп-программы на будущую судьбу вычисления могут повлиять только те объекты, до которых можно добраться с помощью какой-нибудь последовательности операций car и cdr, начиная с указателей, хранимых в этот момент в регистрах машины.14 Любую ячейку памяти, до которой так добраться нельзя, можно освободить.

Есть множество способов сборки мусора. Метод, который мы опишем здесь, называется остановка с копированием (stop-and-copy). Основная идея состоит в том, чтобы разделить память на две половины: «рабочую память» и «свободную память». Когда cons строит пары, он это делает в рабочей памяти. Когда рабочая память заполняется, проводится сборка мусора: мы отыскиваем все используемые пары в рабочей памяти и копируем их в последовательные ячейки свободной памяти. (Используемые пары ищутся просмотром всех указателей car и cdr, начиная с машинных регистров.) Поскольку мусор мы не копируем, предполагается, что при этом появится дополнительная свободная память, где можно выделять новые пары. Кроме того, в рабочей памяти не осталось ничего нужного, поскольку все полезные пары из нее скопированы в свободную память. Таким образом, если мы поменяем роли рабочей и свободной памяти, мы можем продолжить работу; новые пары будут выделяться в новой рабочей памяти (бывшей свободной). Когда она заполнится, мы можем скопировать используемые пары из нее в новую свободную память (старую рабочую).15

Реализация сборщика мусора методом остановки с копированием

Теперь мы можем с помощью языка регистровых машин описать алгоритм остановки с копированием более подробно. Предположим, что имеется регистр root, и в нем хранится указатель на корневой объект - структуру, которая (через перенаправления) указывает на все доступные данные. Такой конфигу-

14Здесь мы предполагаем, что стек представляется в виде списка, как описано в разделе 5.3.1, так что элементы стека доступны через указатель, хранящейся в стековом регистре.

15Эта идея была придумана и впервые реализована Минским, как часть реализации Лиспа для машины PDP-1 в Исследовательской лаборатории Электроники в MIT. Ее дополнили Феничель и Йохельсон (Fenichel and Yochelson 1969) для реализации Лиспа в системе разделения времени Multics. Позднее Бейкер (Baker 1978) разработал версию для «реального времени», в которой не требуется останавливать вычисления на время сборки. Идею Бейкера расширили Хьюитт, Либерман и Мун (Lieberman and Hewitt 1983), использовав то, что часть структуры более подвижна, а часть более постоянна.

Второй часто используемый метод сборки мусора - это пометка с очисткой (mark-sweep). Он состоит в том, что все структуры, доступные из машинных регистров, просматриваются и помечаются. Затем вся память просматривается, и всякий непомеченный участок «вычищается» как мусор и объявляется свободным. Полное обсуждение метода пометки с очисткой можно найти в Allen 1978.

В системах с большой памятью, как правило, используется алгоритм Минского-Феничеля-Йохельсона, поскольку он просматривает только используемую часть памяти. Напротив, при методе пометки с очисткой фаза очистки должна проверять всю память. Второе преимущество остановки с копированием состоит в том, что это сжимающий (compacting) сборщик мусора. Это означает, что в конце фазы сборки мусора все используемые данные оказываются в последовательной области памяти, а весь мусор «выжат». На машинах с виртуальной памятью это может давать весьма большой выигрыш в производительности, поскольку доступ к сильно различающимся адресам в памяти может приводить к дополнительной подкачке страниц.

рации можно добиться, если переместить содержимое всех регистров машины в заранее выделенный список, на который и будет указывать root, непосредственно перед запуском сборщика мусора.16 Кроме того, мы предполагаем, что помимо текущей рабочей памяти имеется свободная память, в которую мы можем копировать используемые данные. Текущая рабочая память состоит из векторов, базовые адреса которых хранятся в регистрах the-cars и the-cdrs, а свободная память доступна через регистры new-cars и new-cdrs.

Сборка мусора запускается, когда кончаются свободные ячейки в текущей рабочей памяти, то есть когда операция cons пытается сдвинуть указатель free за пределы вектора памяти. По завершении сборки мусора указатель root будет указывать на новую память, все объекты, доступные через root, будут перемещены в новую память, а указатель free будет указывать на место в новой памяти, начиная с которого можно выделять новые пары. Кроме того, поменяются местами роли рабочей памяти и свободной памяти - новые пары будут выделяться в новой памяти, начиная с места, на которое показывает free, а (предыдущая) рабочая память будет доступна в качестве новой памяти для следующей сборки мусора. На рисунке 5.15 показано устройство памяти непосредственно перед сборкой мусора и сразу после нее.

Состояние процесса сборки мусора управляется содержимым двух регистров: free и scan. Оба они сначала указывают на начало новой памяти. При запуске алгоритма пара, на которую указывает root, переносится в начало новой памяти. Пара копируется, регистр root переставляется в новое место, а указатель free увеличивается на единицу. В дополнение к этому в старом месте, где хранилась пара, делается пометка, которая говорит, что содержимое перенесено. Отметка делается так: в позицию car мы помещаем особое значение, показывающее, что объект перемещен. (По традиции, такой объект называется разбитое сердце (broken heart).)17 В позицию cdr мы помещаем перенаправляющий адрес (forwarding address), который указывает на место, куда перемещен объект.

После того, как перемещен корневой объект, сборщик мусора входит в основной цикл. На каждом шаге алгоритма регистр scan (вначале он указывает на перемещенный корневой объект) содержит адрес пары, которая сама перемещена в новую память, но car и cdr которой по-прежнему указывают на объекты в старой памяти. Каждый из этих объектов перемещается, а затем регистр scan увеличивается на единицу. При перемещении объекта (например, того, на который указывает car сканируемой пары) мы прежде всего проверяем, не перемещен ли он уже (об этом нам говорит разбитое сердце в позиции car объекта). Если объект еще не перемещен, мы переносим его в место, на которое указывает free, увеличиваем free, записываем разбитое сердце по старому местоположению объекта, и обновляем указатель на объект (в нашем случае, car пары, которую мы сканируем) так, чтобы он показывал на новое место. Если же объект уже был перемещен, то его перенаправляющий адрес (он находится в позиции cdr разбитого сердца) подставляется на место указателя в сканируемой паре. В конце концов все доступные объекты окажутся пере-

16Этот список регистров не включает в себя регистры, которые используются подсистемой выделения памяти - root, the-cars, the-cdrs и еще несколько регистров, которые будут введены в этом разделе.

17Термин разбитое сердце придумал Дэвид Кресси, когда он писал сборщик мусора для MDL, диалекта Лиспа, разработанного в MIT в начале 70х годов.