Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 9
Текст из файла (страница 9)
В противном случае он вычисляет hальтернативуi и возвращает еезначение19.В дополнение к элементарным предикатам вроде <, = и >, существуют операциилогической композиции, которые позволяют нам конструировать составные предикаты.Из них чаще всего используются такие:• (and he1 i . . . hen i)Интерпретатор вычисляет выражения hei по одному, слева направо. Если какое-нибудьиз hei дает ложное значение, значение всего выражения and — ложь, и остальные hei невычисляются.
Если все hei дают истинные значения, значением выражения and являетсязначение последнего из них.• (or he1 i . . . hen i)Интерпретатор вычисляет выражения hei по одному, слева направо. Если какое-нибудьиз hei дает истинное значение, это значение возвращается как результат выраженияor, а остальные hei не вычисляются.
Если все hei оказываются ложными, значениемвыражения or является ложь.• (not hei)Значение выражения not — истина, если значение выражения hei ложно, и ложь впротивном случае.19 Небольшая разница между if и cond состоит в том, что в cond каждое hei может быть последовательностью выражений. Если соответствующее hpi оказывается истинным, выражения из hei вычисляются по очереди,и в качестве значения cond возвращается значение последнего из них. Напротив, в if как hследствиеi, таки hальтернативаi обязаны состоять из одного выражения.38Глава 1. Построение абстракций с помощью процедурЗаметим, что and и or — особые формы, а не процедуры, поскольку не обязательновычисляются все подвыражения. Not — обычная процедура.Как пример на использование этих конструкций, условие что число x находится вдиапазоне 5 < x < 10, можно выразить как(and (> x 5) (< x 10))Другой пример: мы можем определить предикат, который проверяет, что одно числобольше или равно другому, как(define (>= x y)(or (> x y) (= x y)))или как(define (>= x y)(not (< x y)))Упражнение 1.1.Ниже приведена последовательность выражений.
Какой результат напечатает интерпретатор в ответ на каждое из них? Предполагается, что выражения вводятся в том же порядке, в каком онинаписаны.10(+ 5 3 4)(- 9 1)(/ 6 2)(+ (* 2 4) (- 4 6))(define a 3)(define b (+ a 1))(+ a b (* a b))(= a b)(if (and (> b a) (< b (* a b)))ba)(cond ((= a 4) 6)((= b 4) (+ 6 7 a))(else 25))(+ 2 (if (> b a) b a))1.1. Элементы программирования39(* (cond ((> a b) a)((< a b) b)(else -1))(+ a 1))Упражнение 1.2.Переведите следующее выражение в префиксную форму:5 + 4 + (2 − (3 − (6 +4)))53(6 − 2)(2 − 7)Упражнение 1.3.Определите процедуру, которая принимает в качестве аргументов три числа и возвращает суммуквадратов двух бо́льших из них.Упражнение 1.4.Заметим, что наша модель вычислений разрешает существование комбинаций, операторы которых — составные выражения.
С помощью этого наблюдения опишите, как работает следующаяпроцедура:(define (a-plus-abs-b a b)((if (> b 0) + -) a b))Упражнение 1.5.Бен Битобор придумал тест для проверки интерпретатора на то, с каким порядком вычислений онработает, аппликативным или нормальным. Бен определяет такие две процедуры:(define (p) (p))(define (test x y)(if (= x 0)0y))Затем он вычисляет выражение(test 0 (p))Какое поведение увидит Бен, если интерпретатор использует аппликативный порядок вычислений?Какое поведение он увидит, если интерпретатор использует нормальный порядок? Объясните Вашответ.
(Предполагается, что правило вычисления особой формы if одинаково независимо от того,какой порядок вычислений используется. Сначала вычисляется выражение-предикат, и результатопределяет, нужно ли вычислять выражение-следствие или альтернативу.)40Глава 1. Построение абстракций с помощью процедур1.1.7. Пример: вычисление квадратного корня методом НьютонаПроцедуры, как они описаны выше, очень похожи на обыкновенные математическиефункции. Они устанавливают значение, которое определяется одним или более параметром. Но есть важное различие между математическими функциями и компьютернымипроцедурами.
Процедуры должны быть эффективными.В качестве примера рассмотрим задачу вычисления квадратного корня. Мы можемопределить функцию «квадратный корень» так:√x = такое y, что y ≥ 0 и y 2 = xЭто описывает совершенно нормальную математическую функцию. С помощью такогоопределения мы можем решать, является ли одно число квадратным корнем другого,или выводить общие свойства квадратных корней. С другой стороны, это определениене описывает процедуры. В самом деле, оно почти ничего не говорит о том, как найтиквадратный корень данного числа.
Не поможет и попытка перевести это определение напсевдо-Лисп:(define (sqrt x)(the y (and (>= y 0)(= (square y) x))))Это только уход от вопроса.Противопоставление функций и процедур отражает общее различие между описанием свойств объектов и описанием того, как что-то делать, или, как иногда говорят,различие между декларативным знанием и императивным знанием. В математике насобычно интересуют декларативные описания (что такое), а в информатике императивные описания (как)20 .Как вычисляются квадратные корни? Наиболее часто применяется Ньютонов методпоследовательных приближений, который основан на том, что имея некоторое неточноезначение y для квадратного корня из числа x, мы можем с помощью простой манипуляции получить более точное значение (более близкое к настоящему квадратному корню),если возьмем среднее между y и x/y 21 .
Например, мы можем вычислить квадратный20 Декларативные и императивные описания тесно связаны между собой, как и математика с информатикой.Например, сказать, что ответ, получаемый программой, «верен», означает сделать об этой программе декларативное утверждение. Существует большое количество исследований, направленных на отыскание методовдоказательства того, что программа корректна, и большая часть сложности этого предмета исследования связана с переходом от императивных утверждений (из которых строятся программы) к декларативным (которыеможно использовать для рассуждений). Связана с этим и такая важная область современных исследованийпо проектированию языков программирования, как исследование так называемыхязыков сверхвысокого уровня, в которых программирование на самом деле происходит в терминах декларативных утверждений.
Идеясостоит в том, чтобы сделать интерпретаторы настолько умными, чтобы, получая от программиста знание типа«что такое», они были бы способны самостоятельно породить знание типа «как». В общем случае это сделатьневозможно, но есть важные области, где удалось достичь прогресса. Мы вернемся к этой идее в главе 4.21 На самом деле алгоритм нахождения квадратного корня представляет собой частный случай метода Ньютона, который является общим методом нахождения корней уравнений. Собственно алгоритм нахожденияквадратного корня был разработан Героном Александрийским в первом веке н.э. Мы увидим, как выразитьобщий метод Ньютона в виде процедуры на Лиспе, в разделе 1.3.4.1.1.
Элементы программирования41корень из 2 следующим образом: предположим, что начальное приближение равно 1.Приближение Частное x/y11.51.41671.4142Среднее2=212= 1.33331.52= 1.41181.41672+1= 1.521.3333 + 1.5= 1.416721.4167 + 1.4118= 1.41422......Продолжая этот процесс, мы получаем все более точные приближения к квадратномукорню.Теперь формализуем этот процесс в терминах процедур. Начнем с подкоренного числа и какого-то значения приближения. Если приближение достаточно хорошо подходитдля наших целей, то процесс закончен; если нет, мы должны повторить его с улучшенным значением приближения. Запишем эту базовую стратегию в виде процедуры:(define (sqrt-iter guess x)(if (good-enough? guess x)guess(sqrt-iter (improve guess x)x)))Значение приближения улучшается с помощью взятия среднего между ним и частнымподкоренного числа и старого значения приближения:(define (improve guess x)(average guess (/ x guess)))где(define (average x y)(/ (+ x y) 2))Нам нужно еще сказать, что такое для нас «достаточно хорошее» приближение.
Следующий вариант сойдет для иллюстрации, но на самом деле это не очень хороший тест. (См.упражнение 1.7.) Идея состоит в том, чтобы улучшать приближения до тех пор, покаего квадрат не совпадет с подкоренным числом в пределах заранее заданного допуска(здесь 0.001)22 :(define (good-enough? guess x)(< (abs (- (square guess) x)) 0.001))22 Обычно мы будем давать предикатам имена, заканчивающиеся знаком вопроса, чтобы было проще запомнить, что это предикаты.
Это не более чем стилистическое соглашение. С точки зрения интерпретатора,вопросительный знак — обыкновенный символ.42Глава 1. Построение абстракций с помощью процедурНаконец, нужно с чего-то начинать. Например, мы можем для начала предполагать, чтоквадратный корень любого числа равен 123 :(define (sqrt x)(sqrt-iter 1.0 x))Если мы введем эти определения в интерпретатор, мы сможем использовать sqrt каклюбую другую процедуру:(sqrt 9)3.00009155413138(sqrt (+ 100 37))11.704699917758145(sqrt (+ (sqrt 2) (sqrt 3)))1.7739279023207892(square (sqrt 1000))1000.000369924366Программа sqrt показывает также, что того простого процедурного языка, который мы описали до сих пор, достаточно, чтобы написать любую чисто вычислительнуюпрограмму, которую можно было бы написать, скажем, на Си или Паскале.
Это может показаться удивительным, поскольку в наш язык мы не включили никаких итеративных (циклических) конструкций, указывающих компьютеру, что нужно производитьнекое действие несколько раз. Sqrt-iter, с другой стороны, показывает, как можновыразить итерацию, не имея никакого специального конструкта, кроме обыкновеннойспособности вызвать процедуру24 .Упражнение 1.6.Лиза П. Хакер не понимает, почему if должна быть особой формой. «Почему нельзя простоопределить ее как обычную процедуру с помощью cond?» — спрашивает она. Лизина подруга ЕваЛу Атор утверждает, что, разумеется, можно, и определяет новую версию if:(define (new-if predicate then-clause else-clause)(cond (predicate then-clause)(else else-clause)))Ева показывает Лизе новую программу:23 Обратите внимание, что мы записываем начальное приближение как 1.0, а не как 1.Во многих реализацияхЛиспа здесь не будет никакой разницы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
