Введение в программирование на Лиспе



             

Замедленные вычисления (lazy evaluation) - часть 2


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

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

Избежать целостного представления большого и возможно бесконечного ряда чисел можно небольшим изменением формулы, отложив вычисление второго аргумента 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))) )) ))

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




Содержание  Назад  Вперед