## Functional Programming (FP)

1. [Функциональное программирование для всех](https://habr.com/ru/articles/142351/)

## История

Совместно с другими учёными Алонзо Чёрч разработал формальную систему названную Лямбда-исчислением. Система по сути была языком программирования для одной из воображаемых машин. Она была основана на функциях, которые принимают в качестве аргументов функции, и возвращают функцию. Такая функция была обозначена греческой буквой Лямбда, что дало название всей системе.

> Каждый раз, когда вы слышите «лямбда» в разговоре о функциональном программировании, переводите это про себя в «функцию». А греческая буква используется для удобства математической записи.

Система Чёрча интересна тем, что в конечном итоге она преобразовалась в реальный язык программирования `List Processing language (Lisp)`, исполняемый компьютером. Это произошло в 1958 году, что делает Lisp вторым (или третьим) по старшинству языком программирования, [используемым до сих пор](https://typeable.io/blog/2021-10-04-lisp-usage).

Так началось FP на [функциональных языках](../../2.2.1%20TypesOfLanguages.md) Lisp/Haskel.

Независимо от Алонзо, [Алан Тьюринг](/3%20Memory%20and%20Concurrency/3.1%20Memory/3.1.2%20RandomAccessMemory/3.1.2.1%20RAM.md#алан-тьюринг-и-ram) проводил подобное исследование. Он разработал другую формальную систему (которую сейчас называют [Машиной Тьюринга](/3%20Memory%20and%20Concurrency/3.1%20Memory/3.1.2%20RandomAccessMemory/3.1.2.1%20RAM.md#алан-тьюринг-и-ram), и используя её пришёл к выводам, подобным Алонзо. Позже было доказано, что машина Тьюринга и лябда-исчисление имеют [одинаковую мощность](https://cstheory.stackexchange.com/a/637).

Далее они привели доказательство, названное в последствии [теоремой Чёрча — Тьюринга](https://ru.wikipedia.org/wiki/Теорема_Чёрча_—_Тьюринга), что не существует решения для [проблемы разрешения (Entscheidungsproblem)](https://ru.wikipedia.org/wiki/Проблема_разрешения)

> [Проблемы разрешения (Entscheidungsproblem))](https://ru.wikipedia.org/wiki/Проблема_разрешения) - найти такой алгоритм, который бы принимал в качестве входных данных описание проблемы, требующей ответа ИСТИНА или ЛОЖЬ, затем после n количества шагов останавливался бы, и выдовал один из таких ответов.

## Функциональное программирование

Функциональное программирование — это практическая реализация идей Алонзо Чёрча, а не четкие инструкции и действия. Поэтому FP — это набор идей, а не набор четких указаний. Существует много функциональных языков, и большинство из них делают одни схожие вещи по разному.

## Функции

Лямбда исчисление было придумано для изучения проблем, связанным с вычислениями. Функциональное программирование, стало быть, в первую очередь имеет дело с вычислениями, и, на удивление, использует для этого функции.

Функция — это базовый элемент FP. Функции используются почти для всего, даже для простейших расчётов. Даже переменные заменяются функциями. В функциональном программировании переменные — это просто синонимы (alias) для выражений (чтобы нам не пришлось писать всё в одну строку). Их нельзя изменять. В каждую переменную можно записать только один раз. В терминах Swift это означает, что все переменные объявляются как [final](/5%20Swift/5.6%20MethodDispatch/5.6.1%20MethodDispatch.md) (или const если имеем дело с C++). В ФП нет не-final переменных.

> неизменяемое состояние и отсутствие побочных эффектов

### Характеристики функций

Функции в ФП бывают: **Higher-Order (высшего порядка)** и   **First-Class (первого класса)**.

1 ) Функции, которые оперируют функциями (принимают их в качестве аргументов) называются **функциями высшего порядка - higher-order**. Пусть это вас не пугает. Понятие функций высшего порядка почти не отличается от понятия Swift классов, которые оперируют друг другом (мы можем передавать классы в другие классы). Мы можем называть их «классы высшего порядка», но никто этим не заморачивается, потому что за Swift не стоит строгое академическое сообщество.

Наиболее распространенными функциями высшего порядка в языках FP: `filter`, `map` и `reduce`. Пример: ссылка

2 ) **Функции первого класса** - фича языка, позволяющая использованы функции как любые другие значения. Это включает в себя:
* Присваивание переменным ссылки на функцию;
* Передача функции как аргумента другой функции;
* Возвращение функции из другой функции;
* Хранение функций в структурах данных;

---

По сути первого класса и высшего порядка - разные вещи, но по отдельности смысла в них не много :)

Альтернатива - указатели на функций. C и C++ используют указатель функции для имитации поведения функции высшего порядка.

### Вытекающие правила для "чистых" функций в ФП   

* Функции должны быть объектами высшего порядка и первого класса;

* Функция не должна изменять внешнее состояние;

* Функция не должна изменять переданные ей аргументы;

* Результат функции зависит только от ее аргументов;  

* Можно откладывать, параллелить вычисления на разных потоках/ядрах, серверах и результат всегда будет один и тот же;

## Рекурсия

Рекурсия — это когда функция вызывает саму себя, и при этом ей нужно держать в памяти все предыдущие этапы.

## Паттерны для функций

### Лексическое замыкания / [Сlosure](/5%20Swift/5.3%20DataRepresentations/5.3.1%20DataTypes/5.3.1.3%20ReferenceTypes/Closure.md) в Swift

До сих пор мы обсуждали особенности ФП в контексте «чисто» [функциональных языков](../../2.2.1%20TypesOfLanguages.md) — языков, которые являются реализацией лямбда исчисления и не содержат особенностей, противоречащих формальной системе Чёрча.  Тем не менее, многие черты функциональных языков используются за пределами лямбда исчисления.

Хотя реализация аксиоматической системы интересна с точки зрения программирования в терминах математических выражений, это не всегда может быть применимо на практике. Многие языки предпочитают использовать элементы функциональных языков не придерживаясь строгой **функциональной доктрины**.

Они даже не требуют, чтобы функции зависели только от своих аргументов — функциям дозволенно обращаться к состоянию за пределом своей области видимости. Но при этом они включают в себя такие особенности, как __функции высшего порядка__. Передача функции в не-чистом языке немного отличается от аналогичной операции в пределах лямбда исчисления и требует наличия интересной особенности под названием: лексическое замыкание.

Замыкание, сделано как обычная функция, за исключением того, что в нём есть дополнительная ссылка на окружающие переменные извне.

Если замыкание обращается к переменной, которой нет в локальной области видимости, тогда оно принимает во внимание родительскую область. Вот и всё! Замыкание связывает функциональный мир с миром ООП. Каждый раз, когда вы создаёте класс, который хранит некоторое состояние, и передаёте его куда-то, вспомните про замыкания. Замыкание — это всего лишь объект, который создаёт «атрибуты» на лету, забирая их из области видимости, чтобы вам не пришлось делать это самим.

Общий синтаксис:

```python
{ (<#parameters#>) -> <#return type#> in
   <#statements#>
}
```

Пример использования:

```swift
func someFunctionThatTakesAClosure(closure: () -> Void) {
   // тело функции
}
 
// Вот как вы вызываете эту функцию без использования последующего замыкания:
 
someFunctionThatTakesAClosure(closure: {
   // тело замыкания
})
 
// Вот как вы вызываете эту функцию с использованием последующего замыкания:
 
someFunctionThatTakesAClosure() {
   // тело последующего замыкания
}
```

### Каррирование 

> В честь специалиста по логике Хаскелла Карри (Haskell Curry), который провёл ряд математических трюков, чтобы всё это формализовать.

В функциональном языке вам не понадобятся паттерны проектирования, потому что язык настолько [высокоуровневый](../../2.2.1%20TypesOfLanguages.md), что вы легко начнёте программировать в концепциях, которые исключают все известные паттерны программирования.

Одним из таких паттернов является [Адаптер](/2%20ComputerScience/2.4%20Architecture/2.4.1%20PatternsAndPrinciple/2.4.1.3%20DesignPattern/2.4.1.3.4%20Structural/Adapter.md) (чем он отличается от [Фасада](/2%20ComputerScience/2.4%20Architecture/2.4.1%20PatternsAndPrinciple/2.4.1.3%20DesignPattern/2.4.1.3.4%20Structural/Facade.md))? Похоже, что кому-то понадобилось наштамповать побольше страниц, чтобы выполнить условия контракта). Этот паттерн оказывается ненужным если в языке есть поддержка каррирования.

