— ООП не сможет больше спасать нас от «Облачных монстров».
Примечание переводчика: Есть два понятия — параллельность (выполнение одновременно, независимо) и конкурентность (выполнение по шагам, поочерёдно, но одновременно несколько задач) и как всегда, мне пришлось поломать голову подобрая правильные термины.
Некоторые слова или термины я буду дублировать в скобках в оригинале, для того, чтобы искать по англоязычным терминам дополнительную информацию, которой будет в разы больше.
Возможно вы уже слышали такое выражение, вроде: “Clojure”, “Scala”, “Erlang” или даже “Java теперь имеет лямбды”. И вы имеете хоть и отдалённое представление о «Функциональном программировании». Если вы участник какого-либа программисткого сообщества, тогда эта тема могла уже вами обсуждаться.
Если вы поищите в Google по словосочетанию «Функциональное программирование», вы не увидите что-то нового. Второй язык из созданных ранее уже охватывает эту тему, он был создан в 50-ых и называется Lisp. Тогда, какого чёрта, эта тема стала популярна только сейчас? Всего то 60 лет спустя?
В начале, компьютеры были очень медленными
Верите вы этому или нет, но компьютеры были нааамного медленнее чем DOM. Нет, действительно. И в то-же время были 2 основные идеи в соглашении по дизайну и реализации языков программирования:
- Начинайте исходя из архитектуры фон Неймана и добавьте абстракцию.
- Начните с математики и удалите абстракцию.
Компьютеры не имели достаточно вычислительных мощностей, чтоб иметь дело со всеми абстракциями и справляться с программами, написанными в функциональном стиле. Так Lisp выдыхался раньше, будучи чрезвычайно медленным и следовательно, не пригодным для работы. Тогда-то и началось господство императивного стиля программирования, особенно с расцветом C.
Но компьютеры сильно улучшились
Сейчас стало практически нормальным использовать большинство приложений, совершенно не заботясь на каком языке они были написаны. Наконец-то функциональные языки получили второй шанс.
Функциональное программирование 50.5
Эта статья, ни в коем случае, не введение в ФП. В конце этого раздела вы должны будете знать, что из себя представляет ФП и с чего начать своё путешествие по изучению.
Вы можете понимать термин «Функциональное программирование» слишком буквально, как программирование с использованием функций и это недалеко от истины. Вы будете создавать функции в терминах других функций и писать функции (Вы помните f ? g из школьной программы? Сейчас вам это пригодится). Это всё.
Список (не полный) особенностей ФП:
- Функции первого класса (First-Class Functions)
- Функции высшего порядка (High-Order Functions)
- Чистые функции (Pure Functions)
- Замыкания (Closures)
- Неизменяемое состояние (Immutable State)
Сейчас вы не должны переживать об этих странных терминах, просто поймите что они означают.
Функции первого класса значит, что вы сможете сохранять функции в переменные. Я уверен вы делали что-то похожее, как в примере на JavaScript:
var add = function(a, b){
return a + b
}
Вы только что создали анонимную функцию, которая получает a и b и возвращает a + b, и присвоили эту функцию переменной add.
Функции высшего порядка значит, что функции могут возвращать функции или принимать функции как параметры.
И снова на JavaScript:
document.querySelector('#button')
.addEventListener('click', function(){
alert('yay, i got clicked')
})
или
var add = function(a){
return function(b){
return a + b
}
}
var add2 = add(2)
add2(3) // => 5
Оба варианта пример функций высшего порядка, даже если вы не писали что-то подобное, вы возможно видели похожее ещё где-то.
Чистые функции значит, что функция не меняет переменные, она просто принимает данные и возвращает данные, как наши любимые функции из математики. Так-же это значит, что если вы вызовите функцию f с аргументом 2 и она возвращает 10, то она всегда будет возвращать 10. Не имеет значение какое окружение, количество нитей или порядок выполнения. Они не вызывают никаких побочных эффектов в других частях программы и это действительно мощная концепция.
Замыкания значит, что вы можете сохранять некоторые данные внутри функции, которые будут доступны в специфичной возвращаемой функции, другими словами возвращаемая функция хранит свою среду выполнения.
var add = function(a){
return function(b){
return a + b
}
}
var add2 = add(2)
add2(3) // => 5
Снова взгляните на второй пример из параграфа Функции высшего порядка, переменная a была замкнута и доступна только в возвращаемой функции. На самом деле, замыкания не особенность ФП парадигмы, скорее оптимизация.
Неизменяемое состояние значит, что вы вообще не можете менять любые состояния (хотя можете создать новые). В следующем коде (на OCaml), вы присвоили переменной x значение 5 и x всегда будет 5.
let x = 5;;
x = 6;;
print_int x;; (* prints 5 *)
Эти особенности выглядят достаточно странно, но вы скоро поймёте как они облегчат вашу жизнь.
Объектно-ориентированное программирование не может больше вас защищать
Это многообещающее время, когда мы сможем иметь распределённые и многопоточные приложения, наконец-то наступило. К сожалению, наша существующая (или наиболее используемая) модель не готова к многопоточности (concurrency) и параллельности (parallelism), хотя она и решает текущие задачи, но и добавляет большие проблемы.
Чтобы улучшить приложения, мы нуждаемся в простом и надёжном способе добиться желаемого. Вы помните выше упомянутые особенности ФП? Чистые функции и неизменяемое состояние? Правильно, вы можете выполнять функции тысячи раз, на разных ядрах или машинах и результат будет всегда одинаковым. И так, мы можем один и тот-же код запускать и на одном ядре и на тысячах. Жизнь опять становится безоблачной.
«Но почему я не могу продолжать использовать ООП?»
По крайней мере, для многопоточности и параллельности ООП не может вас больше выручить. Потому, что ООП относится к стилю с изменяемым состоянием (в императивных языках, которые написаны в ООП стиле, в большинстве случаях). Вызываемые методы объекта предполагают изменять текущие self или this. Придётся приложить достаточно усилий, чтобы корректно обновлять и синхронизировать все потоки.
Пишу это не для того, чтобы агитировать вас переходить на ФП с тех парадигм, которые вы сейчас используете (хотя некоторые люди скажут я должен), но вы однозначно должны усвоить: Java и C++11 уже имеют лямбда исчисления. Могу сказать, что почти все современные и поддерживаемые языки собираются реализовать ФП особенности или уже сделали это.
Стоить отметить, что мы не должны прекращать использовать изменяемое состояние. Мы должны использовать ввод/вывод (IO) и т.д., чтобы наши программы были полезны. Основная идея ФП является: используй изменяемое состояние, только тогда, когда это действительно необходимо.
«Я не работаю с облаками, мне действительно нужно изучать ФП?»
Да.
Функциональное Программирование поможет вам писать программы лучше и рассуждать о проблемах, которые вам придётся решать.
«Я пытался. Это слишком сложно и код трудночитаемый»
Начинать всегда трудно в любой области. Уверен, вы начали изучать программирование тоже имея кучу проблем, даже в ООП языках. Возможно начинать писать в ООП стиле было проще, чем писать свою первую программу потому, что вы уже были знакомы с некоторыми общими идиомами, вроде объявление переменных и for/while циклами.
Начинать изучать ФП — это почти тоже самое, как снова начать писать программы с нуля (вне зависимости какой язык вы начали изучать, это будет однозначно как начать с самого начала).
Многие могут отметить, что ФП трудночитаемый. Если у вас опыт в императивных языках, функциональные программы будут выглядеть как тайнопись. И не потому, что это действительно так, а потому, что вы не знаете его основные идиомы. Однажды, поняв фундаментальные принципы, программы станут на много более читаемыми.
Просмотрите программу написанную на Haskell и JavaScript (в императивном стиле):
guess :: Int -> [Char]
guess 7 = "Much 7 very wow."
guess x = "Ooops, try again."
-- strongly inspired by http://learnyouahaskell.com
function guess(x){
if(x == 7){
return "Much 7 very wow."
}
else {
return "Oops, try again."
}
}
Это очень простая программа. Она выводит поздравительное сообщение, когда пользователь угадал и ввёл цифру 7 или выведет сообщение об ошибке во всех других случаях. Возможно это выглядит шифровкой, как Haskell может делать всю работу всего в две строки кода (первую строку вы можете игнорировать, это просто «объявление типа»). Но это станет достаточно простым, однажды, поняв возможности сопоставления с образцом (Pattern Matching) (которые реализованы не только в ФП языках, но были их особенностью).
Что делает Haskell:
Если принимаемый аргумент у функции guess равен цифре 7, то она вернёт «Much 7 very wow.» или вернёт «Oooops, try again.» в других случаях.
И это тоже самое, что делает код на JavaScript, но Haskell сопоставляет с «образцом», объявленным программистом в коде.
Данный подход может показаться не очень полезным в данном случае, если вы можете использовать if/else. Но это станет действительно полезным, когда вы сами начнёте писать более сложные структуры данных.
plus1 :: [Int] -> [Int]
plus1 [] = []
plus1 (x:xs) = x + 1 : plus1 xs
-- plus1 [0,1,2,3]
-- > [1,2,3,4]
В программе выше, *plus1* функция, которая принимает список целых чисел и прибавляет по 1 к каждому элементу списка. Функция сопоставляет, когда список пустой [] (возвращает другой пустой список, раз в нём нет элементов) обходит не пустой список и определяет образец сопоставления: x как первый элемент списка, xs как оставшийся список. Потом просто считает сумму и объединяет через рекурсивный вызов.
Я уверен, вы потратите много минут (не самых приятных), переписывая данный пример в императивном стиле, уместив код в две строки, и при этом, сохранив читаемость.
Итак, давайте начнём
Вышло много материалов по Функциональному программированию, но эти ссылки вы не должны пропустить однозначно:
- Principles of Functional Programming in Scala: курс будет полезен для тех, кто знает Java и хочет попробовать Функциональное программирование не спрыгивая с JVM. Курс охватывает базовые концепции.
- Paradigms of Computer Programming?—?Fundamentals: курс будет полезен для тех, кто хочет узнать как писать программы на функциональном языке. На курсе используется обучающий язык Qz. В курсе много упражнений, вы сможете использовать функциональный язык и попробовать создать свою структуру данных. Полагаю, курс предоставляет строительные блоки для «здания» с названием «Функциональное программирование», он поможет вам с другими языками в будущем.
К сожалению, курсы будут доступны только в конце года. Но вы можете следить за контентом и видео, они доступны на Youtube.
С другой стороны, если вы предпочитаете текстовые материалы, я непременно рекомендую некоторые из них:
- Structure and Interpretation of Computer Programs
- How to Design Programs
- Concepts, Techniques, and Models of Computer Programming
Первые две имеют похожие учебные планы, познакомят вас с базисом Функционального программирования и очень подходят для начинающих. Третья из ссылок, это курс Парадигм компьютерного программирования, охватывает больше, чем Функциональное программирование. Важно отметить, что эти материалы для начального уровня.
Кроме того, Крис Аллен (Chris Allen) написал отличную статью по изучению Функционального программирования. Она называется Functional Education и имеет исчерпывающий список материалов для изучения Функционального программирования используя Haskell, а так же расскажет о сильных и слабых сторонах этого подхода. Следуя рекомендованным Крисом ссылкам, вы сможете изучить начальные принципы и более сложные темы (я уверен вы слышали о монадах) Функционального программирования и возможно поймёте как писать приложения используя их. (Спасибо тебе Крис, за ссылки на материалы.)
Удачи в вашем Функциональном Новом Году! O
Комментарии (93)
eandr_67
31.08.2015 16:37+5Автор делает вид, что параллельное программирование появилось только сейчас. И упорно не замечает, что всё, что он пытается приписать исключительно функциональным языкам, имеет давно отработанные механизмы в императивных языках.
Да, некоторые вещи в функциональных языках можно записать короче. Ну и что? На языке APL сложнейшие вычисления можно записать одной строкой — стало-ли от этого кому-то легче?
eaa
31.08.2015 16:44-13Всегда удивляли авторы статей, у которых ошибки в пунктуации чуть ли не в каждом предложении.
Вы пишете так, чтобы побесить читателей? Я понимаю, что бывают опечатки, но просто безграмотно написанная и абсолютно не проверенная статья — это уже перебор. Обычно я игнорирую такие вещи, но сейчас уже просто переполнилась чаша моего терпения… нельзя же так. Если Вы пишете для себя — пишите в уголке и не выставляйте на всеобщее обозрение. Если для людей — будьте добры, выпускайте качественный продукт.
greg_fat
31.08.2015 16:47+15Уговорили, переводить и писать больше не буду.
vdasus
31.08.2015 21:09+9Не обращайте внимания. Есть масса людей, для которых форма гораздо важнее содержания. Вот как поступил бы здравый человек? Написал в личку где именно много ошибок. Помог исправить. Как поступают эээ… неразумные? Заявляют всему миру, что вот как раз они-то — самые умные и грамотные. И смысл без запятой уловить не в состоянии. Простите, ощущаютъ некое амбрэ. _вытер носик платочком_
Хотите чему-то научиться, да ещё бесплатно? Учитесь, говорите спасибо. Хотите все запятые — покупайте книги профессионально проверенные редакторами. И идите в суды если что не так.
К сожалению мы не все обладаем 100% грамотностью. Мало того, не для всех русский язык родной. Мало того, даже для русскоязычных, не для всех русский язык основной. Но люди прикладывают массу усилий (как вы, например), чтобы поделиться с другими опытом. СПАСИБО.
Понятно, что статью а-ля «накапал, прикались братва, типерь можна на сиплюплюхсас ссылко овсвабаждадь нифсигда» читать сложно. Но если статья *несёт в себе пользу* — мне лично глубоко наплевать все там зяпятые или нет.
Я давно смотрю в сторону функционального программирования и мне интересны любые статьи, которые обращают моё внимание на какие-то тонкости, особенности, ссылки и проч. Спасибо за ваше время. На критиков граммар-наци я лично плюю с высокой колокольни.
Статьи бывают полезные и бесполезные. Полезным прощается всё. Бесполезные (как статьи так и комментарии) и с запятыми никому не нужны.
malan
31.08.2015 18:14+9Будьте добры, не решайте за всех людей. Мне вот статья понравилась и недостаток запятых я переживу. У нас не так много авторов занимаются переводом интересных статей, больше новости постят и рекламу.
aronsky
31.08.2015 22:59Вы, вероятно, не в курсе, что обычно люди, которым ошибки режут глаза не стесняются писать в PM с указанием списка оных? А ежели лень — то и глаза, выходит, не режет.
eaa
31.08.2015 23:21-10Я очень надеюсь, что автор, кроме изучения функционального программирования, немного обратит еще внимания и на русский язык. А расписывать ошибки, коих более чем достаточно — это уже немного другая тема и обсуждается на других сайтах. Да, я в курсе, что отдельные ошибки пишут личкой, но не в таком количестве. И спасибо за слив кармы и кучи минусов, но надеюсь это поможет стать гигтаймсу хоть немножеско грамотнее, кто-то же должен об этом говорить.
freeAKK
31.08.2015 17:27+4Поинт статьи в том, что в функциональных языках мы пытаемся разделить программу на много простых частей, например, на набор параллельных функций (процессы в том же ерланге). После этого общаемся сообщениями, не нуждаемся в блокировках. Такое проще отлаживать, мониторить, потому что каждый процесс отделён, ведёт себя предсказуемо, имеет свой кусок памяти.
Тоже можно сделать на любом языке, просто _сложнее_. Даже тот же эрланг VM написан на с. Правда, чтобы отдебажить эту VM, понадобилось каких-то лет двадцать.
И другой поинт. Есть процессоры (или будут?) с 64-ядрами на которых _любая_ синхронизация бьёт по производительности ой-ой-ой. Тут даже э-г загибается, и, например, приходится изменять привычные функции по работе с временем, т.к. на некоторых есть глобальный лок.
Gorthauer87
01.09.2015 14:04Обмен сообщениями тоже вещь не бесплатная, в идеале было бы круто, чтобы для работы их как можно меньше требовалось.
freeAKK
01.09.2015 15:37+1Это зависит от программы. Но мы не часто шлём сообщения. Обычно это таймеры (когда нужно подождать и сделать что-то), перессылка сообщений в ejabberd между пользователями, логгинг, общение с базой, кешем, очередями (RabbitMQ). И в принципе, всё. Но тут уже надо вдаватся в подробности как мы делим всю систему на процессы.
Сообщения — это _достаточно_ дешёво. Не забывайте, что копируя данные, мы избавляемся от небесплатной синхронизации. Обычно сообщения в эрланге короткие (сто байт?). Но для больших кусков памяти можно передавать reference-counted binary, то есть указатель на кусок памяти, защищённый локом. В принципе, трогать мы этот лок будем в двух случаях: когда шлём сообщение, и когда процесс сделал gc и больше не использует эту память.
А если нужно хранить большой кусок данных и многие процессы будут хотеть сделать вычисления, используя эти данные, то мы можем хранить адрес этого процесса в других процессах и когда нужно что-то сделать, просто пересылать запрос этому процессу с данными.
А ещё мы копируем данные между разными по сети между виртуальными машинами. А это может быть 80% трафика в том же ejabberd.
Если подробнее копать по этой теме, то ещё можно посмотреть эрланг VM на jvm (Java Virtual Machine), который не копирует данные. И оба подхода работают хорошо.
solver
01.09.2015 15:46А это походу бесполезно объяснять адептам ООП.
У них есть железобетонный аргумент «я то же самое могу написать на ООП».
Им нет дела, до более корректных инженерных решений.
Они не понимают, что такое надежность, предсказуемость и т.д.
Лучше всего про это сказал кто-то из докладчиков, вроде на джипоинте.
Правда он говорил это про тесты, но суть можно применить ко многим вещам.
«Чак Норрис не ходит на охоту, потому что охота подразумевает неудачу. Чак Норрис ходит убивать.»
Так и инженер, может писать программу без тестов и тогда он «ходит на охоту».
Или писать программы сложным подходом с кучей потенциальных проблем, но который он уже применял.
И делать это просто потому, что он не знает/не понимает как можно делать лучше, проще и с большей гарантией.
babayota_kun
31.08.2015 20:58+5Я с функциональным программированием сталкивался лишь в подобных вводных статьях, но мне, как человеку со стороны, такое программирование кажется лишь шагом назад в череде абстракций, наложенных друг на друга с развитием языков программирования. Ведь люди (и программисты, я уверен, тоже) не мыслят рекурсиями и подобными функциональными выкрутасами. Всякие if..else, while и for схожи с людским типом мышления. Ещё больше с ним схожи выражения в духе
for (нога : сороконожка) { нога.поднять(); }
Такие конструкции ведь писать и понимать совсем не сложно и думать нужно над тем «что именно нужно сделать?», а не «как вообще это делается?».A1ien
31.08.2015 21:40+2А как по мне такой код еще более читаемый — сороконожка.форич(нога=>нога.поднять());
babayota_kun
31.08.2015 22:03Наверное, такими вопросами должна заниматься какая-нибудь профильная лингвистика. Мне вот совсем не кажется логичным то, что «форич» вызывается у объекта-сороконожки. Но это частности :)
Я к тому, что «многопоточность» и прочие клёвые слова — это здорово, но код-таки должно становиться писать легче, а не тяжелее. И нельзя сказать, что «вы просто не привыкли к такому типу программирования, потому тяжело» — такие функциональные выкрутасы тяжелы из-за несоответствия им нашего мышления. Неспроста ведь выделяют глаголы (функции) и существительные (объекты).Правда инфинитивы — это скорее существительные, а не глаголы, что скажет вам филолог, проходивший историю языка, а в английском там вообще всё ещё страннее и чудоковатее
vintage
01.09.2015 08:25+5Ваш код не имеет никакого отношения к ФП. Вы передали грязную функцию первого порядка в грязную функцию высшего порядка.
В ФП этот код выглядел бы так:
сороконожка_с_поднятыми_ногами = сороконожка.мап( нога => нога.поднять() )dmiceman
03.09.2015 07:54Ну я же правильно понимаю, на выходе будет две сороканожки? Когда сороканожка — это реальный робот с сорока ногами, получится немного не то.
vintage
03.09.2015 11:31В этом вся суть функционального программирования — вы создаёте новый объект с новыми свойствами, а старый просто выбрасываете. :-)
FoxCanFly
31.08.2015 22:51поднимание_ног [] = [] поднимание_ног(нога:ноги) = поднять(нога) : поднимание_ног[ноги] поднимание_ног(сороконожка)
Как то…
niamster
31.08.2015 22:54+1Я уверен, вы потратите много минут (не самых приятных), переписывая данный пример в императивном стиле, уместив код в две строки, и при этом, сохранив читаемость.
Потратил 10 секунд на python, столько же на ruby. На C/C++/Java/etc. это получится чуть больше.
>>> def plus1(lst): ... return [x+1 for x in lst] ... >>> plus1([1,2,3]) [2, 3, 4] >>>
irb> def plus1(lst) irb> lst.map {|x, obj| x+1} irb> end => :plus1 irb> plus1([1,2,3]) => [2, 3, 4]
svfat
31.08.2015 23:11+2А разве генераторы списков и map это не функциональщина?
niamster
31.08.2015 23:34+1Если я понял правильно автора статьи и вообще концепцию ФП, то надо сказать «нет» императивному подходу.
Я просто показал, что в языках с императивным стилем можно создавать вполне лаконичные конструкции-аналоги.
Согласен, мои примеры не совсем императивные, но это то, что используют «императивщики» каждый день.
Я предпочитаю балансировать и не вдаваться в крайности. Я не вижу смысла переходить на Erlang только потому, что это, возможно, круто.
Я вот к стати попробовал на С++14(уже 300 лет не прикасался к С++ выше С++98):
template<typename T> auto plus1(const vector<T> &lst) { auto mod = lst; transform(mod.begin(), mod.end(), mod.begin(), [](auto &x) { return x+1; }); return mod; }
Не самый красивый вариант, да и для rvalue прийдется перегружать, если захочется оптимизировать. Но можно, товарищи =)vintage
01.09.2015 08:33+2Многие думают, что ФП — это про первоклассные функции. Но нет, ФП, на самом деле, про чистые функции. Так что ваш код вполне себе императивен в том плане, что вы можете изменять стороннее состояние внутри замыкания.
ncix
01.09.2015 09:46А не проще так?:
templateT plus1(const vector &lst)
{
T result;
for(T::const_iterator it = lst.begin(); it != lst.end(); ++it)
result.push_back(it.value() + 1);
return result;
}niamster
01.09.2015 18:50Вообще я так посмотрел и можно сделать так(раз уж идет копирование):
template<typename T> auto plus1(const vector<T> lst) { transform(lst.begin(), lst.end(), lst.begin(), [](auto &x) { return x+1; }); return lst; }
Конечно, если T не PDO, то будет неэффективно.
NonGrate
01.09.2015 16:13public static int[] incrementArray(int... array) { for(int i = 0; i < array.length; array[i] += 1, i++) {} return array; }
Думаю, можно не считать закрывающую скобку как строку?vintage
01.09.2015 19:29Коль пошла такая пьянка…
T[] increment( T )( T[] list ) { foreach( &item : list ) ++item; }
bubuq
01.09.2015 01:45+3Тако ж
plus1 [] = [] plus1 (x:xs) = x + 1 : plus1 xs
суть лишь
plus1 = map (+1)
vintage
01.09.2015 08:07+10Я просто оставлю вам одну главу из книги «Язык программирования D» от Андрея Александреску:
5.11.1.1. «Чист тот, кто чисто поступает»
По традиции функциональные языки запрещают абсолютно любые изменения, чтобы программа могла называться чистой. D ослабляет это ограничение, разрешая функциям изменять собственное локальное
и временное состояние. Таким образом, даже если внутри функции есть изменения, для окружающего кода она все еще непогрешима.
Посмотрим, как работает это допущение. В качестве примера возьмем наивную реализацию функции Фибоначчи в функциональном стиле:
ulong fib(uint n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
Ни один преподаватель программирования никогда не должен учить реализовывать расчет чисел Фибоначчи таким способом. Чтобы вычислить результат, функции fib требуется экспоненциальное время, поэтому все, чему она может научить, – это пренебрежение сложностью и ценой вычислений, лозунг «небрежно, зато находчиво» и спортивный стиль вождения. Хотите знать, чем плох экспоненциальный порядок? Вызовы fib(10) и fib(20) на современной машине не займут много времени, но вызов fib(50) обрабатывается уже 19 минут. Вполне вероятно, что вычисление fib(1000) переживет человечество.
Хорошо, но как выглядит «правильная» функциональная реализация Фибоначчи?
ulong fib(uint n) { ulong iter(uint i, ulong fib_1, ulong fib_2) { return i == n ? fib_2 : iter(i + 1, fib_1 + fib_2, fib_1); } return iter(0, 1, 0); }
Переработанная версия вычисляет fib(50) практически мгновенно. Эта реализация требует для выполнения O(n) времени, поскольку оптимизация хвостовой рекурсии (см. раздел 1.4.2) позволяет уменьшить сложность вычислений. (Стоит отметить, что для расчета чисел Фибоначчи существуют и алгоритмы с временем выполнения O(log n)).
Проблема в том, что новая функция fib как бы утратила былое великолепие. Особенность переработанной реализации – две переменные состояния, маскирующиеся под параметры функции, и вполне можно было с чистой совестью написать явный цикл, который зачем-то был закамуфлирован функцией iter:
ulong fib(uint n) { ulong fib_1 = 1, fib_2 = 0; foreach (i; 0 .. n) { auto t = fib_1; fib_1 += fib_2; fib_2 = t; } return fib_2; }
К сожалению, это уже не функциональный стиль. Только посмотрите на все эти изменения, происходящие в цикле. Один неверный шаг – и с вершин математической чистоты мы скатились к неискушенности чумазых низов.
Но подумав немного, мы увидим, что итеративная функция fib не такая уж чумазая. Если принять ее за черный ящик, то можно заметить, что при одних и тех же аргументах функция fib всегда возвращает один
и тот же результат, а ведь «красив тот, кто красиво поступает». Тот факт, что она использует локальное изменение состояния, делает ее менее функциональной по букве, но не по духу. Продолжая эту мысль, приходим к очень интересному выводу: пока изменяемое состояние внутри функции остается полностью временным (то есть хранит данные в стеке) и локальным (то есть не передается по ссылке другим функциям, которые могут его нарушить), эту функцию можно считать чистой.
Вот как D определяет функциональную чистоту: в реализации чистой функции разрешается использовать изменения, если они временные и локальные. Сигнатуру такой функции можно снабдить ключевым словом pure, и компилятор без помех скомпилирует этот код:
pure ulong fib(uint n) { ... // Итеративная реализация }
Принятые в D допущения, смягчающие математическое понятие чистоты, очень полезны, поскольку позволяют взять лучшее из двух миров: железные гарантии функциональной чистоты и удобную реализацию
(если код с изменениями более предпочтителен).
MuLLtiQ
01.09.2015 19:05Ой, ну правда
fib n = fibs !! n where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Красота же :)vintage
01.09.2015 19:34+3Что-то я не понимаю, что ваш код делает :-)
Leeb
01.09.2015 21:35Оператор!!! возвращает элемент списка по его номеру (в данном случает n-й элемент). Список fibs — бесконечный список чисел фибоначчи, который мы определяем следующим образом. Первые два элемента — это 0 и 1 (тут должно быть очевидно), а все последующие элементы получаются комбинированием (а именно, сложением; комбинирование осуществляет функция zipWith с помощью своего первого аргумента) самого списка fibs (т.е. 0,1,...) и его хвоста (tail; хвост списка получается откусыванием первого элемента, головы; т.е. 1,...).
Такое проходит только потому, что хаскелль — ленивый язык, и он не вычисляет весь список целиком (если не предпринимать дополнительных телодвижений).
jokagent
01.09.2015 10:31+6var add = function(a, b){ return a + b }
Вы только что создали анонимную функцию, которая получает a и b и возвращает a + b в переменную add.
Это неправда. Переменная add — функция. Никакого результата она не получает.
heilage
01.09.2015 10:40+3Статья вызывает смешанные чувства. С одной стороны, все упомянутые принципы (преподносимые как основополагающие для ФП) известны и полезны, но нет никаких препятствий для того, чтобы придерживаться этих принципов в языках императивных. С другой стороны, складывается впечатление, аналогичное тому, когда некто упорно и назойливо пытается продвигать свои взгляды как единственно верные, как панацею и серебряную пулю. Но при этом вероятные проблемы, с которыми столкнется программист на чисто функциональном языке в попытке описать идеальными методами наш неидеальный мир — в очередной раз элегантно замалчиваются.
nehaev
01.09.2015 11:25-2> Но при этом вероятные проблемы, с которыми столкнется программист на чисто функциональном языке в попытке описать идеальными методами наш неидеальный мир — в очередной раз элегантно замалчиваются.
Справедливости ради, наш неидеальный мир вообще с тудом поддается описанию. И методами ООП, например, это делать ничуть не легче (а может даже и сложнее), чем методами ФП.heilage
01.09.2015 11:57+2Для меня несколько странно звучит, когда противопоставляют именно ООП и ФП, а не императивщину и функциональщину.
Что касается простоты — поправьте, если я не прав, но мне как человеку довольно поверхностно знакомому с функциональными языками кажется, что современные языки типа эрланга, хаскеля добавляют какие-то невероятные объемы сложности туда, где они совершенно не требуются.
Хотя не могу поспорить с тем, что есть некоторые вполне конкретные применения (типа каких-то супер-многопоточных сервисов, способных держать хреналион одновременных коннектов), где тот же эрланг может подойти гораздо лучше других решений. Но это опять же — относится к конкретной экосистеме, а не к ФП в целом.
Duduka
01.09.2015 12:24ответ на вторую часть вопроса… не верно! На функциональных языках можно писать такие же простые хелоуворлды, как и на императивных, но там, где в императивной программе обработки ошибок, управление потоками, распределение и поддержание целосности данных, в функциональной программе — тот же ад и магия 993 уровня на межгалактическом подпространственном кластере. Функциональное программирование никак не мешает писать программы работающие с состояниями, нет нормального функционального языка, который бы мог оптимизировать такие программы (одни со сложным синтаксисом, другие,… плохо оптимизируют), но это недостаток не «функционального программирования» вообще.
nehaev
01.09.2015 12:52-1> Для меня несколько странно звучит, когда противопоставляют именно ООП и ФП, а не императивщину и функциональщину.
Почему я противопоставил ООП и ФП в контексте описания неидеального мира? Потому что в популярных ООП-языках (Java, C#, C++ и т.д.) реализация ООП завязана на императивную парадигму: объекты имеют изменяемое состояние. В этих языках ООП призвано улучшать модульность и возможности повторного использования императивного кода. Но зачастую ФП позволяет достичь этого более простым путем. Неизменяемость состояния и отсутствие побочных эффектов против инкапсуляции, наследования и полиморфизма. Разумные ограничения против богатых возможностей, которыми еще надо научиться пользоваться (паттерны, SOLID и т.п.) Противопоставлял я их именно в этом смысле, а не вообще. А вообще, сам я в пишу на Scala, где ФП и ООП вполне успешно сочитаются.
> Что касается простоты — поправьте, если я не прав, но мне как человеку довольно поверхностно знакомому с функциональными языками кажется, что современные языки типа эрланга, хаскеля добавляют какие-то невероятные объемы сложности туда, где они совершенно не требуются.
1. Кроме эрланга и хаскеля, бывают и другие современные ФП-языки.
2. Я считаю, что смысл ФП в упрощении кода, а не в усложнении. Два главных ограничения, неизменяемость состояния и отсутствие побочных эффектов, дают referential transparency — важное свойство, позволяющее достаточно просто проверить корректность программы. Чистые функции позволяют использовать функциональную композицию — мощное средство обеспечения модульности и возможностей повторного использования.
3. Таки да, есть экстремисты от ФП, которые используют его везде и для всего. В том числе, для тех задач, для которых оно не очень подходит (никто и не утверждает, что оно подходит всегда и везде). Скорее всего представление о «невероятных объемах сложности, где они совершенно не требуются» возникло у вас после ознакомления с их творчеством. В этом нет ничего плохого, и это совсем не обязательно. Использовать элементы ФП можно во многих языках, лишь единицы из них заставляют вас писать полностью «чистый» код.
dendron
01.09.2015 11:11-2Может кто-то из гуру ФП рассказать, как прогнозировать время работы программы на функциональном языке? То есть можно ли в общем случае глядя на код двух разных программ понять, какая из них будет работать быстрее?
Потому что в импертивном языке, даже щедро присыпанном ООП можно прикинуть быстродействие программы (в случае многопоточности всё конечно усложняется).
А в случае ФП у меня сложилось впечатление, что да, программа это волшебный свиток написанный красивыми рунами, и как оно там выполнится и во что развернётся на железе — не знает даже автор.nehaev
01.09.2015 11:19+2А в чем вы видите проблему? Любой уважающий себя программист независимо от используемой парадигмы должен иметь представление о сложности операций над используемыми структурами данных. Обычно это все описано в документации, и никакой нужды лезть внутрь и считать циклы или рекурсивные вызовы нет. Хотя никто не мешает сделать это при большом желании и соответствующей квалификации.
dendron
01.09.2015 13:30Вы сейчас описываете использование готовых алгоритмов из библиотек, я прав? В таком случае конечно не имеет значения на чём там код написан.
Проблему вижу в накладных расходах на всю эту магию. Скажем, ООП тоже совсем не бесплатное.
И в целом есть плохие способы писать код на императивном языке (в плане быстродействия), есть хорошие, и можно объяснить чем одни отличаются от других, на что тратятся циклы процессора. В случае ФП я не понимаю как отличить быстрый код от медленного и возможно ли это в принципе, чем руководствуются программисты на ФП при выборе способа написания программы и.т.д. Просто у меня из статьи сложилось впечатление (возможно обманчивое), что предлагается откинуться на спинку стула и не думать о быстродействии, потому что современные компьютеры такие быстрые-пребыстрые.nehaev
01.09.2015 14:18> Вы сейчас описываете использование готовых алгоритмов из библиотек, я прав? В таком случае конечно не имеет значения на чём там код написан.
Ну, современное программирование во многих случаях сводится к грамотному использованию готовых библиотек (например, коллекций).
> Проблему вижу в накладных расходах на всю эту магию. Скажем, ООП тоже совсем не бесплатное.
Тут, как и везде, многое зависит от компилятора. Умеет ли он оптимизировать хвостовую рекурсию, лямбды и т.п.
> Просто у меня из статьи сложилось впечатление (возможно обманчивое), что предлагается откинуться на спинку стула и не думать о быстродействии, потому что современные компьютеры такие быстрые-пребыстрые.
Ну там имелось ввиду, что императивный стиль хорошо мапится на фон-неймановскую архитектуру, а функциональный — не очень хорошо. Нагрузку по маппингу в основном на себя берут компиляторы и функциональные структуры данных (из готовых библиотек). И то и другое, как правило, имеет повышенные требования к ресурсам по сравнению с императивными аналогами. С развитием технологий плюсы от использования ФП перевесили минусы от накладных расходов (вполне изученных и достаточно широко известных) на его использование.dendron
01.09.2015 18:52Извиняюсь за настойчивость, но я так и не получил ответа на вопрос, как именно программист на функциональном языке выбирает как ему написать эффективную программу? Неужели ответ — швырять любой, логически правильный код в очень умный компилятор и ждать что он сгенерирует оптимальный машинный код?
nehaev
01.09.2015 20:11Вопрос вроде был про быстродействие, а не про эффективность. И ответ на этот вопрос вроде бы уже прозвучал, и не раз. Может я не понимаю, чего вы от меня добиваетесь? Можете сформулировать ответ на свой вопрос для императивного языка? Например для Java или PHP? А я тогда на базе этого ответа попытаюсь выявить различия с функциональным подходом, если они есть.
dendron
02.09.2015 11:51Хорошо, давайте. Например, при написании программы на языке с ООП мы знаем, что есть затраты на вызов виртуальных методов. Поэтому не очень хорошая идея засовывать тысячи объекты в контейнер и проходить по ним циклом с вызовом виртуальных методов, а ля
for ( baseObj: array )
{
baseObj->foo();
}
В данном случае лучше переписать эту часть, выделив функцию foo из класса, чтобы она работала сразу с коллекцией объектов.
foo( array );
Таким образом мы избегаем ненужных трат на поддержку ООП, хотя в общем-то и в первом случае код выглядит логичным и «правильным» (просто будет более медленным).
Существуют ли подобные правила для написания эффективного кода на функциональных языках?Leeb
02.09.2015 12:39Существуют. Но как и в вашем примере (некоторые языки не очень-то разделяют виртуальные и невиртуальные функции), правила во многом применимы только к конкретному языку. Например, для Haskell обычным советом (настоятельной рекомендацией) является не изобретать велосипед и не писать явную рекурсию самому, а воспользоваться функциями наподобие fold(l/r)/map/filter и т.п. В Erlang же наоборот, чаще гораздо лучше воспользоваться list comprehension, чем lists:map, потому что для первого компилятор генерирует гораздо более эффективный код. Опять же, из рекомендаций для Haskell, в структурах данных делать поля строгими (чтобы не копить thunk-и), но так как распространённых ленивых языков, кроме Haskell нет, то эту рекомендацию трудно представить применимой для каких-либо ещё функциональных языков.
В любом случае, мне кажется, что пример вы приводите не вполне корректный в рамках общей канвы обсуждения. Вы предлагаете оптимизировать ООП путём отказа от ООП.dendron
02.09.2015 13:00Спасибо за ответ, интересно. Что касается примера, то я привёл его специально чтобы показать, что абстрактная и «красивая» концепция ООП, так сказать, в реальном мире имеет свою стоимость и ограничения. И об этом приходится думать при программировании и временами отказываться от «красивого» с точки зрения концепции кода.
Можно ещё вспомнить о «красивых» рекурсивных решениях (вроде стандартного вычисления чисел Фибоначчи), которые в реальном мире и на реальном железе работают не очень.
Соответственно о стоимости ФП тоже очевидно придётся думать при программировании. Только поскольку я не знаком с ФП, я совершенно не знаю как принимаются подобные решения.
nehaev
02.09.2015 13:20Наверняка для вас не является секретом, что современные компиляторы применяют over 100500 оптимизаций к тому, что накалякал программист. Например, в данном случае, в зависимости от того, как объявлен foo() и что именно из baseObj он использует, компилятор может просто заинлайнить реализацию foo() внутрь цикла. И код не надо менять, и никакого вызова виртуального метода.
Конечно, никто не запрещает играть в подобные игры (уродовать код в рассчете на определенное поведение компилятора), но как бы не перехитрить самого себя: после обновления компилятора изначальная версия вдруг станет работ быстрее «оптимизированной», ведь типовые паттерны оптимизируются в первую очередь.
Ответ на ваш вопрос: такойхернейэкономией на спичках не занимается даже подавляющее большинство императивных программистов, ибо они пишут на ОО-языках высокого уровня. Видимо, водораздел здесь проходит не по используемой парадигме.dendron
02.09.2015 13:34Да, наверное Вы правы, но только «водораздел» видимо проходит не по высокоуровневым языкам.
Значение имеет на какие машины ориентируется программист при написании кода. Скажем, если мы ориентируемся на массовую параллельность, то даже если на одной машине код работает в 10 раз медленнее, но отлично масштабируется с увеличением числа станций — то такое решение даже может быть предпочтительнее.
Но в то, что программист может обитать в прекрасном мире абстрактных парадигм а компилятор за него думает об оптимизации я не верю.
nehaev
02.09.2015 13:37Последний абзац, возможно, получился несколько резковатым. Но кода я вижу, что в качестве best practices императивного ОО-программирования преподносится призыв заранее уродовать код, без бенчмарков, без поиска реальных узких мест в процессе выполнения — я испытываю горечь :)
freeAKK
01.09.2015 11:34+1Не надо судить смотря, если можно измерить. Benchmarking на входных данных, генерирумых чем-нибудь вроде пропера поможет.
Возможно ленивость может влиять на производительность. Но тот же эрланг не ленив, так что предсказать, как будет программа довольно просто. Но тут возникает интересный случай, что производительность одного процесса в системе не говорит о производительности всей системы.
Иными словами, измеряй, думай. Быстрое не значит отзывчивое.
nosuchip
01.09.2015 11:43+3Поясните, пожалуйста вот это:
var add = function(a, b){ return a + b }
Вы только что создали анонимную функцию, которая получает a и b и возвращает a + b в переменную add.
Я читаю эту фразу как «ваша функция получит a и b, результат вернет в переменную add». Но это же не так! Ваш код идентичен вот этому:
function add(a, b){ return a + b }
Который ничего ни в какую переменную не возвращает.
extempl
01.09.2015 14:22+1Выше уже указали на эту ошибку.
Разумеется, присваивание результата будет только в случае вызова созданной анонимной функции:
var added = (function(a, b){ return a + b })(1, 2)greg_fat
01.09.2015 14:43-1Да, ошибка перевода, поправил. Спасибо!
Кстати:
> var added = (function(a, b){ return a + b })(1, 2)
это уже каррирование.(carrying)bubuq
06.09.2015 05:28+1Каррированием (currying) было бы
var add = function(x){return function(y){return x + y}} add(1)(2)
Это возможно, но в процедурном языке очень мало применимо.
solver
02.09.2015 14:17Так смешно читать, что для многих ФП это когда можно в одну строчку написать код…
Suvitruf
«Но почему я не могу продолжать использовать ООП?»
Мне тоже интересно.
greg_fat
Мне кажется автор статьи ответил на этот вопрос.
Suvitruf
«Придётся приложить достаточно усилий, чтобы корректно обновлять и синхронизировать все потоки.»
Автор оригинальной статьи не умеет в синхронизацию в ООП, поэтому просит всех переходить на ФП?
greg_fat
В статье он прямым текстом пишет «я не агитирую», мне кажется основная цель показать красоту ФП :)
pfemidi
IMHO он показал не красоту, а ещё более подчеркнул всю несуразность и полную аляповатость ФП. Нет, не убедили. Меня во всяком случае не убедили. if/else на много понятнее, проще да и выглядит в 100500 раз красивее чем пример про guess в стиле какого-то не то мастера Йоды, не то с трудом говорящего по-русски гастарбайтера.
greg_fat
Понятно, что вы привыкли к if/else, только в мире не только едят котлеты с картошкой, есть и миллионы других блюд. Не кажется ли вам, что такая «узколобость» только ограничивает вас? Скажу вам больше, в ФП вообще нет for/while только рекурсии. И мне они кажутся очень удобными.
pfemidi
Я же сказал «IMHO» и «меня не убедили». Так что я никого не агитирую против, просто по мне это (если сравнивать литературно) не текст романа, а бессвязный набор букв, только и всего.
Chamie
Про Йоду-гастарбайтера — это вы про синтаксис или про текст в кавычках? Потому как синтаксис примера с guess почти один в один switch-case:
Или так, через подобие тернарного оператора:Только более компактно.
kasperos
«каждый своего жука хвалит» (с) «Том Сойер» если не ошибаюсь
вообще доверять иностранным авторам только потому что они написали книгу или статью. Попадались мне книги, дословно не помню но примерное содержание фраз:
-в байте 9 бит, но при поступлении в процессор один бит теряется.
-регистры IDE как-то хитро сделаны, по 0 смещению идет работа с 16 битным словом, а по смещению 1 доступен по чтению 8 битный регистр ошибок, как они это сделали? какой-то радиолюбительский трюк.
Ostrovski
Простите, а кто-то умеет? Тут, на мой взгляд, как повезет. Сумел предусмотреть все кейсы — молодец. Нет — получай дедлоки или состояние гонки. И хуже всего, когда автор кода слишком уверен в своих способностях мыслить в терминах нескольких потоков одновременно.
vintage
В любом современном императивном языке состояние по умолчанию не разделяемое и явная работа с разделяемым состоянием является антипаттерном.
nehaev
> В любом современном императивном языке состояние по умолчанию не разделяемое
В каком, например? C, Java, C#, Python?
vintage
D, Go, Rust.
С, Java, C# — языки с устаревшим дизайном.
В Pyhon многопоточности фактически нет, ибо GIL.
nehaev
Путаете квантор существования и квантор всеобщности?
vintage
Не путаю. Прямая работа с разделяемым состоянием в многопоточной среде сейчас считается дурной практикой по всем известным причинам. Во времена появления Java, C# и, прости господи, C это было ещё не очевидно. Поэтому все современные языки по умолчанию состояние не разделяют. А те не многие поделки, что таки разделяют современными считаться не могут, так как отстали в этом плане от развития компьютерной науки.
nehaev
Хорошо. Если взять за основу ваше понимание слова «современный», то соглашусь :)
vintage
Я вам даже ещё процитирую Александреску:
Duduka
функциональное и императивное существуют в разное время, совместить их нельзя, любая программа имеет функциональную и объектную часть. Первая отвечает за поток управления, вторая за состояние.
В самом функциональном программировании нет понятия функция, оно берется из теории множеств, как отображение одного семейства множеств в другое, и программа строится как абстрактное отображение «входного» состояния на «выходное», которое и зовут «выводом», правила строительства его и составляют суть функционального программирования. Императивное — это костыль, в котором весь вывод ограничен «последовательностью» исполнения, т. е. запустить параллельно несколько задач, меняющих общее состояние, имеет смысл только как генератор случайного шума, поэтому создается следующий костыль — обеспечение конкурентного исполнения.
Но за бортом осталось описание «входного-выходного» мира… тут-то и используют объекты/состояния. Разница в программировании тут существенна: 1) ООП в императивном стиле — нарезать мир на плоскости последовательности состояний, и подавать их последовательно на вход простого преобразователя (вашей программы) состояний; 2) ООП в функциональном стиле — нарезается мир на последовательность преобразований, которые и применяются последовательно друг к другу, а потом этот клубок исполняется на входном состоянии (если бы в haskell был бы параллельный исполнитель, то можно было бы натравливать на входное состояние много ядер [что-то вроде fork-map-reduce], и си код стал бы тормазнутым из-за немасштабируемости). Как недостаток функционального программирования можно назвать — нелокальность представления, которое необходимо костылить декомпозицией и синтаксическим сахором.
Но и императивное имеет свои плюсы — локальность. Часто можно расположить измененные состояния рядом, или закостылить — хранить «будущее» в «настоящем» (модель «состояние»), но если состояние петобайтное, то хранение в кеше — невозможно и этот плюс теряется.
Вывод: для получения выгоды от применения этих парадигм нужны специфические задачи и условия (поддержка языка и архитектуры) и синергия из-за этого не получится, но самое противное — это разное мышление и программируя на haskell в слиле си, или на плюсах/java/scala в стиле haskell получим недостатки обеих стилей, с одним плюсом — достаточно знать один из языков.
Lol4t0
Присоединяюсь, почему это нельзя использовать ООП вместе с ФП, раз уж эти парадигмы описывают разные вещи?
Newbilius
Как вы можете использовать ложку, если познали существование вилки?! Еретик!