Functional Programing

ФП появилось раньше ООП и структурного программирования LISP 1958 Закон Мура 1965 Simula 1967 Структурное программирование 1970 ML 1973 С++ 1983 Ocaml 1985 Erlang 1987 Haskell 1990 Scala 2003 F# 2005 Clojure 2007 Elm 2012 More than Moore 2014

Но не получило распространения в индустрии из-за дороговизны памяти на заре computer science, хотя и нашло свое место в научных кругах

Интерес вернулся в последние 5 лет • Закон Мура «выдыхается» • Популярность облачных решений растет • Big Data, машинное обучение, боты, когнитивные сервисы

LISP • Появился в 1958 году • Создатель Лиспа Джон Маккарти занимался исследованиями в области искусственного интеллекта (в дальнейшем ИИ) и созданный им язык по сию пору является одним из основных средств моделирования различных аспектов ИИ • Это один из старейших (наряду с Фортраном и Коболом) используемых по сей день высокоуровневых языков программирования • Основой архитектуры его является лямбда-исчисление • Интерпретатор Лиспа, написанный на Лиспе, занимает 15 строк

Что не так с состоянием? • Locking, Memory Bandwidth • How To Reproduce / Debug • Race Conditions • Side Effects • Не возможно доказать корректность программы

Чему равен y? var x = 2; DoSomething(x); // чему равен y? var y = x - 1;

Это JavaScript  function DoSomething (foo) { x = false } var x = 2; DoSomething(x); var y = x - 1;

Функциональное программиирование • Раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних • Понимание функции отличается от функции как подпрограммы в процедурном программировании

Функция – Соответствие между элементами двух множеств, установленное по такому правилу, что каждому элементу одного множества ставится в соответствие некоторый элемент из другого множества.

