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

Добавьте к модели регистровой машины подсчет команд (instruction counting). Это значит, что машина должна подсчитывать число выполненных ею команд. Расширьте интерфейс модели и добавьте новое сообщение, которое печатает счетчик команд и переустанавливает его в ноль.

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

Добавьте к имитатору трассировку команд (instruction tracing). А именно, перед тем, как выполнить каждую команду, имитатор должен распечатывать ее текст. Заставьте модель принимать сообщения trace-on и trace-off, которые включают и выключают трассировку.

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

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

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

Измените процедуру make-register из раздела 5.2.1, так, чтобы можно было трассировать регистры. Регистры должны принимать сообщения, которые включают и выключают трассировку. Когда регистр подвергается трассировке, присваивание ему значения должно вызывать распечатку имени регистра, старого его содержимого и нового, которое ему присваивается. Расширьте интерфейс модели и дайте пользователю возможность включать и выключать трассировку для указанных регистров машины.

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

Лиза П. Хакер хочет добавить в имитатор контрольные точки (breakpoints) для облегчения отладки проектов машин. Вас наняли для реализации такой возможности. Лиза хочет, чтобы в последовательности команд контроллера можно было указать место, где имитатор остановится и позволит ей исследовать состояние машины. Вам нужно реализовать процедуру

(set-breakpoint (машина) (метка) (n))

которая устанавливает контрольную точку перед n-й командой, следующей за указанной меткой. Например,

(set-breakpoint gcd-machine test-b 4)

установит контрольную точку в gcd-machine непосредственно перед присваиванием регистру a. Когда моделирование достигает контрольной точки, имитатор должен распечатать метку и смещение точки, а затем прекратить выполнение команд. Тогда Лиза может с помощью get-register-contents и set-register-contents! исследовать и изменять состояние имитируемой машины. Затем она должна быть способна продолжить выполнение, сказав

(proceed-machine (машина))

Кроме того, необходимо иметь возможность удалить контрольную точку с помощью (cancel-breakpoint (машина) (метка) (n)) и удалить все контрольные точки с помощью (cancel-all-breakpoints (машина))

5.3 Выделение памяти и сборка мусора

В разделе 5.4 мы покажем, как реализовать вычислитель для Scheme в виде регистровой машины. Для того, чтобы упростить обсуждение, мы будем предполагать, что наши машины обладают памятью со списковой структурой (list-structured memory), в которой основные операции по работе с данными списковой структуры элементарны. Постулирование такой памяти - удобная абстракция, если мы хотим сконцентрировать внимание на механизмах управления в интерпретаторе Scheme, однако она не дает реалистической картины того, как на самом деле устроены элементарные операции с данными в современных компьютерах. Для того, чтобы получить более полное понимание работы Лисп-системы, требуется исследовать, как списковую структуру можно представить способом, совместимым с устройством памяти обыкновенных компьютеров.

При реализации списковой структуры возникает два вопроса. Первый относится только к способу представления: как изобразить структуру «ячеек и указателей», присущую лисповским парам, используя только механизмы хранения и адресации, которыми обладает обыкновенная компьютерная память. Второй вопрос связан с управлением памятью по мере того, как вычисление развивается. Работа Лисп-системы существенным образом зависит от ее способности постоянно создавать новые объекты данных. Сюда включаются как объекты, которые явным образом выделяются в интерпретируемых Лисп-процедурах, так и структуры, создаваемые самим интерпретатором, например окружения и списки аргументов. Несмотря на то, что постоянное создание новых объектов данных не вызвало бы проблемы на компьютере с бесконечным количеством быстродействующей памяти, в настоящих компьютерах объем доступной памяти ограничен (к сожалению). Поэтому Лисп-системы реализуют автоматическое распределение памяти (automatic storage allocation), которое поддерживает иллюзию бесконечной памяти. Когда объект данных перестает быть нужным, занятая под него память автоматически освобождается и используется для построения новых объектов данных. Имеются различные методы реализации такого автоматического распределителя памяти. Метод, обсуждаемый нами в этом разделе, называется сборка мусора (garbage collection).

5.3.1 Память как векторы

