На этом шаге мы рассмотрим понятие таких вычислений.
В языках императивного программирования (например, С) вызов функции приводит к вычислению всех переданных ей на вход аргументов. Константы в качестве аргументов передаются в функцию непосредственно. Переменные означиваются, и в самой функции используются значения этих переменных, которые они получили на момент передачи в качестве параметров в функцию. Если среди аргументов имеется вызов функции, то сначала происходит запуск процесса вычисления этой функции, а полученный результат уже передаётся внутрь исходного вычислительного процесса.
Таким образом, известны значения всех входных параметров на момент входа в процесс вычислений, описанный функцией, в обычных языках программирования, не поддерживающих свойства отложенности вычислений. Это позволяет в ходе вычислительного процесса не заботиться о том, что во время вычислений какой-либо из входных аргументов может изменить своё значение. Этот момент вызова функции называется вызовом функции по значению.
Ясно, что если какой-либо аргумент не использовался в функции, то результат его вычисления пропадает, следовательно, сами вычисления были произведены впустую.
Противоположностью вызова по значению является вызов функции по необходимости. В этом случае аргумент вычисляется только в том случае, если он нужен для вычисления окончательно результата, возвращаемого функцией.
Примером таких вычислений является операция "логическое И" (&&) языка С, которая не вычисляет значение второго аргумента, если первый аргумент имеет ложное значение; также не вычисляется значение второго операнда операции "дизъюнкция" (||), если первый операнд принимает значение, отличное от 0. Поэтому можно написать такой код (несмотря на то что вычисление второго операнда операции (&&) приведёт к возникновению ошибки "деление на нуль", на деле ошибка не возникает):
if (false && (x/0))
{
...
}
Иногда подобный способ организации вычислений называется логикой короткого замыкания - это автоматическое прекращение вычислений в случае, если результат вычислений уже известен.
Приведем несколько демонстрационных примеров.
/* Демонстрация: */ /* (1) операций, нестрогих по второму аргументу */ /* (отложенных вычислений); */ /* (2) энергичных вычислений */ /* --------------------------------------------- */ #include<stdio.h> #include<conio.h> int bot(); int const_1 (int); /* -------------- */ int main() { int x=0, y=1; /* ----------------------------- */ /* Простые отложенные вычисления */ /* ----------------------------- */ printf("(1) %d\n",y||5/x); getch(); printf("(2) %d\n",0&&5/x); getch(); printf("(3) %d\n",x<y?y:1/0); getch(); x=1/0, y=2; printf("(4) %d\n",y); getch(); /* ------------------------------------------- */ /* "Энергичные" вычисления */ /* ------------------------------------------- */ printf("Вошли в функцию bot() и \"висим\"...\n"); const_1 (bot()); return 0; } /* --- */ int bot() /* Функция реализует бесконечную рекурсию */ { return bot(); } /* ------------- */ int const_1 (int n) /* Функция возвращает 1 независимо */ /* от значения аргумента */ { return 1; }
Описанный случай вызова по необходимости в языках императивного программирования - является, скорее, исключением, нежели общим принципом построения таких языков программирования.
Вызов по необходимости в языках функционального программирования называется отложенными вычислениями.
Отметим, что свойство отложенности вычислений характеризует исключительно функциональные языки программирования (правда, не все функциональные языки поддерживают это важное свойство).
- Определение.
- Отложенными ("ленивыми", нестрогими) вычислениями называется организация процесса вычислений, для которой характерно отсутствие вычислений в случаях, когда результат этих вычислений не требуется.
Итак, в языках функционального программирования можно определять и использовать конструкции, подобные следующей:
x = constant_1 bot
where bot = bot
constant_1 n = 1
На вход функции constant_1() подаётся функция bot(), которая определяет бесконечный рекурсивный вызов самой себя. Однако это не вызовет никаких последствий для транслятора языка Haskell, так как значение функции constant_1() равно 1.
Приведем несколько демонстрационных примеров.
-- Демонстрация отложенных ("ленивых") вычислений -- в языке Haskell -- ********************* fun1:: Int -> Int -> Int fun1 x y = if x>0 then x else y `div` 0 --------------------------- test1 = fun1 34 45==34 ------------------------- fun2:: Int -> t -> t -> t fun2 n x y | n>0 = x | True = y --------------------------------------------- test2 = fun2 1 234 (100 `div` 0) == 234 && (fun2 1) 234 (100 `div` 0) == 234 && ((fun2 1) 234) (100 `div` 0) == 234 ------------------------------------------------- -- Демонстрация необходимости вычисления значений -- аргументов при вызове функции -------------------------------- fun3:: Int -> Int -> Int fun3 a b = a+b ---------------------------------------------------- test3 = fun3 (9-3) (fun3 34 3 `div` 0) -- Ошибка... ----------------------------------------------------- -- Демонстрация отложенности ("ленивости") вычисления -- значения второго аргумента b функции fun3. -- Если бы вычисления были "энергичными", то было бы -- получено сообщение об ошибке ------------------------------- fun4:: Int -> Int -> Int fun4 a b = a+12 ------------------------------------------ test4 = fun4 (9-3) (fun3 34 3 `div` 0)==18 ----------------------------------------------------- -- Демонстрация отложенности ("ленивости") вычисления -- значения второго компонента пары (a,b). -- Если бы вычисления были "энергичными", то было бы -- получено сообщение об ошибке ------------------------------- fun5:: (Int,Int) -> Int fun5 (a,b) = a + 1 --------------------------------- test5 = fun5 (3+2,-17 `div` 0)==6 ---------------------------------- -- Вычисления стали "энергичными": -------------------------------------------- test6 = fun5 (-17 `div` 0, 34) -- Ошибка... -------------------------------------------- fun6:: Int -> Int -> Int fun6 a b = b + 1 ------------------------------- test7 = fun6 (3 `div` 0) 12==13
-- Демонстрация ленивых вычислений в Haskell -- ******************************************** -- Функция возвращает 0, если значением первого -- аргумента является 0, и значение второго ар- -- гумента - в противном случае ------------------------------- func:: Int -> Int -> Int func x y | x==0 = 0 | True = y -------------------------------------- -- Рекурсивная функция без аргументов, -- моделирующая зацикливание ---------------------------- p = p ------------------------- main = func 0 (1 `div` 0) -- ********************** test = main==0
-- Демонстрация "ленивых" вычислений в языке Haskell -- ************************************************* f x y = if y==0 then 0 else f (f x y) (f y x) -- ***************************** -- Неудачные тестовые примеры: ------------------------------ test1 = f 1 1 test2 = f 12 1 test3 = f 1 12 test4 = f 0 1
- Определение.
-
- (1) Строгим (энергичным) языком функционального программирования называется язык функционального программирования, который не поддерживает отложенных вычислений, т.е. порядок вычисления строго определён.
- (2) Нестрогим (ленивым) языком функционального программирования называется язык функционального программирования, который поддерживает отложенные вычисления.
Примерами строгих языков являются Scheme, Standard ML, Caml. Примерами нестрогих языков являются Haskell, Miranda.
Часто строгие языки включают в себя средства поддержки некоторых полезных возможностей, присущих нестрогим языкам (например, бесконечные списки); так, например:
- в Standard ML присутствует специальный модуль для поддержки отложенных вычислений;
- Objective Caml поддерживает дополнительное ключевое слово lazy и специальную конструкцию для списков значений, вычисляемых по необходимости.
Нестрогие языки программирования часто также поддерживают свойство чистоты языка.
- Определение (повторение).
- Говорят, что функция является чистой функцией, если вычисление её значения не влияет на результаты работы других функций (другими словами, функция не имеет побочных эффектов.
На следующем шаге мы рассмотрим моделирование "ленивых" вычислений.
