Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

5.3. Функции высшего порядка.

Язык программирования - не просто средство указывать компьютеру выполнить те или иные действия. Мощный язык программирования служит средством выражения наших мыслей. Поэтому, любой приличный язык программирования должен обеспечивать возможность создавать абстракции, и затем работать непосредственно в терминах этих абстракций. Функции, которые мы описывали, представляют собой такие абстракции. Например, когда мы определяли

(define (sqr x) (* x x))

мы говорили не о квадрате какого-то числа, а о методе для возведения в квадрат любого числа. Конечно мы могли обойтись без определения этой функции и всегда записывать выражения типа (* 5 5) или (* x x), но тем самым мы были бы вынуждены всегда рассуждать в терминах примитивных операций языка, а не в терминах операций более высокого уровня. Наши программы были бы способны вычислять квадраты чисел, но наш язык был бы неспособен выразить концепцию возведения в квадрат. Функции обеспечивают эту способность, поэтому практически все языки программирования содержат механизмы для определения функций или процедур.

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

Рассмотрим два примера

1. Вычислить сумму целых чисел от m до n.

(define (sum-int m n)
    (if (> m n)
        0
        (+ m (sum-int (+ m 1) n)))) 

2. Вычислить сумму квадратов целых чисел от m до n.

(define (sum-sqr m n)
    (if (> m n)
        0
        (+ (sqr m) (sum-sqr (+ m 1) n)))) 

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

и

Точно так же и мы хотели бы написать функцию, которая выражает концепцию суммирования, а не просто функции, вычисляющие конкретные суммы. Мы можем это сделать, используя функцию высшего порядка.

(define (sum f m n)
   (if (> m n)
       0
       (+ (f m) (sum f (+ m 1) n))))

Имея такую абстракцию, мы можем с лёгкостью определить

(define (sum-sqr m n)   (sum sqr m n) )

(define (sum-int m n)   (sum id m n))
(define (id x) x)

Несколько смущает необходимость описывать такую тривиальную функцию, как id. Однако, вспомнив о лямбда-выражениях, мы легко перепишем наше определение.

(define (sum-int m n)
   (sum (lambda (x) x) m n))

Теперь нас совсем не затруднит подсчитать сумму кубов чисел от 1 до 10

(sum [lambda (x) (* x x x)] 1 10)
3025

как и любую подобную сумму

(sum [lambda (x) (/ (* x x))] 1 1000)
1.64393456668156

Упражнение

Используя функцию sum, определите функцию (integral f a b dx) для приближённого вычисления интеграла функции f на отрезке [a,b] с шагом dx.

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

(define (prod f m n)
    (if (> m n)
        1
        (* (f m) (prod f (+ m 1) n))))

а затем выделить ещё более общий образец «накопления»

(define (acc op e f m n)
    (if (> m n)
        e
        (op (f m) (acc op e f (+ m 1) n)))) 

для которого sum и prod будут частными случаями.

(define (sum f m n)
   (acc  + 0 f m n) )

(define (prod f m n)
   (acc  * 1  f m n) )

Давайте рассмотрим поподробнее нашу новую абстракцию. Функция acc имеет следующие аргументы:

• некоторую бинарную операцию op и её нейтральный элемент e;
• некоторую функцию f числового аргумента;
• пару чисел m n, определяющих интервал.

Её результат получается последовательным «накоплением» значений функции f на этом интервале посредством операции op, начиная со значения e. Для наглядности запишем выражение в инфиксной форме. Тогда наше определение будет выглядеть так

acc[o, e, f, m, n] =  f_m o ( f_m+1 … o ( f_n o e) …).

Теперь мы можем определить массу подобных функций, подставляя вместо «o» различные операции.

