Особенности функционального программирования
Функциональное программирование базируется на идеях Алонзо Чёрча и его λ-исчислении, которое опирается на функцию в его математическом смысле и значении, что отличает его от императивного программирования, которое описывает процесс вычисления как последовательность изменения состояния некоторого автомата.
λ-исчисление
λ-исчисление является формальной математической системой, разработанной Алонзо Чёрчем в первой половине XX века. Алонзо Чёрч и Алан Тьюринг доказали, что существуют задачи, которые невозможно решить механически за конечное число шагов (см. теорему Чёрча — Тьюринга и проблему разрешения).
Формальная система λ-исчисление записывается в следующей форме Бэкуса-Наура: 
, где s — выражение, а x — переменная. 
также называется абстракцией, а 
— аппликацией.
Я не буду подробно останавливаться на полном описании идей Чёрча. Следующие материалы могут быть полезны для дальнейшего изучения вопроса:
- Lambda Calculus and Types by Andrew D. Ker [pdf]
- What is Lambda Calculus and should you care? (пер. λ-исчисление. Часть первая: история и теория)
- Church numbers by Robert ”Corky” Cartwright [pdf]
Свойства функциональных языков
Часто к достоинствам функциональных языков (для удобство обзовём их свойствами) относят следующее [1]:
- лаконичность;
- функции как значения
- отсутствие побочных эффектов (сайд-эффектов)
- ленивые вычисления
- строгая типизация
- модульность
Лаконичность
Конструкции функциональных языков позволяют описывать решение задач, близкому к математическому описанию. Сравните описание функции возведения в степень на C++:
#include <iostream>
int power(int a, int n) {
if (n == 0) {
return 1;
}
return a * power(a, n - 1);
}
int main(int argc, char *argv[]) {
std::cout << power(3, 3);
}
и на Хаскеле:
power a 0 = 1
power a n = a * power a (n - 1)
main = do
print (power 2 8)
Другой пример состоит в сортировке вставками. Код на Джава выглядит следующим образом:
import java.util.Arrays;
public class Main {
public void sort(int[] input) {
for (int j = 1; j < input.length; j++) {
int value = input[j];
for (int i = j - 1; i >= 0 && value < input[i]; i--) {
input[i + 1] = input[i];
input[i] = value;
}
}
}
public static void main(String[] args) {
int[] array = {5, 3, 9, 5, 6, 1, 2, 4, 8, 7};
new Main().sort(array);
System.out.println(Arrays.toString(array));
}
}
Возможности Хаскеля позволяют решить эту задачу быстрее:
import Data.List
insertionSort = foldr insert []
main = do
let xs = insertionSort [5, 3, 9, 5, 6, 1, 2, 4, 8, 7]
print xs
Функции как значения
В функциональных языках программирования функции являются объектами первого класса. Другими словами, они могут быть переданы как значение параметров, возвращены как результат или же присвоены переменной. Возможность передавать функцию в качестве аргумента была перенесена в другие языки программирования, такие как Джава (начиная с Java 8), С++ (начиная c С++11) и др. как анонимные функции. Примитивная реализация функции fold на Джаве:
public class Main {
interface Function {
int apply(int a, int b);
}
public static int fold(Function function, int acc, int[] xs) {
for (int x : xs) {
acc = function.apply(acc, x);
}
return acc;
}
public static void main(String[] args) {
// До версии Java 8 используется анонимный класс
// int result = fold(new Function() {
// @Override
// public int apply(int a, int b) {
// return a + b;
// }
// }, 0, new int[]{1, 3, 2, 4});
// С версии Java 8 можно использовать анонимную функцию (лямбда-функцию)
int result = fold((a, b) -> a + b, 0, new int[]{1, 3, 2, 4});
}
}
Динамические языки, такие как Питон, JS или Руби имеют возможность присваивать функцию переменной:
def fold(f, acc, xs):
for x in xs:
acc = f(acc, x)
return acc
sum = lambda a, b : a + b
print sum(2, 3)
print fold(sum, 0, [1, 3, 2, 4])
Функции, которые принимают другие функции в качестве аргументов называют функциями высшего порядка или функционалами. Функция fold в нашем примере является функционалом, так же, как и функция Хаскеля foldr, используемая в примере выше для сортировки. Достаточно распространённая функция map применяет некоторую функцию к элементам списка:
main = do
let squares = map (\n -> n * n) [1, 2, 3, 4, 5, 6, 7, 8, 9]
print squares
Отсутствие побочных эффектов
Побочными эффектами называют неявное изменение значений переменных, не являющимися локальными для выполняемой последовательности команд (функций или процедур). Так, в языке С имеется возможность изменения значений глобальных переменных, в том числе, определённых в других модулях, а в объектно-ориентируемых языках — значений переменной экземпляра класса. В функциональном программировании никакая функция не может изменить состояние. Такие функции называются чистыми, что даёт уверенность в том, что вызов одной и той же функции несколько раз будет возвращать одно и то же значение (Pure Functions, Laziness, I/O, and Monads). К плюсам относят возможность при выполнении программы параллельно выполнять отдельные функции. Наличие чистых функций хорошо для математиков, но в реальности становится неясным, как работать с внешним миром, например, записывать или читать файлы, отправлять какие-либо данные по сети и т.д.[2] Данная проблема будет подробней описана в другой статье.
Ленивые вычисления
Ленивые вычисления означают, что в ходе выполнения программы не будут вычислены те функции, результат которых не влияет на общий требуемый результат. Например, следующий код приводит к ошибке деления на 0:
main = do
let x = 30 `div` 0
print (x)
-- Main.hs: divide by zero
Но, к примеру, для того, чтобы вычислить длину списка, нет необходимости вычислять сами значения элементов списка. Следующий код не будет вычислять значение и ошибки не произойдёт:
main = do
let x = 30 `div` 0
print (length [x])
Другие свойства
Такие свойства как строгая типизация или модульность не является уникальным для функционального программирования явлением. Более подробно о типизации можно прочитать в статье «Ликбез по типизации в языках программирования».