Содержание


Ленивое программирование и ленивые вычисления

Узнайте о неожиданной пользе отсроченной обработки функций

Comments

Несложное ленивое программирование в Scheme

Ленивое программирование -- технология, которая позволяет вам отсрочить вычисление кода до тех пор, пока не понадобится его результирующее значение. В Scheme, например, ленивое программирование явно поддерживается при помощи двух специальных конструкций. Специальная форма Scheme delay берет блок кода и, вместо того чтобы выполнять, откладывает его и его параметры как promise. Если вы примените к promise force для получения значения, код будет выполнен. Затем promise сохранит результат, так что будущие запросы значения будут возвращены немедленно без повторного выполнения кода.

Вот простой пример совместного использования delay и force:

Листинг 1. Пример использования delay и force
;;The multiplication is saved but not executed
(define my-promise (delay (* 5 6 7 8 9)))

;;Again, saved but not executed
(define another-promise (delay (sqrt 9)))

;;Forces the multiplication to execute.  Saves and returns the value
(display (force my-promise))
(newline)

;;This time, the multiplication doesn't have to execute.  It just returns
;;the value that was previously saved.
(display (force my-promise))
(newline)

;;This produces an error, because the promise must be forced to be used
(display (+ my-promise (force another-promise)))

Эти конструкции довольно просты в использовании, но для чего они нужны? Вообще, ленивое программирование используют, когда функция генерирует значение, которое может не использоваться вызывающей программой. Например, у вас есть функция, которая вычисляет среднее (mean), расхождение (variance) и стандартное отклонение (standard deviation) для списка чисел. Вот один из способов сделать это:

Листинг 2. Простые статистические вычисления
(define (square x) (* x x))
(define (calculate-statistics the-series)
   (let* (
          (size (length the-series))
          (sum (apply + the-series))
          (mean (/ sum size))
          ;variance is the sum of (x[i] - mean)^2 for all list values
          (variance 
            (let* (
                   (variance-list (map (lambda (x) (square (- x mean))) the-series)))
              (/ (apply + variance-list) size)))
          (standard-deviation (sqrt variance)))
     (vector mean variance standard-deviation)))

;Run the program
(display (calculate-statistics '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(newline)

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

Лучшим вариантом может быть ленивое вычисление с задержкой расчетов:

Листинг 3. Статистические вычисления при помощи ленивых вычислений
(define (square x) (* x x))
(define (calculate-statistics the-series)
   (let* (
          (size (delay (length the-series)))
          (mean (delay (/ (apply + the-series) (force size))))
          ;variance is the sum of  (x[i] - mean)^2
          (variance 
            (delay 
              (let* (
                     (variance-list (map (lambda (x) (square (- x (force mean)))) 
                      the-series)))
                (/ (apply + variance-list) (force size)))))
          (standard-deviation (delay (sqrt (force variance)))))
     (vector mean variance standard-deviation)))

;Run the program
(define stats (calculate-statistics '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(define mean (force (vector-ref stats 0)))
(define variance (force (vector-ref stats 1)))
(define stddev (force (vector-ref stats 2)))
(display (list mean variance stddev))
(newline)

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

Этот тип лени также довольно легко может быть осуществлен в объектно-ориентированном языке. Везде, где необходима группа связанных вычислений, вы можете создать класс для хранения промежуточных значений. Конструктор берет используемые исходные значения и все вычисленные значения должны быть установлены в null. Вместо использования force у вас будет getter для каждого значения, который будет проверять, является ли значение null, и, если нет, будет производиться вычисление. Вот заготовка такого класса, написанная на языке Java™:

Листинг 4. Переформулирование ленивых вычислений на языке Java
public class StatisticsCalculator {
       private List the_series;
       private Double mean;
       private Integer size;
       private Double variance;
       private Double standard_deviation;
       public StatisticsCalculator(List l)
       {
          the_series = l;
       }
       public int getSize()
       {
          if(size == null)
          {
             size = the_series.size();
          }
          return size;
       }
       public double getStandardDeviation()
       {
          if(stddev == null)
          {
             stddev = Math.sqrt(getVariance());
          }
          return stddev;
       }
       ...
       ...
}

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

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

Неопределенные списки

Скажем, у вас есть список всех чисел, кратных пяти. Затем, вы хотите возвести все эти числа в квадрат. И, наконец, вы хотите повторить вычисления и выявить все числа, результат для которых оказался менее 500. Что? Вы не можете работать с бесконечными списками? Почему нет?

Действительно, несмотря на то, что это может не быть интуитивно-понятно, для хранения бесконечных списков может потребоваться меньше места, чем для хранения множества конечных списков, в случае, если бесконечный список основан на порождающем правиле (generative rule). В вышеприведенном примере первоначальный список основан на правиле X[i] = (i + 1) * 5, где X[i] -- значение индекса списка i. X[i] также может быть выражен при помощи предшествующих членов: X[i] = X[i-1] + 5; X[0] = 5. Используя операции Scheme'ы force и delay, вы можете создать поток (stream) значений, основанных на этом правиле:

Листинг 5. Пример потока
;This is the generative rule for the list. It returns a pair 
;with the car being the next value, and the cdr being a promise 
;for the next pair
(define (my-generative-rule last-val)
        (let (
              ;generative formula based on previous value
              (next-val (+ last-val 5)))
          ;put the next value together with a promise for another one
          (cons next-val (delay (my-generative-rule next-val)))))
;Since the cdr is a promise of a pair, rather than a pair itself, 
;we have our own functions for getting the car and cdr.
(define (mystream-car the-stream) (car the-stream))
(define (mystream-cdr the-stream) (force (cdr the-stream)))

;Create our list
(define multiples-of-five (cons 5 (delay (my-generative-rule 5))))

;Display the fourth element of the list
(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr multiples-of-five)))))
(newline)

