Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 82
Текст из файла (страница 82)
Процедура apply метациклического интерпретатора (раздел 4.1.1) имитирует работу этого примитива.Наличие двух процедур с одинаковым именем ведет к технической проблеме при запуске интерпретатора,356Глава 4. Метаязыковая абстракция(define (apply-primitive-procedure proc args)(apply-in-underlying-scheme(primitive-implementation proc) args))Для удобства работы с метациклическим интерпретатором мы организуем управляющий цикл (driver loop), который моделирует цикл чтения-выполнения-печати нижележащей Лисп-системы.
Этот цикл печатает подсказку (prompt), считывает входноевыражение, вычисляет это выражение в глобальном окружении и распечатывает результат. Перед каждым результатом мы помещаем подсказку вывода (output prompt), чтобыотличить значение выражения от всего прочего, что может быть напечатано18 .(define input-prompt ";;; Ввод M-Eval:")(define output-prompt ";;; Значение M-Eval:")(define (driver-loop)(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)))поскольку определение apply метациклического интерпретатора загородит определение примитива.
Можноизбежать этого, переименовав метациклический apply, и избавиться таким образом от конфликта с именем элементарной процедуры. Мы же вместо этого приняли решение сохранить ссылку на исходный apply,выполнив(define apply-in-underlying-scheme apply)прежде, чем определили apply в интерпретаторе. Теперь мы можем обращаться к исходной версии apply поддругим именем.18 Элементарная процедура read ожидает ввода от пользователя и возвращает ближайшее полное выражение, которое он напечатает.
Например, если пользователь напечатает (+ 23 x), результатом read будеттрехэлементный список из символа +, числа 23 и символа x. Если пользователь введет ’x, результатом readбудет двухэлементный список из символа quote и символа x.4.1. Метациклический интерпретатор357Теперь для запуска интерпретатора нам остается только проинициализировать глобальное окружение и войти в управляющий цикл. Вот пример работы интерпретатора:(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 не работает, а у Евы работает.4.1.5. Данные как программыПри рассмотрении программы на Лиспе, вычисляющей лисповские выражения, можетбыть полезна аналогия. Одна из возможных точек зрения на значение программы состоитв том, что программа описывает абстрактную (возможно, бесконечно большую) машину.Рассмотрим, например, знакомую нам программу для вычисления факториалов:(define (factorial n)(if (= n 1)1(* (factorial (- n 1)) n)))Можно считать эту программу описанием машины, которая содержит узлы для вычитания, умножения и проверки на равенство, двухпозиционный переключатель и еще однуфакториал-машину. (Факториал-машина получается бесконечной, поскольку она содержит другую факториал-машину внутри себя.) На рисунке 4.2 изображена потоковаядиаграмма факториал-машины, которая показывает, как спаяны ее части.Подобным образом, мы можем рассматривать вычислитель как особого рода машину,которой подается в виде сырья описание другой машины.
Обработав свои входные данные, вычислитель перестраивает себя так, чтобы моделировать описываемую машину.Глава 4. Метаязыковая абстракция358factorial611:=720*factorial1Рис. 4.2. Программа вычисления факториала, изображенная в виде абстрактной машины.6eval720(define (factorial n)(if (= n 1)1(* (factorial (- n 1)) n)))Рис. 4.3. Вычислитель, моделирующий факториальную машину.4.1. Метациклический интерпретатор359Например, если мы скормим вычислителю определение factorial, как показано нарисунке 4.3, он сможет считать факториалы.С этой точки зрения, наш вычислитель-интерпретатор выглядит как универсальнаямашина (universal machine). Она имитирует другие машины, представленные в видеЛисп-программ19 . Это замечательное устройство.
Попробуйте представить себе аналогичный вычислитель для электрических схем. Это была бы схема, которой на вход поступает сигнал, кодирующий устройство какой-то другой схемы, например, фильтра.Восприняв этот вход, наша схема-вычислитель стала бы работать как фильтр, соответствующий описанию. Такая универсальная электрическая схема имеет почти невообразимую сложность. Удивительно, что интерпретатор программ — сам по себе программадовольно простая20 .Еще одна замечательная черта интерпретатора заключается в том, что он служитмостом между объектами данных, которыми манипулирует язык программирования, исамим языком.
Представим себе, что работает программа интерпретатора (реализованная на Лиспе), и что пользователь вводит выражения в интерпретатор и рассматриваетрезультаты. С точки зрения пользователя, входное выражение вроде (* x x) являетсявыражением языка программирования, которое интерпретатор должен выполнить. Однако с точки зрения интерпретатора это всего лишь список (в данном случае, список изтрех символов: *, x и x), с которым нужно работать по ясно очерченным правилам.Нас не должно смущать, что программы пользователя являются данными для интерпретатора.
На самом деле, иногда бывает удобно игнорировать это различие и, предоставляя пользовательским программам доступ к eval, давать пользователю возможностьявным образом вычислить объект данных как выражение Лиспа. Во многих диалектахЛиспа имеется элементарная процедура eval, которая в виде аргументов берет выражение и окружение, и вычисляет выражение в указанном окружении21 . Таким образом,19 То, что машины описаны на языке Лисп, несущественно.
Если дать нашему интерпретатору программу наЛиспе, которая ведет себя как вычислитель для какого-нибудь другого языка, скажем, Си, то вычислитель дляЛиспа будет имитировать вычислитель для Си, который, в свою очередь, способен сымитировать любую машину, описанную в виде программы на Си. Подобным образом, написание интерпретатора Лиспа на Си порождаетпрограмму на Си, способную выполнить любую программу на Лиспе. Главная идея здесь состоит в том, чтолюбой вычислитель способен имитировать любой другой. Таким образом, понятие «того, что в принципе можновычислить» (если не принимать во внимание практические вопросы времени и памяти, потребной для вычисления), независимо от языка компьютера и выражает глубинное понятие вычислимости (computability).
Этовпервые было ясно показано Аланом М. Тьюрингом (1912-1954), чья статья 1936 года заложила основы теоретической информатики. В этой статье Тьюринг представил простую модель вычислений, — теперь известнуюкак машина Тьюринга (Turing machine), — и утверждал, что любой «эффективный процесс» выразим в видепрограммы для такой машины. (Этот аргумент известен как тезис Чёрча-Тьюринга (Church-Turing thesis).)Затем Тьюринг реализовал универсальную машину, т. е. машину Тьюринга, которая работает как вычислительдля программ машин Тьюринга.
При помощи этой схемы рассуждений он показал, что существуют коррекнопоставленные задачи, которые не могут быть решены машиной Тьюринга (см. упражнение 4.15), а следовательно не могут быть сформулированы в виде «эффективного процесса». Позднее Тьюринг внес фундаментальныйвклад и в развитие практической информатики. Например, ему принадлежит идея структурирования программс помощью подпрограмм общего назначения. Биографию Тьюринга можно найти в Hodges 1983.20 Некоторые считают странным, что вычислитель, реализованный с помощью относительно простой процедуры, способен имитировать программы, более сложные, чем он сам. Существование универсальной машинывычислителя — глубокое и важное свойство вычисления.
Теория рекурсии (recursion theory), отрасль математической логики, занимается логическими пределами вычислимости. В прекрасной книге Дугласа Хофштадтера«Гёдель, Эшер, Бах» (Hofstadter 1979) исследуются некоторые из этих идей.21 Предупреждение: эта процедура eval — не то же самое, что процедура eval, реализованная нами вразделе 4.1.1, потому что она работает с настоящими окружениями, а не с искусственными структурами360Глава 4. Метаязыковая абстракциякак(eval ’(* 5 5) user-initial-environment)так и(eval (cons ’* (list 5 5)) user-initial-environment)возвращают результат 2522 .Упражнение 4.15.Если даны одноаргументная процедура p и объект a, то говорят, что p «останавливается» на a,если выражение (p a) возвращает значение (а не печатает сообщение об ошибке или выполняетсявечно).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
