Совместно с другими учёными Алонзо разработал формальную систему названную Лямбда-исчислением. Система по сути была языком программирования для одной из воображаемых машин. Она была основана на функциях, которые принимают в качестве аргументов функции, и возвращают функцию. Такая функция была обозначена греческой буквой Лямбда, что дало название всей системе.
Каждый раз, когда вы слышите «лямбда» в разговоре о функциональном программировании, переводите это про себя в «функцию». А греческая буква используется для удобства математической записи.
Система Чёрча интересна тем, что в конечном итоге она преобразовалась в реальный язык программирования List Processing language (Lisp), исполняемый компьютером. Это произошло в 1958 году, что делает Lisp вторым (или третьим) по старшинству языком программирования, используемым до сих пор.
Так началось FP на функциональных языках Lisp/Haskel.
Независимо от Алонзо, Алан Тьюринг проводил подобное исследование. Он разработал другую формальную систему (которую сейчас называют Машиной Тьюринга, и используя её пришёл к выводам, подобным Алонзо. Позже было доказано, что машина Тьюринга и лябда-исчисление имеют одинаковую мощность.
Далее они привели доказательство, названное в последствии теоремой Чёрча — Тьюринга, что не существует решения для проблемы разрешения (Entscheidungsproblem)
Проблемы разрешения (Entscheidungsproblem)) - найти такой алгоритм, который бы принимал в качестве входных данных описание проблемы, требующей ответа ИСТИНА или ЛОЖЬ, затем после n количества шагов останавливался бы, и выдовал один из таких ответов.
Функциональное программирование — это практическая реализация идей Алонзо Чёрча, а не четкие инструкции и действия. Поэтому FP — это набор идей, а не набор четких указаний. Существует много функциональных языков, и большинство из них делают одни схожие вещи по разному.
Лямбда исчисление было придумано для изучения проблем, связанным с вычислениями. Функциональное программирование, стало быть, в первую очередь имеет дело с вычислениями, и, на удивление, использует для этого функции.
Функция — это базовый элемент FP. Функции используются почти для всего, даже для простейших расчётов. Даже переменные заменяются функциями. В функциональном программировании переменные — это просто синонимы (alias) для выражений (чтобы нам не пришлось писать всё в одну строку). Их нельзя изменять. В каждую переменную можно записать только один раз. В терминах Swift это означает, что все переменные объявляются как final (или const если имеем дело с C++). В ФП нет не-final переменных.
неизменяемое состояние и отсутствие побочных эффектов
Функции в ФП бывают: Higher-Order (высшего порядка) и First-Class (первого класса).
1 ) Функции, которые оперируют функциями (принимают их в качестве аргументов) называются функциями высшего порядка - higher-order. Пусть это вас не пугает. Понятие функций высшего порядка почти не отличается от понятия Swift классов, которые оперируют друг другом (мы можем передавать классы в другие классы). Мы можем называть их «классы высшего порядка», но никто этим не заморачивается, потому что за Swift не стоит строгое академическое сообщество.
Наиболее распространенными функциями высшего порядка в языках FP: filter, map и reduce. Пример: ссылка
2 ) Функции первого класса - фича языка, позволяющая использованы функции как любые другие значения. Это включает в себя:
- Присваивание переменным ссылки на функцию;
- Передача функции как аргумента другой функции;
- Возвращение функции из другой функции;
- Хранение функций в структурах данных;
По сути первого класса и высшего порядка - разные вещи, но по отдельности смысла в них не много :)
Альтернатива - указатели на функций. C и C++ используют указатель функции для имитации поведения функции высшего порядка.
-
Функции должны быть объектами высшего порядка и первого класса;
-
Функция не должна изменять внешнее состояние;
-
Функция не должна изменять переданные ей аргументы;
-
Результат функции зависит только от ее аргументов;
-
Можно откладывать, параллелить вычисления на разных потоках/ядрах, серверах и результат всегда будет один и тот же;
Рекурсия — это когда функция вызывает саму себя, и при этом ей нужно держать в памяти все предыдущие этапы.
Лексическое замыкания / Сlosure в Swift
До сих пор мы обсуждали особенности ФП в контексте «чисто» функциональных языков — языков, которые являются реализацией лямбда исчисления и не содержат особенностей, противоречащих формальной системе Чёрча. Тем не менее, многие черты функциональных языков используются за пределами лямбда исчисления.
Хотя реализация аксиоматической системы интересна с точки зрения программирования в терминах математических выражений, это не всегда может быть применимо на практике. Многие языки предпочитают использовать элементы функциональных языков не придерживаясь строгой функциональной доктрины.
Они даже не требуют, чтобы функции зависели только от своих аргументов — функциям дозволенно обращаться к состоянию за пределом своей области видимости. Но при этом они включают в себя такие особенности, как функции высшего порядка. Передача функции в не-чистом языке немного отличается от аналогичной операции в пределах лямбда исчисления и требует наличия интересной особенности под названием: лексическое замыкание.
Замыкание, сделано как обычная функция, за исключением того, что в нём есть дополнительная ссылка на окружающие переменные извне.
Если замыкание обращается к переменной, которой нет в локальной области видимости, тогда оно принимает во внимание родительскую область. Вот и всё! Замыкание связывает функциональный мир с миром ООП. Каждый раз, когда вы создаёте класс, который хранит некоторое состояние, и передаёте его куда-то, вспомните про замыкания. Замыкание — это всего лишь объект, который создаёт «атрибуты» на лету, забирая их из области видимости, чтобы вам не пришлось делать это самим.
Общий синтаксис:
{ (<#parameters#>) -> <#return type#> in
<#statements#>
}Пример использования:
func someFunctionThatTakesAClosure(closure: () -> Void) {
// тело функции
}
// Вот как вы вызываете эту функцию без использования последующего замыкания:
someFunctionThatTakesAClosure(closure: {
// тело замыкания
})
// Вот как вы вызываете эту функцию с использованием последующего замыкания:
someFunctionThatTakesAClosure() {
// тело последующего замыкания
}В честь специалиста по логике Хаскелла Карри (Haskell Curry), который провёл ряд математических трюков, чтобы всё это формализовать.
В функциональном языке вам не понадобятся паттерны проектирования, потому что язык настолько высокоуровневый, что вы легко начнёте программировать в концепциях, которые исключают все известные паттерны программирования.
Одним из таких паттернов является Адаптер (чем он отличается от Фасада? Похоже, что кому-то понадобилось наштамповать побольше страниц, чтобы выполнить условия контракта). Этот паттерн оказывается ненужным если в языке есть поддержка каррирования.
Паттерн Адаптер наиболее часто применяется к «стандартной» единице абстракции в Java — классу. В функциональных языках паттерн применяется к функциям. Паттерн берёт интерфейс и преобразует его в другой интерфейс, согласно определённым требованиям. Вот пример паттерна Адаптер:
int pow(int i, int j);
int square(int i)
{
return pow(i, 2);
}Этот код адаптирует интерфейс функции, возводящей число в произвольную степень, к интерфейсу функции, которая возводит число в квадрат. В аккадемических кругах этот простейший приём называется каррирование. Так как в ФП функции используются повсеместно в качестве аргументов, каррирование используется очень часто, чтобы привести функции к интерфейсу, необходимому в том или ином месте. Так как интерфейс функции — это её аргументы, то каррирование используется для уменьшения количества аргументов (как в примере выше).
Этот инструмент является встроенным в функциональные языки. Вам не нужно вручную создавать функцию, которая оборачивает оригинал. Функциональный язык сделает всё за вас. Как обычно давайте расширим наш язык, добавив в него каррирование.
square = int pow(int i, 2);Как видите, мы просто написали обёртку над оригинальной функцией. Вы сосредотачиваетесь на задаче, а компилятор пишет необходимый код за вас! Всё очень просто, и происходит каждый раз, когда вы хотите использовать паттерн Адаптер (обёртку).
В ФП каррирование как раз и представляет из себя простой и удобный способ создания обёрток
Почитать дополнительно можно здесь
Композиция - склеивание функций для получения более сложный функций, где результат предыдущей
Более распространенный пример:
Array.compactMap { $0 }.filter { $0.count > 0 }Ленивые (или отложенные) вычисления — это интересная техника, которая становится возможной как только вы усвоите функциональную философию.
В императивных языках программирования очерёдность вычисления не вызывает никаких вопросов. Поскольку каждая функция может повлиять или зависеть от внешнего состояния, то необходимо соблюдать чёткую очерёдность вызовов (последовательную).
В ФП вычислениея !не зависят от внешного состояния, поэтому функции не обязательно выполняются последовательно (в том смысле, что они могут не вызваться и не хранить значение до момента его вызова).
Haskell — это пример языка с отложенными вычислениями. В Haskell отсутствует гарантия какой-либо очередности вызовов (вообще!), потому что Haskell выполняет код по мере необходимости.
System.out.println("Please enter your name: ");
System.in.readLine();В ленивом языке никто не гарантирует, что первая строка выполнится раньше второй!
Ленивые языки позволяют создавать бесконечные структуры данных, создание которых в строгих языках гораздо сложнее.
Например, представьте себе последовательность Фибоначи. Очевидно, что мы не можем вычислить бесконечный список за конечное время и при этом сохранить его в памяти. В строгих языках, таких как Java, мы просто написали бы функцию, которая возвращает произвольный член последовательности. В языках подобных Haskell мы можем абстрагироваться и просто объявить бесконечный список чисел Фибоначи. Так как язык ленивый, то будут вычислены лишь необходимые части списка, которые реально используются в программе.
Это позволяет абстрагироваться от большого числа проблем и посмотреть на них с более высокого уровня (например можно использовать функции обработки списков на бесконечных последовательностях).
В функциональной программе всё состояние хранится в стеке в виде аргументов функций, поэтому функциональная программа сразу готова к распараллеливанию без каких-либо изменений. Вам не придётся задумываться о deadlock-ах или состояниях гонки (race conditions) потому что вам не нужны блокировки! Ни один кусочек данных в функциональной программе не меняется дважды одним и тем же потоком или разными. Это означает, что вы можете легко добавить потоков к вашей программе даже не задумываясь при этом о проблемах, присущих императивным языкам.
2.2.1 Types Of Languages Theme | Back To iOSWiki Contents | 2.2.2.1.2 Reactive Programming Theme