Паттерн Адаптер наиболее часто применяется к «стандартной» единице абстракции в Java — классу. В функциональных языках паттерн применяется к функциям. Паттерн берёт интерфейс и преобразует его в другой интерфейс, согласно определённым требованиям. Вот пример паттерна [Адаптер](/2%20ComputerScience/2.4%20Architecture/2.4.1%20PatternsAndPrinciple/2.4.1.3%20DesignPattern/2.4.1.3.4%20Structural/Adapter.md):

```java
int pow(int i, int j);
int square(int i)
{
    return pow(i, 2);
}
```

Этот код адаптирует интерфейс функции, возводящей число в произвольную степень, к интерфейсу функции, которая возводит число в квадрат. В аккадемических кругах этот простейший приём называется каррирование. Так как в ФП функции используются повсеместно в качестве аргументов, каррирование используется очень часто, чтобы привести функции к интерфейсу, необходимому в том или ином месте. Так как интерфейс функции — это её аргументы, то каррирование используется для уменьшения количества аргументов (как в примере выше).

Этот инструмент является встроенным в функциональные языки. Вам не нужно вручную создавать функцию, которая оборачивает оригинал. Функциональный язык сделает всё за вас. Как обычно давайте расширим наш язык, добавив в него каррирование.

```java
square = int pow(int i, 2);
```

