Если вы новичок в функциональном программировании, вам может быть интересно: «Как я могу создать цикл в функциональном языке программирования?»
Предположим, мы хотим вычислить сумму 1 + 2 + 3 + … + n для заданного n натурального числа. В нефункциональных языках программирования мы обычно используем цикл for или while:
// Imperative style in Java
int sum (int n) {
int s = 0;
for (int i = 1; i <= n; i++) {
s = s + i;
}
return s;
}
Большинство инженеров-программистов настолько знакомы с этими конструкциями циклов, что они кажутся неотъемлемой частью любого языка программирования. Тем не менее, если вы начнете изучать функциональный язык программирования — особенно такой чистый, как Haskell, — вы можете быть удивлены, узнав, что в нем нет таких вещей, как for/while циклов.
Почему так? Потому что циклические конструкции по своей природе императивны. В частности, это утверждения, которые говорят: «Выполните это выражение/команду x раз или выполните это выражение/команду, пока это условие истинно». Эти циклы for и while не являются выражениями, потому что они не возвращают значения. Приведенный выше код является типичным примером императивного стиля программирования: цикл многократно обновляет переменную s посредством присваивания переменной.
Однако в функциональной парадигме все является выражением. В результате нет операторов и, следовательно, нет конструкций цикла. Вместо этого функциональная парадигма смещает мышление с Как я могу использовать цикл для вычисления этого? на Какова рекурсивная структура выражения, которое я пытаюсь сформулировать?
Функций достаточно для повторных вычислений
Как мы можем сформулировать sum как выражение? Мы можем сделать это, опираясь на математическое определение sum следующим образом:
Мы можем перевести это определение непосредственно в рекурсивную функцию — функцию, которая вызывает сама себя.
(* Functional style in OCaml or Haskell *) let rec sum n = if n <= 0 then 0 else n + sum (n-1)
Если подумать, императивное решение довольно низкоуровневое, потому что оно просто состоит из набора последовательных команд, которые обновляют переменную. С другой стороны, рекурсивная версия демонстрирует более высокий уровень абстракции. Действительно, рекурсивное решение формулирует sum n как выражение, которое составлено из двух других выражений.
Увлекательный вывод из функционального программирования заключается в том, что возможности определять функции в терминах самих себя, т. е. рекурсивно, уже достаточно для формулирования повторяющихся вычислений. Никаких специальных циклов не требуется.
Переполнение стека
Какой бы мощной ни была рекурсия, она связана с печально известной проблемой — «переполнением стека». Если мы применим рекурсивное sum из предыдущего раздела к большому числу, выполнение функции может в конечном итоге достичь предела стека. Если мы посчитаем sum 1000000, мы увидим исключение переполнения стека.
let rec sum n = if n <= 0 then 0 else n + sum (n-1) sum 1000000 (* Result: exception Stack_overflow *)
Чтобы понять, почему происходит переполнение стека, давайте посмотрим на выполнение sum применительно к 5.
sum 5 5 + sum 4 5 + (4 + sum 3) 5 + (4 + (3 + sum 2)) 5 + (4 + (3 + (2 + sum 1))) 5 + (4 + (3 + (2 + (1 + sum 0)))) 5 + (4 + (3 + (2 + (1 + 0)))) 5 + (4 + (3 + (2 + 1))) 5 + (4 + (3 + 3)) 5 + (4 + 6) 5 + 10 15
Обратите внимание, что цепочка отложенных вычислений вызвана тем, что рекурсивный вызов является частью операции n + sum (n — 1). Среда выполнения использует стек вызовов, чтобы помнить, куда вернуться после разрешения отложенных вычислений. Мы ясно видим, что чем больше n, тем длиннее цепочка расширяется вправо. Точнее, количество кадров стека, используемых во время выполнения, растет линейно с n. Если это число превышает определенный порог, мы получаем ошибку переполнения стека. Но не все рекурсивные функции вызывают переполнение стека.
Хвост-рекурсивные функции
Давайте еще раз посмотрим на функцию суммы для вычисления 1 + 2 + 3 + … + n, но на этот раз по-другому. Мы поддерживаем текущий sum и счетчик c. Изначально sum равно 0, а c равно 1. На каждом шаге sum и c обновляются в соответствии со следующими правилами.
Процесс итерации завершается, когда c больше n, и в этом случае sum содержит окончательный результат.
На первый взгляд может показаться, что мы отошли от функционального программирования и вернулись к императивной парадигме. В конце концов, это именно то, что мы сделали в императивной реализации в начале этой статьи. Там мы также поддерживали счетчик и текущую сумму в цикле for. Тем не менее, мы сохраняем мышление, основанное на выражениях, формулируя приведенный выше алгоритм как функцию.
Здесь аргумент s представляет текущую сумму, c представляет счетчик, а n представляет количество натуральных чисел, которое мы хотим сложить. Мы можем перевести эту функцию с тремя аргументами в рекурсивную функцию.
let rec sum_iter s c n = if c > n then s else sum_iter (s + c) (c + 1) n sum_iter 0 1 3 (* Result: 6 *)
В отличие от sum из предыдущего раздела, sum_iter не вызывает ошибки переполнения стека даже в случае большого аргумента. Например, sum_iter 0 1 1000000 без проблем возвращает результат.
let rec sum_iter s c n = if c > n then s else sum_iter (s + c) (c + 1) n sum_iter 0 1 1000000 (* Result: 500000500000 *)
Переполнения стека не происходит, потому что sum_iter — это особый тип рекурсивной функции, называемой функция хвостовой рекурсии. Он вызывает сам себя напрямую без дополнительных операций. Ниже показано выполнение sum_iter 0 1 5.
let rec sum_iter s c n = if c > n then s else sum_iter (s + c) (c + 1) n sum_iter 0 1 5 sum_iter 1 2 5 sum_iter 3 3 5 sum_iter 6 4 5 sum_iter 10 5 5 sum_iter 15 6 5
Как мы видим, выполнение хвостовой рекурсии сильно отличается от выполнения нехвостовой рекурсии. В хвостово-рекурсивном варианте цепочка отложенных вычислений не выстраивается. Каким бы большим ни было n, форма исполнения остается неизменной. В результате компилятор функциональных языков программирования при компиляции хвостовой рекурсивной функции в машинный или байтовый код не использует никакого стека вызовов для выполнения хвостовой рекурсивной функции. Эта оптимизация называется устранением хвостовой рекурсии. Благодаря этой оптимизации версия с хвостовой рекурсией не вызывает проблемы переполнения стека, несмотря на то, что является рекурсивной функцией.
Таким образом, есть три основные причины, по которым функциональные языки не нуждаются в специальных конструкциях циклов for и while. Во-первых, в функциональных языках программирования все рассматривается как выражение, тогда как циклы for и while являются операторами, а не выражениями. Во-вторых, функции, если они определены сами по себе, достаточны для формулировки повторяющихся вычислений. Наконец, функциональные языки поддерживают оптимизацию хвостовой рекурсии. Это означает, что хвостовая рекурсия использует тот же объем памяти, что и эквивалентный цикл, и, следовательно, не вызывает проблем с переполнением стека.
Если вам понравилась эта статья, вы можете прочитать мою книгу Искусство функционального программирования, в которой я углубляюсь в функциональный образ мышления и попутно сравниваю его с парадигмой императивного программирования.
