Измените преобразование let->combination из упражнения 4.6 так, чтобы оно поддерживало именованный let.

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

Во многих языках имеются различные конструкции для построения циклов, например, do, for, while и until. В Scheme итеративные процессы можно выразить через обычные вызовы процедур, так что особые конструкции не дают никакого существенного выигрыша в вычислительной мощности. С другой стороны, часто они удобны. Придумайте какие-нибудь конструкции для итерации, дайте примеры их использования и покажите, как их реализовать в виде производных выражений.

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

При помощи абстракции данных мы смогли написать процедуру eval так, что она не зависит от конкретного синтаксиса интерпретируемого языка. Чтобы проиллюстрировать это свойство, разработайте новый синтаксис для Scheme, изменив процедуры из этого раздела и ничего не трогая в eval и apply.

4.1.3 Структуры данных интерпретатора

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

Проверка предикатов

В условных выражениях мы воспринимаем в качестве истины все, кроме специального ложного объекта false.

(define (true? x)

(not (eq? x false)))

(define (false? x) (eq? x false))

Представление процедур

Работая с примитивами, мы предполагаем, что у нас есть следующие процедуры:

•(apply-primitive-procedure (процедура) (аргументы))

применяет данную элементарную процедуру к значениям аргументов из списка (аргументы) и возвращает результат вызова.

•(primitive-procedure? (процедура)) проверяет, является ли (процедура) элементарной.

Эти механизмы работы с элементарными процедурами подробнее описаны в разделе 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 (переменная) (окружение)) возвращает значение, связанное с символом (переменная) в (окружении), либо сообщает об ошибке, если переменная не связана.

•(extend-environment (переменные) (значения) (исх-окр))

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

•(define-variable! (переменная) (значение) (окружение)) добавляет к первому кадру (окружения) новое связывание, которое сопоставляет (переменной) (значение).

•(set-variable-value! (переменная) (значение) (окружение))

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

Чтобы реализовать все эти операции, мы представляем окружение в виде списка кадров. Объемлющее окружение живет в cdr этого списка. Пустое окружение - это просто пустой список.

(define (enclosing-environment env) (cdr env))

(define (first-frame env) (car env))

(define the-empty-environment ())

Каждый кадр в окружении представляется в виде пары списков: список переменных, связанных в кадре, и список значений.14

14 В нижеследующем коде кадры не являются настоящей абстракцией данных: set-variable-value! и define-variable! явным образом изменяют значения в кадре при помощи set-car!. Назначение процедур работы с кадрами - сделать код операций над окружениями простым для чтения.

(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))) ((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))