4.2 Общая схема накопления
4.2.1 Определим новую абстракцию acc в таком виде:
> (define (acc op st f m n) (4Ш)
(if
(> m
n)
st
(op (f m) (acc op st f (+ m 1) n))))
где
оp - некоторая повторяющаяся операция
f - задаваемая функция числового аргумента
st - её начальное значение
m и n - числа, определяющие начало и конец интервала вычисляемой функции.
Теперь функции sum и prod можно определить как частные случаи этой новой абстракции, назвав их соответственно sum2 и prod2.
> (define (sum2 f m n)
(acc + 0 f m n) )
> (define (prod2 f m n)
(acc * 1 f m n) )
> (prod2 (lambda (x) (sqr x)) 3 9)
32920473600
Можно даже определить подсчет максимального элемента последовательности:
> (define (max_acc f m n)
(acc max (f m) f m n) )
Последнее определение интересно тем, что оказывается, существуют функции, для которых можно просто задать начальное значение вычисляемой функции, используя один из аргументов её диапазона, например первый, т.е. (f m).
4.2.2. Но лучше сразу модернизировать определение основной функции acc таким образом, чтобы сразу учитывать начальное значение. Назовём её accm(одернизированная):
> (define (accm op f m n)
(acc op (f m) f (+ m 1) n) )
Здесь мы не задаем начального значения: оно вычисляется, и мы продолжаем со следующего, т.е. (m + 1)–го члена ряда.
Теперь определения конкретных функций приобретают более изящный вид. Например, найдём тот же максимум:
> (define (max_accm f m n)
(accm max f m n ))
Или даже сумму квадратов:
> (max_accm (lambda (x) (sqr x)) 3 9)
81
Пример с максимумом возрастающей последовательности хотя и глуповат, но хорошо осмысливается.
4.2.3 Теперь попытаемся превратить эту линейную рекурсию в хвостовую. Такая оптимизация, как известно, даёт существенный выигрыш во времени.
Итак, наше определение таково:
(acc op st f m n) =>
Что рекурсивно перейдет в обращение – записываем только суть следующего вызова
=> op (f m) (acc op st f (+ m 1) n) =>
Далее нижеследующий вызов
=> op (f m) (op (f (+ m 1)) (acc op st f (+ m 2) n)) =>
…
и в конце получается выражение из последовательностей вызовов
=> op (f m) (op (f (+ m 1)) (op f (+ m 2) …
(op (f n)(acc op st f (+ n 1) n)…)=
Теперь начинаем упрощение этой формулы.
Заметим, что при m>n,т.е. при m=n+1, обращение (acc op st f (+ n 1) n)
в первый раз возвращает числовое значение равное st. Тогда, заменим самый внутренний вызов функции acc на это st и получим выражение
=> op (f m) (op (f (+ m 1)) (op f (+ m 2) …
(op (f n) st) …)=
Скобочную запись вызовов функций (f i) можно упростить, введя индексные обозначения и убирая соответствующие парные скобки
=> op fm ( op fm+1 … (op fm+(n-1) (op fn st) …) =
Теперь для наглядности запишем выражение в привычной инфиксной форме:
=
>
fm
op ( fm+1
… (fm+(n-1)
op (fn op
st)
…) =
и немножечко подсократим запись, выбрасывая предпоследний член, т.е.
=> fm op [fm+1 op ( … (fn op st)… )] (5Ш)
Замечание.Обратим внимание, что первая внутренняя скобка - это не что иное, следующий по порядку рекурсивный вызов нашей процедуры, а именно
=> fm op acc[op, st, f, m+1, n]
4.2 4. Докажем, что выражение (acc op st f m n) есть ни что иное, как вызов исходной функции acc со следующим значением начального значения st и, поэтому, меньшим количеством шагов т.е: (запись не формальная!!!) = = = ( acc op (st op fm) f m+1 n)
Итак, есть выражение (5Ш), т.е.
fm op (fm+1 op ( … (fn op st)… ))
Мы можем опустить скобки, подразумевая под op обозначение одной из двух операций: или сложение иди умножение, т.е. считая, что у нас будет происходить обычные вычисление обычной числовой функции
fm op fm+1 op … op fn op st
Справедливо полагая, что числовая операция op коммутативна, перепишем это выражение так:.
st op fm op fm+1 op … op fn
Но поскольку действие, строго говоря, должно начинаться с правой стороны, то для соблюдения приоритета операций, напишем скобки
(st op fm) op fm+1 … op fn =
И если считать, что в скобках оказалось начальное значение, с которого начинается вычисление, то можно написать
acc[op, (st op fm), f, m+1, n]
Что и требовалось доказать.
Теперь, переходя к префиксной записи на ЛИСПе, вместо выражения (4Ш), а именно:
(define (acc op st f m n)
(if (> m n) st
(op (f m) (acc op st f (+ m 1) n))
))
мы получаем замечательное выражение с хвостовой рекурсией:
(define (acc op st f m n)
(if (> m n) st
{acc op [op st (f m)] f (+ m 1) n}
))
Результатом всех преобразований явилась оптимизация общей схемы накопления и теперь все процедуры, определённые с её использованием, ,будут работать намного эффективнее.
Обратите внимание и на многоликость параметра st.
Во-первых, он задает начальное значение
Во-вторых, определяет значение, которое должно быть возвращено в случае пустого интервала.
В-третьих, это накапливающий, иными словами, результирующий параметр.