Такая реализация обработки cond упрощает интерпретатор, поскольку она уменьшает количество особых форм, для которых требуется явно описывать процесс вычисления.

Мы включаем в интерпретатор синтаксические процедуры, которые определяют доступ к частям выражения cond, а также процедуру cond->if, которая преобразует выражения cond в выражения if. Анализ случаев начинается с cond и состоит из списка ветвей-вариантов вида предикат-действие. Вариант считается умолчательным, если его предикатом является символ else.12

(define (cond? exp) (tagged-list? exp cond))

(define (cond-clauses exp) (cdr exp))

(define (cond-else-clause? clause) (eq? (cond-predicate clause) else))

(define (cond-predicate clause) (car clause))

(define (cond-actions clause) (cdr clause))

(define (cond->if exp)

(expand-clauses (cond-clauses exp)))

(define (expand-clauses clauses) (if (null? clauses)

false; нет ветви else

(let ((first (car clauses)) (rest (cdr clauses))) (if (cond-else-clause? first)

(if (null? rest)

(sequence->exp (cond-actions first)) (error "Ветвь ELSE не последняя - COND->IF" clauses)) (make-if (cond-predicate first)

(sequence->exp (cond-actions first)) (expand-clauses rest))))))

Выражения (вроде cond), которые мы желаем реализовать через синтаксические преобразования, называются производными (derived expressions). Выражения let также являются производными (см. упражнение 4.6).13

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

Хьюго Дум хочет переупорядочить ветви cond так, чтобы ветвь для вызова процедур располагалась перед веткой для присваивания. Он утверждает, что при этом интерпретатор станет эффективнее: поскольку в программах обычно больше вызовов процедур,

12Значение выражения cond, когда все предикаты ложны, а вариант по умолчанию else отсутствует, в языке Scheme не определено; здесь мы решили сделать его ложным.

13Практические Лисп-системы предоставляют механизм, который дает пользователю возможность добавлять новые производные выражения и определять их значения через синтаксические преобразования, не внося изменений в вычислитель. Такое преобразование, определяемое пользователем, называется макрос (macro). Добавить простой механизм для определения макросов легко, однако в получающемся языке возникают сложные проблемы конфликта имен. Множество исследований посвящено поиску механизмов определения макросов, в которых такие проблемы не возникают. См., например, Kohlbecker 1986, Clinger and Rees 1991 и Hanson 1991.

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

a.Что за ошибка содержится в плане Хьюго? (Подсказка: что сделает его интерпретатор с выражением (define x 3)?)

b.Хьюго расстроен, что его план не сработал. Он готов пойти на любые жертвы, чтобы позволить интерпретатору распознавать вызовы процедур до того, как он проверяет все остальные типы выражений. Помогите ему, изменив синтаксис интерпретируемого языка так, чтобы вызовы процедур начинались с символа call. Например, вместо (factorial 3) нам теперь придется писать (call factorial 3), а вместо (+ 1 2) - (call + 1 2).

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

Перепишите eval так, чтобы диспетчеризация происходила в стиле, управляемом данными. Сравните результат с дифференцированием, управляемым данными, из упражнения 2.73. (Можно использовать car составного выражения в качестве типа этого выражения, так как это хорошо сочетается с синтаксисом, реализованным в этом разделе.)

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

Вспомним определения особых форм and и or из главы 1:

•and: выражения вычисляются слева направо. Если значение какого-то из них оказывается ложным, возвращается ложь; оставшиеся выражения не вычисляются. Если все выражения оказываются истинными, возвращается значение последнего из них. Если нет ни одного выражения, возвращается истина.

•or: выражения вычисляются слева направо. Если значение какого-то из них оказывается истинным, возвращается это значение; оставшиеся выражения не вычисляются. Если все выражения оказываются ложными, или нет ни одного выражения, возвращается ложь.

Введите and и or в качестве новых особых форм интерпретатора, определив соответствующие синтаксические процедуры и процедуры выполнения eval-and и eval-or. В качестве альтернативы покажите, как можно реализовать and и or в виде производных выражений.

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

В языке Scheme есть дополнительная разновидность синтаксиса вариантов cond, ((проверка) => (потребитель)). Если результат вычисления (проверки) оказывается истинным значением, то вычисляется (потребитель). Его значение должно быть одноместной процедурой; эта процедура вызывается со значением (проверки) в качестве аргумента, и результат этого вызова возвращается как значение выражения cond. Например,

(cond ((assoc b ((a 1) (b 2))) => cadr)

(else false))

имеет значение 2. Измените обработку cond так, чтобы она поддерживала этот расширенный синтаксис.

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

Выражения let производны, поскольку

(let (((пер1)(выр1)) ... ((перп){вырп))) (тело))

эквивалентно

((lambda ((пер1) ... (перп)) ( тело ) )

(выр1) ( вырп ) )

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

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

Особая форма let* подобна let, но только связывания переменных в let* происходят последовательно, и каждое следующее связывание происходит в окружении, где видны все предыдущие. Например,

(let* ((x 3)

(У (+ x 2)) (z (+ x y 5))) (* x z))

возвращает значение 39. Объясните, каким образом можно переписать выражение let* в виде набора вложенных выражений let, и напишите процедуру let*->nested-lets, которая проделывает это преобразование. Если мы уже реализовали let (упражнение 4.6) и хотим теперь расширить интерпретатор так, чтобы он обрабатывал let*, достаточно ли будет добавить в eval ветвь, в которой действием записано

(eval (let*->nested-lets exp) env)

или нужно явным образом преобразовывать let* в набор непроизводных выражений? Упражнение 4.8.

«Именованный let» - это вариант let, который имеет вид (let (переменная) (связывание) (тело))

(Связывание) и (тело) такие же, как и в обычном let, но только (переменная) связана в (теле) с процедурой, у которой тело (тело), а имена параметров - переменные в (связываниях). Таким образом, можно неоднократно выполнять (тело), вызывая процедуру по имени (переменная). Например, итеративную процедуру для порождения чисел Фибоначчи (раздел 1.2.2) можно переписать при помощи именованного let как

(define (fib n)

(let fib-iter ((a 1) (b 0)

(count n)) (if (= count 0)

b

(fib-iter (+ a b) a (- count 1)))))