Как видите, мы просто написали обёртку над оригинальной функцией. Вы сосредотачиваетесь на задаче, а компилятор пишет необходимый код за вас! Всё очень просто, и происходит каждый раз, когда вы хотите использовать паттерн Адаптер (обёртку).

>  В ФП каррирование как раз и представляет из себя простой и удобный способ создания **обёрток**

### [Композиция](/2%20ComputerScience/2.4%20Architecture/2.4.1%20PatternsAndPrinciple/2.4.1.3%20DesignPattern/2.4.1.3.4%20Structural/Composite.md)

Почитать дополнительно можно [здесь](/2%20ComputerScience/2.4%20Architecture/2.4.1%20PatternsAndPrinciple/2.4.1.3%20DesignPattern/2.4.1.3.4%20Structural/Composite.md)

Композиция - склеивание функций для получения более сложный функций, где результат предыдущей 

Более распространенный пример: 

```swift
Array.compactMap { $0 }.filter { $0.count > 0 }
```

## Ленивые вычисление

Ленивые (или отложенные) вычисления — это интересная техника, которая становится возможной как только вы усвоите функциональную философию.

В [императивных языках](../2.2.2.2%20Imperative/2.2.2.2.1%20AboutImperative.md) программирования очерёдность вычисления не вызывает никаких вопросов. Поскольку каждая функция может повлиять или зависеть от внешнего состояния, то необходимо соблюдать чёткую очерёдность вызовов (последовательную).

В ФП вычислениея !не зависят от внешного состояния, поэтому функции не обязательно выполняются последовательно (в том смысле, что они могут не вызваться и не хранить значение до момента его вызова).

Haskell — это пример языка с отложенными вычислениями. В Haskell отсутствует гарантия какой-либо очередности вызовов (вообще!), потому что Haskell выполняет код по мере необходимости.

```Haskell
System.out.println("Please enter your name: ");
System.in.readLine();
```

В ленивом языке никто не гарантирует, что первая строка выполнится раньше второй!

## Бесконечность

Ленивые языки позволяют создавать бесконечные структуры данных, создание которых в строгих языках гораздо сложнее. 

Например, представьте себе последовательность Фибоначи. Очевидно, что мы не можем вычислить бесконечный список за конечное время и при этом сохранить его в памяти. 
В строгих языках, таких как Java, мы просто написали бы функцию, которая возвращает произвольный член последовательности. 
В языках подобных Haskell мы можем абстрагироваться и просто объявить бесконечный список чисел Фибоначи. Так как язык ленивый, то будут вычислены лишь необходимые части списка, которые реально используются в программе. 

Это позволяет абстрагироваться от большого числа проблем и посмотреть на них с более высокого уровня (например можно использовать функции обработки списков на бесконечных последовательностях).

## Многопоточность

В функциональной программе всё состояние хранится в стеке в виде аргументов функций, поэтому функциональная программа сразу готова к распараллеливанию без каких-либо изменений. Вам не придётся задумываться о [deadlock-ах](/3%20Memory%20and%20Concurrency/3.2%20Multithreading/3.2.2%20ProblemsOfMultithreading.md) или состояниях гонки ([race conditions](/3%20Memory%20and%20Concurrency/3.2%20Multithreading/3.2.2%20ProblemsOfMultithreading.md)) потому что вам не нужны блокировки! Ни один кусочек данных в функциональной программе не меняется дважды одним и тем же потоком или разными. Это означает, что вы можете легко добавить потоков к вашей программе даже не задумываясь при этом о проблемах, присущих императивным языкам.

---

[2.2.1 Types Of Languages Theme](../../2.2.1%20TypesOfLanguages.md) | [Back To iTWiki Contents](https://github.com/eldaroid/iTWiki) | [2.2.2.1.2 Reactive Programming Theme](./2.2.2.1.2%20ReactiveProgramming.md)