Ленивые вычисления
Средства управления процессами изначально опираются на интуитивное представление о вычислении выражений, согласно которому функция применяется к полному списку заранее вычисленных аргументов.
Результат управления вычислениями проявляется в изменении некоторых оценок, например можно влиять на эффективность и надежность программ, обусловленную целостностью объемных, сложных данных, избыточностью вычислений, возможно, бесполезных выражений, необоснованной синхронизацией формально упорядоченных действий. Подобные источники неэффективности могут быть устранены достаточно простыми методами организации частичных вычислений с учетом дополнительных условий для их фактического выполнения, таких как достижимость или востребованность результата вычислений, что и обеспечивается моделью ленивых вычислений.
Любое очень объемное, сложное данное можно вычислять "по частям". Рассмотрим вычисление списка
(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))))) )
Пример 13.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 основная модель вычислений.
Более подробно о тонкостях определения ленивых вычислений рассказано в книге Хендерсона [[23]].
