Основы функционального программирования

       

Замедленные вычисления


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

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

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

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

Любое очень объемное, сложное данное можно вычислять "по частям". Вместо вычисления списка

(x1 x2 x3 ... )

можно вычислить x1 и построить структуру:

(x1 ( рецепт вычисления остальных элементов))

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

(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N)))))

(defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) )

Пример 12.1. Построение ряда целых от M до N с последующим их суммированием.

Введем специальные операции || — приостановка вычислений и @ — возобновление ранее отложенных вычислений. Избежать целостного представления ряда целых можно, изменив формулу:

(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M ( || (ряд_цел (1+ M) N))))))

(defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( @ ( сумма (cdr X))))) ))

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

Тогда в выражении (all (cons { 1 | 2 } || (цел 3 100) )) второй аргумент cons выполнится только для одного варианта, а для второго подставится готовый результат. Таким образом, рецепт имеет вид:

{ ( F e AL ) | ( T X ) },

где X = ( eval e AL ).

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

(defun цел (M) (cons M ( || (цел (1+ M) ))))

Можно из организованного таким образом списка выбирать нужное количество элементов, например первые K элементов можно получить по формуле:

(defun первые (K Int) (cond ((= Int Nil) Nil)((= K 0) Nil) (T (cons (car Int)( первые ( @ (cdr Int))) )) ))

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

||e = > (lambda () e ) @e = > (e ),

что при интерпретации приводит к связыванию функционального аргумента с ассоциативным списком для операции || и к вызову функции EVAL для операции @.

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

В некоторых языках программирования, таких как язык SAIL и Hope, отложенные или замедленные вычисления — lazy evaluation основная модель вычислений.

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

Более подробно о тонкостях определения ленивых вычислений рассказано в книге Хендерсона [3].


Содержание раздела