Две популярные формулировки:
-
Язык программирования, в котором функции можно передавать в качестве параметров или получать в результате выполнения функций:
- functions as first-class citizens
- higher-order functions
- очень доброе и широкое объяснение, включает "нефункциональные" языки - C, C++, C#, Java.
-
Язык, в котором написанная программа представляет собой функцию (в математическом смысле), а выполнение программы - вычисление функции.
- Функциональные языки базируются на теории λ-исчисления.
- Теория разработана Алонсо Чёрчем в 1930-х годах.
- Позволяет описать любой алгоритм, включая императивный (структурный) код. Является аналогом машины Тьюринга.
В теории λ-исчисления есть два понятия:
- Абстракция (abstraction) - определение какого-либо выражения. Например, F (используются заглавные буквы).
- Применение (application) - вычисление выражения. Например, F X.
- Чтобы определить аргументы выражения, мы определяем функцию: (λx.M). Это называется λ-абстракция.
- Это означает, что выражнеие M принимает x в качестве аргумента. Так мы получаем функцию, которая для каждому аргументу x ставит в соответствие результат вычисления M.
- Определенная функция анонимная, то есть у неё нет имени.
M = 2 * x + 4 M 5 = (2 * x + 4) 5
L = a + b + c L 5? (a + b + c) 5?
λx.M = λx.(2 * x + 4)
(λx.M) 5 = (λx. (2 * x + 4)) 5 = 2 * 5 + 4 = 14
- чтобы применить параметр к выражению, мы осуществляем подстановку.
- упрощенный пример. Есть выражение (λx. 5 * x * x - 10 * x - 50)
- применение функции будет выглядеть как: (λx. 5 * x * x - 10 * x - 5) 3 = 5 * 3 * 3 - 10 * 3 - 5 = 45 - 30 - 5 = 10
Более формальное описание выражений в λ-исчислении, λ-термом (λ-выражением) может быть:
- переменная - x, y, z (может быть и значением и выражением)
- абстракция - (λx.M)
- применение - M N, или (λx.M) N
Примеры λ-термов: x xz λx.xz (λx.xz)y λy.(λx.xz)y
x - переменная xz - применение z к x λx.xz - абстракция по x (то есть объявление анонимной функции с аргументом x) (λx.xz)y - применение y к выражению λy.(λx.xz)y - абстракция по y
Абстракция в примерах выше идет по одному аргументу. Можно упростить запись, определив в λ-функции несколько аргументов: λxyz.M - то же самое, что и: (λx.(λy.(λz.(M)))) Переход от функции нескольких аргументов к последовательности функций с одним аргументом называется каррирование (curring).
когда мы применяем аргументы к такой функции, параметры ассоциативны влево, то есть в выражении (λxyz.M) 1 2 3, значения аргументов x = 1, y = 2, z = 3
имена переменных могут быть любыми, важно только при абстракции (аналог области видимости).
λx.(λy.(λz. (x + y + z))) = λxyz. x + y + z
(λxyz. x + y + z) 1 2 3
(λx.(λy.(λz. (x + y + z)))) 1 = (λy.(λz. (1 + y + z))) (λy.(λz. (1 + y + z))) 2 = (λz. (1 + 2 + z)) (λz. (1 + 2 + z)) 3 = 1 + 2 + 3 = 6
Абстракция λx.M в Хаскеле выглядит как: \x -> M (вместо λ используется , вместо точки . используется ->)
Примеры анонимных функций: \x -> x + 1 \x -> \y -> x + y \x y -> x + y (равно предыдущей функции)
λ -
. ->
sum2 :: Int -> Int -> Int sum2 = \x -> \y -> x + y
sum15 :: Int -> Int sum15 = sum2 15 = (\x -> \y -> x + y) 15 = \y -> 15 + y
result :: Int result = sum15 6 = (\y -> 15 + y) 6 = 15 + 6 = 21
- Программа в функциональном стиле - функция, выполнение программы - вычисление функции.
- Должно быть понятней более широкое объяснение функциональных языков черех function as first class citizen - в λ-исчислении нет различия между значением и выражением для λ-терма. Такое объяснение подходит для языков, которые имеют элементы функционального программирования.
- В теории λ-исчисления есть понятие вычисления функции, но нет понятия присваивания переменной - благодаря этому нет вопросов насчет чистоты функций и изменения глобального состояния.
- Долно быть понятней, почему в Хаскеле декларации функции записываются через стрелки, например Int->Int->Int. Все функции нескольких аргументов можно рассматривать, как последовательность функций одного параметра.
- Каррирование (currying) или частичное применение функций в функциональных языках получается естественным путем из теории λ-исчисления.
λx.x λx.y λx.xx λxy.x λxy.y λfgx. f(gx)
λx.x - возвращает переданное значение λx.y - возвращает y независимо от переданного x (константная функция) λx.xx - применяет x к самому себе λxy.x - всегда возвращает первый аргумент λxy.y - всегда возвращает второй аргумент λfgx. f(gx) - композиция функций (передаем две функции и параметр, сначала вычисляем g x, потом результат передаем f)
- https://www.youtube.com/watch?v=7BPQ-gpXKt4&list=PLlb7e2G7aSpRDR44HMNqDHYgrAOPp7QLr - подробное описание теории λ-исчисления.
- https://www.youtube.com/watch?v=eis11j_iGMs - краткое описание и пример реализации булевой логики: True, False и логических операций в λ-исчислении.