Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 81
Текст из файла (страница 81)
В Scheme итеративные процессы можно выразить через обычные вызовы процедур, так что особые конструкции не дают никакого существенного выигрыша в вычислительноймощности. С другой стороны, часто они удобны. Придумайте какие-нибудь конструкции для итерации, дайте примеры их использования и покажите, как их реализовать в виде производныхвыражений.Упражнение 4.10.При помощи абстракции данных мы смогли написать процедуру eval так, что она не зависитот конкретного синтаксиса интерпретируемого языка. Чтобы проиллюстрировать это свойство,разработайте новый синтаксис для Scheme, изменив процедуры из этого раздела и ничего нетрогая в eval и apply.4.1.3. Структуры данных интерпретатораПомимо внешнего синтаксиса выражений, реализация интерпретатора должна определить также внутренние структуры данных, с которыми она работает во время выполнения программы, в частности, представление процедур и окружений, а также истинныхи ложных значений.Проверка предикатовВ условных выражениях мы воспринимаем в качестве истины все, кроме специального ложного объекта false.(define (true? x)(not (eq? x false)))(define (false? x)(eq? x false))4.1.
Метациклический интерпретатор351Представление процедурРаботая с примитивами, мы предполагаем, что у нас есть следующие процедуры:• (apply-primitive-procedure hпроцедураi hаргументыi)применяет данную элементарную процедуру к значениям аргументов из спискаhаргументыi и возвращает результат вызова.• (primitive-procedure? hпроцедураi)проверяет, является ли hпроцедураi элементарной.Эти механизмы работы с элементарными процедурами подробнее описаны в разделе 4.1.4.Составная процедура строится из параметров, те́ла процедуры и окружения при помощи конструктора make-procedure:(define (make-procedure parameters body env)(list ’procedure parameters body env))(define (compound-procedure? p)(tagged-list? p ’procedure))(define (procedure-parameters p) (cadr p))(define (procedure-body p) (caddr p))(define (procedure-environment p) (cadddr p))Действия над окружениямиИнтерпретатору нужно иметь несколько операций, действующих над окружениями.Как объясняется в разделе 3.2, окружение представляет собой последовательность кадров, а каждый кадр является таблицей связываний, соотносящих переменные с их значениями.
Для работы с окружениями мы используем следующие операции:• (lookup-variable-value hпеременнаяi hокружениеi) возвращает значение, связанное с символом hпеременнаяi в hокруженииi, либо сообщает об ошибке,если переменная не связана.• (extend-environment hпеременныеi hзначенияi hисх-окрi) возвращаетновое окружение, состоящее из нового кадра, в котором символы из списка hпеременныеiсвязаны с соответствующими элементами списка hзначенияi, а объемлющим окружением является окружение hисх-окрi.• (define-variable! hпеременнаяi hзначениеi hокружениеi) добавляет кпервому кадру hокруженияi новое связывание, которое сопоставляет hпеременнойihзначениеi.• (set-variable-value! hпеременнаяi hзначениеi hокружениеi) изменяетсвязывание hпеременнойi в hокруженииi так, что в дальнейшем ей будет соответствоватьhзначениеi, либо сообщает об ошибке, если переменная не связана.352Глава 4.
Метаязыковая абстракцияЧтобы реализовать все эти операции, мы представляем окружение в виде спискакадров. Объемлющее окружение живет в cdr этого списка. Пустое окружение — этопросто пустой список.(define (enclosing-environment env) (cdr env))(define (first-frame env) (car env))(define the-empty-environment ’())Каждый кадр в окружении представляется в виде пары списков: список переменных,связанных в кадре, и список значений14.(define (make-frame variables values)(cons variables values))(define (frame-variables frame) (car frame))(define (frame-values frame) (cdr frame))(define (add-binding-to-frame! var val frame)(set-car! frame (cons var (car frame)))(set-cdr! frame (cons val (cdr frame))))Чтобы расширить окружение новым кадром, который связывает переменные со значениями, мы порождаем кадр, который состоит из списка переменных и списка значений,и присоединяем его к окружению.
Если количество переменных и количество значенийне совпадают, сообщаем об ошибке.(define (extend-environment vars vals base-env)(if (= (length vars) (length vals))(cons (make-frame vars vals) base-env)(if (< (length vars) (length vals))(error "Получено слишком много аргументов" vars vals)(error "Получено слишком мало аргументов" vars vals))))Чтобы найти переменную в окружении, мы просматриваем список переменных в первом кадре. Если находим нужную переменную, то возвращаем соответствующий элементсписка значений. Если мы не находим переменную в текущем кадре, то ищем в объемлющем окружении, и так далее.
Если мы добираемся до пустого окружения, нужносообщить об ошибке «неопределенная переменная».(define (lookup-variable-value var env)(define (env-loop env)(define (scan vars vals)(cond ((null? vars)(env-loop (enclosing-environment env)))14 В нижеследующем коде кадры не являются настоящей абстракцией данных: set-variable-value! иdefine-variable! явным образом изменяют значения в кадре при помощи set-car!. Назначение процедурработы с кадрами — сделать код операций над окружениями простым для чтения.4.1. Метациклический интерпретатор353((eq? var (car vars))(car vals))(else (scan (cdr vars) (cdr vals)))))(if (eq? env the-empty-environment)(error "Несвязанная переменная" var)(let ((frame (first-frame env)))(scan (frame-variables frame)(frame-values frame)))))(env-loop env))Чтобы присвоить переменной новое значение в указанном окружении, мы ищем переменную, точно так же, как в lookup-variable-value, и изменяем соответствующеезначение, когда его находим.(define (set-variable-value! var val env)(define (env-loop env)(define (scan vars vals)(cond ((null? vars)(env-loop (enclosing-environment env)))((eq? var (car vars))(set-car! vals val))(else (scan (cdr vars) (cdr vals)))))(if (eq? env the-empty-environment)(error "Несвязанная переменная -- SET!" var)(let ((frame (first-frame env)))(scan (frame-variables frame)(frame-values frame)))))(env-loop env))Чтобы определить переменную, мы просматриваем первый кадр в поисках связываниядля нее, и изменяем связывание, если его удается найти (так же, как в set-variablevalue!).
Если связывания не существует, мы присоединяем его к первому кадру.(define (define-variable! var val env)(let ((frame (first-frame env)))(define (scan vars vals)(cond ((null? vars)(add-binding-to-frame! var val frame))((eq? var (car vars))(set-car! vals val))(else (scan (cdr vars) (cdr vals)))))(scan (frame-variables frame)(frame-values frame))))Описанный здесь метод — только один из многих способов представления окружений. Поскольку мы при помощи абстракции данных отделили конкретную реализациюот остальных частей интерпретатора, при желании мы можем сменить представлениеокружений.
(См. упражнение 4.11.) В Лисп-системе промышленного качества быстрота операций над окружениями — особенно обращения к переменной — очень сильновлияет на общую производительность. Представление, описанное здесь, при всей своей354Глава 4. Метаязыковая абстракцияконцептуальной простоте неэффективно и, скорее всего, его не стали бы использовать врабочей системе15 .Упражнение 4.11.Вместо того, чтобы представлять кадр в виде списка списков, его можно представить как списоксвязываний, где каждое связывание является парой из имени и значения. Перепишите операции сокружениями в соответствии с этим альтернативным представлением.Упражнение 4.12.Процедуры set-variable-value!, define-variable! и lookup-variable-value можновыразить посредством более абстрактных процедур для просмотра структуры окружений.
Определите абстракции, которые фиксируют общую схему поведения, и с их помощью перепишите этитри процедуры.Упражнение 4.13.Scheme позволяет создавать новые связывания через define, но не дает никакого способа избавиться от связывания. Реализуйте в интерпретаторе особую форму make-unbound!, котораяизымает связывание данного символа из окружения, в котором make-unbound! выполняется.Задача определена не до конца. Например, нужно ли удалять связывания в других кадрах, кромепервого? Дополните спецификацию и объясните свой выбор вариантов.4.1.4.
Выполнение интерпретатора как программыНаписав интерпретатор, мы получаем в руки описание (выраженное на Лиспе) процесса вычисления лисповских выражений. Одно из преимуществ наличия описания ввиде программы в том, что эту программу можно запустить. У нас внутри Лиспа естьработающая модель того, как сам Лисп вычисляет выражения. Она может служить средой для экспериментов с правилами вычисления, и дальше в этой главе мы такимиэкспериментами и займемся.Программа-вычислитель в конце концов сводит выражения к применению элементарных процедур.
Следовательно, единственное, что нам требуется для запуска интерпретатора, — создать механизм, который обращается к нижележащей Лисп-системе имоделирует вызовы элементарных процедур.Нам нужно иметь связывание для каждого имени элементарной процедуры, чтобы,когда eval выполняет вызов примитива, у него был объект, который можно передать вapply. Поэтому мы выстраиваем глобальное окружение, связывающее особые объектыс именами элементарных процедур, которые могут появляться в вычисляемых нами выражениях. Кроме того, глобальное окружение включает связывания для символов trueи false, так что их можно использовать как переменные в вычисляемых выражениях.(define (setup-environment)(let ((initial-env15 Недостаток этого представления (как и варианта из упражнения 4.11) состоит в том, что вычислителюможет понадобиться просматривать слишком много кадров, чтобы найти связывание конкретной переменной.(Такой подход называется глубокое связывание (deep binding).) Один из способов избежать такой потерипроизводительности — использовать стратегию под названием лексическая адресация (lexical addressing),которая обсуждается в разделе 5.5.6.4.1.
Метациклический интерпретатор355(extend-environment (primitive-procedure-names)(primitive-procedure-objects)the-empty-environment)))(define-variable! ’true true initial-env)(define-variable! ’false false initial-env)initial-env))(define the-global-environment (setup-environment))Как именно мы представляем объекты-элементарные процедуры, не имеет значения.Требуется только, чтобы их можно было распознавать и применять, вызывая процедурыprimitive-procedure? и apply-primitive-procedure. Мы решили представлять примитивы в виде списка, начинающегося с символа primitive и содержащегопроцедуру нижележащего Лиспа, которая реализует данный примитив.(define (primitive-procedure? proc)(tagged-list? proc ’primitive))(define (primitive-implementation proc) (cadr proc))Setup-environment получит имена и реализации элементарных процедур из списка16 .(define primitive-procedures(list (list ’car car)(list ’cdr cdr)(list ’cons cons)(list ’null? null?)другие примитивы))(define (primitive-procedure-names)(map carprimitive-procedures))(define (primitive-procedure-objects)(map (lambda (proc) (list ’primitive (cadr proc)))primitive-procedures))Чтобы вызвать элементарную процедуру, мы просто применяем процедуруреализацию к аргументам, используя нижележащую Лисп-систему17 .16 Любую процедуру, определенную в нижележащем Лиспе, можно использовать как примитив для метациклического интерпретатора.
Имя примитива, установленного в интерпретаторе, не обязательно должно совпадатьс именем его реализации в нижележащем Лиспе; здесь имена одни и те же потому, что метациклический интерпретатор реализует саму Scheme. Так, например, мы могли бы написать в списке primitive-proceduresчто-нибудь вроде (list ’first car) или (list ’square (lambda (x) (* x x))).17 Apply-in-underlying-scheme — это процедура apply, которой мы пользовались в предыдущих главах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
