Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 80
Текст из файла (страница 80)
hпараметрni)hтелоi)Вторая форма (стандартное определение процедуры) является синтаксическим сахаромдля(define hпеременнаяi(lambda (hпараметр1 i ... hпараметрni)hтелоi))Соответствующие синтаксические процедуры выглядят так:(define (definition? exp)(tagged-list? exp ’define))(define (definition-variable exp)(if (symbol? (cadr exp))9 В разделе 2.3.1 упоминается, что интерпретатор рассматривает закавыченное выражение как список, начинающийся с quote, даже если выражение напечатано через знак кавычки. Например, выражение ’a будетвыглядеть для интерпретатора как (quote a). См. упражнение 2.55.4.1. Метациклический интерпретатор345(cadr exp)(caadr exp)))(define (definition-value exp)(if (symbol? (cadr exp))(caddr exp)(make-lambda (cdadr exp)(cddr exp))))• Lambda-выражения являются списками, которые начинаются с символа lambda:(define (lambda? exp) (tagged-list? exp ’lambda))(define (lambda-parameters exp) (cadr exp))(define (lambda-body exp) (cddr exp))Мы приводим также конструктор для lambda-выражений.
Он используется в вышеприведенной процедуре definition-value:(define (make-lambda parameters body)(cons ’lambda (cons parameters body)))• Условные выражения начинаются с if и имеют предикат, следствие и (необязательную) альтернативу. Если в выражении нет части-альтернативы, мы указываем в еекачестве false10 .(define (if? exp) (tagged-list? exp ’if))(define (if-predicate exp) (cadr exp))(define (if-consequent exp) (caddr exp))(define (if-alternative exp)(if (not (null? (cdddr exp)))(cadddr exp)’false))Мы предоставляем также конструктор для if-выражений.
Его будет использовать процедура cond->if для преобразования выражений cond в выражения if:(define (make-if predicate consequent alternative)(list ’if predicate consequent alternative))10 Значение выражения if в случае, когда предикат ложен, а альтернатива отсутствует, в Scheme не определено; здесь мы решили сделать его ложным. Мы будем поддерживать переменные true и false в выполняемыхвыражениях путем связывания их в глобальном окружении. См. раздел 4.1.4.346Глава 4. Метаязыковая абстракция• Begin упаковывает последовательность выражений в одно выражение. В синтаксические операции над выражениями begin мы включаем извлечение самой последовательности из выражения begin, а также селекторы, которые возвращают первое выражение и остаток выражений в последовательности11.(define (begin? exp) (tagged-list? exp ’begin))(define (begin-actions exp) (cdr exp))(define (last-exp? seq) (null? (cdr seq)))(define (first-exp seq) (car seq))(define (rest-exps seq) (cdr seq))Кроме того, мы даем конструктор sequence->exp (для использования в процедуреcond->if), который преобразует последовательность в единое выражение, используя,если надо, begin:(define (sequence->exp seq)(cond ((null? seq) seq)((last-exp? seq) (first-exp seq))(else (make-begin seq))))(define (make-begin seq) (cons ’begin seq))• Вызов процедуры — это любое составное выражение, не попадающее ни в один изперечисленных типов.
Его car — это оператор, а cdr — список операндов:(define (application? exp) (pair? exp))(define (operator exp) (car exp))(define (operands exp) (cdr exp))(define (no-operands? ops) (null? ops))(define (first-operand ops) (car ops))(define (rest-operands ops) (cdr ops))Производные выраженияНекоторые особые формы языка можно определить через выражения, включающиедругие особые формы, вместо того, чтобы задавать их напрямую. Как пример рассмотрим cond, который можно реализовать как гнездо выражений if. Например, задачувычисления выражения11 Эти селекторы для списка выражений, а также соответствующие им селекторы для списка операндов,не предназначаются для абстракции данных.
Они введены в качестве мнемонических имен для основныхсписковых операций, чтобы легче было понимать вычислитель с явным управлением из раздела 5.4.4.1. Метациклический интерпретатор347(cond ((> x 0) x)((= x 0) (display ’zero) 0)(else (- x)))можно свести к задаче вычисления следующего выражения, состоящего из форм if иbegin:(if (> x 0)x(if (= x 0)(begin (display ’zero)0)(- x)))Такая реализация обработки cond упрощает интерпретатор, поскольку она уменьшаетколичество особых форм, для которых требуется явно описывать процесс вычисления.Мы включаем в интерпретатор синтаксические процедуры, которые определяют доступ к частям выражения cond, а также процедуру cond->if, которая преобразует выражения cond в выражения if.
Анализ случаев начинается с cond и состоит из спискаветвей-вариантов вида предикат-действие. Вариант считается умолчательным, если егопредикатом является символ else12 .(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)12 Значение выражения cond, когда все предикаты ложны, а вариант по умолчанию else отсутствует, вязыке Scheme не определено; здесь мы решили сделать его ложным.Глава 4.
Метаязыковая абстракция348(sequence->exp (cond-actions first))(expand-clauses rest))))))Выражения (вроде cond), которые мы желаем реализовать через синтаксические преобразования, называются производными (derived expressions). Выражения let такжеявляются производными (см. упражнение 4.6)13 .Упражнение 4.2.Хьюго Дум хочет переупорядочить ветви cond так, чтобы ветвь для вызова процедур располагалась перед веткой для присваивания. Он утверждает, что при этом интерпретатор станетэффективнее: поскольку в программах обычно больше вызовов процедур, чем присваиваний, определений и т.
д., его усовершенствованный eval обычно будет рассматривать меньше вариантов,чем исходный, при распознавании типа выражения.а. Что за ошибка содержится в плане Хьюго? (Подсказка: что сделает его интерпретатор свыражением (define x 3)?)б. Хьюго расстроен, что его план не сработал. Он готов пойти на любые жертвы, чтобы позволить интерпретатору распознавать вызовы процедур до того, как он проверяет все остальныетипы выражений. Помогите ему, изменив синтаксис интерпретируемого языка так, чтобы вызовыпроцедур начинались с символа 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 в виде производных выражений.13 Практические Лисп-системы предоставляют механизм, который дает пользователю возможность добавлятьновые производные выражения и определять их значения через синтаксические преобразования, не внося изменений в вычислитель. Такое преобразование, определяемое пользователем, называется макрос (macro).
Добавить простой механизм для определения макросов легко, однако в получающемся языке возникают сложныепроблемы конфликта имен. Множество исследований посвящено поиску механизмов определения макросов, вкоторых такие проблемы не возникают. См., например, Kohlbecker 1986, Clinger and Rees 1991 и Hanson 1991.4.1.
Метациклический интерпретатор349Упражнение 4.5.В языке Scheme есть дополнительная разновидность синтаксиса вариантов cond, (hпроверкаi => hпотребительi). Если результат вычисления hпроверкиi оказывается истинным значением, то вычисляется hпотребительi. Его значение должно быть одноместной процедурой; этапроцедура вызывается со значением hпроверкиi в качестве аргумента, и результат этого вызовавозвращается как значение выражения cond.
Например,(cond ((assoc ’b ’((a 1) (b 2))) => cadr)(else false))имеет значение 2. Измените обработку cond так, чтобы она поддерживала этот расширенныйсинтаксис.Упражнение 4.6.Выражения let производны, поскольку(let ((hпер1 ihвыр1 i) ... (hперn ihвырn i))hтелоi)эквивалентно((lambda (hпер1 i ... hперn i)hтелоi)hвыр1 i...hвырn i)Напишите синтаксическое преобразование let->combination, которое сводит вычисление letвыражений к вычислению комбинаций указанного вида, и добавьте соответствующую ветку дляобработки let к eval.Упражнение 4.7.Особая форма let* подобна let, но только связывания переменных в let* происходят последовательно, и каждое следующее связывание происходит в окружении, где видны все предыдущие.Например,(let* ((x 3)(y (+ 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 hпеременнаяi hсвязываниеi hтелоi)350Глава 4.
Метаязыковая абстракцияhСвязываниеi и hтелоi такие же, как и в обычном let, но только hпеременнаяi связана в hтелеiс процедурой, у которой тело hтелоi, а имена параметров — переменные в hсвязыванияхi. Таким образом, можно неоднократно выполнять hтелоi, вызывая процедуру по имени hпеременнаяi.Например, итеративную процедуру для порождения чисел Фибоначчи (раздел 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)))))Измените преобразование let->combination из упражнения 4.6 так, чтобы оно поддерживалоименованный let.Упражнение 4.9.Во многих языках имеются различные конструкции для построения циклов, например, do, for,while и until.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