Помните, вы хотели возвести в квадрат все числа. Чтобы сделать это, вам необходима функция, которая может создать новый поток из существующих потоков и порождающих правил, отчасти похожую на map, но для потоков. Вот эта функция:

Листинг 6. Специализированный map для потоков
(define (mystream-map function the-stream)
  (cons 
    ;;The first value will be the function applied to the car
    (function (car the-stream)) 
    ;;The remaining values will be stored in a promise
    (delay (mystream-map function (mystream-cdr the-stream)))))

(define squared-stream (mystream-map (lambda (x) (* x x)) multiples-of-five))

;Display the fourth element of this new list
(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr squared-stream)))))
(newline)

Теперь все, что осталось сделать, это выполнить итерацию через поток и вывести значения меньше 500:

Листинг 7. Итерация через поток
(let loop (
           (remaining-stream squared-stream))
  (if (>= (mystream-car remaining-stream) 500)
      #f
      (begin
        (display (mystream-car remaining-stream))
        (newline)
        (loop (mystream-cdr remaining-stream)))))

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

Потоки, о которых я рассказывал до этого момента, полезны для изучения понятий, выходящих за пределы собственно потоков. Однако имплементацию сопровождают многочисленные трудности. Прежде всего, есть много случаев, когда потокам необходим ограничитель. Эта имплементация не предоставляет такой возможности. Кроме того, показанные здесь потоки известны как нечетные потоки (odd streams), и нечетный стиль легко имплементировать. Но такие потоки могут привести к тому, что будет произведено большее количество вычислений, чем подразумевалось, поскольку всегда оценивается "car" списка. Как определено в SRFI-40, стандартные потоки имеют отношение к этим и другим вещам (подробнее см. в разделе Ресурсы).

Пропуск промежуточных переменных

До сих пор все наши примеры ленивых вычислений заставляли полностью выполнять промежуточные вычисления, прежде чем двигаться дальше. Часть этих вычислений необходима для решения проблемы и часть вызвана выполнением самих delay и force. Например, рассмотрим следующий код:

(define val1 20)
(define val2 30)
(define val3 40)
(define val4 0)
(define val5 (delay (* val1 val2)))
(define val6 (delay (* val4 val3)))
(define val7 (* (force val5) (force val6)))

В этом случае мы знаем, что ответом будет ноль, просто потому что мы знаем, что ноль всегда ноль. И хотя может показаться, что в этом случае могут подойти ленивые вычисления (поскольку мы пытаемся предотвратить излишние вычисления), фактически использование delay и force нам не поможет.

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

Вот часть специализированной пары delay/force, предназначенной для выполнения умножения:

Листинг 8. Простая специализированная пара delay/force
;This will simply use a list to keep track of the values to be multiplied
(define (multiply-delay x y)
   (let (
         ;convert to lists if they aren't already
         (x-list (if (list? x) x (list x)))
         (y-list (if (list? y) y (list y))))
     ;append them together
     (append x-list y-list)))
