Накапливающий параметр — аккумулятор

Элементы программирования

Локальные переменные

Охрана

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

Length (L) = 0 when L == []

Length (L) = 1 + Length (tail (L)) otherwise

В рассмотренном коде слова when (когда) и otherwise (в противном случае) являются зарезервированными словами языка. Однако использование этих слов не является необходимым условием для организации охраны. Охрану можно организовывать различными способами, в том числе и с помощью l-исчисления:

Append = l[].(lL.L)

Append = l(H:T).(lL.H: Append (T, L))

Представленная запись не очень читабельна, поэтому использоваться она будет только в крайних случаях по необходимости.

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

Пусть f и h — функции, и необходимо вычислить выражение h (f (X), f(X)). Если в языке нет оптимизирующих методов, то в этом случае произойдет двойное вычисление выражения f (X). Чтобы этого не произошло, можно прибегнуть к такому изощренному способу: (lv.h (v, v))(f (X)). Естественно, что в этом случает выражение f (X) вычислится первым и один раз. Для того, чтобы минимизировать использование l-исчисления, далее будет применяться следующая форма записи:

let v = f (X) in h (v, v)

(слова let, = и in — зарезервированы в языке). В этом случае v будет называться локальной переменной.

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

Factorial (0) = 1

Factorial (N) = N * Factorial (N – 1)

Если провести пример вычисления этой функции с аргументом 3, то можно будет увидеть следующую последовательность:

Factorial (3)

3 * Factorial (2)

3 * 2 * Factorial (1)

3 * 2 * 1 * Factorial (0)

3 * 2 * 1 * 1

3 * 2 * 1

3 * 2

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

Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример:

Пример 10. Функция вычисления факториала с аккумулятором.

Factorial_A (N) = F (N, 1)

F (0, A) = A

F (N, A) = F ((N – 1), (N * A))

В этом примере второй параметр функции F выполняет роль аккумулирующей переменной, именно в ней содержится результат, который возвращается по окончании рекурсии. Сама же рекурсия в этом случае принимает вид «хвостовой», память при этом расходуется только на хранение адресов возврата значения функции.

Хвостовая рекурсия представляет собой специальный вид рекурсии, в которой имеется единственный вызов рекурсивной функции и при этом этот вызов выполняется после всех вычислений.

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

Дата добавления: 2014-01-07