Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 17
Текст из файла (страница 17)
Например, определенный интеграл функции fмежду пределами a и b можно численно оценить с помощью формулыZab dxdxdx+ f a + dx ++ f a + 2dx ++ . . . dxf = f a+222для малых значений dx. Мы можем прямо выразить это в виде процедуры:(define (integral f a b dx)(define (add-dx x) (+ x dx))(* (sum f (+ a (/ dx 2)) add-dx b)dx))50 Обратите внимание, что мы использовали блочную структуру (раздел 1.1.8), чтобы спрятать определенияpi-next и pi-term внутри pi-sum, поскольку вряд ли эти процедуры понадобятся зачем-либо еще. Вразделе 1.3.2 мы совсем от них избавимся.1.3. Формулирование абстракций с помощью процедур высших порядков73(integral cube 0 1 0.01).24998750000000042(integral cube 0 1 0.001).249999875000001(Точное значение интеграла cube от 0 до 1 равно 1/4.)Упражнение 1.29.Правило Симпсона — более точный метод численного интегрирования, чем представленный выше.С помощью правила Симпсона интеграл функции f между a и b приближенно вычисляется в видеh[y0 + 4y1 + 2y2 + 4y3 + 2y4 + .
. . + 2yn−2 + 4yn−1 + yn ]3где h = (b − a)/n, для какого-то четного целого числа n, а yk = f (a + kh). (Увеличение n повышает точность приближенного вычисления.) Определите процедуру, которая принимает в качествеаргументов f , a, b и n, и возвращает значение интеграла, вычисленное по правилу Симпсона. Спомощью этой процедуры проинтегрируйте cube между 0 и 1 (с n = 100 и n = 1000) и сравнитерезультаты с процедурой integral, приведенной выше.Упражнение 1.30.Процедура sum порождает линейную рекурсию.
Ее можно переписать так, чтобы суммированиевыполнялось итеративно. Покажите, как сделать это, заполнив пропущенные выражения в следующем определении:(define (sum term a next b)(define (iter a result)(if h??ih??i(iter h??i h??i)))(iter h??i h??i))Упражнение 1.31.а. Процедура sum — всего лишь простейшая из обширного множества подобных абстракций,которые можно выразить через процедуры высших порядков.51. Напишите аналогичную процедурупод названием product, которая вычисляет произведение значений функции в точках на указанном интервале. Покажите, как с помощью этой процедуры определить factorial. Кроме того,при помощи product вычислите приближенное значение π по формуле52π2 · 4 · 4 · 6 · 6 · 8···=43 · 3 · 5 · 5 · 7 · 7···51 Смысл упражнений 1.31–1.33 состоит в том, чтобы продемонстрировать выразительную мощь, получаемую, когда с помощью подходящей абстракции обобщается множество операций, казалось бы, не связанныхмежду собой.
Однако, хотя накопление и фильтрация — изящные приемы, при их использовании руки у наспока что несколько связаны, поскольку пока что у нас нет структур данных, которые дают подходящие к этимабстракциям средства комбинирования. В разделе 2.2.3 мы вернемся к этим приемам и покажем, как использовать последовательности (sequences) в качестве интерфейсов для комбинирования фильтров и накопителей,так что получаются еще более мощные абстракции.
Мы увидим, как эти методы сами по себе становятсямощным и изящным подходом к проектированию программ.52 Эту формулу открыл английский математик семнадцатого века Джон Уоллис.74Глава 1. Построение абстракций с помощью процедурб. Если Ваша процедура product порождает рекурсивный процесс, перепишите ее так, чтобыона порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобыона порождала рекурсивный.Упражнение 1.32.а. Покажите, что sum и product (упражнение 1.31) являются частными случаями еще болееобщего понятия, называемого накопление (accumulation), которое комбинирует множество термов с помощью некоторой общей функции накопления(accumulate combiner null-value term a next b)Accumulate принимает в качестве аргументов те же описания термов и диапазона, что и sum сproduct, а еще процедуру combiner (двух аргументов), которая указывает, как нужно присоединить текущий терм к результату накопления предыдущих, и null-value, базовое значение,которое нужно использовать, когда термы закончатся.
Напишите accumulate и покажите, как иsum, и product можно определить в виде простых вызовов accumulate.б. Если Ваша процедура accumulate порождает рекурсивный процесс, перепишите ее так,чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так,чтобы она порождала рекурсивный.Упражнение 1.33.Можно получить еще более общую версию accumulate (упражнение 1.32), если ввести понятиефильтра (filter) на комбинируемые термы. То есть комбинировать только те термы, порожденныеиз значений диапазона, которые удовлетворяют указанному условию. Получающаяся абстракцияfiltered-accumulate получает те же аргументы, что и accumulate, плюс дополнительныйодноаргументный предикат, который определяет фильтр.
Запишите filtered-accumulate ввиде процедуры. Покажите, как с помощью filtered-accumulate выразить следующее:а. сумму квадратов простых чисел в интервале от a до b (в предположении, что процедураprime? уже написана);б. произведение всех положительных целых чисел меньше n, которые просты по отношению кn (то есть всех таких положительных целых чисел i < n, что НОД(i, n) = 1).1.3.2. Построение процедур с помощью lambdaКогда в разделе 1.3.1 мы использовали sum, очень неудобно было определять тривиальные процедуры вроде pi-term и pi-next только ради того, чтобы передать их какаргументы в процедуры высшего порядка. Было бы проще вместо того, чтобы вводитьимена pi-next и pi-term, прямо определить «процедуру, которая возвращает свойаргумент плюс 4» и «процедуру, которая вычисляет число, обратное произведению аргумента и аргумента плюс 2». Это можно сделать, введя особую форму lambda, котораясоздает процедуры.
С использованием lambda мы можем записать требуемое в такомвиде:(lambda (x) (+ x 4))и(lambda (x) (/ 1.0 (* x (+ x 2))))Тогда нашу процедуру pi-sum можно выразить безо всяких вспомогательных процедур:1.3. Формулирование абстракций с помощью процедур высших порядков75(define (pi-sum a b)(sum (lambda (x) (/ 1.0 (* x (+ x 2))))a(lambda (x) (+ x 4))b))Еще с помощью lambda мы можем записать процедуру integral, не определяявспомогательную процедуру add-dx:(define (integral f a b dx)(* (sum f(+ a (/ dx 2.0))(lambda (x) (+ x dx))b)dx))В общем случае, lambda используется для создания процедур точно так же, какdefine, только никакого имени для процедуры не указывается:(lambda (hформальные-параметрыi) hтелоi)Получается столь же полноценная процедура, как и с помощью define.
Единственнаяразница состоит в том, что она не связана ни с каким именем в окружении. На самомделе(define (plus4 x) (+ x 4))эквивалентно(define plus4 (lambda (x) (+ x 4)))Можно читать выражение lambda так:(lambda↑Процедура(x)↑от аргумента x,которая(+↑складываетx↑xи4))↑4Подобно любому выражению, значением которого является процедура, выражение сlambda можно использовать как оператор в комбинации, например((lambda (x y z) (+ x y (square z))) 1 2 3)12Или, в более общем случае, в любом контексте, где обычно используется имя процедуры53 .53 Было бы более понятно и менее страшно для изучающих Лисп, если бы здесь использовалось болееясное имя, чем lambda, например make-procedure.
Однако традиция уже прочно укоренилась. Эта нотациязаимствована из λ-исчисления, формализма, изобретенного математическим логиком Алонсо Чёрчем (Church1941). Чёрч разработал λ-исчисление, чтобы найти строгое основание для понятий функции и примененияфункции. λ-исчисление стало основным инструментом математических исследований по семантике языковпрограммирования.Глава 1. Построение абстракций с помощью процедур76Создание локальных переменных с помощью letЕще одно применение lambda состоит во введении локальных переменных. Часто нам в процедуре бывают нужны локальные переменные помимо тех, что связаныформальными параметрами.
Допустим, например, что нам надо вычислить функциюf (x, y) = x(1 + xy)3 + y(1 − y) + (1 + xy)(1 − y)которую мы также могли бы выразить какa =b =f (x, y) =1 + xy1−yxa2 + yb + abКогда мы пишем процедуру для вычисления f , хотелось бы иметь как локальные переменные не только x и y, но и имена для промежуточных результатов вроде a и b. Можносделать это с помощью вспомогательной процедуры, которая связывает локальные переменные:(define (f x y)(define (f-helper a b)(+ (* x (square a))(* y b)(* a b)))(f-helper (+ 1 (* x y))(- 1 y)))Разумеется, безымянную процедуру для связывания локальных переменных мы можем записать через lambda-выражение.
При этом тело f оказывается просто вызовомэтой процедуры.(define (f x y)((lambda (a b)(+ (* x (square a))(* y b)(* a b)))(+ 1 (* x y))(- 1 y)))Такая конструкция настолько полезна, что есть особая форма под названием let, которая делает ее более удобной. С использованием let процедуру f можно записатьтак:(define (f x y)(let ((a (+ 1 (* x y)))(b (- 1 y)))(+ (* x (square a))(* y b)(* a b))))Общая форма выражения с let такова:1.3. Формулирование абстракций с помощью процедур высших порядков77(let ((hпер1 i hвыр1 i)(hпер2 i hвыр2 i)...(hперn i hвырn i))hтелоi)Это можно понимать какПусть hпер1 i имеет значение hвыр1 iи hпер2 i имеет значение hвыр2 i...и hперn i имеет значение hвырn iв hтелеiПервая часть let-выражения представляет собой список пар вида имя–значение. Когдаlet вычисляется, каждое имя связывается со значением соответствующего выражения.Затем вычисляется тело let, причем эти имена связаны как локальные переменные.Происходит это так: выражение let интерпретируется как альтернативная форма для((lambda (hпер1 i ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
