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

b. Можете ли Вы предложить изменения в компиляторе, помогающие ему порождать код, который приблизится к показателям версии, построенной вручную?

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

Проведите анализ, подобный анализу из упражнения 5.45, и определите эффективность компиляции для процедуры Фибоначчи с древовидной рекурсией

(define (fib n) (if (< n 2) n

(+ (fib (- n 1)) (fib (- n 2)))))

по сравнению с эффективностью работы специализированной машины Фибоначчи с рисунка 5.12. (Измерения интерпретируемой версии см. в упражнении 5.29.) Для процедуры Фибоначчи время растет в нелинейной зависимости от n; следовательно, отношение числа стековых операций не будет приближаться к независимому от n приделу.

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

В этом разделе рассказывалось, как модифицировать вычислитель с явным управлением и позволить интерпретируемому коду вызывать скомпилированные процедуры. Покажите, как можно изменить компилятор и позволить скомпилированным процедурам вызывать не только элементарные и скомпилированные процедуры, но и интерпретируемые. При этом придется изменить compile-procedure-call так, чтобы обрабатывался случай составных (интерпретируемых) процедур. Проследите, чтобы обрабатывались все те же сочетания target и linkage, что и в compile-proc-appl. Для того, чтобы произвести собственно применение процедуры, код должен переходить на точку входа compound-apply вычислителя. На эту метку нельзя напрямую ссылаться из объектного кода (потому что ассемблер требует, чтобы все метки, на которые явно ссылается объектный код, в нем и определялись), так что придется добавить в машину-вычислитель специальный регистр compapp, в котором будет храниться эта точка входа, и команду для его инициализации:

(assign compapp (label compound-apply))

(branch (label external-entry)) ; переход, если установлен flag read-eval-print-loop

Чтобы проверить свой код, для начала определите процедуру f, которая вызывает процедуру g. С помощью compile-and-go скомпилируйте определение f и запустите вычислитель. Теперь, вводя код для интерпретации, определите g и попробуйте вызвать

f.

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

Интерфейс compile-and-go, реализованный в этом разделе, неудобен, поскольку компилятор можно вызвать только один раз (при запуске машины-вычислителя). Дополните интерфейс между компилятором и интерпретатором, введя примитив compile-and-run, который можно будет вызывать из вычислителя с явным управлением так:

;;; Ввод EC-Eval: (compile-and-run (define (factorial n)

(if (= n 1)

1

(* (factorial (- n 1)) n)))) ;;; Значение EC-Eval: ok

;;; Ввод EC-Eval:

(factorial 5)

;;; Значение EC-Eval:

120

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

В качестве альтернативы циклу ввод-выполнение-печать вычислителя с явным управлением, спроектируйте регистровую машину, которая работала бы в цикле ввод-компиляция-выполнение-печать. А именно, машина должна работать в цикле, при каждой итерации которого она считывает выражение, компилирует его, ассемблирует и исполняет получившийся код, и печатает результат. В нашей имитируемой среде это легко устроить, поскольку мы можем заставить compile и assemble работать как «операции регистровой машины».

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

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

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

Разработайте рудиментарную реализацию Scheme на C (или на другом низкоуровневом языке по Вашему выбору), переведя на C вычислитель с явными управлением из раздела 5.4. Для того, чтобы запустить этот код, Вам потребуется предоставить также функции для выделения памяти и прочую поддержку времени выполнения.

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

В качестве обратной задачи к упражнению 5.51, измените компилятор так, чтобы он компилировал процедуры Scheme в последовательности команд C. Скомпилируйте метацик-лический интерпретатор из раздела 4.1 и получите интерпретатор Scheme, написанный на C.

Литература

Abelson, Harold, Andrew Berlin, Jacob Katzenelson, William McAllister, Guiller-mo Rozas, Gerald Jay Sussman, and Jack Wisdom. 1992. The Supercomputer Toolkit: A general framework for special-purpose computing. International Journal of High-Speed Electronics 3(3):337-361.

Allen, John. 1978. Anatomy of Lisp. New York: McGraw-Hill.

ANSI X3.226-1994. American National Standard for Information Systems-Programming Language-Common Lisp.

Appel, Andrew W. 1987. Garbage collection can be faster than stack allocation. Information Processing Letters 25(4):275-279.

Backus, John. 1978. Can programming be liberated from the von Neumann style? Communications of the ACM 21(8):613-641.

Baker, Henry G., Jr. 1978. List processing in real time on a serial computer. Communications of the ACM 21(4):280-293.

Batali, John, Neil Mayle, Howard Shrobe, Gerald Jay Sussman, and Daniel Weise. 1982. The Scheme-81 architecture-System and chip. In Proceedings of the MIT Conference on Advanced Research in VLSI, edited by Paul Penfield, Jr. Dedham, MA: Artech House.

Borning, Alan. 1977. ThingLab-An object-oriented system for building simula-ti-ons using constraints. In Proceedings of the 5th International Joint Conference on Artificial Intelligence.

Borodin, Alan, and Ian Munro. 1975. The Computational Complexity of Algebraic and Numeric Problems. New York: American Elsevier.

Chaitin, Gregory J. 1975. Randomness and mathematical proof. Scientific American 232(5):47-52.

Church, Alonzo. 1941. The Calculi of Lambda-Conversion. Princeton, N.J.: Princeton University Press.

Clark, Keith L. 1978. Negation as failure. In Logic and Data Bases. New York:

Plenum Press, pp. 293-322.

Clinger, William. 1982. Nondeterministic call by need is neither lazy nor by name.