(define (for-all p m n)
   (acc and #t p m n) )

(define (for-any p m n)
   (acc or  #f p m n) )

(define (maximum f m n)
   (acc max (f m) (+ m 1) n) )

Последнее определение выбивается из общей схемы. Действительно, трудно определить понятие нейтрального элемента для функции max. Поэтому мы использовали аргумент. Но этот случай даёт нам повод ввести новую функцию.

(define (acc1 op f m n)
   (acc op (f m) (+ m 1) n) )

Теперь определение максимума приобретает более изящный вид

(define (maximum f m n)
   (acc1 max m n )

(define (minimum f m n)
   (acc1 min m n ))

Упражнение

Дайте прямое определение функции acc1 .
Определите с её помощью функции sum, prod, for-all, maximum.
В чём достоинства и недостатки такого подхода?

Такая мощная абстракция, пожалуй, стоит некоторой оптимизации. Заметим, что наша процедура определяет линейный рекурсивный процесс. Попытаемся превратить его в итерационный. Наше определение по сути гласит:

acc[o, e, f, m, n] =  f_m o (f_m+1 … o f_n o e)  = f_m o acc[o, e, f, m+1, n]

Чисто формальными преобразованиями перепишем его в форме с хвостовой рекурсией.

acc[o, e, f, m, n] =  f_m o f_m+1 o … o f_n o e  =  e o f_m o f_m+1 o … o f_n = (e o f_m) o f_m+1 … o f_n = acc[o, (e o f_m), f, m+1, n]

Или, переходя к префиксной записи на Лиспе.

(define (acc op e f m n)
   (if (> m n)
       e
       (acc op (op e (f m) ) f (+ m 1) n)))

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

Обратите внимание и на двойственную природу параметра e. С одной стороны, он указывает значение, которое должно быть возвращено в случае пустого интервала. С другой стороны, он используется в качестве аккумулятора.

Упражнение.

Какие свойства операции op были неявно использованы при оптимизации acc?
Определите две процедуры: первоначальную (назовём её accr) и оптимизированную (accl) и сравните результаты их применения к различным операциям.

Упражнение.

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

Упражнение.

Рассмотрите возможность перейти от последовательности аргументов m, m+1, m+2,... к более общей последовательности m, next(m), next(next(m)),... Какие значения для next могли бы быть полезны?.

Упражнение.

Можно двигаться и в другом направлении. Например, возможно потребуется суммировать не все числа из данного диапазона. Введите в качестве параметра предикат, определяющий, какие значения полежат обработке.

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

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

Пусть нам приходится неоднократно вычислять значение sin(x)+cos(x). Конечно, мы можем определить

(define (sin+cos x)   (+ (sin x) (cos x)))

Однако, теперь мы вряд ли удовлетворимся таким определением. Нашим первым шагом будет функция f+, вычисляющая значение суммы двух функций.

(define (f+ f g x)   (+ (f x) (g x)))

Мы можем использовать её например следующим образом

(f+ sin cos x)

Но чувство неудовлетворённости остаётся. Мы описали как вычислять значения суммы функций, но нам хотелось бы выразить саму идею суммирования функций. Поэтому, перепишем наше определение f+.

(define (f+ f g)
   (lambda (x) (+ (f x) (g x))))

Новая функция f+ возвращает функцию вычисляющую значение суммы функций. Теперь её можно использовать как в следующих примерах.

((f+ sin cos) x)

(integral (f+ sin cos) a b dx)

Другая полезная абстракция - композиция функций.

(define (comp f g)
   (lambda (x) (f (g x))))

С её помощью мы можем, например, выразить идею двукратного применения функции

(define (twice f)
   (comp f f))

и даже n-кратного применения.

(define (iter f n)
   (if (= n 1)
       f
       (comp f (iter f (- n 1)))))

Упражнение.

Распространите определение iter на случай n=0.

Упражнение.

Определите набор функций, аналогичных f+ , позволяющий представлять функции одного аргумента вида (lambda (x) (+ (* 3 (sin x))(* 5 (cos x)))) не используя лямбда-выражений.

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

Метод Ньютона.

Использованный нами метод извлечения квадратного корня фактически представляет собой частный случай общего метода поиска корней уравнений известного как метод Ньютона. Если f(x) - дифференцируемая функция, то решение уравнения f(x) = 0 может быть получено как предел последовательности приближений, определяемой рекуррентным соотношением

x_k+1 = x_k - f(x_k)/ Df(x_k).

Для многих функций эта последовательность сходится очень быстро. Общая схема процедуры, реализующей метод Ньютона, схожа с той, что была использована для вычисления квадратного корня . Фактически, необходимо только изменить функцию improve.

(define (newton-method f df x)
   (define (improve x)
      (- x (/ (f x) (df x))) )
   (define (newton-iter x)
      (let ((y (improve x)))
         (if (near? y x)
             y
             (newton-iter y))))
   (newton-iter x))

(define err 0.00001)
(define (near? x1 x2)
   (< (abs (- x1 x2)) err))

Вычисление квадратного корня можно представить как решение уравнения x² - a = 0 , то есть как поиск нуля функции (x -> x² - a). Производная этой функции - (x -> 2*x). Поэтому мы можем определить.

(define (sqrt a)
   (newton-method (lambda (x) (- (sqr x) a))
                  (lambda (x) (* 2 x))
                  1.0))

Нетрудно убедиться, что эта процедура вычисляет ту же последовательность приближений, что и наша первоначальная процедура sqrt.

Неудобство метода Ньютона - необходимость знать производную функции. Однако, можно заменить ее вычисление приближённой оценкой. Если dx - достаточно маленькое число, то функция Df, определённая как

Df(x) = (f(x+dx)-f(x))/dx

дает приближённое значение производной функции f.  Обратите внимание, что производная, отображает функцию в другую функцию. Таким образом, мы можем выразить идею «производной» как функции высшего порядка.

(define dx 0.00001)

(define (deriv f)
   (lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))

Объединяя эту функцию с newtons-method, получаем разновидность метода секущих

(define (secant-method f x)
   (newton-method f (deriv а) x)

Этот метод сходится не так быстро, как метод Ньютона, но часто удобнее на практике, особенно, в случае сложных функций.

Неподвижные точки функций.

Число x называется неподвижной точкой функции f, если оно удовлетворяет уравнению f(x) = x. Для некоторых функций f мы можем найти неподвижную точку, начиная с некоторого начального предположения и многократно применяя f, пока изменение значения не станут очень малы. Используя эту идею, мы можем создать процедуру, которая получает функцию и начальное значение и выдаёт приближение к неподвижной точке функции.

(define (fixed-point f x)
   (define (fixp-iter x)
      (let ((y (f x)))
         (if (near? x y)
              y
             (fixp-iter y))))
   (fixp-iter x))

(define err 0.00001)
(define (near? x1 x2)
   (< (abs (- x1 x2)) err))

Вычисление квадратного корня можно сформулировать и как поиск неподвижной точки. Действительно квадратный корень из a представляет собой решение уравнения x² = a. Преобразовав это уравнение в эквивалентную форму x = a/x, мы обнаружим, что мы ищем неподвижную точку функции (x-> x * a/x). Поэтому мы можем пробовать вычислить квадратные корни следующим образом:

(define (sqrt a)
   (fixed-point (lambda (x) (/ a x)) 1.0))

К сожалению, этот процесс не сходится. Пусть начальное приближение x₁. Тогда следующие приближения x₂ = a/x₁ и x₃ = a/x₂ = a / (a / x₁) = x₁. Это приводит к бесконечному циклу, в котором два значения x₁ и x₂, колеблющиеся вокруг правильного значения, повторяются до бесконечности. Но можно попытаться предотвратить такие сильные колебания. Так как ответ всегда расположен между x и a/x, мы можем выбрать в качестве следующего предположения их среднее арифметическое. Таким образом от уравнения x = a/x мы переходим к равносильному уравнению x = (1/2) (x + a/x)

(define (sqrt x)
   (fixed-point (lambda (y) (average y (/ x y)))
                1.0))

С такой модификацией, наша процедура работает. Фактически, если мы раскроем определения, мы увидим, что последовательность приближений к квадратному корню, определяемая этой процедурой - всё та же, что и у наших процедур вычислявших корень по методу Герона и по методу Ньютона.

Этот метод усреднения (демпфирования) последовательных приближений часто помогает добиться сходимости вычислительных процессов. То есть, это полезная общая методика сама по себе и, значит, полезная абстракция. Мы можем выразить идею этой абстракции посредством следующей процедуры:

(define (average-damp f)
   (lambda (x) (average x (f x))))

Процедура average-damp преобразует функцию f в функцию (x-> (x + f(x))/2) , то есть в функцию, которая получив аргумент x возвращает среднее арифметическое x и f(x). Используя average-damp, мы можем переформулировать функцию извлечения квадратного корня следующим образом:

(define (sqrt a)
  (fixed-point (average-damp (lambda (x) (/ a x)))
               1.0))

Обратите внимание, как эта формулировка выделяет три идеи алгоритма: поиск неподвижной точки, усреднение, и функцию (x -> x/a). Сравните эту формулировку с первоначальной версией и отметьте, насколько более ясной становится идея метода, когда мы выражаем его в терминах таких абстракций. Более того, эти абстракции являются полезными элементами и  могут многократно использоваться в других программах. Например, кубический корень из a - неподвижная точка функции (x -> a/x²), так что мы можем немедленно написать процедуру извлечения кубического корня.

(define (cube-root a)
   (fixed-point (average-damp (lambda (x) (/ a (sqr x))))
                1.0))

К сожалению, метод не срабатывает для  корней более высоких степеней - усреднения уже не достаточно, чтобы обеспечить сходимость. Но мы можем применить усреднение многократно. Например, корни четвертой  степени можно вычислять дважды усреднив функцию (x -> a/x³).

(define (root-4th a)
   (fixed-point
      (average-damp
         (average-damp
             (lambda (x) (/ a (* x x x)))))
      1.0))

Наконец, внимательно рассмотрев наши процедуры, мы можем обнаружить, что метод Ньютона представляет собой не что иное, как поиск неподвижной точки некоторой функции!

Упражнение

Завершите следующие определения:
(define (newtons-method f df x)
   (fixed-point <...> x))

(define (secant-method f x)
   (fixed-point <...> x))


Упражнение

Определите функции newtons-transform и secant-transform, с помощью которых мы могли бы записать:
(define (newtons-method f df x)
   (fixed-point (newton-transform f df) x))
и
(define (secant-method f x)
   (fixed-point (secant-transform f) x))


[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]