Отложенные вычисления (Lazyevaluation) - Функциональные языки программирования

В традиционных языках программирования (например, C++) вызов функции приводит к вычислению всех аргументов. Этот метод вызова функции называется Вызов-по-значению (call-by-value). Если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, следовательно, вычисления были произведены впустую. В каком-то смысле противоположностью вызова-по-значению является Вызов-по-необходимости (call-by-need). В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Предположим, что мы хотим определить оператор конъюнкции (логическое и). На C мы можем прибегнуть к следующему определению (намеренно не используя оператор&;&;):

Int and (int x, int y) { if (x) return y; else return 0; }

Мы не сможем пользоваться этим оператором также как предопределенным оператором, потому что даже если x == FALSE, y все равно будет вычислен перед вызовом функции, так что простой оператор

If (and (y!= 0.0, 1.0 / y > 2.0)) printf ("y = %g ", y);

В случае если y окажется равным 0.0 произойдет деление на 0, а это совсем не то, что нам нужно. Если же мы определим подобную функцию на Haskell (который поддерживает отложенные вычисления), то все будет работать как должно:

-- Возвращает True, Если Оба Аргумента Истинны

And:: Bool -> Bool -> Bool

And x y = cond (x, y, False)

Cond:: Bool -> a -> a

Cond True result _ = result

CondFalse _ result = result

Обратите внимание на функцию cond, которая представляет собой не что иное как аналог конструкции if-then-else в традиционных языках программирования. В языках, использующих вызов-по-значению определить такую функцию невозможно, т. к. вне зависимости от логического условия будут вычислены Оба других аргумента, хотя в каждом случае вычислять нужно только Один.Одним из самых полезных свойств отложенного вычисления является, пожалуй, возможность определения потенциально бесконечных структур данных, чаще всего - списков (lazylists). Например, Haskell позволяет очень просто определить список всех простых чисел.

-- Возвращает Список Делителей Аргумента

Divisors:: Int -> [Int]

Divisors n = [m | m <- [1.. n], n 'mod' m == 0]

    -- Предикат, Возвращает True, Если Аргумент - Простое Число -- Число Является Простым, Если Оно Делится Только На 1 И На Себя

IsPrime:: Int -> Bool

IsPrime n = (divisors n) == [1, n]

    -- Возвращает Список Всех Простых Чисел, Получая Его Фильтрацией -- Множества Натуральных Чисел Предикатом IsPrime

Primes:: [Int]

Primes = filter isPrime [1..]

Разумеется, это далеко не самый быстрый способ вычисления простых чисел, однако один из самых простых. Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим (strict). В самом деле, в таких языках порядок вычисления строго определен. В качестве примера строгих языков можно привести Scheme, Standard ML и Caml. Языки использующие отложенные вычисления называются нестрогими (non-strict или lazy). Haskell - нестрогий язык, так же как, например, Gofer и Miranda. Нестрогие языки зачастую являются чистыми. Зачастую строгие языки включают в себя средства поддержки некоторых полезных элементов, присущих нестрогим языкам, например, бесконечных списков. В поставке Standard ML присутствует специальный модуль для поддержки отложенных вычислений. А ObjectiveCaml помимо этого поддерживает дополнительное зарезервированное слово lazy и конструкцию для списков значений, вычисляемых по необходимости.

Похожие статьи




Отложенные вычисления (Lazyevaluation) - Функциональные языки программирования

Предыдущая | Следующая