Обыкновенную память компьютера можно рассматривать как массив клеток, каждая из которых может содержать кусочек информации. У каждой клетки имеется собственное имя, которое называется ее адресом (address). Типичная система памяти предоставляет две элементарные операции: одна считывает данные, хранящиеся по указанному адресу, а вторая записывает по указанному адресу новые данные. Адреса памяти можно складывать с целыми числами и получать таким образом последовательный доступ к некоторому множеству клеток. Если говорить более общо, многие важные операции с данными требуют, чтобы адреса памяти рассматривались как данные, которые можно записывать в ячейки памяти, и которыми можно манипулировать в регистрах машины. Представление списковой структуры - одно из применений такой адресной арифметики (address arithmetic).

Для моделирования памяти компьютера мы используем новый вид структуры данных, называемый вектором (vector). С абстрактной точки зрения,

вектор представляет собой составной объект, к отдельным элементам которого можно обращаться при помощи целочисленного индекса за время, независимое от величины индекса.5 Чтобы описать операции с памятью, мы пользуемся двумя элементарными процедурами Scheme для работы с векторами:

•(vector-ref (вектор) (n)) возвращает n-ый элемент вектора.

•(vector-set! (вектор) (n) (значение)) устанавливает n-ый элемент вектора в указанное значение.

Например, если v - вектор, то (vector-ref v 5) получает его пятый элемент, а (vector-set! v 5 7) устанавливает значение его пятого элемента равным 7.6 В памяти компьютера такой доступ можно было бы организовать через адресную арифметику, сочетая базовый адрес (base address), который указывает на начальное положение вектора в памяти, с индексом (index), который указывает смещение определенного элемента вектора.

Представление лисповских данных

С помощью списков можно реализовать пары - основные объекты данных, нужные для памяти со списковой структурой. Представим, что память разделена на два вектора: the-cars и the-cdrs. Списковую структуру мы будем представлять следующим образом: указатель на пару есть индекс, указывающий внутрь этих двух векторов. Содержимое элемента the-cars с указанным индексом является car пары, а содержимое элемента the-cdrs с тем же индексом является cdr пары. Кроме того, нам нужно представление для объектов помимо пар (например, чисел и символов) и способ отличать один тип данных от другого. Есть много способов этого добиться, но все они сводятся к использованию типизированных указателей (typed pointers) - то есть понятие «указатель» расширяется и включает в себя тип данных.7 Тип данных позволяет системе отличить указатель на пару (который состоит из метки типа данных «пара» и индекса в вектора памяти) от указателей на другие типы данных (которые состоят из метки какого-то другого типа и того, что используется для представления значений этого типа). Два объекта данных считаются равными (eq?), если равны указатели на них.8 На рисунке 5.14 показано, как

5Можно было бы представить память в виде списка ячеек. Однако тогда время доступа не было бы независимым от индекса, поскольку доступ к n-му элементу списка требует п - 1 операций cdr.

6Полноты ради, надо было бы указать еще операцию make-vector, которая создает вектора. Однако в текущем приложении мы используем вектора исключительно для моделирования заранее заданных участков компьютерной памяти.

7Это в точности понятие «помеченных данных», которое мы ввели в главе 2 для работы с обобщенными операциями. Однако здесь типы данных вводятся на элементарном машинном уровне, а не конструируются через списки.

8Информация о типе может быть представлена различными способами, в зависимости от деталей машины, на которой реализована Лисп-система. Эффективность выполнения Лисп-программ будет сильно зависеть от того, насколько разумно сделан этот выбор, однако правила проектирования, определяющие, какой выбор хорош, сформулировать трудно. Самый простой способ реализации типизированных указателей состоит в том, чтобы в каждом указателе выделить несколько бит как поле типа (type field) (или метку, тег типа (type tag)) которое кодирует тип. При этом требуется решить следующие важные вопросы: сколько требуется битов для поля типа? Как велики должны быть индексы векторов? Насколько эффективно можно использовать элементарные команды машины для работы с полями типа в указателях? Про машины, в которых имеется специальная аппаратура для эффективной обработки полей типа, говорят, что они обладают теговой архитектурой (tagged architecture).