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

Рассмотрим альтернативную стратегию обработки определений, которая переводит пример из текста в

(lambda (переменные)

(let ((u *unassigned*) (v *unassigned*)) (let ((a (e1)) (b (e2))) (set! u a)

(set! v b))

(e3)))

Здесь a и b представляют новые имена переменных, созданные интерпретатором, которые не встречаются в пользовательской программе. Рассмотрим процедуру solve из раздела 3.5.4:

(define (solve f y0 dt)

(define y (integral (delay dy) y0 dt)) (define dy (stream-map f y))

y)

Будет ли эта процедура работать, если внутренние определения преобразуются так, как предлагается в этом упражнении? А если так, как в тексте раздела? Объясните.

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

Бен Битобор, Лиза П. Хакер и Ева Лу Атор спорят о том, каким должен быть результат выражения

(let ((a 1)) (define (f x)

(define b (+ a x)) (define a 5)

(+ a b)) (f 10))

Бен говорит, что следует действовать согласно последовательному правилу для define: b равно 11, затем a определяется как 5, так что общий результат равен 16. Лиза возражает, что взаимная рекурсия требует правила одновременной сферы действия для внутренних определений и нет причин рассматривать имена процедур отдельно от прочих имен. То есть она выступает за механизм, реализованный в упражнении 4.16. При этом a оказывается не определено в момент, когда вычисляется b. Следовательно, по мнению Лизы, процедура должна выдавать ошибку. Ева не согласна с обоими. Она говорит, что если определения вправду должны считаться одновременными, то 5 как значение a должно использоваться при вычислении b. Следовательно, по мнению Евы, a должно равняться 5, b должно быть 15, а общий результат 20. Какую из этих точек зрения Вы поддерживаете (если у Вас нет своей четвертой)? Можете ли Вы придумать способ реализации внутренних определений, который бы работал так, как предлагает Ева?26

26Авторы MIT Scheme согласны с Лизой, и вот почему: в принципе права Ева - определения следует рассматривать как одновременные. Однако придумать универсальный эффективный механизм, который вел бы себя так, как она требует, кажется трудным. Если же такого механизма нет, то лучше порождать ошибку в сложных случаях параллельных определений (мнение Лизы), чем выдавать неверный ответ (как хочет Бен).

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

Поскольку внутренние определения выглядят последовательными, а на самом деле параллельны, некоторые предпочитают их вовсе избегать и вместо этого пользуются особой формой letrec. Letrec выглядит так же, как let, поэтому неудивительно, что переменные в нем связываются одновременно и имеют одинаковую для всех сферу действия. Можно переписать процедуру-пример f из текста без внутренних определений, но при этом в точности с тем же значением, так:

(define (f x)

(letrec ((even?

(lambda (n) (if (= n 0) true

(odd? (- n 1)))))

(odd?

(lambda (n) (if (= n 0) false

(even? (- n 1))))))

(остаток тела f))) Выражение letrec имеет вид

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

и является вариантом let, в котором выражения (еыр), устанавливающие начальные значения для переменных (пер), вычисляются в окружении, которое включает все связывания letrec. Это делает возможным рекурсию между связываниями, к примеру, взаимную рекурсию even? и odd? в последнем примере, или вычисление факториала 10 через

(letrec ((fact

(lambda (n) (if (= n 1)

1

(* n (fact (- n 1)))))))

(fact 10))

a.Реализуйте letrec как производное выражение, переводя выражение letrec в выражение let, как показано в тексте раздела или в упражнении 4.18. То есть переменные letrec должны создаваться в let, а затем получать значение через set! .

b.Хьюго Дум совсем запутался во всех этих внутренних определениях. Ему кажется, что если кому-то не нравятся define внутри процедуры, то пусть пользуются обычным let. Покажите, что в его рассуждениях неверно. Нарисуйте диаграмму, показывающую окружение, в котором выполняется (остаток тела f) во время вычисления выражения (f 5) , если f определена как в этом упражнении. Нарисуйте диаграмму окружений для того же вычисления, но только с let на месте letrec в определении f.

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

Как ни удивительно, интуитивная догадка Хьюго (в упражнении 4.20) оказывается верной. Действительно, можно строить рекурсивные процедуры без использования letrec (и даже без define), только способ это сделать намного тоньше, чем казалось Хьюго. Следующее выражение вычисляет факториал 10 с помощью рекурсивной процедуры:27

27В этом примере показан программистский трюк, позволяющий формулировать рекурсивные процедуры без помощи define. Самый общий прием такого рода называется Y-оператор (Y

((lambda (n)

((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1)

1

(* k (ft ft (- k 1)))))))

10)

a.Проверьте, что это выражение на самом деле считает факториалы (вычисляя его). Постройте аналогичное выражение для вычисления чисел Фибоначчи.

b.Рассмотрим следующую процедуру, включающую взаимно рекурсивные внутренние определения:

(define (f x)

(define (even? n)

(if (= n 0)

true

(odd? (- n 1))))

(define (odd? n)

(if (= n 0)

false

(even? (- n 1))))

(even? x))

Восстановите пропущенные фрагменты так, чтобы получилось альтернативное определение f, где нет ни внутренних определений, ни letrec:

(define (f x)

((lambda (even? odd?) (even? even? odd? x)) (lambda (ev? od? n)

(if (= n 0) true (od? ( ?? ) ( ?? ) ( ?? ) ))) (lambda (ev? od? n) (if (= n 0) false (ev? (??) (??) (??))))))

4.1.7 Отделение синтаксического анализа от выполнения

Написанный нами интерпретатор прост, но очень неэффективен, потому что синтаксический анализ выражений перемешан в нем с их выполнением. Таким образом, сколько раз выполняется программа, столько же раз анализируется ее синтаксис. Рассмотрим, например, вычисление (factorial 4), если дано следующее определение факториала:

(define (factorial n)

(if (= n 1) 1

(* (factorial (- n 1)) n)))

Каждый раз, когда вызывается factorial, интерпретатор должен определить, что тело процедуры является условным выражением, и извлечь его предикат. Только после этого он может вычислить предикат и поступить в

operator), и с его помощью можно реализовать рекурсию в «чистом Л-исчислении». (Подробности о лямбда-исчислении можно найти в Stoy 1977, а демонстрацию Y-оператора на Scheme в Gabriel 1988.)