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

Когда мы реализовывали в разделе 4.1 интерпретатор, мы видели, как можно избежать конфликтов между именами параметров процедур при помощи локальных окружений. Например, при вычислении

(define (square x) (* x x))

(define (sum-of-squares x y) (+ (square x) (square y)))

(sum-of-squares 3 4)

не возникает смешения между x из square и x из sum-of-squares, поскольку тело каждой процедуры мы вычисляем в окружении, которое специально построено для связывания локальных переменных. В запросной системе мы избегаем конфликтов имен при применении правил с помощью другой стратегии. Каждый раз при применении правила мы переименовываем переменные и даем им новые имена, которые обязаны быть уникальными. Аналогичная стратегия в интерпретаторе Лиспа заключалась бы в том, чтобы отменить внутренние окружения и просто переименовывать переменные в теле процедуры каждый раз, как мы ее вызываем.

Реализуйте для языка запросов метод применения правил, который использует не переименования, а окружения. Рассмотрите, можно ли использовать Вашу систему окружений для построения в языке запросов конструкций для работы с большими системами, например аналога блочной структуры процедур для правил. Можно ли связать это с проблемой ведения рассуждений в контексте (например: «Если бы я предположил, что истинно P, то я смог бы доказать A и В») в качестве метода решения задач? (Это упражнение не имеет однозначного решения. Хороший ответ, скорее всего, мог бы служить темой диссертации.)

Глава 5

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

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

Иоганн Кеплер (письмо к Герварту фон Гогенбургу, 1605)

Эта книга начинается с изучения процессов и с описания процессов в терминах процедур, написанных на Лиспе. Чтобы объяснить значение этих процедур, мы последовательно использовали несколько моделей вычисления: подстановочную модель из главы 1, модель с окружениями из главы 3 и метациклический интерпретатор из главы 4. Изучая последний, мы по большей части сняли покров тайны с деталей интерпретации лиспоподобных языков. Однако даже мета-циклический интерпретатор оставляет многие вопросы без ответа, поскольку он не проясняет механизмы управления Лисп-системы. Например, интерпретатор не показывает, как при вычислении подвыражения удается вернуть значение выражению, это значение использующему, или почему одни рекурсивные процедуры порождают итеративные процессы (то есть занимают неизменный объем памяти), в то время как другие процедуры порождают рекурсивные процессы. Эти вопросы остаются без ответа потому, что метациклический интерпретатор сам по себе является программой на Лиспе, а следовательно, наследует управляющую структуру нижележащей Лисп-системы. Чтобы предоставить более полное описание управляющей структуры вычислителя Лиспа, нам нужно работать на более элементарном уровне, чем сам Лисп.

В этой главе мы будем описывать процессы в терминах пошаговых операций традиционного компьютера. Такой компьютер, или регистровая машина (register machine), последовательно выполняет команды (instructions), которые работают с ограниченным числом элементов памяти, называемых регистрами (registers). Типичная команда регистровой машины применяет элементарную операцию к содержимому нескольких регистров и записывает результат еще в один регистр. Наши описания процессов, выполняемых регистровыми машинами, будут очень похожи на «машинный язык» обыкновенных компьютеров. Однако вместо того, чтобы сосредоточиться на машинном языке какого-то конкретного компьютера, мы рассмотрим несколько процедур на Лиспе и спроектируем специальную регистровую машину для выполнения каждой из этих

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

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

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

5.1 Проектирование регистровых машин

Чтобы спроектировать регистровую машину, требуется описать ее пути данных (data paths), то есть регистры и операции, а также контроллер (controller), который управляет последовательностью этих операций. Чтобы продемонстрировать строение простой регистровой машины, рассмотрим алгоритм Евклида для вычисления наибольшего общего делителя (НОД) двух натуральных чисел. Как мы видели в разделе 1.2.5, алгоритм Евклида можно реализовать в виде итеративного процесса, который описывается следующей процедурой:

(define (gcd a b)

(if (= b 0)

a

(gcd b (remainder a b))))

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