Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 18
Текст из файла (страница 18)
hперn i)hтелоi)hвыр1 i ... hвырn i)От интерпретатора не требуется никакого нового механизма связывания переменных.Выражение с 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).78Глава 1.
Построение абстракций с помощью процедурИногда с тем же успехом, что и 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 .Упражнение 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 (x) = 0, где f — непрерывная функция.
Идея состоит втом, что если нам даны такие точки a и b, что f (a) < 0 < f (b), то функция f должна54 Если мы хотим понимать внутренние определения настолько, чтобы быть уверенными, что программадействительно соответствует нашим намерениям, то нам требуется более сложная модель процесса вычислений,чем приведенная в этой главе. Однако с внутренними определениями процедур эти тонкости не возникают.
Кэтому вопросу мы вернемся в разделе 4.1.6, после того, как больше узнаем о вычислении.1.3. Формулирование абстракций с помощью процедур высших порядков79иметь по крайней мере один ноль на отрезке между a и b. Чтобы найти его, возьмем x,равное среднему между a и b, и вычислим f (x). Если f (x) > 0, то f должна иметь нольна отрезке между a и x. Если f (x) < 0, то f должна иметь ноль на отрезке между x и b.Продолжая таким образом, мы сможем находить все более узкие интервалы, на которыхf должна иметь ноль.
Когда мы дойдем до точки, где этот интервал достаточно мал,процесс останавливается. Поскольку интервал неопределенности уменьшается вдвое накаждом шаге процесса, число требуемых шагов растет как Θ(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посредством следующей процедуры, которая проверяет, который конец интервала имеетположительное, а который отрицательное значение, и соответствующим образом зовет55 Мы использовали 0.001 как достаточно «малое» число, чтобы указать допустимую ошибку вычисления.Подходящий допуск в настоящих вычислениях зависит от решаемой задачи, ограничений компьютера и алгоритма. Часто это весьма тонкий вопрос, в котором требуется помощь специалиста по численному анализу иливолшебника какого-нибудь другого рода.Глава 1.
Построение абстракций с помощью процедур80search. Если на обоих концах интервала функция имеет одинаковый знак, метод половинного деления использовать нельзя, и тогда процедура сообщает об ошибке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)))))В следующем примере метод половинного деления используется, чтобы вычислить πкак корень уравнения sin x = 0, лежащий между 2 и 4.(half-interval-method sin 2.0 4.0)3.14111328125Во втором примере через метод половинного деления ищется корень уравнения x3 −2x − 3 = 0, расположенный между 1 и 2:(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))1.02.0)1.89306640625Нахождение неподвижных точек функцийЧисло x называется неподвижной точкой (fixed point) функции f , если оно удовлетворяет уравнению f (x) = x.
Для некоторых функций f можно найти неподвижнуюточку, начав с какого-то значения и применяя f многократно:f (x), f (f (x)), f (f (f (x))), . . .— пока значение не перестанет сильно изменяться. С помощью этой идеи мы можем составить процедуру fixed-point, которая в качестве аргументов принимает функцию иначальное значение и производит приближение к неподвижной точке функции. Мы многократно применяем функцию, пока не найдем два последовательных значения, разницамежду которыми меньше некоторой заданной чувствительности:(define tolerance 0.00001)(define (fixed-point f first-guess)(define (close-enough? v1 v2)(< (abs (- v1 v2)) tolerance))(define (try guess)56 Этого можно добиться с помощью процедуры error, которая в качестве аргументов принимает несколькозначений и печатает их как сообщение об ошибке.1.3.
Формулирование абстракций с помощью процедур высших порядков81(let ((next (f guess)))(if (close-enough? guess next)next(try next))))(try first-guess))Например, с помощью этого метода мы можем приближенно вычислить неподвижнуюточку функции косинус, начиная с 1 как стартового приближения57:(fixed-point cos 1.0).7390822985224023Подобным образом можно найти решение уравнения y = siny + cosy:(fixed-point (lambda (y) (+ (sin y) (cos y)))1.0).2587315962971173Процесс поиска неподвижной точки похож на процесс, с помощью которого мы искали квадратный корень в разделе 1.1.7. И тот, и другой основаны на идее последовательного улучшения приближений, пока результат не удовлетворит какому-то критерию.На самом деле мы без труда можем сформулироватьвычисление квадратного корня какпоиск неподвижной точки. Вычислить квадратного корня из произвольного числа x означает найти такое y, что y 2 = x.
Переведя это уравнение в эквивалентную форму y = x/y,мы обнаруживаем, что должны найти неподвижную точку функции58 y 7→ x/y, и, следовательно, мы можем попытаться вычислять квадратные корни так:(define (sqrt x)(fixed-point (lambda (y) (/ x y))1.0))К сожалению, этот поиск неподвижной точки не сходится. Рассмотрим исходное значение y1 . Следующее значение равно y2 = x/y1 , а следующее за ним y3 = x/y2 =x/(x/y1 ) = y1 . В результате выходит бесконечный цикл, в котором два значения y1 и y2повторяются снова и снова, прыгая вокруг правильного ответа.Один из способов управлять такими прыжками состоит в том, чтобы заставить значения изменяться не так сильно.
Поскольку ответ всегда находится между текущимзначением y и x/y, мы можем взять новое значение, не настолько далекое от y, как x/y,1взяв среднее между ними, так что следующее значение будет не x/y, а (y + x/y). Про2цесс получения такой последовательности есть всего лишь процесс поиска неподвижной1точки y 7→ (y + x/y).2(define (sqrt x)(fixed-point (lambda (y) (average y (/ x y)))1.0))57 Попробуйте во время скучной лекции установить калькулятор в режим радиан и нажимать кнопку cos,пока не найдете неподвижную точку.58 7→ (произносится «отображается в») — это математический способ написать lambda.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
