(prompt-for-input input-prompt) (let ((input (read)))

(let ((output (eval input the-global-environment)))

(announce-output output-prompt)

(user-print output))) (driver-loop))

(define (prompt-for-input string)

(newline) (newline) (display string) (newline))

(define (announce-output string)

(newline) (display string) (newline))

Мы пользуемся специальной процедурой вывода user-print, чтобы не печатать окружение составных процедур, которое может быть очень длинным списком, и даже может содержать циклы.

(define (user-print object)

(if (compound-procedure? object)

(display (list compound-procedure

(procedure-parameters object) (procedure-body object) <procedure-env>)) (display object)))

Теперь для запуска интерпретатора нам остается только проинициализиро-вать глобальное окружение и войти в управляющий цикл. Вот пример работы интерпретатора:

(define the-global-environment (setup-environment))

(driver-loop)

;;; Ввод M-Eval: (define (append x y)

(if (null? x) y

(cons (car x)

(append (cdr x) y))))

;;; Значение M-Eval: ok

;;; Ввод M-Eval:

(append (a b c) (d e f))

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

(a b c d e f)

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

Ева Лу Атор и Хьюго Дум экспериментируют с метациклическим интерпретатором каждый по отдельности. Ева вводит определение map и запускает несколько тестовых программ с его использованием. Они замечательно работают. Хьюго, со своей стороны, ввел системную версию map как примитив метациклического интерпретатора. Когда он пытается его выполнить, все ломается самым ужасным образом. Объясните, почему у Хьюго map не работает, а у Евы работает.

720

Рис. 4.2: Программа вычисления факториала, изображенная в виде абстрактной машины.

4.1.5 Данные как программы

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

(define (factorial n) (if (= n 1) 1

(* (factorial (- n 1)) n)))

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

Подобным образом, мы можем рассматривать вычислитель как особого рода машину, которой подается в виде сырья описание другой машины. Обработав свои входные данные, вычислитель перестраивает себя так, чтобы моделировать описываемую машину. Например, если мы скормим вычислителю определение factorial, как показано на рисунке 4.3, он сможет считать факториалы.

С этой точки зрения, наш вычислитель-интерпретатор выглядит как универсальная машина (universal machine). Она имитирует другие машины, представленные в виде Лисп-программ.19 Это замечательное устройство. Попробуйте представить себе аналогичный вычислитель для электрических схем. Это

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

6

r Г

(define (factorial (if (= n 1)\s

1

ч (* (factorial (- n 1)) n)))

Рис. 4.3: Вычислитель, моделирующий факториальную машину.

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

20

простая.20

Еще одна замечательная черта интерпретатора заключается в том, что он служит мостом между объектами данных, которыми манипулирует язык программирования, и самим языком. Представим себе, что работает программа интерпретатора (реализованная на Лиспе), и что пользователь вводит выражения в интерпретатор и рассматривает результаты. С точки зрения пользователя, входное выражение вроде (* x x) является выражением языка программирования, которое интерпретатор должен выполнить. Однако с точки зрения интерпретатора это всего лишь список (в данном случае, список из трех символов: * , x и x), с которым нужно работать по ясно очерченным правилам.

любую программу на Лиспе. Главная идея здесь состоит в том, что любой вычислитель способен имитировать любой другой. Таким образом, понятие «того, что в принципе можно вычислить» (если не принимать во внимание практические вопросы времени и памяти, потребной для вычисления), независимо от языка компьютера и выражает глубинное понятие вычислимости (computability). Это впервые было ясно показано Аланом М. Тьюрингом (1912-1954), чья статья 1936 года заложила основы теоретической информатики. В этой статье Тьюринг представил простую модель вычислений, - теперь известную как машина Тьюринга (Turing machine), - и утверждал, что любой «эффективный процесс» выразим в виде программы для такой машины. (Этот аргумент известен как тезис Чёрча-Тьюринга (Church-Turing thesis).) Затем Тьюринг реализовал универсальную машину, т. е. машину Тьюринга, которая работает как вычислитель для программ машин Тьюринга. При помощи этой схемы рассуждений он показал, что существуют коррекно поставленные задачи, которые не могут быть решены машиной Тьюринга (см. упражнение 4.15), а следовательно не могут быть сформулированы в виде «эффективного процесса». Позднее Тьюринг внес фундаментальный вклад и в развитие практической информатики. Например, ему принадлежит идея структурирования программ с помощью подпрограмм общего назначения. Биографию Тьюринга можно найти в Hodges 1983.

20Некоторые считают странным, что вычислитель, реализованный с помощью относительно простой процедуры, способен имитировать программы, более сложные, чем он сам. Существование универсальной машины-вычислителя - глубокое и важное свойство вычисления. Теория рекурсии (recursion theory), отрасль математической логики, занимается логическими пределами вычислимости. В прекрасной книге Дугласа Хофштадтера «Гёдель, Эшер, Бах» (Hofstadter 1979) исследуются некоторые из этих идей.