Замедленные вычисления (lazy evaluation)
Интуитивное представление о вычислении выражений, согласно которому функция применяется к заранее вычисленным аргументам, не всегда гарантирует получение результата. Ради полноты вычислений, гибкости программ и результативности процессов такое представление можно расширить и ввести категорию специальных функций, которые "сами знают", когда и что из их аргументов следует вычислить. Примеры таких функций - специальные функции QUOTE и COND, которые могут анализировать и варьировать условия, при которых вычисление необходимо. Такие функции манипулируют данными, представляющими выражения, и явно определяют в программах позиции обращения к интерпретатору.
Источником неэффективности стандартных "прямолинейных" вычислений может быть целостность больших сложных данных, избыточное вычисление бесполезных выражений, синхронизация формально независимых действий. Такую неэффективность можно смягчить простыми методами замедленных вычислений (lazy evaluation). Необходимо лишь вести учет дополнительных условий для их фактического выполнения, таких как востребованность результата вычислений. Такие соображения по обработке параметров функций называют "вызов по необходимости".
Любое большое сложное данное можно вычислять "по частям". Вместо вычисления списка
(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))))) )
Пример 9.1. Построение ряда целых от M до N с последующим их суммированием. Обычная формула: (html, txt)
Введем специальные операции || - приостановка вычислений и @ - возобновление ранее отложенных вычислений.
Приостановка сводится к запоминанию символьного представления программы, которая временно не вычисляется, но можно вернуться к ее вычислению с помощью операции возобновления. Отложенная программа преобразуется в так называемый рецепт вычисления, который можно хранить как данное и выполнять в любой момент.
В рецепте хранится не только вычисляемая форма, но и контекст, в котором первоначально было предусмотрено ее вычисление. Таким образом, гарантируется, что переход от обычной программы к программе с отложенными действиями не нарушает общий результат.
Избежать целостного представления большого и возможно бесконечного ряда чисел можно небольшим изменением формулы, отложив вычисление второго аргумента CONS "до лучших времен" – когда его значение действительно понадобится более внешней функции:
(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 - истина для уже выполненных рецептов, Nil - ложь для невыполненных.
Таким образом рецепт имеет вид (Nil e AL ) или ( T X ), где X = (eval e AL ) для произвольного e, в зависимости от того, понадобилось ли уже значение рецепта или еще не было в нем необходимости.
Это заодно дает возможность понятие данных распространить на бесконечные множества. Вместо привычного оперирования отрезками целых, не превосходящий заданное число М, можно манипулировать рядом целых, превосходящих M.
(defun цел (M) (cons M ( || (цел (1+ M) ))))
Пример 9.2. Функция над целыми, начиная с М: (html, txt)
Можно из таким образом организованного списка выбирать нужное количество элементов, например, первые K элементов можно получить по формуле:
(defun первые (K Int) (cond ((= Int Nil) Nil) ((= K 0) Nil) (T (cons (car Int)( первые ( @ (cdr Int))) )) ))
Формально эффект таких приостанавливаемых и возобновляемых вычислений получается следующей реализацией операций || и @:
||e = > (lambda () e ) @e = > (e ),
что при интерпретации дает связывание функционального аргумента с ассоциативным списком для операции || - приостановка и вызов функции EVAL для операции @ - возобновление вычислений.
Обычно в языках программирования различают вызовы по значению, по имени, по ссылке. Техника приостановки и возобновления функций может быть названа вызовом по необходимости.
При небольшом числе значений заданного типа, например, для истиностных значений, возможны вычисления с вариантами значений с последующим выбором реальной альтернативы пользователем, но это удобнее обсудить позднее, при изучении вариантов и недетерминированных вычислений.
Техника замедленных вычислений позволяет выполнять декомпозицию программы на обязательно выполнимые и возможно невыполнимые действия. Выполнимые действия в тексте определения замещаются на их результат, а невыполнимые преобразуются в остаточные, которые будут выполнены по мере появления дополнительной информации.
Многие выражения по смыслу используемых в них операций иногда определены при частичной определенности их операндов, что часто используется при оптимизации кода программ (умножение на 0, разность или частное от деления совпадающих форм и т.п.)
Отложенные действия - естественный механизм управления заданиями в операционных системах, а также программирования асинхронных и параллельных процессов.
