Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 10
Текст из файла (страница 10)
Однако интерпретатор MIT Scheme отличает точные целые числа отдесятичных значений, и при делении двух целых получается не десятичная дробь, а рациональное число.Например, поделив 10/6, получим 5/3, а поделив 10.0/6.0, получим 1.6666666666666667. (Мы увидим, какреализовать арифметические операции над рациональными числами, в разделе 2.1.1.) Если в нашей программеквадратного корня мы начнем с начального приближения 1, а x будет точным целым числом, все последующиезначения, получаемые при вычислении квадратного корня, будут не десятичными дробями, а рациональнымичислами.
Поскольку при смешанных операциях над десятичными дробями и рациональными числами всегдаполучаются десятичные дроби, то начав со значения 1.0, все прочие мы получим в виде десятичных дробей.24 Читателям, которых заботят вопросы эффективности, связанные с использованием вызовов процедур дляитерации, следует обратить внимание на замечания о «хвостовой рекурсии» в разделе 1.2.1.1.1. Элементы программирования43(new-if (= 2 3) 0 5)5(new-if (= 1 1) 0 5)0Обрадованная Лиза переписывает через new-if программу вычисления квадратного корня:(define (sqrt-iter guess x)(new-if (good-enough? guess x)guess(sqrt-iter (improve guess x)x)))Что получится, когда Лиза попытается использовать эту процедуру для вычисления квадратныхкорней? Объясните.Упражнение 1.7.Проверка good-enough?, которую мы использовали для вычисления квадратных корней, будетдовольно неэффективна для поиска квадратных корней от очень маленьких чисел.
Кроме того, внастоящих компьютерах арифметические операции почти всегда вычисляются с ограниченной точностью. Поэтому наш тест оказывается неадекватным и для очень больших чисел. Альтернативныйподход к реализации good-enough? состоит в том, чтобы следить, как от одной итерации к другой изменяется guess, и остановиться, когда изменение оказывается небольшой долей значенияприближения.
Разработайте процедуру вычисления квадратного корня, которая использует такойвариант проверки на завершение. Верно ли, что на больших и маленьких числах она работаетлучше?Упражнение 1.8.Метод Ньютона для кубических корней основан на том, что если y является приближением ккубическому корню из x, то мы можем получить лучшее приближение по формулеx/y 2 + 2y3С помощью этой формулы напишите процедуру вычисления кубического корня, подобную процедуре для квадратного корня. (В разделе 1.3.4 мы увидим, что можно реализовать общий методНьютона как абстракцию этих процедур для квадратного и кубического корня.)1.1.8. Процедуры как абстракции типа «черный ящик»Sqrt — наш первый пример процесса, определенного множеством зависимых друг отдруга процедур. Заметим, что определение sqrt-iter рекурсивно (recursive); это означает, что процедура определяется в терминах самой себя. Идея, что можно определитьпроцедуру саму через себя, возможно, кажется Вам подозрительной; неясно, как такое«циклическое» определение вообще может иметь смысл, не то что описывать хорошоопределенный процесс для исполнения компьютером.
Более осторожно мы подойдем кэтому в разделе 1.2. Рассмотрим, однако, некоторые другие важные детали, которыеиллюстрирует пример с sqrt.Глава 1. Построение абстракций с помощью процедур44sqrtsqrt-itergood-enough improvesquare absaverageРис. 1.2. Процедурная декомпозиция программы sqrt.Заметим, что задача вычисления квадратных корней естественным образом разбивается на подзадачи: как понять, что очередное приближение нас устраивает, как улучшить очередное приближение, и так далее. Каждая из этих задач решается с помощьюотдельной процедуры.
Вся программа sqrt может рассматриваться как пучок процедур(показанный на рис. 1.1.8), отражающий декомпозицию задачи на подзадачи.Важность декомпозиционной стратегии не просто в том, что задача разделяется начасти. В конце концов, можно взять любую большую программу и поделить ее на части:первые десять строк, следующие десять строк и так далее. Существенно то, что каждая процедура выполняет точно определенную задачу, которая может быть использованапри определении других процедур.
Например, когда мы определяем процедуру goodenough? с помощью square, мы можем рассматривать процедуру square как «черныйящик». В этот момент нас не интересует, как она вычисляет свой результат, — важнотолько то, что она способна вычислить квадрат. О деталях того, как вычисляют квадраты, можно сейчас забыть и рассмотреть их потом. Действительно, пока мы рассматриваем процедуру good-enough?, square — не совсем процедура, но скорее абстракцияпроцедуры, так называемая процедурная абстракция (procedural abstraction). На этомуровне абстракции все процедуры, вычисляющие квадрат, одинаково хороши.Таким образом, если рассматривать только возвращаемые значения, то следующиедве процедуры для возведения числа в квадрат будут неотличимы друг от друга.
Каждаяиз них принимает числовой аргумент и возвращает в качестве значения квадрат этогочисла25 .(define (square x) (* x x))(define (square x)(exp (double (log x))))(define (double x) (+ x x))Таким образом, определение процедуры должно быть способно скрывать детали. Мо25 Неясно даже, которая из этих процедур более эффективна. Это зависит от того, какая имеется аппаратура. Существуют машины, на которых «очевидная» реализация будет медленней.
Представьте себе машину, вкоторой очень эффективным способом хранятся большие таблицы логарифмов и обратных логарифмов.1.1. Элементы программирования45жет оказаться, что пользователь процедуры не сам ее написал, а получил от другогопрограммиста как черный ящик. От пользователя не должно требоваться знания, какработает процедура, чтобы ее использовать.Локальные именаОдна из деталей реализации, которая не должна заботить пользователя процедуры —это то, какие человек, писавший процедуру, выбрал имена для формальных параметровпроцедуры. Таким образом, следующие две процедуры должны быть неотличимы:(define (square x) (* x x))(define (square y) (* y y))Этот принцип — что значение процедуры не должно зависеть от имен параметров, которые выбрал ее автор, — может сначала показаться очевидным, однако он имеет глубокиеследствия.
Простейшее из этих следствий состоит в том, что имена параметров должныбыть локальными в теле процедуры. Например, в программе вычисления квадратногокорня при определении good-enough? мы использовали square:(define (good-enough? guess x)(< (abs (- (square guess) x)) 0.001))Намерение автора good-enough? состоит в том, чтобы определить, достаточно ли близко квадрат первого аргумента лежит ко второму. Мы видим, что автор good-enough?обращается к первому аргументу с помощью имени guess, а ко второму с помощьюимени x. Аргументом square является guess. Поскольку автор square использовалимя x (как мы видели выше), чтобы обратиться к этому аргументу, мы видим, чтоx в good-enough? должно отличаться от x в square.
Запуск процедуры square недолжен отразится на значении x, которое использует good-enough?, поскольку этозначение x понадобится good-enough?, когда square будет вычислена.Если бы параметры не были локальны по отношению к телам своих процедур, топараметр x в square смешался бы с параметром x из good-enough?, и поведениеgood-enough? зависело бы от того, какую версию square мы использовали. Такимобразом, процедура square не была бы черным ящиком, как мы того хотим.У формального параметра особая роль в определении процедуры: не имеет значения, какое у этого параметра имя.
Такое имя называется связанной переменной (boundvariable), и мы будем говорить, что определение процедуры связывает (binds) свои формальные параметры. Значение процедуры не изменяется, если во всем ее определениипараметры последовательным образом переименованы26 . Если переменная не связана,мы говорим, что она свободна (free). Множество выражений, для которых связываниеопределяет имя, называется областью действия (scope) этого имени. В определениипроцедуры связанные переменные, объявленные как формальные параметры процедуры,имеют своей областью действия тело процедуры.В приведенном выше определении good-enough?, guess и x — связанные переменные, а <, -, abs и square — свободные.
Значение good-enough? должно быть26 Понятие последовательного переименования на самом деле достаточно тонкое и трудное для определения.Знаменитым логикам случалось делать здесь ужасные ошибки.46Глава 1. Построение абстракций с помощью процедурнезависимо от того, какие имена мы выберем для guess и x, пока они остаются отличными друг от друга и от <, -, abs и square. (Если бы мы переименовали guessв abs, то породили бы ошибку, захватив (capture) переменную abs. Она превратиласьбы из свободной в связанную.) Однако значение good-enough? не является независимым от ее свободных переменных. Разумеется, оно зависит от того факта (внешнегопо отношению к этому определению), что символ abs называет процедуру вычислениямодуля числа.
Good-enough? будет вычислять совершенно другую функцию, если в ееопределении мы вместо abs подставим cos.Внутренние определения и блочная структураДо сих пор нам был доступен только один вид изоляции имен: формальные параметры процедуры локальны по отношению к телу этой процедуры. Программа вычисленияквадратного корня иллюстрирует еще один вид управления использованием имен, которым мы хотели бы владеть. Существующая программа состоит из отдельных процедур:(define (sqrt x)(sqrt-iter 1.0 x))(define (sqrt-iter guess x)(if (good-enough? guess x)guess(sqrt-iter (improve guess x) x)))(define (good-enough? guess x)(< (abs (- (square guess) x)) 0.001))(define (improve guess x)(average guess (/ x guess)))Проблема здесь состоит в том, что единственная процедура, которая важна для пользователей sqrt — это сама sqrt.
Остальные процедуры (sqrt-iter, good-enough? иimprove) только забивают им головы. Теперь пользователи не могут определять другихпроцедур с именем good-enough? ни в какой другой программе, которая должна работать совместно с программой вычисления квадратного корня, поскольку sqrt требуетсяэто имя.
Эта проблема становится особенно тяжелой при построении больших систем,которые пишут много различных программистов. Например, при построении большойбиблиотеки численных процедур многие числовые функции вычисляются как последовательные приближения и могут потому иметь в качестве вспомогательных процедурыgood-enough? и improve. Нам хотелось бы локализовать подпроцедуры, спрятав ихвнутри sqrt, так, чтобы sqrt могла сосуществовать с другими последовательнымиприближениями, при том что у каждой из них была бы своя собственная процедураgood-enough?. Чтобы сделать это возможным, мы разрешаем процедуре иметь внутренние определения, локальные для этой процедуры. Например, при решении задачивычисления квадратного корня мы можем написать(define (sqrt x)(define (good-enough? guess x)1.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
