((1 2) 3 4)

Глава 5. Вычисления на регистровых машинах

--с

Рис. 5.14: Представления списка ((1 2) 3 4) в виде стрелочной диаграммы и в виде вектора памяти.

с помощью этого метода представляется список ((1 2) 3 4) , а также дана его стрелочная диаграмма. Информацию о типах мы обозначаем через буквенные префиксы. Например, указатель на пару с индексом 5 обозначается p5, пустой список обозначается e0, а указатель на число 4 обозначается n4. На стрелочной диаграмме мы в левом нижнем углу каждой пары ставим индекс вектора, который показывает, где хранятся car и cdr пары. Пустые клетки в the-cars и the-cdrs могут содержать части других структур (которые нам сейчас неинтересны).

Указатель на число, например n4 , может состоять из метки, указывающей, что это число, и собственно представления числа 4.9 Для того, чтобы работать с числами, не умещающимися в ограниченном объеме, отводимом под указатель, может иметься особый тип данных большое число (bignum), для которого указатель обозначает список, где хранятся части числа.10

Символ можно представить как типизированный указатель, обозначающий последовательность знаков, из которых состоит печатное представление символа. Эта последовательность создается процедурой чтения Лиспа, когда строка-представление в первый раз встречается при вводе. Поскольку мы хотим, чтобы два экземпляра символа всегда были «одинаковы» в смысле eq?, а eq? должно быть простым сравнением указателей, нам нужно обеспечить, чтобы процедура чтения, когда она видит ту же строку второй раз, использовала тот же самый указатель (к той же последовательности знаков) для представления обоих вхождений символа. Ради этого процедура чтения содержит таблицу, которая по традиции называется обмассив (obarray), и в ней хранит все когда-либо встреченные символы. Когда процедура видит строку и готова создать символ, она проверяет в обмассиве, не было ли уже ранее такой же строки. Если нет, она

9Решение о представлении чисел определяет, можно ли сравнивать числа через eq?, который проверяет одинаковость указателей. Если указатель содержит само число, то равные числа будут иметь одинаковые указатели. Однако если в указателе содержится индекс ячейки, в которой хранится само число, то у равных чисел будут одинаковые указатели только в том случае, если нам удастся никогда не хранить одно и то же число в двух местах.

10Это представление очень похоже на запись числа в виде последовательности цифр, только каждая «цифра» является числом между 0 и максимальным значением, которое можно уместить в указателе.

1

2

4

3

4

5

7

1

2

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

Реализация элементарных списковых операций

Имея вышеописанную схему представления, можно заменить каждую «элементарную» списковую операцию регистровой машины одной или более элементарной векторной операцией. Мы будем обозначать векторы памяти двумя регистрами the-cars и the-cdrs, и предположим, что операции vector-ref и vector-set! даны как элементарные. Кроме того, предположим, что численные операции с указателями (добавление единицы, индексирование вектора с помощью указателя на пару и сложение чисел) используют только индексную часть типизированного указателя.

Например, можно заставить регистровую машину поддерживать команды

(assign (рее (op car) (reg (рев2)))

(assign (рее) (op cdr) (reg (рее2))) если мы реализуем их, соответственно, как

(assign (рее1) (op vector-ref) (reg the-cars) (reg (рее2))) (assign (рее1) (op vector-ref) (reg the-cdrs) (reg (рее2))) Команды

(perform (op set-car!) (reg (рее1)) (reg (рее(2)))) (perform (op set-cdr!) (reg (рее1)) (reg (рее(2)))) реализуются как (perform

(op vector-set!) (reg the-cars) (reg (рее1)) (reg (рее2))) (perform

(op vector-set!) (reg the-cdrs) (reg (рее1)) (reg (рее2)))

При выполнении cons выделяется неиспользуемый индекс, и аргументы cons записываются в the-cars и the-cdrs в ячейках с выделенным индексом. Мы предполагаем, что имеется особый регистр free, в котором всегда содержится указатель на следующую свободную пару, и что мы можем его увеличить и получить следующую свободную ячейку." Например, команда

(assign (рее (op cons) (reg (рее)) (reg (рее 3)))

"Имеются и другие способы поиска свободной памяти. Например, можно было бы связать все неиспользуемые пары в список свободных ячеек (free list). Наши свободные ячейки идут подряд, поскольку мы пользуемся сжимающим сборщиком мусора, как будет описано в разделе 5.3.2.

реализуется как следующая последовательность векторных операций: 12 (perform

(op vector-set!) (reg the-cars) (reg free) (reg (рве2))) (perform

(op vector-set!) (reg the-cdrs) (reg free) (reg (рве))) (assign (reg (рве)) (reg free)) (assign free (op +) (reg free) (const 1))

Операция eq?

(op eq?) (reg (рве!)) (reg (рве2))

попросту проверяет равенство всех полей регистров, а предикаты вроде pair? , null?, symbol? и number? смотрят только на поле типа.

Реализация стеков

Хотя наши регистровые машины используют стеки, нам ничего специально здесь делать не надо, поскольку стеки можно смоделировать на основе списков. Стек может быть списком сохраненных значений, на которые указывает особый регистр the-stack. Таким образом, (save (рее)) может реализовываться как

(assign the-stack (op cons) (reg (рве)) (reg the-stack))

Подобным образом, (restore (рее)) можно реализовать как

(assign (рве) (op car) (reg the-stack)) (assign the-stack (op cdr) (reg the-stack))

а (perform (op initialize-stack)) реализуется как

(assign the-stack (const ()))

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

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

Нарисуйте стрелочную диаграмму и представление в виде вектора (как на рисунке 5.14) списка, который порождается кодом

(define x (cons 1 2)) (define y (list x x))

если вначале указатель free равен p1. Чему равно значение free после исполнения кода? Какие указатели представляют значения x и y?

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

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

12В сущности, это реализация cons через set-car! и set-cdr!, как описано в разделе 3.3.1. Операция get-new-pair, которая там используется, здесь реализуется через указатель free.