(define (multiply-force mul-list)
  (let (
        (has-zero? #f))
    (for-each 
      (lambda (x) 
        (if (eqv? 0 x) 
            (set! has-zero? #f) 
            #f))
      mul-list)
    (if has-zero?
        0
        (apply * mul-list))))
(define a (multiply-delay 23 54))
(define b (multiply-delay 0 5))
(define c (multiply-delay a b))
(define d (multiply-delay c 55)
(display (multiply-force d))
(newline)

Однако эта имплементация имеет свои проблемы. Отдельные части больше не ленивы и больше не сохраняют свои значения. Мы потеряли все преимущества первоначальных delay и force, чтобы достичь единственной оптимизации. Поэтому, вместо того чтобы хранить длинный список всех параметров, нам необходимо хранить их разделенными на отдельные promise'ы, так что мы по-прежнему сможем иметь те преимущества, которые имели ранее. То, что нам нужно, это признак, который показывает, произведено вычисление значения или нет. Если да, там есть только один элемент, который не нуждается в вычислении. В противном случае присутствуют множитель и множимое. Вот новый код:

Листинг 9. Другая специализированная ленивая конструкция
;Unevaluated promises will have the structure ('delayed val1 val2)
;Evaluated promises will have the structure ('forced result)

;Create an unevaluated promise
(define (multiply-delay x y)
   (list 'delayed x y))

;Checks promises (and values) to see if they contain any zeros
(define (has-zero promise)
  (if (pair? promise)
      (if (eq? (car promise) 'forced)
          ;check forced value
          (if (eqv? (cdr promise) 0)
              #t
              #f)
          ;check unforced value
          (if (or (has-zero (cadr promise)) (has-zero (caddr promise)))
              #t
              #f))
      ;Check scalar value
      (if (eqv? promise 0)
          #t
          #f)))

;Attempts zero optimization, then defaults to regular delay/force behavior
(define (multiply-force promise)
  (if (eq? (car promise) 'forced)
      ;if we've already been forced, return the value
      (cdr promise)
      ;otherwise, search for a zero
      (if (has-zero promise)
          (begin
             (set-car! promise 'forced)
             (set-cdr! promise 0)
             0)
          (multiply-force-nonzero promise))))
   
;This is for promises which are known to be free of zeros
(define (multiply-force-nozero promise)
  (if (pair? promise)
      (if (eq? (car promise) 'forced)
          ;if the promise has been forced, just return the value
          (cdr promise) 
          ;otherwise, compute the value, and convert this into a "forced" promise
          (begin
            (set-car! promise 'forced)
            (set-cdr! promise
              (* 
                 (multiply-force-nonzero (cadr promise)) 
                 (multiply-force-nonzero (caddr promise))))
            ;return the forced value
            (cdr promise)))
      ;This is just a number, so return it
      promise))

Этот код имеет все полезные свойства обычного delay/force. Умножение -- довольно быстрая операция. Вся эта работа, возможно, заняла много времени, но это хороший пример. Это может сэкономить время для операций, требующих более значительных затрат, особенно тех, которые могут потребовать переключения контекста или использования мощного процессора.

Одно из широко распространенных применений этого метода -- добавление к строке. Вместо того чтобы при каждом добавлении записи выделять новое пространство, вы можете просто вести список строк, которые должны быть соединены. Затем, когда необходим последний вариант строки, вы должны только один раз выделить пространство для новой строки. Это позволит не выполнять некоторое количество вызовов malloc, а также сэкономить время на копировании каждой строки.

Ленивые вычисления

До сих пор я фокусировал внимание на ленивых конструкциях внутри неленивого языка. Однако в некоторых языках, например, Haskell, леность является частью обычного процесса вычислений. Это ленивые вычисления (lazy evaluation). В ленивых вычислениях ни один параметр не вычисляется, пока в нем нет необходимости. Программы фактически начинаются с конца и работают от конца к началу. Программа вычисляет, что должно быть возвращено, и продолжает движение назад, чтобы определить, какое значение для этого требуется. В сущности каждая функция вызывается с promise'ами для каждого параметра. Когда для вычисления необходимо значение, тогда выполняется promise. Поскольку код выполняется только тогда, когда необходимо значение, это называется вызов по необходимости (call-by-need). В традиционных языках программирования вместо promise'ов передаются значения, это называется вызов по значению (call-by-value).

Технология программирования "вызов по необходимости" имеет ряд преимуществ. Потоки имплементируются автоматически. Ненужные значения никогда не вычисляются. Однако, поведение ленивых программ часто трудно предсказать. В программах типа "вызов по значению" порядок вычисления довольно предсказуем, поэтому любые time- или sequence-based вычисления относительно легко имплемнтировать. В ленивых языках, где специальные конструкции, например, monads, необходимы для описания явно упорядоченных событий, это намного труднее. Все это также делает связь с другими языками более трудной.

Существуют языки программирования, например, Haskell и Clean, использующие ленивое программирование по умолчанию. Кроме того, для некоторых языков, таких как Scheme, ML и другие, существуют ленивые версии.

Заключение

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


Ресурсы для скачивания


Похожие темы


Комментарии

Войдите или зарегистрируйтесь для того чтобы оставлять комментарии или подписаться на них.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=208651
ArticleTitle=Ленивое программирование и ленивые вычисления
publish-date=04112007