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

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

От интерпретатора не требуется никакого нового механизма связывания переменных. Выражение с let - это всего лишь синтаксический сахар для вызова lambda.

Из этой эквивалентности мы видим, что область определения переменной, введенной в let-выражении - тело let. Отсюда следует, что:

•Let позволяет связывать переменные сколь угодно близко к тому месту, где они используются. Например, если значение x равно 5, значение выражения

(+ (let ((x 3))

(+ x (* x 10)))

x)

равно 38. Значение x в теле let равно 3, так что значение let-выражения равно 33. С другой стороны, x как второй аргумент к внешнему + по-прежнему равен 5.

•Значения переменных вычисляются за пределами let. Это существенно, когда выражения, дающие значения локальным переменным, зависят от переменных, которые имеют те же имена, что и сами локальные переменные. Например, если значение x равно 2, выражение

(let ((x 3)

(y (+ x 2))) (* x y))

будет иметь значение 12, поскольку внутри тела let x будет равно 3, а y 4 (что равняется внешнему x плюс 2).

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

(define (f x y)

(define a (+ 1 (* x y))) (define b (- 1 y))

(+ (* x (square a))

(* y b) (* a b)))

В таких ситуациях, однако, мы предпочитаем использовать let, а define

54

писать только при определении локальных процедур.54

54Если мы хотим понимать внутренние определения настолько, чтобы быть уверенными, что программа действительно соответствует нашим намерениям, то нам требуется более сложная модель процесса вычислений, чем приведенная в этой главе. Однако с внутренними определениями процедур эти тонкости не возникают. К этому вопросу мы вернемся в разделе 4.1.6, после того, как больше узнаем о вычислении.

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

Допустим, мы определили процедуру

(define (f g)

(g 2))

Тогда мы имеем (f square)

4

(f (lambda (z) (* z (+ z 1)))) 6

Что случится, если мы (извращенно) попросим интерпретатор вычислить комбинацию (f f) ? Объясните.

1.3.3 Процедуры как обобщенные методы

Мы ввели составные процедуры в разделе 1.1.4 в качестве механизма для абстракции схем числовых операций, так, чтобы они были независимы от конкретных используемых чисел. С процедурами высших порядков, такими, как процедура integral из раздела 1.3.1, мы начали исследовать более мощный тип абстракции: процедуры, которые используются для выражения обобщенных методов вычисления, независимо от конкретных используемых функций. В этом разделе мы рассмотрим два более подробных примера - общие методы нахождения нулей и неподвижных точек функций, - и покажем, как эти методы могут быть прямо выражены в виде процедур.

Нахождение корней уравнений методом половинного деления

Метод половинного деления (half-interval method) - это простой, но мощный способ нахождения корней уравнения f (х) = 0, где f - непрерывная функция. Идея состоит в том, что если нам даны такие точки а и b, что f(а) < 0 < f(b), то функция f должна иметь по крайней мере один ноль на отрезке между а и b. Чтобы найти его, возьмем x, равное среднему между а и b, и вычислим f (х). Если f (х) > 0, то f должна иметь ноль на отрезке между а и х. Если f (х) < 0, то f должна иметь ноль на отрезке между х и b. Продолжая таким образом, мы сможем находить все более узкие интервалы, на которых f должна иметь ноль. Когда мы дойдем до точки, где этот интервал достаточно мал, процесс останавливается. Поскольку интервал неопределенности уменьшается вдвое на каждом шаге процесса, число требуемых шагов растет как 0(log(L/T)), где L есть длина исходного интервала, а T есть допуск ошибки (то есть размер интервала, который мы считаем «достаточно малым»). Вот процедура, которая реализует эту стратегию:

(define (search f neg-point pos-point)

(let ((midpoint (average neg-point pos-point))) (if (close-enough? neg-point pos-point) midpoint

(let ((test-value (f midpoint))) (cond ((positive? test-value)

(search f neg-point midpoint)) ((negative? test-value)

(search f midpoint pos-point)) (else midpoint))))))

Мы предполагаем, что вначале нам дается функция f и две точки, в одной из которых значение функции отрицательно, в другой положительно. Сначала мы вычисляем среднее между двумя краями интервала. Затем мы проверяем, не является ли интервал уже достаточно малым, и если да, сразу возвращаем среднюю точку как ответ. Если нет, мы вычисляем значение f в средней точке. Если это значение положительно, мы продолжаем процесс с интервалом от исходной отрицательной точки до средней точки. Если значение в средней точке отрицательно, мы продолжаем процесс с интервалом от средней точки до исходной положительной точки. Наконец, существует возможность, что значение в средней точке в точности равно 0, и тогда средняя точка и есть тот корень, который мы ищем.

Чтобы проверить, достаточно ли близки концы интервала, мы можем взять процедуру, подобную той, которая используется в разделе 1.1.7 при вычислении

« 55

квадратных корней:

(define (close-enough? x y) (< (abs (- x y)) 0.001))

Использовать процедуру search непосредственно ужасно неудобно, поскольку случайно мы можем дать ей точки, в которых значения f не имеют нужных знаков, и в этом случае мы получим неправильный ответ. Вместо этого мы будем использовать search посредством следующей процедуры, которая проверяет, который конец интервала имеет положительное, а который отрицательное значение, и соответствующим образом зовет search. Если на обоих концах интервала функция имеет одинаковый знак, метод половинного деления использовать нельзя, и тогда процедура сообщает об ошибке.56

(define (half-interval-method f a b)

(let ((a-value (f a)) (b-value (f b)))

(cond ((and (negative? a-value) (positive? b-value))

(search f a b)) ((and (negative? b-value) (positive? a-value))

(search f b a)) (else

(error "У аргументов не разные знаки " a b)))))

В следующем примере метод половинного деления используется, чтобы вычислить п как корень уравнения sinx = 0, лежащий между 2 и 4.

(half-interval-method sin 2.0 4.0) 3.14111328125

Во втором примере через метод половинного деления ищется корень уравнения x3 - 2x - 3 = 0, расположенный между 1 и 2:

55Мы использовали 0.001 как достаточно «малое» число, чтобы указать допустимую ошибку вычисления. Подходящий допуск в настоящих вычислениях зависит от решаемой задачи, ограничений компьютера и алгоритма. Часто это весьма тонкий вопрос, в котором требуется помощь специалиста по численному анализу или волшебника какого-нибудь другого рода.

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