Замедленные вычисления
Средства управления процессами в функциональном программировании изначально опираются на интуитивное представление о вычислении выражений, согласно которому функция применяется к заранее вычисленным аргументам.
Ради полноты пространства вычислений, гибкости программ и результативности процессов такое представление пришлось расширить и ввести категорию специальных функций, которые "знают", когда и что из их аргументов следует вычислить. Специальные функции могут анализировать и варьировать условия, при которых вычисление аргументов необходимо. Так используется возможность манипулировать данными, представляющими выражения, и явно определять в программах позиции обращения к интерпретатору. Эта возможность применялась для поддержки стандартной программотехники и традиционных форм конструирования функциональных объектов.
Свойственная функциональному программированию тенденция к полномасштабному применению всех попадающих в поле зрения средств логически требует перехода от частных случаев к поддержке универсального механизма, т.е. от набора конкретных специальных функций к более общему аппарату управления процессами вычислений.
Результат управления проявляется в изменении некоторых оценок, например можно влиять на эффективность и надежность программ, обусловленную целостностью объемных, сложных данных, избыточностью вычислений, возможно, бесполезных выражений, необоснованной синхронизацией формально упорядоченных действий. Подобные источники неэффективности могут быть устранены достаточно простыми методами организации частичных вычислений с учетом дополнительных условий для их фактического выполнения, таких как достижимость или востребованность результата вычислений.
Любое очень объемное, сложное данное можно вычислять "по частям". Вместо вычисления списка
(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].