Принцип разделения интерфейса Принцип разделения интерфейсов говорит о том, что слишком «толстые» интерфейсы необходимо разделять на более маленькие и специфические, чтобы клиенты маленьких public interface IMessyCalc { float Add(float a, float b); Rocket LaunchRocket(); // WAT? }

Принцип разделения интерфейса public interface ICalc { float Add(float a, float b); } public interface IRocketLauncher { Rocket LaunchRocket(); // ok }

ICalc проще let add x y = x + y; // float -> float -> float

Функции и вывод типов let add1 x = x + 1 // int -> int let add2 x = x + 2 // int -> int let add3C = add1 >> add2 //композиция let add3P x = x |> add1 |> add2 // pipe-оператор let toString x = x.ToString() // 'a -> string

Аналогия с конвеерной лентой

Каррирование и частичное применение let printTwoParameters x y = printfn "x=%i y=%i" x y //explicitly curried version let printTwoParametersC x = // only one parameter! let subFunction y = printfn "x=%i y=%i" x y // new function with one param subFunction let add x y = x + y let add1P = add 1 let v = add1P 2 let result = [1..10] |> List.map (fun i -> i+1) |> List.filter (fun i -> i>5)

Изменяемые данные (не тру) let mutable mut = 5 mut <- 6

λ-исчисление • Формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости • Строится на простых двух операциях: аппликации и абстракции • Определены фундаментальные понятия α-эквивалентностью и β- редукции • Многие функциональные языки можно рассматривать как "надстройку" над ними

λ-исчисление • Нет циклов • Нет переменных • Нет операции присвоения • Нет изменяемого состояния • Нет условных переходов и циклов • Нет «обычной» рекурсии • Обладает свойством полноты по Тьюрингу и, следовательно, представляет собой простейший язык программирования

Теорема о неподвижной точке • И в λ-исчислении, и в комбинаторной логике для каждого терма X существует по крайней мере один терм P такой, что XP = P. И более того, существует комбинатор Y такой, что YX = X(YX) • Комбинатор неподвижной точки преобразует нерекурсивную функцию, вычисляющую один шаг рекурсии, в рекурсивную • Y = λf.(λx.f(xx))(λx.f(xx)) • Z = λf.(λx.f(λy.xxy))(λx.f(λy.xxy)) • https://habrahabr.ru/post/79713/

α-эквивалентность • λx.x и λy.y альфа-эквивалентные лямбда-термы и оба представляют одну и ту же функцию (функцию тождества). • Термы x и y не альфа-эквивалентны, так как они не находятся в лямбда абстракции

β-редукция •(λx.2 * x + 1)3 -> 7

Структурирование программ Expressions VS Statements Expression<Func<int, string>> expr = x => { return x.ToString(); }; CS0834 A lambda expression with a statement body cannot be converted to an expression tree

Statement var str = "test"; var i = 1; if (flag) { str += i; } else { i++; }

Expression var fiveOrSix = Math.Cos(1) > 0 ? 5 : 6;

Fixed Expression<Func<int, string>> expr = x => x.ToString(); // ok

Что возвращает функция? function DoSomething (foo) { if (foo > 5) return 2; throw "Error"; } var x = 2; DoSomething(x); var y = x - 1;

Exception Handling Considered Harmful • Hidden Control Flow & Corrupt State • Mismatch With Parallel Programming • Exceptional Exceptions • Exceptions only really work reliably when nobody catches them

do { using (var lifetimeScope = _container.BeginLifetimeScope()) { var billingService = lifetimeScope.Resolve<BillingService>(); try { int activityCount = billingService.ProcessNotRatedActivities(); if (activityCount > 0) { Logger.Instance.Info($"Handled {activityCount} pending rated activities"); } } catch (Exception exception) { Logger.Instance.Error(exception, CultureInfo.CurrentCulture, "An error occured while handling pending rated activities"); } } } while (!cancellationToken.WaitHandle.WaitOne(_pollingInterval));

Ограничения императивного стиля

Convert exceptions into Failures

Алгебраические типы данных type Option<'T> = | Some of 'T | None type Season = Autumn | Winter | Spring | Summer type Profile = { FirstName: string LastName: string }

Pattern Matching let printSomeOrNone x = match x with | Some(y) -> printfn "some: %A" y | None -> printfn "none" | _ -> printfn "Never hit" // only use if you have to

Организация приложения в функциональном стиле

Монада – это просто моноид в категории эндофункторов • Если не затрагивать тему гомоморфизмов • В чем проблема?

Какие милые котята

Ой, какие щеночки

Определение порядковых чисел по фон Нейману • Множество S является ординалом тогда и только тогда, когда оно строго вполне упорядочено отношением «принадлежать» и каждый элемент S одновременно является его подмножеством • Любой ординал есть вполне упорядоченное множество, состоящее из всех ординалов, меньших его

Основы теории категорий • В программах, использующих операционную семантику, очень трудно что-то доказать. Чтобы показать некое свойство программы вы, по сути, должны «запустить ее» через идеализированный интерпретатор • Но есть и альтернатива. Она называется денотационной семантикой и основана на математике. В денотационной семантике для каждой языковой конструкции описана математичесая интерпретация • По сравнению с теоремами, которые доказывают профессиональные математики, задачи, с которыми мы сталкиваемся в программировании, как правило, довольно просты, если не тривиальны

Какова математическая модель для чтения символа с клавиатуры, или отправки пакета по сети? • Долгое время это был бы неловкий вопрос, ведущий к довольно запутанным объяснениям. Казалось, денотационная семантика не подходит для значительного числа важных задач, которые необходимы для написания полезных программ, и которые могут быть легко решаемы операционной семантикой • Прорыв произошел из теории категорий. Евгенио Моджи обнаружил, что вычислительные эффекты могут быть преобразованы в монады

Чистая функция • Является детерминированной • Не обладает побочными эффектами • В Haskell все функции чистые, поэтому без монады IO нельзя написать hello world

Моноид – это категория • 1 + 2 = 3 • 1 + (2 + 3) = (1 + 2) + 3 • 1 + 0 = 1 • 0 + 1 = 1

Строки – тоже моноид • "Foo" + "Bar" = "FooBar" • "Foo" + ("Bar" + "Baz") = ("Foo" + "Bar") + "Baz" • "Foo" + "" = "Foo« • "" + "Foo" = "Foo"

Монада как значение в контексте

Map (fmap, lift, Select, <$>, <!>) 1. (a->b) -> M<a> -> M<b> 2. fmap id = id 3. fmap (g >> f) = (fmap g) >> (fmap f)

Return ( pure, unit, yield, point) • A -> M<A>

Apply <*> • M<(a->b)> -> M<a> -> M<b> • Аппликативные функторы применяют упакованную функцию к упакованному же значению: • Используя apply и return можно сконструировать map

Bind (flatMap, andThen, SelectMany >>=) • (a -> M<b>) -> M<a> -> M<b>

Maybe • Является функтором, аппликативным функтором и монадой одновременно

Все вместе • функтор: вы применяете функцию к упакованному значению, используя fmap или <$> • аппликативный функтор: вы применяете упакованную функцию к упакованному значению, используя <*> или liftA • монада: вы применяете функцию, возвращающую упакованное значение, к упакованному значению, используя >>= или liftM

Either Control Flow public static ActionResult ViewOrError<TIn, TOut>( this IQueryController<TIn,TOut> controller, TIn spec) where TIn : class, new() where TOut : class => spec.ThisOrDefault() .ToWorkflow( x => controller.ModelState.IsValid, x => (OrderFailure?)OrderFailure.ArgumentInvalidState) .Then(x => controller.Query.Ask(x)) .Then(x => x != null, controller.View, x => OrderFailure.ObjectNotFound) .Finish(x => x, x => x.ToActionResult());

Императивный аналог protected ActionResult ViewOrErrorImperative<TIn, TOut>(IQuery<TIn, TOut> query, TIn spec) where TIn : class, new() where TOut : class { if (spec == null) { spec = new TIn(); } if (ModelState.IsValid) { var data = query.Ask(spec); if (data != null) { return View(data); } return new HttpNotFoundResult(); } return new HttpStatusCodeResult(HttpStatusCode.BadRequest); }

Монады • LINQ • Async/Await • Map/Reduce • Lazy<T> • Nullable<T> • IEnumerable<T> • Task<T>

SelectMany public static Maybe<int> Add(this Maybe<int> m, Maybe<int> add) => from v1 in m from v2 in add select v1 + v2;

Бастион ООП содержит монады (на странице 243)

Interpreter • Expression Tree • RegEx

Другие элементы ФП, которые мы используем каждый день • Делегаты • Ad-Hoc полиморфизм • String • Замыкания • Bind • Promise

ООП VS ФП • Инкапсуляция -> Immutability • Наследование -> Композиция, Каррирование, Частичное применение, Continuation Style • Полиморфизм -> Вывод типов, Монады

Сильные стороны • Повышение надёжности кода • Возможность формального доказательства корректности программы • Удобство организации модульного тестирования • Возможности оптимизации при компиляции • Возможности параллелизма • Лучшие возможности композиции и повторного использования кода • Значительное уменьшение количества строк кода и cyclomatic complexity • Лучшая читабельность

Недостатки • Необходимости постоянного выделения и автоматического освобождения памяти • Нестрогая модель вычислений приводит к непредсказуемому порядку вызова функций, что создает проблемы с побочными эффектами • Отсутствие алгоритмической базы для функциональных структур данных • Принципиальная невозможность эффективной реализации некоторых важных эмпиративных алгоритмов (например, quicksort) • Нехватка специалистов на рынке труда • В Haskell ввод/вывод реализован с помощью не тривиальных абстракций – монад

Сколько раз в день ваша бабушка пользуется ПО? • Ни одного • Один раз • От двух до пяти • Да постоянно!

Сколько раз в день ваша бабушка пользуется ПО? • Начисление пенсии • Оплата товаров в магазине • Социальные льготы • Медицинское страхование • ...

Список использованных материалов • http://fsharpforfunandprofit.com/ • https://habrahabr.ru/post/79713/ • https://habrahabr.ru/post/183150/ • https://habrahabr.ru/post/245797/ • https://ru.wikipedia.org/ • https://ericlippert.com/2013/02/21/monads-part-one/ • http://blog.ploeh.dk/2016/04/11/async-as-surrogate-io/ • https://www.youtube.com/watch?v=ecIWPzGEbFc

Functional Programing

More Related Content

What's hot

Viewers also liked

Similar to Functional Programing

Functional Programing