1. На чистых функциональных языках не существует эффективного неупорядоченного словаря и множества
С 90х годов использование словарей в разработке побило все рекорды. Словари теперь—стандартная коллекция, которую каждый разработчик ожидает найти в своей стандартной библиотеке.
Чисто функциональные или персистентные структуры данных, типа тех, что можно найти в небезызвестной монографии Окасаки—отличный инструмент. В частности, персистентность, которую они предоставляют, означает, что вы можете обращаться к старым версиям коллекций, не беспокоясь о том, как коллекции модифицируются. Во многих случаях (особенно в задачах типа логического программирования или написания компиляторов) это может сделать решения короче и проще—частично потому, что сделает слежение за изменениями тривиальным. Но за персистентность нужно заплатить большую цену в смысле производительности: чисто функциональные словари обычно примерно в 10 раз медленнее, чем хорошо реализованные хэш-таблицы, и я видел случаи, когда разница достигала 40 раз. Для некоторых приложений это непозволительно медленно.
Более того, большинство функциональных языков (OCaml, Haskell, Scala) неспособны выразить быструю изменяемую generic хэш-таблицу, потому что у них нет убийственной комбинации из reified generics, типов-значений (value types) и быстрого write barrier для сборщика мусора.
ВНИМАНИЕ! Остерегайтесь людей которые пытаются утверждать, что чисто функциональные словари Хаскеля быстрые, сравнивая их с изменяемыми хэш-таблицами того же самого Хаскеля. Правильный вывод из такого сравнения: это изменяемые хэш-таблицы Хаскеля медленные.
2. Не существует чисто функциональных слабых хэш-таблиц (weak hash table)
В императивном языке со сборкой мусора отношения между узлами и ребрами графа можно выразить с помощью слабых хэш-таблиц. Сборщик мусора соберет за вас недостижимые подграфы. Поскольку чисто функциональных слабых хэш-таблиц не существует, в чистом функциональном языке вам придется писать свою сборку мусора (прим. перев. я так понимаю, в смысле удалять недостижимые подграфы руками).
Впрочем, это не самый серьезный недостаток, учитывая то, что большинство разработчиков никогда не пользовались слабыми хэш-таблицами…
3. Не существует чисто функциональных потокобезопасных коллекций
По определению, неизменяемые коллекции не могут поддерживать мутабельность, в том числе и потокобезопасную. Так что, если вы хотите shared изменяемую коллекцию (такую как in-memory базу данных), то чисто функционального решения не существует.
4. Большинство алгоритмов на графах выглядят хуже и работают намного медленнее, если написаны в функциональном стиле
Функциональное программирование—отличный инструмент для некоторых типов задач, но, по моим наблюдениям, алгоритмы на графах—то место, где чисто функциональные решения часто хуже и с точки зрения простоты кода, и с точки зрения производительности.
Сравните алгоритм Прима на 12 строчках Питона и алгоритм Прима на 20 строчках Хаскеля. А и почему, собственно, Хаскель использует алгоритм Прима в библиотеке? Наверное, потому что алгоритм Крускала основывается на структуре данных "система непересекающихся множеств" (union-find collection, aka Disjoint-set data structure), а в функциональных языках нет ее эффективной реализации.
5. Инерция традиционных императивных структур данных и алгоритмов огромна
Помимо алгоритмов на графах, существует много областей computer science, в которых 65 лет научной литературы фокусировались почти полностью на императивных решениях. Следовательно, программисты на императивных языках могут стоять на плечах гигантов и пользоваться этими наработками, в то время как программистам на функциональных языках часто приходиться начинать с нуля. В конце концов, всего пару лет назад мемоизация в Хаскеле была темой кандидатской диссертации.
Однажды я предложил нескольким программистам на Хаскеле (и у некоторых из них были диссертации по этому языку) написать на нем эффективную параллельную быструю сортировку (quicksort)—и вот что из этого вышло.
6. Как оказывается, все существующие реализации функциональных языков—как чистых, так и нечистых (impure)—спроектированы так, что аллоцируют слишком много памяти
Примерно в 1960 году МакКарти изобрел Лисп. Основной структурой данных был односвязный список. Каждый элемент списка аллоцировался отдельно в куче. Все современные функциональные языки развились из этой идеи. В 70х Scheme использовал по сути ту же стратегию представления данных, что и Лисп. В 80х, SML добавил немного распаковывания (unboxing) в связи с включением в язык кортежей (tuples), аллоцируемых в куче как цельные блоки памяти. В 90х OCaml добавил еще немного распаковывания в связи с включением в язык распакованных массивов действительных чисел. Хаскель добавил возможность распаковывать определенные типы данных. Но по сегодняшний день ни у одного функционального языка нет по умолчанию распакованных кортежей (прим. перев. судя по всему, автор выбрал почему-то такой способ сказать «кортежей, по умолчанию расположенных на стеке»). Даже F#, основанный на .Net, в котором можно создавать любые типы-значения (value types), все еще использует запакованные кортежи .Net. Следовательно, все современные функциональные языки несут на себе бремя частых аллокаций памяти в куче без всякой на то необходимости. Следовательно, они нагружают свои сборщики мусора намного больше, чем нужно. Это серьезная проблема не только потому, что это делает однопоточный код медленным, но и потому, что сборщик мусора—совместно используемый ресурс и, как следствие, нагрузка на сборщик мусора ведет к плохой масштабируемости параллельных программ.
Нужно заметить, что объявление такого поведения «недостатком» может быть спорным. Xavier Leroy из сообщества OCaml считает, что представление данных в OCaml по образу Лиспа—это преимущество, потому что это основа отличной производительности OCaml в среде для автоматического доказательства теорем Кок (Coq). Ксавье заявляет, что «стратегия Ocaml для символьных вычислений близка к оптимальной». Функциональные языки часто оптимизированы для высокопроизводительных чисто функциональных коллекций за счет низкой производительности императивных коллекций. С учетом того, что императивные коллекции в основном быстрее, это ведет к искусственно заниженному потолку производительности почти всех функциональных языков.
7. Чистое функциональное программирование хорошо для параллелизма в теории, но не очень хорошо с точки зрения производительности на практике, а высокая производительность на практике—единственная настоящая задача параллелизма
Сегодня есть две причины писать параллельные программы. Первая—это писать объективно быстрые решения. Вторая—делать медленные решения не такими медленными. В большинстве случаев параллельное программирование на функциональном языке—вариация второй причины. Почти никто в среде высокопроизводительных вычислений (high performance computing), то есть на суперкомпьютерах, не запускает напрямую функциональный код. Если разработчик на функциональном языке параллелизует программу, в большинстве случаев он делает это не для того, чтоб добиться отличной абсолютной производительности, а чтоб улучшить ту скорость, что у него есть.
Чистые функциональные языки типа Хаскель разработаны, чтоб скрыть от программиста работу с памятью и временем. Это дает программисту вид на программу с высоты птичьего полета, но делает очень сложным оценку того, сколько памяти будет потреблять программа на Хаскеле и сколько времени она будет выполняться, прежде чем получит результат. В параллельном программировании всегда очень важно убедиться, что выигрыш от параллелизации перевесит административные затраты на параллельное выполнение кода. В Хаскеле это очень тяжело. На самом деле, настолько тяжело, что опубликованное исследование о параллельном выполнении Хаскеля очень избирательно предоставляет результаты о степени параллелизации, которая максимизирует производительность, при том что эту степень нельзя предсказать заранее без того, чтоб не прогнать программу много раз. По моему опыту, в языках типа С++ параллелизация самыми стандартными методами часто дает предсказуемый выигрыш в скорости, в отличие от Хаскеля, где производительность не предсказуема.
ВНИМАНИЕ! Остерегайтесь людей, которые говорят о масштабируемости программ без учета абсолютной производительности. Вы можете улучшить масштабируемость почти любой параллельной программы путем бессмысленного вычисления множеств Мандельброта после каждой строчки кода без всякой на то причины, потому что большая часть вычислений будет происходить в невероятно параллельном коде. Масштабируемость—необходимое, но не достаточное условие. Нужно обяэательно смотреть и на абсолютную производительность.
8. Понадобилось 50 лет, чтоб разбавить концентрацию высокомерных снобов в сообществе до той степени, чтоб можно было получить полезный ответ по функциональному программированию
Я занимаюсь функциональным программированием уже больше 20 лет. Десятилетиями существовала социальная пропасть между программистами на функциональных языках и теми, кто решал настоящие задачи. Слава богу, эта проблема начала рассасываться вместе с тем, как функциональные языки типа Scala, Clojure и F# начали использоваться для настоящих задач; но много лет в сообществе функционального программирования преобладали именно высокомерные снобы, что делало очень трудным получение настоящих решений для настоящих проблем. Причиной для этого было то, что многие сообщества (особенно Лисп), на десятилетия преданные забвению и предоставленные сами себе, имели очень развитые (но неправильные) аргументы о том, почему их язык (Лисп) такой хороший. Мне потребовалось много лет, чтоб понять, что не так в этих аргументах.
9. О функциональном программировании циркулирует множество ложной информации
Если вы критикуете производительность хэш-таблиц в Хаскеле (более свежая критика здесь), то вы можете получить абсолютно дикие советы от светил сообщества—например, они могут буквально посоветовать вам просто отключить сборку мусора.
Долгое время сообщество функционального программирования потрясало замечательно короткими реализациями алгоритмов решета Эратосфена и quicksort. Их даже годами преподавали студентам. И только спустя многие годы пришло понимание, что эти реализации не соответствуют исходным алгоритмам. Мелисса О'Нил (Melissa O’Neill) даже опубликовала научную статью, исправляющую решето Эратосфена в Хаскеле. В частности, ее настоящее решето требует в сто раз больше кода, чем ошибочная оригинальная версия. То же справедливо и для quicksort'а, где «элегантная» двухстрочная версия на Хаскеле более чем в 1000 раз медленнее версии Сэджвика на C, потому что Хаскель делает глубокую копию списков на каждом вызове quicksort'а, портя к чертям асимптотическую сложность оригинального алгоритма Хоара.
Смотрите также "Почему Хаскель так мало используется в индустрии", где подробно опровергается страница "Хаскель в индустрии".
От автора: статью «Почему Хаскель так мало используется в индустрии» я тоже надеюсь когда-нибудь перевести, потому что она пытается опровергнуть мнение о том, что Хаскель последние пять лет широко используется в индустрии. Но надо заметить, что (судя по комментариям к оригинальной версии на английском) она не так однозначна и автор сам, кажется, кое-где сгущает краски.
Комментарии (256)
NeoCode
24.06.2016 09:14+17Мышление человека в основном императивно, и большинство рельных задач по сути своей императивны и имеют состояния (работа с БД, железом, сетью, файловой системой и т.д.). Поэтому чистое ФП это ИМХО скорее что-то для математиков. А вот применение элементов функционального программирования в императивных языках — это очень хорошая штука, и это прекрасно что ФП все больше проникает в классические языки.
Duduka
24.06.2016 09:32-2Моноид может(и хранит состояние), например: цифра, строка, список, массив и матрица… все это состояние некоего моноида, и не так много практических языков хранит весь вывод состояния из единицы, часто используются уже вычисленные состояния («аб», а не список "" + «а» + «б»). Императивный язык — функционален по определению (программа — это функция преобразования одного состояния в другое), но имеет один «баг/фичу» — не обязан обеспечивать корректное состояние все время преобразования (DataBase, FilesSystem, Net...), вот и все отличие, императивная программа «почти всегда» срабатывает (вычислима, и порождая корректное состояние), но «иногда» что-то идет не так.
OsipovRoman
24.06.2016 09:52+4Поддерживаю, NeoCode
Функциональные языки позволяют записать многие вещи крайне элегантно. Для меня функциональный подход довольно близок, так как он является одной из парадигм, реализованных в Wolfram Language. И как показывает практика, да, математикам, конечно, писать на них проще и даже естественно.
gaki
24.06.2016 12:25+4Мышление человека мультипарадигменно. Читаем книгу и, встретив незнакомое слово не вываливаемся в крэш дамп — вот вам Хаскель. Делаем из имеющихся в нашем распоряжении фактов вывод «Васька — дурак» — вот вам Пролог.
OsipovRoman
24.06.2016 09:44+1Какой-то «заказ» на то, чтобы «разоблачить» функциональные языки — на Хабре вышло подряд по сути несколько статей о них, особенно применительно к Haskell.
kekekeks
24.06.2016 10:17+9Ну сначала была серия статеек об их крутизне. Да и вообще много о них сейчас говорят. Надо же и о недостках, не только о достоинствах.
Source
24.06.2016 22:28Что о недостатках, что о достоинствах надо говорить с учётом области применения, иначе получается оторванный от реальности маркетинговый булшит. Desktop, Web, Mobile, Machine Learning, AI, разработка ОС и драйверов и т.д. — это всё принципиально разные области.
kmikeru
24.06.2016 10:54+1По-моему, просто у автора оригинальной статьи была необходимость продвигать свои услуги по консалтингу на F#, а известность, хотя бы и скандальная — лучшая реклама.
cs0ip
24.06.2016 10:55+5Мне кажется не важно заказ это или нет в данном случае (хотя не могу придумать кому это нужно), т.к. все аргументы легко проверить самостоятельно. А если видите здесь какую-то неправоту автора, то можете опровергать фактами, если найдете такие.
VolCh
24.06.2016 13:10+2Хорошая пропаганда не искажает факты, как раз потому что это легко проверить. Хорошая пропаганда оперирует набором, очередностью, тональностью, эмоциональностью, контекстом и т. п. подачи абсолютно достоверных фактов.
Cryvage
24.06.2016 14:49+14Ну почему сразу заказ? По моему в статье все логично. Вообще, если не вдаваться в конкретику, то можно сформулировать довольно кратко. Функциональные языки это очень высокий уровень абстракции. Гораздо более высокий, чем любой императивный язык. От этого, прежде всего, будет всегда страдать производительность. При этом, виртуальную машину, которая выполняет функциональную программу, можно оптимизировать, но, как и всегда, только под определенные классы задач, проиграв при этом где-то еще. А вот оптимизировать конкретный алгоритм мы практически не в силах, потому что абстрагированы от железа практически полностью.
И эта проблема не является эксклюзивной для функциональных языков. Каждый раз, когда мы поднимаемся на более высокий уровень абстракции, мы теряем в производительности. Но если при этом растет скорость и простота разработки, и вообще появляется хоть какое-то преимущество, всегда найдется сфера применения, где это преимущество окажется важнее недостатков. Вопрос только в том, насколько эта сфера применения будет широка.
И вот исходя из этого и следует определять, где ФП применимо, а где нет. В последнее время просто была тенденция, форсить функциональные языки везде и всюду, как какую-то новую религию. А потом уже и в комментариях на Хабре, на прочих форумах, и вообще в разговорах с другими программистами, я стал замечать, что некоторые видят написание чего-либо в функциональном стиле, как самоцель. Будто если программа написана на функциональном языке, то это ее главное преимущество. Поэтому появление таких вот контр аргументирующих статей вполне закономерно. Такое и с другими новыми технологиями/языками случается. Сначала появляется шквал статей, где какая-то технология описывается, как серебряная пуля. Следом идут статьи, где происходит срыв покровов, и объявляется, что серебро оказалось простой нержавейкой.
Программисты в своей массе вообще довольно «религиозны». Я конечно же имею в виду не традиционные религии, а фанатичное следование каким-либо трендам. Для многих ООП — это настоящая религия. А для других, вот — ФП. Есть те, для кого нет бога кроме MVC. А кто-то делает идола из соглашений по написанию кода. Встречались мне и более экзотические верования, например священный джихад против множественных return'ов из функции. Может и в других профессиях такое наблюдается, но мне почему-то кажется, что программисты, чаще всего участвуют в священных войнах. Проблема еще в том, что у нас это легко может выйти за пределы какого-нибудь форума. У многих есть возможность проталкивать свои идеи на практике. И вот тут надо проявлять осторожность.
Bas1l
25.06.2016 03:16Ну вот это моя вторая подряд (и вообще) статья, «разоблачающая» ФП (первая вот тут)—но никакого заказа тут нет. Просто попались на глаза хорошие и интересные статьи. Мысли автора прошлой статьи показались мне очень близкими и к тому же точными. Текущая статья показалась интересной и глубокой технически. Тут и ссылки на научную литературу и на, действительно, нелепые советы на stackoverflow от «гуру» хаскеля и про то, как в хаскеле алгоритмы на графах реализованы и много еще чего.
Кроме того, как раз тогда, когда на глаза попались эти статьи, я узнал, что в одном университете на специальной программе обучения ИТ для людей с не-ИТ образованием (типа биологов или химиков) обучение начинают с диалекта Лиспа. И лично мне показалось, что это уже слишком и надо что-то с этим делать. Вот, к примеру, как-то компенсировать бесконечный поток предвзятых и, в общем, необоснованных похвал и агитации за функциональные языки.IIvana
25.06.2016 04:45+2я узнал, что в одном университете на специальной программе обучения ИТ для людей с не-ИТ образованием (типа биологов или химиков) обучение начинают с диалекта Лиспа. И лично мне показалось, что это уже слишком и надо что-то с этим делать.
Помню, читал в комментах к прошлой статье, как знакомая автора коммента, уехавшая в Германию, жаловалась ему что их там бедных Лиспу учат и как это ретроградно и ужасно, прямо ах!.. А я почему-то сильно подозреваю, что речь идет о том самом MIT-овском курсе SICP на Scheme, о котором существует мнение (и я его разделяю), что это введение в специальность программиста как таковую. А «что-то с этим делать» совершенно не обязательно — деградация поколения селфи уже происходит и без вашей помощи.Bas1l
25.06.2016 13:09Это был, как ни странно, я, и говорю об этой же истории. Нет, речь идет не об MIT-овском SICP. И дело не в ретроградстве, а в том, что сама программа обучения на 1,5 года, вроде, и вам за полтора года нужно научить людей делать что-то полезное на компьютерах (программировать, то есть), которые этим никогда не занимались. И начинать сразу с императивного языка, мне кажется, намного эффективнее и разумнее. К деградации это не имеет никакого отношения (и к поколению селфи тоже). Есть много других сложных тем, которые, помимо прочего, на мой взгляд, учить еще и полезно, в отличие от Лиспа.
Bas1l
25.06.2016 13:33Точнее, я даже не против обучения Лиспу или Хаскелю, если у вас достаточно времени (если вы, к примеру, на бакалавра по ИТ учитесь). Я даже за. Но когда времени мало, то приоритеты, я думаю, можно расставлять по-другому. И вот в надежде на то, чтоб в спорных случаях приоритеты могли расставляться по-другому, я и сделал два перевода с критикой ФП.
ElMachete
25.06.2016 13:34-1В Lisp функционального не больше чем в плюсах.
Idot
25.06.2016 14:53+1От чего же LISP тогда столько лет преподносится как ФП?
ElMachete
25.06.2016 15:12Lisp — мультипарадигменный язык. Можете писать в стиле, который вам больше нравится. Видимо те, кто категорично относят Lisp к ФП не знают Lisp. Python или Ruby — ФП?
Idot
25.06.2016 15:24+1Это самый первый ФП-язык, и появился он ещё в 1958 году:
https://ru.wikipedia.org/wiki/LISP
Функциональная парадигма является для Лиспа «родной», поскольку основой архитектуры его является лямбда-исчисление Чёрча. Собственно, именно с Лиспа началось функциональное программирование как практическая методология разработки программного обеспечения.ElMachete
25.06.2016 15:30-1И? Если вы захотите, например на Common Lisp, ООП — есть CLOS, хотите — пишите в императивном стиле. Никто не запрещает…
Idot
25.06.2016 15:34+4Ваше утверждение «LISP — не ФП», по абсурдности смахивает «Христос — не христианин, потому что не ходил в церковь».
ElMachete
25.06.2016 15:38-1Моё утверждение — Lisp — мультипарадигменный язык. Там выше написано. «LISP — не ФП» — ваше утверждение, которое вы и разоблачили. :)
Idot
25.06.2016 15:54Ваше утверждение:
В Lisp функционального не больше чем в плюсах.
В стандартах C++ ничего функционального не припомню => C++ не ФП
=> Вы утверждаете, что LISP тоже не ФП.ElMachete
25.06.2016 16:15-1Ещё раз — вы можете писать на Common Lisp в императивном стиле. Можете в ОО стиле. Можете в ФП.
Вы дернули цитату из википедии из раздела «Парадигмы программирования в Лиспе», что вам помешало прочитать остальные пункты, кроме ФП, я не знаю.
Вы генерируете мои утверждения и сами их опровергаете. Мне кажется я лишнее звено в вашем самсобойчике.Idot
25.06.2016 16:19+2ЕЩЁ РАЗ: Ваше утверждение целиком:
В Lisp функционального не больше чем в плюсах.
вот пруф https://habrahabr.ru/post/303984/#comment_9674488
Если в C++ нет ФП => получается, что Вы утверждаете, что в LISP нет ФП,
PS Про ООП и ИП — в Вашем отверждении ничего нет вообще, я его процитировал полностью как есть.ElMachete
25.06.2016 16:28Может фраза и не совсем корректна, но мной имелось в виду, что на лиспе можно писать и в чисто императивном стиле. Последующие посты вы уже предпочитаете не замечать.
Вас лиспер в детстве обидел? :)Idot
25.06.2016 16:50+2Напротив, у меня в студенческие годы была книжка про LISP, целиком посвящённая ФП (а вот самого LISP'а у меня не было, потому на ФП никогда не писал). А также была куча книг по C++ в которых про ФП не было АБСОЛЮТНО НИЧЕГО.
От чего Ваше утверждение «В Lisp функционального не больше чем в плюсах.» меня оскорбила до глубины души.
potan
26.06.2016 01:09В C++ давно появились const-указатели — выжный шаг к функциональности. В современном есть замыкания.
C++ сожержит чисто функциональный язык шаблонов. В CL язык макросов совпадает с основнам языком со всеми его императивными возможностями, то есть здесь плюсы даже более функциональны :-).
Idot
25.06.2016 15:29+1PS что за мода такая, как только критикуют ФП за медлительность, так сразу открещиваются от Лиспа?
И Basic и Java — тоже критикуют за медлительность, но никто из тех кто пишут на ИП-языках не утверждает про них «это не ИП».ElMachete
25.06.2016 15:40И про скорость я ничего не писал. Но если вам интересно, найдите на киберфоруме холивар на тему Common Lisp vs D. Много интересного узнаете ;)
potan
26.06.2016 01:01Смотря в каком. В Scheme все таки побольше. А уж Clojure больше функциональный, чем какой-нибудь другой.
VolCh
25.06.2016 13:40+1Тут надо смотреть конечную цель обучения. Если на выходе нужно получить (по советским меркам) инженера, то начинать с функционального языка или, хотя бы, парадигмы (хоть JS использовать) есть резоны. Если техника — то, да, потеря времени.
nehaev
25.06.2016 12:06+2Текущая статья показалась интересной и глубокой технически.
У ФП, как и везде, полно проблем, которые конечно стоит обсуждать. Но в данной статье не наблюдается ничего кроме громких заголовков и невнятного бормотания в качестве аргументации. Автор говорит, что вокруг ФП полно мифов, но сам льет воду на мельницу нескольких расхожих мифов:
1. Код в функциональном стиле медленне, чем императивный
2. Простые задачи (типа квиксорт) в ФП решаются неадекватно сложным способом
3. Функциональный код пишут только высокомерные математики
В реальной жизни, как всегда, это все несовсем так:
1. Быстродействие программ зависит в первую очередь от архитектуры, дизайна и грамотного применения библиотечных средств (особенно — коллекций), и в последнюю очередь — от выбранной парадигмы
2. Вряд ли такое будет часто, но если вдруг видите, что функционально решение получается слишком сложным — просто перепишите этот кусок в императивном стиле, или тут прям одни Haskell-программисты сидят?
3. Люди бывают разные, делать по отдельныи индивидам глубокие выводы о всем ФП-сообществе неправильноBas1l
25.06.2016 13:20Во многих пунктах есть очень релевантные ссылки. Про решето Эратосфена аж научная статья. Именно про квиксорт тоже была ссылка, но она в исходном блоге не работала и я ее не стал вставлять.
Вряд ли такое будет часто, но если вдруг видите, что функционально решение получается слишком сложным — просто перепишите этот кусок в императивном стиле, или тут прям одни Haskell-программисты сидят?
А зачем тогда вообще начинать писать на функциональном языке, если можно сразу начать на императивном и избавиться от всех проблем?nehaev
25.06.2016 13:34+3А зачем тогда вообще начинать писать на функциональном языке, если можно сразу начать на императивном и избавиться от всех проблем?
Потому что в «чистых» императивных языках тоже полно всяких проблем. И если решето Эратосфена я писал один раз в жизни как тестовую задачу, а weak hash table использовался всего в двух проектах, из тех, где я участвовал, то обработку коллекций (фильтрация, маппинг, свертка) я пишу по много раз в день, и в императивном виде это просто адски неудобно. Надежный параллелизм реализовать сложно, моки для юнит-тестов иногда выглядят страшнее, чем код, который они тестируют. Люди переходят на ФП не от хорошей жизни, а спасаясь от ошибок, связанных с изменяемым состоянием и побочными эффектами.
VolCh
25.06.2016 13:48+1А зачем тогда вообще начинать писать на функциональном языке, если можно сразу начать на императивном и избавиться от всех проблем?
Если бы в императивных языках не было проблем, то сейчас бы мы о функциональных не дискутировали. У функциональных свои плюсы и минусы, у императивных — свои. Мультипарадигменные пытаются совместить плюсы и избавиться от минусов, хотя бы простотой перехода от одной парадигмы к другой в рамках не то что одного проекта, а в рамках одного блока кода. Если вы когда-нибудь писали код типа
, то вы совмещали преимущества обоих подходов, переходя от императивной парадигмы к функциональной в рамках одной строки кода.var activeItem = items.filter((item) => item.isActive)
qw1
25.06.2016 19:55Конкретно этот пример — приправленное синтаксическим сахаром определение ф-ции.
Если это ФП, тогда вот это тоже ФП:
int compareLen(void* p1, void* p2) { return ((Item*)p1)->len - ((Item*)p2)->len; } qsort(items, N, compareLen);Source
26.06.2016 01:56Когда Вы можете передать функцию в качестве параметра другой функции, или вернуть функцию из функции — это, безусловно, часть ФП, так как только в этой парадигме существуют функции высшего порядка.
VolCh
26.06.2016 10:42Смотря что делает qsort. Если переставляет items, то не совсем — ФП подход используется только внутри реализации функции qsort, но сама она императивная. Если формирует новую структуру данных (которую ваш код никуда не сохраняет, пускай даже назад в items), то ФП используется и вашим кодом как клиентом qsort.
Idot
25.06.2016 15:15Быстродействие программ зависит в первую очередь от архитектуры, дизайна и грамотного применения библиотечных средств (особенно — коллекций), и в последнюю очередь — от выбранной парадигмы
Не убедительно:
0. быстрота на практике часто не требуется (а важно другое, например, ясность кода и т.п.)
1. если требуется именно быстрота, то пишут на C, или смеси C и C++
PS чем не годится преобразование LISP-style кода f(a,b) в Forth-Style код a b f с последующей компиляцией?
Хотелось бы услышать подробно аргументированную критику.nehaev
25.06.2016 23:25+21. если требуется именно быстрота, то пишут на C, или смеси C и C++
Если требуется быстрота, включают голову, корректируют архитектуру и дизайн, включают профайлер и оптимизируют критические места в коде. Да-да, именно так, причем независимо от ЯП. Никакая волшебная смесь С и С++ не поможет написать быстрый код в отсутствие мозгов. А при их наличии, можно писать достаточно быстрый код практически на чем угодно.Idot
26.06.2016 00:17+1На языках с не отключаемой Сборкой Мусора быстрый код не написать в принципе. Такие фичи в языке сделаны не для скорости, а совсем для других задач, которые эти языки в своей нише с успехом выполняют не нуждаясь в быстроте.
PS Что за привычка сначала судить об эффективности по скорости, а затем пытаться натянуть сову на глобус?!Idot
26.06.2016 00:34+1поправка: речь об Автоматической Сборке Мусора, которая в случае её неотключаемости может неожиданно в непредсказуемый момент запустившись затормозить программу — вне зависимости от наличия мозгов.
nehaev
26.06.2016 01:02+4Не путайте быстродействие и отзывчивость в реальном времени. Сборка мусора сильно влияет на второе, но не особо влияет на первое, в том смысле что есть множество других гораздо более существенных факторов, о которых я писал выше.
Bas1l
26.06.2016 03:44-1Ну кончечно не влияет на скорость. Остановить поток, пройти по ссылкам со стека до всех объектов, найти неиспользуемые, вызвать деструкторы (со всякими этими freachable—в .Net, по крайней мере), перекомпоновать память, обновить ссылки на перемещенные объекты и т.д. и т.п.
nehaev
26.06.2016 13:13Самое забавное, что даже то, насколько GC влияет на конечное время исполнение программы, тоже напрямую зависит от кривизны рук разработчиков.
potan
26.06.2016 01:13+4Быстрый написать можно. Нельзя написать код с гарантированным временем исполнения. Это немного разные вещи.
Idot
26.06.2016 00:38Аргументированного ответа на вопрос:
чем не годится преобразование LISP-style кода f(a,b) в Forth-Style код a b f с последующей компиляцией?
я так от Вас и не услышу?
Хотелось бы услышать подробно аргументированную критику.nehaev
26.06.2016 01:08Ума не приложу, где в нашей дискуссии выше я дал повод думать, что имею какое-либо мнение по этому поводу или хотя бы просто понимаю, о чем собственно речь :)
qw1
26.06.2016 10:23Переведите на FORTH фрагмент, который генерирует функции и станет понятно, что 1-в-1 не переводится, нужно выдумывать костыли:
(defun make-adder (n) (lambda (x) (+ n x))) (setq my-add 20) (setq my-func (make-adder my-add)) (my-func 10)
dima_mendeleev
24.06.2016 10:22+38. Понадобилось 50 лет, чтоб разбавить концентрацию высокомерных снобов в сообществе до той степени, чтоб можно было получить полезный ответ по функциональному программированию
По моему это единственная стоящая фраза.
(Я не говорю что остальные не релевантные, но они точно не новые.)
Laney1
24.06.2016 10:54+13мне кажется, суть статьи в том, что в программировании (да и не только в нем) нет универсальных рецептов на все случаи жизни, и бездумное применение какого-то одного инструмента никогда не ведет ни к чему хорошему.
Написать «array.filter(x => x % 2 == 0)» — очень хорошо. Это повышает читаемость кода, снижает число возможных багов, и как правило легко параллелится. Завернуть весь алгоритм в цепочку из сотни вызовов map(), zip(), scan() и т.д. — получится магический рецепт на тайном языке.
Объединить несколько использующихся вместе полей и методов в один объект — очень хорошо. Написать все в ООП-стиле с кучей самых продвинутых паттернов — FizzBuzz Enterprise Edition.
… и так далее.
Antervis
24.06.2016 11:31Это круто если в итоге эта строчка не отработает на тысячи часов больше её многострочного, но оптимизированного аналога.
NeoCode
24.06.2016 13:49+6Полностью согласен. Лучше всего когда код мультипарадигмальный и оптимально сочетает все парадигмы, а не зацикливается на какой-то одной.
nehaev
24.06.2016 14:24+2Статья, которая называется «Недостатки чистого функционального программирования» в основном сводится к тому, что существуют некоторые задачи, которые не удобно решать в рамках ограничений, накладываемых функционально парадигмой. Это примерно как говорить, что недостатком отвертки является то, что ею неудобно забивать гвозди. Если ты взялся забивать гвозди отверткой и тебе неудобно — это твои проблемы, а не недостатки отвертки. Недостаток отвертки — это когда ею неудобно делать то, для чего она предназначена, т.е. закручивать шурупы. Функциональные языки предназначены для работы с неизменяемым состоянием, и пункты 1-5 являются закономерным следствим из этого.
Бросается в глаза желтизна некоторых пунктов:
3. Не существует чисто функциональных потокобезопасных коллекций
И ниже поясняется, что речь идет об изменяемых коллекциях, которых в чисто функциональных языках не может быть по определению, безотносительно потокобезопасности.
6. Как оказывается, все существующие реализации функциональных языков спроектированы так, что аллоцируют слишком много памяти
Как оказывается, все существующие высокоуровневые языки спроектированы так, что аллоцируют слишком много памяти — и все сразу побежали писать на ассемблере.
7. Чистое функциональное программирование хорошо для параллелизма в теории, но не очень хорошо на практике, а высокая производительность на практике—единственная настоящая задача параллелизма
Непонятная формулировка и сумбурное пояснение. В ФП ряд неприятных проблем, возникающие при параллелизме, исключены как класс. В чем недостаток-то?
Последние 2 пункта больше ad hominem, чем объективные недостатки ФП как подхода.Bas1l
24.06.2016 16:58Непонятная формулировка и сумбурное пояснение
О, это я пропустил фразу в заголовке, спасибо. Теперь он вот такой: «Чистое функциональное программирование хорошо для параллелизма в теории, но не очень хорошо с точки зрения производительности на практике, а высокая производительность на практике—единственная настоящая задача параллелизма»
В ФП ряд неприятных проблем, возникающие при параллелизме, исключены как класс. В чем недостаток-то?
Как следует из текста, а теперь и из заголовка, в низкой производительности.VolCh
24.06.2016 17:28а высокая производительность на практике—единственная настоящая задача параллелизма
Смотря что означает «высокая». Для многих не особо важны абсолютные цифры на конкретной конфигурации, но важна практически неограниченная возможность горизонтального масштабирования.
0xd34df00d
28.06.2016 02:40+1Вычисляйте fib 100 после каждой строки вашего кода, будет очень хорошо масштабироваться.
nehaev
24.06.2016 18:13+2Как следует из текста, а теперь и из заголовка, в низкой производительности.
Низкая производительность — понятно. Но причем тогда параллелизм? До сих пор не понимаю смысл этого пункта. Особенно: «остерегайтесь людей, которые говорят о масштабируемости программ без учета абсолютной производительности» — что такое «абсолютная производительность», о чем здесь вообще речь?Bas1l
25.06.2016 03:02Ну, мол, зачем параллелить программы? Чтоб они быстро работали. И если ваша однопоточная программа на С работает в 1000 раз быстрее, чем однопоточная функциональная программа, то что толку от того, что вы распараллелите функциональную программу на, не знаю, 240 потоков (на кластере из 30 процессоров, в каждом по 8 ядер, к примеру). Даже если функциональная программа идеально масштабируется (что почти невероятно), все равно это будет в пять раз медленнее императивной программы. То есть легкость масштабирования—это круто, но нужно смотреть на абсолютную производительность, как и пишет автор.
VolCh
25.06.2016 07:00+1Если однопоточная программа обрабатывает 1000 запросов в секунду, функциональная 100 запросов в секунду, а нам нужно 100 000 запросов в секунду, то тут нужно считать.
nehaev
25.06.2016 12:22+1И если ваша однопоточная программа на С работает в 1000 раз быстрее, чем однопоточная функциональная программа
Не вижу логики. Если заменить «функциональная программа» на «другая императивная программа на С», арифметика как-то изменится? Если нет — причем тут ФП, в чем конкретно его недостаток? Или в императивных программах не может быть проблем с производительностью?Source
25.06.2016 18:15+2Логика очень простая, примерно такая:
Я умею работать с массивами, даже знаю пару алгоритмов на базе массивов. Где тут в вашем ФП массивы? Как нет? А что есть? А, списки… в моём любимом языке класс массива называется ArrayList, значит список — это типа массив такой. Сейчас как напрограммирую… Ой, а почему всё так тормозит? Как это нельзя к списку по индексу обращаться, вот же я обращаюсь и всё работает, тупит правда, но это потому что ФП медленный.
0xd34df00d
28.06.2016 02:42+1При том, что конкретно в хаскеле при параллельном исполнении, по крайней мере, через всякие там parMap, GC начинает жрать неоправданно много времени.
asdf87
26.06.2016 03:50Статья, которая называется «Недостатки чистого функционального программирования» в основном сводится к тому, что существуют некоторые задачи, которые не удобно решать в рамках ограничений, накладываемых функционально парадигмой.
Функциональные языки предназначены для работы с неизменяемым состоянием
А есть такой класс задач «работы с неизменяемым состоянием»? Интересно было бы узнать что туда относится?Idot
26.06.2016 05:50Такой класс задач традиционно решается Транслятором Формул, то есть ForTran'ом, который и быстрый и память не жрёт (а может работать на 640 kb памяти).
asdf87
26.06.2016 08:06Так мне сейчас не интересно как решается. Мне интересно какие задачи вы туда относите? Сами задачи, 2-3 примера привести можете?
VolCh
26.06.2016 09:29Глобально на современных популярных архитектурах неизменяемого состояния нет — работа программ заключается по факту в изменениях состояний оперативной памяти, регистров процессоров, файлов на дисках и т. п. Целью каждого выражения программы является привести компьютер в нужное состояние.
Но на различных уровнях абстракции неизменяемое состояние сплошь и рядом. Любая чистая функция, то есть функция, возвращаемый результат которой зависит исключительно от аргументов и аргументы она не меняет, на уровне клиента этой функции есть функция, не изменяющая состояние клиента. Да даже не функция, а банальное выражение a + b является выражением, не изменяющим состояние клиента. Пока он сам не решит изменить своё состояние, выполнив присваивание c = a + b. Грубо, к классу задач «работы с неизменяемым состоянием» относятся все задачи, которые генерируют новые значения на основании существующих, не изменяя существующих, все задачи в алгоритмах которых можно обойтись без переменных, без операций «присвоить» и «изменить», только «вернуть результат выражения».
nehaev
26.06.2016 12:48+1А есть такой класс задач «работы с неизменяемым состоянием»? Интересно было бы узнать что туда относится?
Задача — это что надо сделать. Использовать неизменяемое состояние — это то, как делать. Функциональные языки являются тьюринг-полными, поэтому на них можно решить ровно такое же множество задач, что и на императивных. Однако эффективность таких решений может быть разная.
Об этом уже шел разговор в этой ветке. Если коротко резюмировать сказанное там, я считаю что функциональный подход надо использовать по умолчанию для любых прикладных (не системных) задач, поскольку функциональные программы в среднем выигрывают по корректности и простоте и незначительно уступают по быстродействию.
Если вы из тех, кто думает, что неизменяемых данных не существует в природе, попробуйте прочитать этот комментарий, а еще лучше — самостоятельно написать что-нибудь в функциональном стиле, и очень скоро ваше мнение изменится.
snizovtsev
24.06.2016 14:28Императивная программа хорошо работает на конкретной среде выполнения традиционного компьютера, под который была написана. При этом работает максимально эффективно. Но иногда среда выполнения меняется или, более того, требуется чтобы пользователь сам ее задавал на свое усмотрение. Тогда приходит функциональное или логическое программирование. Мы просто повышаем уровень абстракции.
johhy13
24.06.2016 14:50-3Я думаю статья уже устарела (если не ошибаюсь 2010) — Хаскель как мне кажется уже другой, чего стоит stack -> с ним мучения почти кончились, а насчёт проблемы наложения функц парадигмы на императивную архитектуру железа (может FPGA ближе есть ли наработки в этом направлении?) с этим я согласен.
Bas1l
24.06.2016 14:51+1Статья про Хаскель, действительно, 2010 года (но многие примеры актуальны, я проверил). А эта статья буквально пару месяцев назад вышла, то есть очень свежая.
Idot
24.06.2016 14:51+3Однажды я предложил нескольким программистам на Хаскеле (и у некоторых из них были диссертации по этому языку) написать на нем эффективную параллельную быструю сортировку (quicksort)—и вот что из этого вышло.
С большим нетерпением жду перевода.
PsyHaSTe
29.06.2016 18:18+3Я все не читал, но концовку можно понять и без перевода:
This solution does run correctly on small inputs but increasing the problem size to 1,000,000 elements results in a stack overflow. Two attempts were made to diagnose this bug, here and here, but both turned out to be wrong. The bug is actually in the getElems function of the Haskell standard library which stack overflows on long arrays.
Surprisingly, more bug fixing seems to have culminated in the world's first parallel generic quicksort written in Haskell. Furthermore, the resulting Haskell solution is only around 55% slower than the equivalent F# solution. Note that this requires the latest GHC that was only released in recent weeks.
stargazr
24.06.2016 17:35+2Лично у меня интерес к ФП угас в тот момент, когда я запустил тот самый шокирующе короткий и понятный quicksort в одну строчку. Ну и над эпичная статьей habrahabr.ru/post/113001 про PDF в Haskell я тоже смеялся в голос (цитирую: «Сразу скажу, сам Haskell пригоден весьма неплохо, но вот, пробежавшись по hackage.haskell.org, я сразу обнаружил проблемы с библиотеками для работы с PDF, что и поставило крест на полноценной реализации.» — да, пригоден весьма неплохо! правда, вообще не работает, но с их-то уморительным квиксортом это и вправду сущий пустяк).
И, кстати, корректно ли сравнивать ФП и ООП, и называть последнее императивщиной?
Мне кажется, ООП — более высокий уровень абстракции, и оно может существовать и с ФП «под капотом» (как в Scala и OCaml).Cryvage
24.06.2016 19:54+1>И, кстати, корректно ли сравнивать ФП и ООП, и называть последнее императивщиной?
>Мне кажется, ООП — более высокий уровень абстракции
Уровень абстракции у ООП высок на этапе описания предметной области в виде структуры классов. Это, можно сказать, декларативная часть ООП. Описание классов и отношений между ними — декларативно, А код методов императивен. И работа с экземплярами классов происходит в императивном режиме. То есть сочетается сразу два уровня абстракции. Чем лучше мы отразим предметную область в терминах классов, тем более высокоуровневым будет наш код. То есть мы можем варьировать уровень абстракции. Возможно именно поэтому ООП пользуется таким успехом. Но, конечно же, у этого варьирования есть свои пределы. Именно поэтому, код в ОО стиле кажется избыточным в очень маленьких проектах — слишком много лишней декларативщины. И поэтому же, код становится слишком запутанным на очень больших проектах — мы не можем избежать императивного кода, а на большом проекте, накапливается его критическая масса. То есть абстракции, предоставляемой ОО подходом становится недостаточно. В этом плане функциональные элементы хорошо дополняют ОО язык, позволяя уменьшить количество императивного кода в некоторых местах. А те же лямбды помогают не засорять декларативную часть всякими служебными, одноразовыми методами, не имеющими никакого смысла в терминах предметной области. Но эти функциональные элементы не имеют особого отношения к чистому функциональному программированию. Ведь предметная область по прежнему остается описана в терминах классов, а основная часть логики по прежнему описывается императивно.
Но опять же, надо учитывать, что большинство применяемых ОО-языков не являются строго ОО-языками. Они все мультипарадигменные. Так уж получилось, что ОО-парадигма хорошо совмещается с элементами других парадигм. Наверное это вторая причина успешности ООП. Если подумать, из всех ОО-языков, которыми я хоть как-то владею, более-менее консервативным, в плане поддерживаемых парадигм, был только Delphi. При чем именно старый Delphi, в котором даже Generic'ов не было. И что-то я не заметил, чтобы он всем очень нравился. Так что, сколько бы не говорили о засилье ООП, на самом деле, самой популярной парадигмой была и остается мультипарадигменность. Потому что ни одна парадигма в отдельности не является достаточно универсальной, чтобы на ней было удобно делать абсолютно всё.stargazr
25.06.2016 00:40-1Вода это все, что вы написали, типичная для фп-сектантов.
Запутанный код в больших проектах, он запутанный относительно чего?
Как вам, кстати, относительно простые фп-программы, наподобие вышеприведенных «настоящих» квиксортов на хаскелле? Не кажутся запутанными? По сравнению с сишным-то аналогом?
Вам сугубо ооп-шные анонимные классы в java «лямбдами на стероидах» не кажутся? Да, синтаксис более громоздкий, но в целом-то?
Мне вот всегда казалось, что фп — это такая до смешного пафосная альтернатива для любителей процедурного программирования, не осиливших то же промышленное ооп. Наверное, это очень сильно сказано, но таково мое мнение.nehaev
25.06.2016 01:17+4Мне вот всегда казалось, что фп — это такая до смешного пафосная альтернатива для любителей процедурного программирования, не осиливших то же промышелнное ооп. Наверное, это очень сильно сказано, но таково мое мнение.
Ни в коей мере не посягая ни на столь глубокомысленное мнение, ни на ООП в целом, хочу заметить, что все-таки ФП и ООП — это очень разные вещи. Сферы их применения, как мне кажется, пересекаются только в части организации модульности и повторного использования кода. ФП говорит о «чистых» функциях и функциональной композиции, а ООП — о наследовании, инкапсуляции и полиморфизме.
ООП как Библия — есть конечное число канонических текстов (гоф, рефакторинг, чистый код и т.п.), но понимают их все по-разному. Одну и ту же задачу сто разных программистов «осиливших промышленное ООП» задизайнят по-разному. И все эти сто дизайнов будут неправильными и подлежащими рефакторингу с точки зрения сто первого программиста, который реально разбирается в такого рода задачах.
ФП предъявляет простые формальные требования, проверить которые может любой — это неизменяемость состояния и отсутствие побочных эффектов. Требования соблюдены — значит дизайн правильный. Если видение задачи изменилось — можно поменять отдельные функции в композиции или порядок их вызова. Подход гораздо проще.Source
25.06.2016 02:07+2ООП — о наследовании, инкапсуляции и полиморфизме.
Есть мнение, что это очень искаженное представление об ООП.
«OOP means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things» © A.Kay
Поэтому практически значимые отличия ООП и ФП:
1) (Им-)мутабельность данных. В ФП данные неизменяемы, что затрудняет реализацию некоторых привычных алгоритмов, основанных на in-place модификации данных. Зато упрощает сборку мусора и конкурентный доступ.
2) Работа с разделяемым состоянием. ООП равномерно размазывает его по всей программе, попутно позорно нарушая инкапсуляцию при помощи геттеров и сеттеров. А ФП изолирует работу с разделяемым состоянием. И вместо блокировок использует очереди сообщений или STM.Cryvage
25.06.2016 03:36+2>В ФП данные неизменяемы, что затрудняет реализацию некоторых привычных алгоритмов
Вот это, лично мне, кажется наиболее спорным моментом в ФП. Дело даже не в затруднении реализации привычных алгоритмов, а в том, что при добавлении элемента в список, мне нужно создать целый новый список. А если он большой? Это мне кажется настолько чудовищно неоптимальным, что все остальные плюсы просто меркнут на этом фоне. На бумаге концепция может и хороша, но мы то на компьютере работаем. И память у него не бесконечная. Да и аллоцируется она не мгновенно. Такое поведение выглядит просто как неуважение к вычислительной технике: «Вообще плевать на ее особенности, пусть пашет на износ, у нас тут всё иммутабельно». Ну нельзя же так.Idot
25.06.2016 05:51А как обстоит с этим в современном F#?
IIvana
25.06.2016 06:55+2Да точно также — то есть абсолютно не так. Товарищу «кажется», и на основе своих фантазий он делает глубокомысленные выводы. Разумеется никто новый список не копирует, просто новый элемент за пару ассемблерных инструкций консится в голову существующему списку и хранятся 2 ссылки — на старую голову и на новую, и это понятно вообще всем — даже сишникам, не читавшим Криса Окасаки и не слышавшим про персистентные чисто функциональные структуры данных.
qw1
25.06.2016 11:46Менять голову списка слишком канонично. А если надо поменять хвост? Или произвольный нужен доступ к массиву/списку?
Bas1l
25.06.2016 13:24Даже если компилятор всегда умеет делать эту оптимизацию (в чем я сомневаюсь), списки по-любому убивают cache locality, то есть вы никогда не закешируете список, в отличие от вектора (хоть данные вектора тоже будут лежать в куче), и это само по себе убьет производительность работы со списком.
Cryvage
25.06.2016 14:22+1Выводы сделаны не на основе фантазий, а по опыту работы, хотя бы с теми же строками в C#. Они там как раз иммутабельные. Скорость их работы на больших строках не просто низкая, она никакая.
Сравнить хотя бы два этих куска кода:
//1------------- string sResult = ""; DateTime sBegin = DateTime.Now; for(int i = 0; i < 200000; ++i){ sResult += "TEST" + "_"; } DateTime sEnd = DateTime.Now; Console.WriteLine(sEnd - sBegin); //2------------- DateTime sbBegin = DateTime.Now; StringBuilder sbResult = new StringBuilder(); for(int i = 0; i < 2000000; ++i){ sbResult.Append("TEST"); sbResult.Append("_"); } DateTime sbEnd = DateTime.Now; Console.WriteLine(sbEnd - sbBegin);
Обратите внимание, для StringBuilder я использовал не двести тысяч, а два миллиона итераций. Потому что на двухстах тысячах он выполняется вообще мгновенно. А на двух миллионах за пол-секунды.
А вот строку не советую проверять больше чем на двухстах тысячах. Она и на них выполняется целых полторы минуты.
Разница даже не в разы, а на несколько порядков. Зато строка иммутабельна.
Я не спорю, что какие-то вещи можно неплохо оптимизировать, особенно такие простые, как вставка в конец списка. Но как-то вот смотрю на иммутабельные строки, и они мне не нравятся. В шарпе у меня хотя бы есть неиммутабельный StringBuilder. А как выкручиваться, если всё вокруг будет иммутабельно, я лично не знаю.
З.Ы. Возможно я действительно чего-то не понимаю, просто я никогда не писал именно на строго функциональных языках. Хотя активно использую, и рекурсии, и замыкания. А уж про лямбды и упоминать смысла нет. Но вот именно с иммутабельностью у меня как-то не заладилось. Возможно все дело в том, что в нефункциональных языках она не оптимизирована. Непонятно только, зачем тогда ее вообще вводить, без оптимизации-то. Может расчет как раз на то, что в случае необходимости можно использовать неиммутабельный аналог?
Сейчас кстати посмотрел, в F# есть не только иммутабельные списки, но и мутабельные. То есть никакого фанатизма. Пожалуй изучу F# для общего развития.
Еще нашел статью, где человек как раз рассказывает про проблему с иммутабельными списками в F#. Как я и предполагал, там проблема с тем, что тратится много времени на аллокацию и сборку мусора:
Берегитесь иммутабльных списков в F# при параллельной обработке
Статья на английском. Если вкратце, то он заменил иммутабельные списки, мутабельными массивами, и вручную следил за иммутабельностью. Выигрыш в производительности получился в 20 раз.
Что самое интересное, он пишет, что именно иммутабельные списки на практике приводили к проблемам с синхронизацией в параллельной обработке. Хотя казалось бы, иммутабельность должна упрощать параллелизм.bohdan4ik
25.06.2016 17:35> Сравнить хотя бы два этих куска кода:
Которые не еквивалентны.
Вы забыли таки построить строку, которую делаете билдером. Сейчас у вас измеряются аллокации/копированя для новых строк (вариант 1) и добавление элемента в конец списка (вариант 2).Cryvage
25.06.2016 19:03+1Если вы имеете в виду sbResult.ToString(); перед DateTime sbEnd = DateTime.Now; то у меня в оригинальном тесте, который я запускал, так и есть. И результаты я сюда написал от того теста. Без этой строки 2 миллиона операций делается вообще за 8 сотых долей секунды. Просто пишу я с основного компьютера, а visual studio у меня на ноутбуке. И я не копировал код, а просто переписал основное вручную. Одну строку пропустил. Там у меня гораздо больше всякой воды понаписано: ввод/вывод, оформление всякое.
Полностью функция Mainstatic void Main ( string [ ] args ) { Console.WriteLine ( "Test string speed." ); Console.WriteLine ( "Input string part:" ); string part = Console.ReadLine ( ); Console.WriteLine ( "Input delimeter:" ); string delim = Console.ReadLine ( ); //string Console.WriteLine ( "Input count for string:" ); int sCount = 0; try { sCount = Int32.Parse ( Console.ReadLine ( ) ); } catch { } string result = ""; DateTime sBegin = DateTime.Now; Console.WriteLine ( "Test string start with "+sCount+" iteration... ["+sBegin+"]" ); for (int i = 0; i<sCount; ++i ) { result += part + delim; } DateTime sEnd = DateTime.Now; Console.WriteLine ( "Test string end. "+sCount+" iteration passed. [" + sEnd + "]" ); Console.WriteLine ( "Result string length:" ); Console.WriteLine ( result.Length ); Console.WriteLine ( "Time Passed:" + ( sEnd - sBegin ) ); //StringBuilder Console.WriteLine ( "Input count for builder. Input \"0\" if you want to keep current count("+sCount+"):" ); int bCount = 0; try { bCount = Int32.Parse ( Console.ReadLine ( ) ); } catch { } if ( bCount == 0 ) bCount = sCount; string bResult = ""; StringBuilder builder = new StringBuilder(); DateTime bBegin = DateTime.Now; Console.WriteLine ( "Test StringBuilder start with " + bCount + " iteration... [" + bBegin+"]" ); for ( int i = 0; i < bCount; ++i ) { builder.Append ( part ); builder.Append ( delim ); } bResult = builder.ToString ( ); DateTime bEnd = DateTime.Now; Console.WriteLine ( "Test StringBuilder end. " + bCount + " iteration passed. [" + bEnd + "]" ); Console.WriteLine ( "Builder Result length:" ); Console.WriteLine ( bResult.Length ); Console.WriteLine ( "Time Passed:" + ( bEnd - bBegin ) ); //Result Console.WriteLine ( ); Console.WriteLine ( "-------------------------------------------------" ); Console.WriteLine ( ); Console.WriteLine ( "Simple string time:" + ( sEnd - sBegin ) + "with " + sCount + " of iterations." ); Console.WriteLine ( "StringBuilder time:" + ( bEnd - bBegin ) + "with " + bCount + " of iterations." ); Console.WriteLine ( ); Console.WriteLine ( "Press any key" ); Console.ReadKey ( ); }Source
25.06.2016 17:50Странные у Вас примеры, честно говоря. Почему Вы противопоставляете StringBuilder и неизменяемые строки? StringBuilder — это просто удобная обёртка для работы с теми самыми неизменяемыми строками. Внутри он скорее всего хранит список этих самых строк, а при необходимости объединяет их в один проход. Другими словами, по сути StringBuilder такой же иммутабельный, как список в любом ФЯП.
На тему массивы vs списки — это ж вообще на уровне К.О. Если не понимать разницу между этими структурами данных, то очень легко писать тормозной код — это факт. По сути все проблемы от того, что некоторые программисты пытаются в силу инертности мышления работать с неизменяемыми структурами данных так, как-будто они изменяемые. Но из этого ничего хорошего не получится и как-то глупо в этом ФП обвинять, оно в инертности мышления не виновато )))
P.S. К.О. просит передать: Нельзя на базе списков реализовывать алгоритмы, предусматривающие доступ к элементам по индексу.Idot
25.06.2016 18:07Чем с точки зрения логики Массив из Констант принципиально кроме названия отличается от Неизменяемого Списка? И почему должна принципиально отличаться практическая реализация?
Source
25.06.2016 18:43+1По определению, массив — структура данных, оптимизированная для произвольного доступа по индексу. Список — структура данных, оптимизированная для последовательного перебора.
А с точки зрения логики, если бы реализация этих структур принципиально не отличалась, то достаточно было бы одного названия )
VolCh
26.06.2016 11:05С точки зрения логики принципиально они отличаются тем, что массив из констант изменяемый (в него можно добавлять новые константы и удалять/заменять уже имеющиеся), а набор элементов в списке зафиксирован (при этом сами значения элементов можно менять чисто формально). Если же вы имели в виду чем отличается неизменяемый массив констант от неизменяемого списка констант, то, как сказали выше — определением :) Реализация даже может быть одинаковой по своему формальному контракту, но скорость выполнения некоторых операций будет весьма неожиданной для разработчика. Обычно от массива ожидают константное время доступа к элементу по индексу, а от неизменяемого списка константное время доступа к первому и последнему элементу, операция же доступа к последнему элементу для массива либо вообще не определена, либо O(N) — стучимся по последовательно возрастающему номеру, пока не получим ошибку «выход за границы массива». Хак с хранением длины массива в клиенте естественно не рассматриваем.
Cryvage
25.06.2016 20:55+1В MSDN четко написано, что StringBuilder представляет собой мутабельную строку. Почему я не должен противопоставлять мутабельную и иммутабельную строку в контексте сравнения производительности мутабельных и иммутабельных типов данных?
Возможно название класса StringBuilder несколько сбивает с толку. Я не знаю почему Microsoft его так назвали, но это не «построитель строк», это именно строка, которую можно свободно модифицировать. В частности вставку можно делать в произвольное место:
string s = Console.ReadLine(); StringBuilder sb = new StringBuilder(); sb.Append ( s ); sb.Insert ( s.Length / 2, Console.ReadLine ( ) ); Console.WriteLine ( sb.ToString ( ) );
Внутри это не список строк, а список массивов char. Один такой массив может содержать символы из нескольких строк, добавленных Append'ом, в то же время, одна строка может размазаться на несколько массивов. Причем, как массивы, так и весь список — мутабельные. В частности, методы Append, Insert, Remove и т.д. возвращают не новый StringBuilder, а this. Так же, будь он иммутабельным, наверняка бы реализовывал интерфейс IClonable, т.к. было бы достаточно вернуть this. Собственно в классе String так и сделано. И вообще, если бы StringBuilder был иммутабельным, в нем бы не было смысла, т.к. он бы не отличался от обычного string'а. В MSDN есть ссылка на исходник (Reference Source), так что там все можно конкретно посмотреть.
Ну очень иммутабельноprivate void MakeRoom(int index, int count, out StringBuilder chunk, out int indexInChunk, bool doneMoveFollowingChars) { ... chunk = this; while (chunk.m_ChunkOffset > index) { chunk.m_ChunkOffset += count; chunk = chunk.m_ChunkPrevious; } indexInChunk = index - chunk.m_ChunkOffset; // Cool, we have some space in this block, and you don't have to copy much to get it, go ahead // and use it. This happens typically when you repeatedly insert small strings at a spot // (typically the absolute front) of the buffer. if (!doneMoveFollowingChars && chunk.m_ChunkLength <= DefaultCapacity * 2 && chunk.m_ChunkChars.Length - chunk.m_ChunkLength >= count) { for (int i = chunk.m_ChunkLength; i > indexInChunk; ) { --i; chunk.m_ChunkChars[i + count] = chunk.m_ChunkChars[i]; } chunk.m_ChunkLength += count; return; } ... }Source
26.06.2016 01:18Ok, мутабельный, так мутабельный… Но это не отменяет того факта, что Вы сравниваете 2 совершенно разных алгоритма и удивляетесь, получив вполне ожидаемый результат. Чтобы сравнение было уместным, возьмите LinkedList добавьте в него строки через AddLast, а потом превратите в строку с помощью Join (желательно найти тот, который без лямбд). Хоть StringBuilder работает не так, но это по крайней мере алгоритмы одной сложности.
IIvana
25.06.2016 07:03+1ЗЫ это если вообще список хоть частично присутствует в памяти в вычисленном виде, а то Хаскель ленивый язык —
пока не пнешь — не полетитвообще старается списки без нужды в памяти не разворачивать а при свертках по ним вообще все в цикл оптимизирует, воспринимая их не как структуру данных а как структуру управления потоком выполнения.qw1
25.06.2016 11:53+1И эта ленивость может стать такими граблями…
Грубо говоря, если императивная программа делая в циклеx:=x+1, полностью помещается в регистры процессора и миллион итераций для неё ничто, то некорректно написанная хаскель-программа может гонять огромный memory-трафик, конструируя цепочки выражений x0+1+1+1+...+1.
Зато, если если результат не пригодится, можно не выполнять сложения. Толку от этого, если выполнить честное сложение на порядки быстрее, чем разводить такие деревья в памяти.
Пример утрирован, но общий смысл — программист на Хаскель не может быть спокоен за оптимальность своих сложных алгоритмов без постоянного профайлинга, ленивая хитрая машина может подставить в любой момент.Source
25.06.2016 17:54Граблями может стать что угодно. Например, GC или ручное управление памятью. И вот уже получается, что языков без граблей не существует )))
qw1
25.06.2016 20:01+1Мне это напоминает ситуацию с Прологом. Адепты говорят: просто запишите все ограничения, и машина сама разберётся. А на практике, без хинтов вывода (отсечений) — никуда, и есть случаи, когда перестановкой двух соседних правил вывод ускоряется в миллион раз. А вот в императивных языках — как написал, так и работает.
Source
26.06.2016 01:38А вот в императивных языках — как написал, так и работает.
Вы уверены, что это в императивных языках, а не в Ваших фантазиях? )
Откуда ж берутся null pointer exception, GIL и ещё 100500 подводных камней, когда работает совсем не так, как написал… Проблемы везде есть, и в императивных языках их совсем не мало. Но можно найти проблемы и в Прологе и в Хаскеле, тут никто не спорит. А если пытаться на них в императивном стиле программировать, то вообще феерический ппц будет, о чём и статья.qw1
26.06.2016 10:34GIL можно отнести к неведомой магии (как пример выше с кривой ленивостью), а вот NPE не надо сюда мешать.
Если возникла NPE, это определённо ошибка алгоритма, а не эффекты среды выполнения, которые сложно просчитать заранее.Source
26.06.2016 12:07Так кривая ленивость — это тоже ошибка алгоритма, просто другого плана. Неведомой магии вообще в программировании не бывает, бывают неочевидные особенности )
qw1
26.06.2016 12:13+2Не согласен. Тормоза GC, переполнение стека из-за недооценки глубины рекурсии, тормоза из-за кривой ленивости могут возникнуть, даже когда алгоритм записан математически правильно, но среда выполнения упёрлась в ограничения реализации.
NPE (в случае, когда программер запуталься в коде и что-то не проверил) — это математически некорректный алгоритм.Source
27.06.2016 00:29-1переполнение стека из-за недооценки глубины рекурсии
ну вот, ещё одну проблему императивного подхода вспомнили, которая при функциональном подходе отсутствует )))
Программирование — это не математика, поэтому математически корректный алгоритм, который во что-то упёрся, с точки зрения программирования такой же ошибочный, как с NPE.qw1
27.06.2016 00:40+1В чём разница проблемы переполнения стека в си например и в ФП-языках?
Хвостовая рекурсия оптимизируется более-менее одинаково, а прочая рекурсия ограничена стеком везде.Source
27.06.2016 01:20Я про языки не писал… В функциональном подходе традиционно используется только хвостовая рекурсия, соответственно переполнение стека исключено.
Насчёт ограничений и языков… у всех по разному, у Erlang, например, глубина нехвостовой рекурсии ограничена только объёмом RAM.qw1
27.06.2016 01:41В функциональном подходе традиционно используется только хвостовая рекурсия
Т.е. традиционно отказываемся от рекурсии, например, на задаче обхода графа в глубину (получения списка файлов в подкаталогах)? Не слышал про такой запрет.
у Erlang, например, глубина нехвостовой рекурсии ограничена только объёмом RAM
Ну а для c++ (x64) стек можно настроить на 100500 терабайт и глубина будет ограничена размером HDD под своп.
Antervis
27.06.2016 05:49+1едва ли стек станет больше от того, что используется фп. А если перекладывать то, что можно разместить на стеке, в кучу, получается уж очень медленный ослик.
VolCh
27.06.2016 11:07Не путайте стек как структуру данных и аппаратный стек конкретной архитектуры, которого вообще может не быть в принципе, а может быть, например, два — отдельные для вызовов и данных.
Cryvage
26.06.2016 01:59+2Мне это тоже очень не нравилось, когда изучал его в универе. По задумке, должна быть сильная абстракция, а на практике, приходится держать в голове алгоритм работы машины вывода. То же самое можно сказать и про SQL. Чтобы писать эффективные запросы, надо знать, как именно СУБД этот запрос выполняет. В такие моменты, абстракция не помогает, а только мешает. Мешает понять, как именно выполняется твой код. То же самое и в языках со сборщиком мусора. В определенных моментах, чтобы оптимизировать программу, надо понимать логику его работы. На самом деле эта проблема носит фундаментальный характер, и лежит она далеко за пределами программирования. С такой же проблемой сталкиваются летчики, при взаимодействии с автопилотом. Они подолгу учатся с ним правильно обращаться, изучают его особенности. Поставили автопилот в автомобиль, и там появились те же проблемы. Во всех системах, где присутствует машина, которая претендует на то, что она сама с чем-то разберется, эта самая машина может стать узким местом. И чем больше от этой машины зависит, тем чаще будут проявляться эти узкие места, и тем более узкими они могут быть.
VolCh
26.06.2016 11:19В императивных языках совсем не «как написал, так и работает». Работает обычно так, как написали разработчики трансляторов, библиотек и т. д. Например, передавая параметр по ссылке/указателю в функцию/процедуру/метод, можно только надеяться, что они не будут его изменять.
qw1
26.06.2016 12:09+1Разве что разработчики библиотеки — вредители ))
Я бы хотел примеров разрушения переданных по ссылке параметров.
Какие грабли оказались для вас самыми больными и неочевидными.
Соглашаясь с теоретической возможностью, в своей практике ничего не могу вспомнить.VolCh
26.06.2016 13:58«Разрушение» не совсем корректное слово, скорее неожидаемые побочные эффекты. Например, из недавнего, вызов метода получения (судя по названию) некоего состояния инстанса записи одной из реализаций ActiveRecord, внутри которого мало что проходило изменение состояния этого инстанса, так и ещё и сохранение его в базу. Причём нельзя сказать, что сознательный вредитель автор — после анализа истории коммитов стало понятно, что такое поведение результат рефакторинга, что в нескольких местах постоянно подряд вызывалось три метода: получение состояния, его изменения, и его сохранения. Вполне логичный (для ActiveRecord) рефакторинг. Единственное, что не создал новый метод или, хотя бы, не переименовал старый получения состояния.
qw1
26.06.2016 14:39Ха, можно подумать ФП язык спасёт от этого. Запись в базу — побочный эффект, так или иначе он появится где-то в функциях, написанных тем же разработчиком.
VolCh
26.06.2016 14:46Функциональный язык должен позволять визуально отличить вызов чистой функции от вызова функции с побочным эффектом.
qw1
26.06.2016 17:18Lisp:
(print 10)
Визуально отличен вывод в консоль?VolCh
26.06.2016 17:40Тут нет побочного эффекта на состояние программы.
qw1
26.06.2016 18:51Сохранение в базу тоже может не влиять на память ))
qw1
26.06.2016 19:13Тут даже большее поле для граблей. Если в ОО-языке я сказал объекту «SaveToDB», нормально написаный метод Save обновит состояние и я всегда буду знать, сохранён ли объект.
А в ФП-парадигме я могу корректно сказатьx = x.SaveToDB, или простоx.SaveToDBи потеряю факт сохранения в базу (потом ищи этот баг), или ещё лучше —у = x.SaveToDB, у получится 2 объекта: один сохранённый, другой нет, а по факту получу расхождение модели с реальным миром, которое сложнее минимизировать.VolCh
27.06.2016 11:12В ФП-парадигме вы не можете корректно сказать "=" как «присвоить значение переменной/свойству»
qw1
27.06.2016 13:35Это и проблема. В программе не может быть одного актуального объекта, при изменении которого все модули, которые получили ссылки на него, видят новое состояние
VolCh
27.06.2016 17:43Это не проблема, а решение проблемы неконтролируемых изменений, когда любой модуль из получивших ссылки на объект, может его изменить. И нередко записать третье состояние поверх второго, которое будет утрачено. А уведомление других модулей о неактуальности переданного им когда-то значения решается другими способами.
VolCh
27.06.2016 11:10Состояние приложения не ограничивается оперативной памятью. Если приложение пишет в базу, а потом само же из неё читает, проще говоря, использует базу для персистентности своих данных, «эмулируя» энергонезависимое террабайтовое ОЗУ, то база тоже часть состояния приложения.
qw1
27.06.2016 13:37Только ФП-среда про это не знает. Если закоммитил в базу, конфликт разрешается в пользу какой-то одной транзакции, а не множится состояние БД.
VolCh
27.06.2016 18:02О чём она не знает? О записи, которую произвела?
qw1
27.06.2016 23:13То, что обычно вся «чистота» внутри рантайма ФП. Я не видел систем, где бы чистота была в комплексе программа + БД + файловая система.
VolCh
28.06.2016 13:33Я такие делал. Глобальный лок на базу и каталог с данными, чтобы минимизировать вероятность изменений извне программы, вернее даже извне её экземпляра.
qw1
28.06.2016 21:32Как это, у вас существовало состояние s1, в котором «select Name from Objects where Id=1» выдаёт «A» и состояние s2, в котором тот же select выдаёт «B»? Любая СУБД скажет 'update conflicts with concurrent update', даже не дожидаясь коммита.
VolCh
28.06.2016 23:01Не так, к состоянию s1 применялась функция, которая возвращала состояние s2, а состояние s1 более не использовалось.
qw1
29.06.2016 22:03Так работает императивный код ))
В момент времени t1 имеем состояние s1, делается шаг (например, в дебагере) — получаем t2 и s2.VolCh
30.06.2016 06:31+1Я уже не раз в этой и «соседних» статьях говорил, что принципиальная разница функционального и императивного программирования лишь в точки зрения. Исполняем мы команду, меняющую состояние, или применяем функцию к старому состоянию и получаем новое.
gaki
27.06.2016 07:49> А вот в императивных языках — как написал, так и работает.
Это, всё же, преувеличение. Branch prediction, out of order execution и прочий false sharing, конечно, не замедлят код в миллион раз, но всё же вполне имеют место быть. Как и соответствующие хинты для компилятора (например, restrict, __builtin_expect).
Source
25.06.2016 10:14Дело даже не в затруднении реализации привычных алгоритмов, а в том, что при добавлении элемента в список, мне нужно создать целый новый список. А если он большой?
На практике это очень легко решается — хвост списка всегда переиспользуется под капотом, он же неизменяемый. Т.е. когда вы добавляете элемент в начало списка — это равнозначно смене указателя на голову списка, никакого копирования данных не происходит.
Cryvage
25.06.2016 04:44+1>Вода это все, что вы написали, типичная для фп-сектантов.
Это я-то фп-сектант? Я же вам про ООП написал и лишь слегка упомянул функциональные элементы. Я это только так и использую обычно. Ну а то что вода, ну может и вода. Я же в общих чертах писал, без конкретики. Так что можете считать это водой, и даже диванными рассуждениями. Я ведь сидел на диване, когда это писал.
>Запутанный код в больших проектах, он запутанный относительно чего?
Относительно не запутанного кода в маленьких проектах. В коде появляется слишком много взаимосвязей, которые не отражаются диаграммой классов. Тяжело потом разобраться. Но с другой стороны, я не уверен, что можно сделать крупный проект простым. Основная проблема в том, что крупный проект начинается с маленького, и растет постепенно. И изначально заложенная архитектура почти никогда не может предсказать дальнейшего развития. То есть банальная болезнь роста. Опять же, я не утверждаю, что это проблема исключительно ООП. Это проблема людей. А ООП здесь просто не может нам помочь. Но я не думаю, что и ФП поможет. Знал бы, как эту проблему решить, жил бы в Сочи.
>Как вам, кстати, относительно простые фп-программы, наподобие вышеприведенных «настоящих» квиксортов на хаскелле? Не кажутся запутанными? По сравнению с сишным-то аналогом?
Всегда можно найти пример, который легко реализуется одним инструментом, и сложно — другим. Но вообще синтаксис у ФП языков мне не очень нравится. Просто это дело привычки. Мне и Си-шный синтаксис не нравится. Слишком много скобочек. Но это уже вкусовщина.
>Вам сугубо ооп-шные анонимные классы в java «лямбдами на стероидах» не кажутся?
Лямбда это анонимный метод. А анонимный класс — это, как ни странно, анонимный класс. Ну да, у них есть общее, то что они оба анонимные и записываются inline, но это разные сущности. Вообще, если проводить параллели между ФП и ООП, то наиболее близкими сущностями из двух парадигм мне кажутся объекты и замыкания. Близость тут условная конечно, но замыкания имеют состояние, как и объекты.
>Мне вот всегда казалось, что фп — это такая до смешного пафосная альтернатива для любителей процедурного программирования
А ООП это тогда что? Структуры с функциями в качестве полей? А человек это до смешного пафосная альтернатива обезьяне. Так про что угодно можно сказать. Все же критика должна быть конструктивной. Ну можно наверное считать, что функциональное программирование это декларативная форма процедурного программирования. Но что это меняет? Лично мне не кажется, что функциональное программирование намного проще, чем ООП. По мне, так даже сложнее в чем-то. Но каким-нибудь математикам, наверное проще въехать в ФП. И зачастую им больше ничего и не надо для их деятельности, особенно ООП. У них другие задачи. Вы серьезно считаете, что люди, которые пишут диссертации по хаскелю, просто не осилили джаву?qw1
25.06.2016 12:14-1Лямбда это анонимный метод
Нет, это конструкция, пришедшая из лиспа(lambda (x y) (+ x y)). Она может захватывать переменные и превращаться в замыкание. В последнем случае она эмулируется анонимным классом, который хранит захваченные переменные. Либо эмулируется анонимной ф-цией, если доп. память не нужна.
но замыкания имеют состояние, как и объекты
У замыканий такое же неизменяемое состояние, как и у любых других конструкций ФП.
Одно замечание — языки, в которых замыкания добавлены поверх ООП (c++ и c#) могут захватывать не значение, а ссылку на переменную и тогда покажется, что состояние замыкания можно менять, меняя переменную. На самом деле, захваченные значения (адрес ссылки) не меняются, это побочные эффекты не чистых ФП-языков.
stargazr
26.06.2016 01:37Вы опять выдали стену бессмысленного текста. Вы, случайно, преподаванием не занимаетесь? Зачем вы мне рассказываете про мультипарадигменность в современных языках, про то, что маленькие проекты по мере роста становятся большими, про подобранные примеры — вы думаете, я всего этого не знаю, не понимаю и не использую? Ваш менторский тон раздражает.
С учетом написанного в статье, сравнивать ФП и ООП с человеком и обезьяной соответственно — провокация покрепче моей, знаете ли! А если уж сравнивать ФП с процедурным, то это как шимпанзе и кошка — шимпанзе (ФП) гораздо выше по своему развитию, да, и может творить просто удивительные вещи, да и человек почти (ну вроде), но только толку-то от его забавных кривляний на практике все равно кот наплакал :)
Ну и про лямбду и классы. С чего вы решили, что если это разные сущности, их нельзя сравнить? И то, и другое содержит некие действия и данные, с которыми будет работать сущность, которой мы их передаем. Только вот объект класса может, например, хранить состояние, и иметь несколько точек входа (методов), а лямбда — лишь одну-единственную точку входа. Там еще есть наследование, интерфейсы и пр., но вы же сами в состоянии про это додумать, правда?
f0rk
28.06.2016 15:02+1Мне кажется, ООП — более высокий уровень абстракции, и оно может существовать и с ФП «под капотом» (как в Scala и OCaml).
Мне кажется, ФП — более высокий уровень абстракции, и оно может существовать и с ООП «под капотом» (как в Scala и OCaml).
Только вот объект класса может, например, хранить состояние, и иметь несколько точек входа (методов), а лямбда — лишь одну-единственную точку входа.
function createObject(a, b) { function addAB() { return a + b; } function mulAB() { return a * b; } function aNTimes(n) { return a * n; } return function dispatch(method) { switch (true) { case method === 'addAB': return addAB; case method === 'mulAB': return mulAB; case method === 'aNTimes': return aNTimes; default: throw new Error('Method not found'); } } } var o = createObject(4,5); o('addAB')(); // => 9 o('mulAB')(); // => 20 o('aNTimes')(3); // => 12
Там еще есть наследование, интерфейсы и пр., но вы же сами в состоянии про это додумать, правда?stargazr
28.06.2016 19:52+1У вас ООП в зачаточном состоянии (createObject) реализовано посредством более низкоуровневых и примитивных сущностей (функций и замыканий). О чем, собственно, я и говорил. Где тут ООП под капотом ФП? Наоборот все. (btw вызов «методов» посредством строк — тот еще номер. Вы б хоть extend() тогда уж запостили.)
Но я все-таки надеюсь увидеть пример ООП под капотом ФП. Попробуйте еще.Source
28.06.2016 22:57stargazr
28.06.2016 23:54Ну объекты в обоих случаях абстракции более высокого уровня, чем функции. Вы не понимаете, о чем спор, и настойчиво суете мне примеры ооп в функциональных языках. Давайте еще скаловские акторы вспомним в следующем комментарии?
(Оставлю в стороне все эти срывы покровов, вытаскивания на свет божий преданий старины глубокой и прочую борьбу с ветряными мельницами. Да, все эти тупые джависты, рубисты и прочие недочеловеки просто дураки и не лечатся, и наплевать, что в 99.99% случаев ООП — это-таки наследование-инкапсуляция-полиморфизм, — сейчас мы откроем глаза миру на его вопиющее невежество!!1 Правда, в фпшных скалах и окамлах то же самое почти, вот парадокс.)Source
29.06.2016 00:26А Вы сами то понимаете о чём спор?
Вы передёрнули факты «Мне кажется, ООП — более высокий уровень абстракции, и оно может существовать и с ФП «под капотом»», Вас протроллили в ответ зеркальным передёргиванием «Мне кажется, ФП — более высокий уровень абстракции, и оно может существовать и с ООП «под капотом»».
Теперь Вы скатились до истерики функции vs объекты, что совсем не то же самое, что ФП vs ООП, надеюсь, хоть это очевидный факт.
Ну а истина как всегда где-то посередине, ФП не конфликтует с ООП, они вообще ортогональны и взаимодополняют друг друга.
Зачем вспоминать акторы Scala, я не понял, это ведь частичная калька с Erlang. И да, ООП на базе акторов — это ООП в рамках ФП, которое Вы так жаждали увидеть.
в 99.99% случаев ООП — это-таки наследование-инкапсуляция-полиморфизм
ну, если Вам легче живётся с этой аффирмацией, то, пожалуйста, никто у Вас её не отнимаетAntervis
29.06.2016 05:59наверное, не совсем «ортогональны», если «дополняют друг друга»? 90% задач можно сделать и на том, и на другом. А остальные 10% тоже, только если пришивать ухо вместо хвоста ослику Иа
Source
29.06.2016 12:48+1не совсем «ортогональны», если «дополняют друг друга»?
Ну, вот была у Вас одна ось X и линейное мышление, а потом Вы добавили ортогональную ось Y, на которой тоже можно линейно мыслить. Но если Вы знаете про обе оси (дополнили одну другой), то у вас уже есть плоскость, а не линия. Так понятнее?
Чем больше парадигм Вы освоите, тем объёмнее станет мышление, а пытаясь кому-то доказать, что одной парадигмы достаточно для всего — Вы добровольно надеваете себе шоры.
stargazr
29.06.2016 12:53-2Вы успокойтесь, валерьяночки выпейте пойдите, перечитайте мое исходное сообщение внимательно, вникните. Просто вы что-то там себе понапридумывали, чего я вообще не писал, обиделись, и теперь доказываете, как я фатально заблуждаюсь.
Да, хардкорное (да и не-хардкорное) ФП непопулярно, а ООП — это наследование-инкапсуляция-полиморфизм, по статистике. Я не вижу в этом трагедии.Source
29.06.2016 14:07+1Ахах, чего ж Вы так нервничаете, сами просили ООП в рамках ФП посмотреть, а как увидели, так сразу за лозунги уровня первого курса )))
Во-первых «наследование-инкапсуляция-полиморфизм» никогда не было определением ООП. Во-вторых, все бенефиты этой триады не зависят от объектно-ориентированности языка.
Наследование прекрасно заменяется композицией и примесями, что и в рамках классового ООП давно и активно применяется для борьбы с антипаттернами наследования. Инкапсуляция по факту только с иммутабельными данными возможна, пока Вы можете менять аргументы метода по ссылке, можно только притворяться, что есть инкапсуляция. Полиморфизм спокойно реализуется через duck-typing и typespecs (аля интерфейсы), в том числе и во многих ООЯП.
И да, Вы упорно путаете ФП и ФЯП. Поддержка ФП в какой-то мере уже включена почти во все популярные нефунциональные языки программирования. И с каждым годом всё больше языков расширяют эту поддержку… посмотрите хотя бы на C# и Java, на эти оплоты ООП, первый уже давно насквозь пронизан ФП, а второй окончательно признал популярность ФП 2 года назад.
P.S. Ну а на тему quicksort, это алгоритм на базе мутабельного массива. Имхо, совершенно очедичный факт, что он не может быть реализован в функциональном стиле вообще никак. Те эмуляции, которые Вы видели, никакого отношения к реализации quicksort не имеют.stargazr
29.06.2016 16:37Не имеет значения. Я даже больше скажу — есть такой язык, называется Haxe — так вот там фп-фишек еще больше, есть сопоставление с образцом, например. Но это ничуть не меняет дело, и большинство проектов пишутся в императивно-оопшном стиле. Так же, как и на упомянутых вами языках.
Вы разве не поняли, что я в верхнем посте именно это и имел в виду касательно quicksort?Source
29.06.2016 21:30+2Но это ничуть не меняет дело, и большинство проектов пишутся в императивно-оопшном стиле.
К чему эти обобщения на всю индустрию на основе своего личного опыта? На мой взгляд выбор между ФП и ООП — это совершенно бесполезное словоблудие (аля эта статья) вне контекста конкретной области программирования (а в идеале конкретного проекта). Ни то, ни другое не является лучшим выбором для 100% задач.
Вы разве не поняли, что я в верхнем посте именно это и имел в виду касательно quicksort?
Так а в чём смысл обсуждать quicksort в контексте ФП? То, что алгоритмы, основанные на in-place модификации данных, нельзя реализовать в рамках ФП, по-моему, вполне очевидно. Не понимаю, чем это Вас разочаровало…stargazr
29.06.2016 23:10-2Не надо мне тут про индустрию. Зайдите на сайты с вакансиями, если не верите. HH, superjob, stackoverflow careers. Или на гитхаб. Тот же Spark, написанный на Scala — какой файл ни открой, код от Java с двух шагов не отличить: try, for, while, if, классы, методы, «поганая императивщина».
Я не знаю, зачем вы мне про quicksort рассказываете, причем то, о чем я и сам писал до этого.
В этой статье полно конкретики, а не словоблудия.
Словоблудие — это вот, например: https://habrahabr.ru/post/190492/. Очень прикольненько так, молодежно, мемчиками пересыпать только забыли.stargazr
30.06.2016 23:37Ну вы бы хоть пояснили, за что минусуете.
Вру все, наверное, да? ;)
Что вам careers-то показал?
nehaev
24.06.2016 18:45+3В большинстве пунктов автор пытается критиковать функциональные языки с точки зрения быстродействия. Однако,
Корректность лучше быстроты. Простота лучше сложности. Ясность лучше хитроумия. Безопасность лучше ненадежности
— Г. Саттер, А. Александреску. Стандарты программирования на С++
Благодаря чистоте функций и неизменяемости состояний, в ФП легче доказать корректность решения. Само по себе решение в функциональном стиле выглядит, как правило, проще — за очевидным исключением случаев применения чистого функционального подхода для решения изначально императивных задач.Idot
24.06.2016 19:19Ну, Delphi — тоже не быстрый. Но, для RAD (Rapid Applications Development) — т.е. для быстрого написания безошибочно работающего ясного кода он очень хорош.
А при каком применении, по-Вашему мнению, ФП имеет явные преимущества?nehaev
24.06.2016 23:37+1ФП замечательно работает там, где нет чувстительных для него органичений на быстродействие и память. Т.е. писать на нем прошивки, операционные системы, драйвера и прочий низкоуровневый софт не рекомендуется.
В прикладном программировании ФП надо применять по умолчанию:
— если объявляем переменную — делаем ее immutable (если ЯП не позволяет указать это явно, просто берем за правило присваивать значение переменной ровно один раз),
— используем только immutable типы данных (если в библиотеках нет immutable-версии нужного типа, берем за правило создавать новый экземпляр на каждое изменение),
— если пишем функцию — в ней не должно быть побочных эффектов.
И отходить от этих правил только в случае крайней необходимости.
Не во всех современных ЯП удобно и вообще имеет смысл следовать этим правилам, поэтому для применения ФП важна не только задача, но и язык, на котором мы собираемся ее решать. Мне нравится подход Scala, где функциональные стиль поощряется, но не навязывается.Idot
25.06.2016 18:26+2используем только immutable типы данных (если в библиотеках нет immutable-версии нужного типа, берем за правило создавать новый экземпляр на каждое изменение)
И зачем такой откровенный мазохизм? На практике практически все данные — изменяемые. А если нужно посчитать один раз какую-нибудь сложную формулу, то необходимо и достаточно использовать ForTran. А "правило создавать новый экземпляр на каждое изменение" — это вообще пухнущий на глазах песец, который с каждым изменением ЖРЁТ память. С Ваших слов получается, что ФП следует применять вместо ForTran'а, без внятных объяснений почему.
PS не получил ответа на вопрос: при каком применении, по-Вашему мнению, ФП имеет явные преимущества?
Переформулирую вопрос: в каких случаях на практике имеет смысл применять ФП? В каких случаях ФП имеет явное преимущество?nehaev
26.06.2016 00:02+1И зачем такой откровенный мазохизм? На практике практически все данные — изменяемые.
Это с философской точки зрения все меняется, и дао подобен реке. А на практике, если внимательно посмотреть на каждую функцию (мы говорим про функциональный подход), окажется, что никакого мазохизма даже близко, в отличие от императивного кода. Входные параметры функции — не меняются в процессе ее работы (во многих императивных языках это тоже стандартная практика). Результат функции получается в процессе обработки входных параметров, но он получается один раз, и не меняется после этого. И даже если результат это какая-то структура, он конструируется весь сразу, одним ударом. Если структура сложная, могут быть промежуточные результаты, из которых уже конструируется конечный, но эти промежуточные результаты также получаются один раз и не меняются после этого.
Есть в императивном программировании такие структуры, с которыми реально удобно работать, именно постоянно их изменяя (коллекции, билдеры). В ФП есть их неизменяемые аналоги, которые при изменении не клонируют все с нуля, а переиспользуют общие данные из предыдущего экземпляра.Cryvage
26.06.2016 00:32Почему просто не признать очевидную вещь: есть сущности, которые удобней не изменять, а есть те, которые удобно изменять. Следовательно должны быть, как изменяемые, так и неизменяемые типы данных. В идеале, чтобы immutable — вообще было атрибутом, который можно применить к любому типу.
VolCh
26.06.2016 11:35В идеале, mutable должно быть атрибутом который можно применить и значение сможет изменить его владелец. А передача владения только явная самим владельцем. Может быть имеет смысл сделать shared mutable для данных, которые может изменить кто угодно и когда угодно (хоть на полтакте исполнения самой простой операции).
Idot
25.06.2016 18:35Если кратко: из Вашего ответа лишь следует, что ФП жрёт память, но нет ни одного аргумента про то в каких случаях это оправдано.
Хотя я спрашивал:
А при каком применении, по-Вашему мнению, ФП имеет явные преимущества?
, а то что ФП — жрёт память, я уже слышал от противников ФП. Я же хочу услышать от Вас ответ, в каких случаях использование ФП оправданно.Source
26.06.2016 01:52Отвечу вместо nehaev… Использование ФП на 100% оправдано, когда вам нужна высококонкурентная программа с высокой степенью надежности и отказоустойчивости.
В таком случае вы либо будете использовать готовый ФЯП, либо переизобретёте большую часть ФП на своём любимом ЯП, либо будете страдать на каждом углу от race conditions, dead locks, гейзенбагов и прочих весёлых вещей.Idot
26.06.2016 05:55Высококонкуреннтая — это с параллелизмом?
А ФП языки работают на CUDA или OpenCL?Source
26.06.2016 12:49Вообще-то, конкурентность и параллелизм — это совсем разные понятия. Параллелизм тоже можно устроить на ФП, но я это не имел в виду в начальном сообщении.
Про программирование на GPU я Вам не подскажу, т.к. не интересуюсь этой темой. Если Вы хотели подколоть на тему, что для параллелизма есть инструменты получше, то вспомнили бы лучше Lambda- и Kappa-архитектуры. А то параллелизм числовых данных на GPU — это насколько узкая тема, что кроме учёных и любителей криптовалют, имхо, никому не интересна.Idot
26.06.2016 13:06Разве ФП не для научных расчётов?
(просто из того, что данные в ФП считаются неизменяемыми списками, у меня сложилось именно такое представление о применении)Source
26.06.2016 13:48Я не улавливаю Вашей логики, честно говоря. В научных расчётах много чего используется, в том числе и ФП. Только какой от этого практический толк, если, допустим, Вы не занимаетесь научными расчётами?
Мне вот интереснее применение ФП для таких проектов как WhatsApp, Twitter и т.д.
Bas1l
26.06.2016 14:20+1Для нересурсоемких научных расчетов нынче питон, еще matlab и R. Для ресурсоемких—С и С++. Функциональные языки в науке, по моему опыту, не используются никак.
qw1
26.06.2016 14:41Как же, лисп — классический язык для экспертных систем и символьных вычислений (упрощение выражений и т.п.).
Source
26.06.2016 14:43Спрашивали про ФП, а не про языки… так что если уж по-честному, R, Wolfram Language и даже Python вполне активно используют ФП.
Antervis
27.06.2016 05:57берем за правило создавать новый экземпляр на каждое изменение
например, создавать копию гигабайтного массива на каждое изменение элемента по отдельному индексу?Idot
27.06.2016 07:13-1На сервере! ФП тут предложили использовать на сервере! Берём базу обычную в 10 гигабайт, с несколькими миллионами записей, и будем каждое изменение миллионов записей создавать по новому экземпляру!
Saffron
27.06.2016 07:24+1Не надо демонстрировать своё невежество всему интернету. Ознакомьтесь с трудом Окасаки «Чисто функциональные структуры данных», там всё популярно расписано. Можно строить гигабайтные структуры, у них даже асимптотическая сложность совпадает с классическими. Только, конечно, коэффициент в разы больше, так что на практике чистые базы данных не встречаются, база данных всё же требует максимум возможной оптимизации.
Idot
27.06.2016 07:28Ну, так расскажите! Напишите статью с опровержением критики про «Чисто функциональные структуры данных». Все Вам будут только благодарны.
Saffron
28.06.2016 04:04Сформулируйте чёткое утверждение. И если оно ложное, я предоставлю доказательства обратное, если верное — соглашусь. Пока вы лишь задали риторический вопрос.
Idot
28.06.2016 07:26?!
Вы посоветовали ознакомиться с трудом Окасаки «Чисто функциональные структуры данных», где всё популярно расписано. Я выразил мысль, что было бы хорошо, если бы Вы написали об этом статью.Saffron
28.06.2016 15:01+1Вы хотите, чтобы я опроверг критику. Собственно прошу предоставить критику для опровержения. В таком случае я смогу предметно объяснить, в чём недоразумение. Повторять классиков целиком не вижу поводов. Есть и сама книга и десятки статей, разбирающие отдельные моменты. Зачем повторять уже существующую информацию?
qw1
27.06.2016 08:41Тут важно, чтобы старые версии данных не разрушались (особенно в банковской сфере и т.п.).
Любая продвинутая СУБД имеет журнал транзакций и режим, когда данные только добавляются.
И можно открутить БД назад к любому состоянию.
В СУБД попроще есть версии записей, одна из которых актуальна, остальные — мусор.
Так что такой подход давно работает с БД.Idot
27.06.2016 08:44В этом случае добавляется новая запись, а старая получает статус неактуальной, без создания нового экземпляра массива/списка/таблицы.
VolCh
27.06.2016 11:28+1Для клиента, «думающего» в функциональной парадигме категориями неизменяемых данных, атомарное изменение одной записи это именно создание нового экземпляра таблицы путём удаления из старой одной записи и вставки новой. Что при этом неизменившиеся записи физически не копируются для такого клиента — деталь реализации сервера.
На самом деле, на уровне физической реализации в современных архитектурах ФП и ИП отличаются лишь точкой зрения, терминологией. Для ИП атомарная инструкция процессора — это команда, изменяющая состояние системы, а для ФП — это функция, применяемая к исходному состоянию системы и возвращающая новое состояние системы с потерей старого.
Cryvage
24.06.2016 23:43>Корректность лучше быстроты. Простота лучше сложности. Ясность лучше хитроумия. Безопасность лучше ненадежности
Это все очевидные вещи, но на мой взгляд, загвоздка тут в самом понятии корректности.
Что такое корректная программа? Это программа, работающая без ошибок. А что такое ошибка в программе? Есть хорошее определение: «В программном обеспечении имеется ошибка, если оно не выполняет того, что пользователю разумно от него ожидать» (Г.Майерс. Надежность программного обеспечения. — М.: Мир, 1980. стр. 12). То есть, в конце концов все упирается в разумные ожидания пользователя. А что делать если требуемая скорость работы явно оговорена пользователем? Или неявно подразумевается, что пользователю разумно ожидать, что какое-то действие программы будет выполняться, скажем минут за 5, а с нашими алгоритмами, оно выполняется за 30? Корректность в данном случае нарушена, т.к. программа не делает того, что от нее требуется. Так что быстротой можно пренебрегать не всегда, и только до определенного предела. То же и с простотой/сложностью. Если простое решение — неправильное, или работает слишком медленно, что как мы выяснили, тоже является неправильным, то придется применять сложное решение. Насчет хитроумия, функциональный код, как раз, выглядит весьма хитроумно. Ну а безопасность, проистекает из корректности. Корректный код и так должен быть безопасным. А программа, не успевающая обрабатывать запросы — ненадежная.
>Благодаря чистоте функций и неизменяемости состояний, в ФП легче доказать корректность решения.
Это верно только для каких-нибудь математических задач. Дело в том, что для строгой проверки корректности, нужно чтобы требования к программе были сформулированы так же строго. Насколько реально, для прикладных задач, строго сформулировать разумные ожидания пользователя? Как это вообще сделать? Кто должен этим заниматься, и сколько времени это займет? Не будет ли написание обычных юнит тестов быстрее? Что проще, набрать команду толковых тестировщиков, или набрать команду толковых математиков? И кому придется больше платить? Кто докажет, что требования в итоге сформулированы корректно? И кто докажет корректность интерпретатора, выполняющего функциональную программу? Где гарантия, что он одинаково работает на любом железе и при любом окружении, под нагрузкой, с временными задержками и т.д? Все равно, без тестирования, в условиях, приближенных к реальным, не обойтись.
Да и к тому же, сколько лет уже используется императивное программирование? До сих пор корректность работы программ была достаточной, и вполне неплохо проверялась с помощью тестов. Так что, это как минимум, не является острой проблемой, которую только ФП может героически решить. Что же касается научной сферы, где строгая проверка действительно актуальна, а проблемы скорости алгоритмов, наверное не очень критичны, то тут никто и не спорит, что функциональное программирование хорошо для этого подходит. Да и количество математиков на квадратный сантиметр, там побольше будет.Source
25.06.2016 00:25+3пользователю разумно ожидать, что какое-то действие программы будет выполняться, скажем минут за 5, а с нашими алгоритмами, оно выполняется за 30?
Вы в каких-то стереотипах живёте… С чего Вы взяли, что ФП само по себе что-то делает в разы медленнее… для реальных задач скорее будет 5 и 6, и то при условии, что 5 — это что-то из серии C/C++, D, Go, Rust.
Более того существуют интерпретируемые императивные ЯП, которые как раз в разы медленнее, компилируемых (в том числе и функциональных). И ничего, прекрасно себе существуют и куча применений им находится.
Насколько реально, для прикладных задач, строго сформулировать разумные ожидания пользователя? Как это вообще сделать? Кто должен этим заниматься, и сколько времени это займет?
Вообще, есть такая профессия, бизнес-аналитик называется. Впрочем, Вы там в сторону математического доказательства корректности углубились. Хотя по факту это не имеет смысла, достаточно того, что ФП упрощает то самое юнит-тестирование.Cryvage
25.06.2016 03:16>С чего Вы взяли, что ФП само по себе что-то делает в разы медленнее
>для реальных задач скорее будет 5 и 6
Так ведь все зависит от конкретной ситуации. Если скорость устраивает, вообще не важно какая разница в скорости и насколько могло быть быстрее. Я просто указал на то, что утверждения типа: «корректность важнее быстроты», нужно всегда принимать с оговоркой: «если быстроты достаточно для обеспечения корректности». А вообще, лучше избегать выражений в форме: «X важнее чем Y». Гораздо правильней будет «стремись оптимизировать X, при Y, лежащем в допустимом диапазоне».
>Впрочем, Вы там в сторону математического доказательства корректности углубились. Хотя по факту это не имеет смысла, достаточно того, что ФП упрощает то самое юнит-тестирование.
С этим согласен. Углубляться в это особо и не хотел, просто так уж получилось. Мысль в эту сторону пошла. На практике, я никогда бы таким заниматься не стал. Думаю, и никто бы не стал.Idot
25.06.2016 06:47Если скорость устраивает, вообще не важно какая разница в скорости и насколько могло быть быстрее.
Типичный случай когда скорость устраивает, это когда программа шлёт какие-нибудь SQL-запросы на сервер, и практическая скорость работы программы зависит от сервера, а клиент может быть и не быстрым. То ситуация когда, вообще нет практической нужды писать quicksort или нечто подобное на медленном языке.
Отсюда вопрос, как с подобным обстоит у ФП-языков? Как с практической поддержкой написания клиентов на ФП? Есть ли например, встроенные библиотеки (как в Delphi) позволяющие быстро написать клиентское приложение, без необходимости изобретать велосипед? И как в ФП с поддержкой UNICODE? (ага, классическая проблема Delphi — в Borland'е вообще забыли, что помимо латиницы, вообще-то существуют и другие системы письменности — от кириллицы до иероглифов) Что-то я не припомню примеров написания клиентов на ФП. Обычно сторонники ФП хвастаются чем-нибудь вроде "посмотрите, как красиво написан quicksort!". И при этом, я вообще не помню, ни одного примера, когда был бы пример написания клиентского приложения на ФП.Source
25.06.2016 19:06Сейчас клиенты пишут либо под браузер, либо под мобильники. И там и там можно использовать ФП, но на, мой взгляд, оно как раз больше для высоконагруженного сервера подходит. На клиентах выигрыш от ФП как-то неочевиден.
VolCh
26.06.2016 11:41+1В браузерах функциональный подход используется очень часто. JavaScript хорошо поддерживает многие принципы функциональной парадигмы.
Source
25.06.2016 11:11Так ведь все зависит от конкретной ситуации.
Это да. Просто в реальных ситуациях программа выполняет кучу действий, какие-то быстрее в функциональном подходе, какие-то — в императивном, и в среднем разница не особо велика.
+ не все задачи требуют «максимально быстро», бывает просто «достаточно быстро»
Например, разбор заголовка MP3-файла можно сделать декларативно, но если это надо сделать для 100500 файлов, то придётся вспомнить про fseek. Другими словами, инструмент зависит от задачи, и чем больше у вас инструментов, тем легче выбрать наиболее подходящий под конкретную задачу.
nehaev
25.06.2016 00:32Неявно подразумевается, что пользователю разумно ожидать, что какое-то действие программы будет выполняться, скажем минут за 5, а с нашими алгоритмами, оно выполняется за 30? Корректность в данном случае нарушена, т.к. программа не делает того, что от нее требуется.
Нет, корректность не нарушена. Программа корректно делает то, что от нее требуется. Да, делает медленно — но это вопрос повышения быстродействия при сохранении корректности результата.
Это верно только для каких-нибудь математических задач. Дело в том, что для строгой проверки корректности, нужно чтобы требования к программе были сформулированы так же строго. Насколько реально, для прикладных задач, строго сформулировать разумные ожидания пользователя? Как это вообще сделать?
Для большинства прикладных задач (от решения которых не зависят жизни людей или дорогостоящее оборудование) доказывать корректность всей программы необязательно. Достаточно проверить корректность ключевых алгоритмов. Если писать эти алгоритмы в функциональном стиле, т.е. на «чистых» функциях — их корректность (всегда вернут такой-то результат при таких-то значениях входных параметров) может быть формально выведена благодаря referential transparency, без всяких математиков. Корректность «грязных» функций в общем случае доказать невозможно.
До сих пор корректность работы программ была достаточной, и вполне неплохо проверялась с помощью тестов. Так что, это как минимум, не является острой проблемой, которую только ФП может героически решить.
До сих пор из-за багов в софте теряются огромные деньги. Если есть парадигма, которая может существенно сократить количество определенных типов багов, использовать ее экономически оправдано.Cryvage
25.06.2016 02:51>Нет, корректность не нарушена. Программа корректно делает то, что от нее требуется. Да, делает медленно — но это вопрос повышения быстродействия при сохранении корректности результата.
Но если время работы является одним из требований, и оно не выполняется, то программа не выполнила своих функций. Либо, если все таки выполнила, то требования по времени были изначально неправильными и излишними. В любом случае, если производительность устраивает, то никаких вопросов нет, я просто говорил о том, что производительность может и не устраивать. Да и обсуждаемая статья именно об этом.
Со всем остальным я в принципе могу согласиться, особенно про ненужность формального доказательства корректности для большинства задач. Я об этом вообще заговорил только в контексте того, что это было заявлено, как решающее преимущество. Использовать аргумент, что это вообще не нужно — не стал, т.к. если бы это было реально достижимо для всей программы, это был бы серьезный плюс. Но если говорить об отдельных алгоритмах, то и спорить не о чем, можно тогда только эти алгоритмы и реализовывать на ФП, а остальное как удобнее. Это уже мультипарадигменность.
Что по поводу чистых функций и их проверки, то я лично не считаю чистые функции неотъемлемым атрибутом именно ФП. Мне ничего не мешает написать обычный метод, или даже процедуру, если хотите, которая будет принимать значения в качестве параметров и возвращать результат, не взаимодействуя с какими-либо глобальными данными и не имея побочных эффектов. Внутри это будет чистый алгоритм. А для внешнего наблюдателя — чистая функция. Любой процедурный язык это позволяет. Плюсы ФП не в том, что они позволяют писать такие функции, а в том, что они позволяют это делать быстрее и проще. И это становится актуально, когда таких функций надо писать много. Чтобы точно избежать недопонимания, это я не к тому написал, что ФП не нужно, а к тому, что даже если язык вообще не позволяет писать в функциональном стиле — это не повод его менять, по крайней мере, если нет реально серьезной потребности в функциональщине.VolCh
25.06.2016 07:17+2Есть требования функциональные, а есть нефункциональные. Ошибка — невыполнение (неправильное выполнение) функции, слишком долгое выполнение функции — невыполнение нефункционального требования, но не ошибка. Программа выполняет то, что пользователь от неё ожидает, она не выполняет это так быстро, как пользователь ожидает. В «вашем» определении есть слово «того», но нет слова «так».
Если язык, претендующий на высокоуровневость, не позволяет быстро и просто написать чистую анонимную функцию высшего порядка с замыканием, то, имхо, это повод его менять.
Antervis
27.06.2016 06:26+1Вы не поняли суть процитированного вами же высказывания. Код на ФП не является более корректным только потому, что он функциональный. И точно так же он (в общем случае, не рассматривая конкретные задачи) не является по умолчанию более простым или безопасным.
При этом пара утверждений однозначно верны:
1. Реальные объекты имеют состояния и эти состояния могут меняться с течением времени.
2. Реальные данные имеют свойство меняться с течением времени.
Т.о. получается, что все задачи динамики (завязанные на времени) являются по своей природе императивными. Т.е. класс «чисто функциональных» задач очень скуден.
Из чего мы приходим к выводу, что имеет смысл внедрять элементы ФП в мультипарадигменные языки для упрощения анализа статики, но при этом чисто функциональные яп не применимы к большинству реальных задач.VolCh
27.06.2016 11:35Реальные объекты имеют состояния и эти состояния могут меняться с течением времени.
Это вопрос терминологии. Можно считать, что состояние реального объекта меняется, а можно считать, что объект получает новое состояние. И, как правило, состояние объектов реального мира, моделируемое с помощью вычислительных систем, меняется не с течением времени, а в результате наступления каких-то событий. На популярных современных архитекторах данные тоже меняются не с течением времени, а по событию как минимум «наступил заданный фронт тактового генератора».Bas1l
27.06.2016 12:15В комментариях к прошлой статье был хороший пример с чайником. Что естественнее: считать, что (i) мы вскипятили воду в чайнике (то есть поменяли ее состояние) или что (ii) мы разрушили холодную воду и заменили ее горячей? Хотя да, оба процесса будут происходить по событию «включил плиту/чайник», к примеру.
VolCh
27.06.2016 12:32+1Не передергивайте. Не «разрушили холодную воду и заменили её горячей», а «разрушили у воды состояние „холодная“ и создали состояние „горячая“». Не заменили объект, а заменили состояние объекта. Что естественней: считать, что в выражении x = 5 в ячейке памяти мы изменили значение или что мы туда записали новое значение?
Cryvage
27.06.2016 21:18Проблема в том, как дать другим знать, что мы это сделали? Старый чайник, с холодной водой должен перестать существовать. Иначе это какая-то мультивселенная получается: в одной версии чайник согрели, в другой он остался нетронутым. Можно конечно всем разослать какие-то события. Но если кому-то не требуется знать сразу, по событию, что чайник согрет, то это будет излишним. Например следует различать ситуации:
1) Я услышал, что чайник вскипел — надо пойти налить кипяток в кружку.
2) Домой вернулась жена из магазина, хочет попить чаю. О, чайник уже горячий, тогда можно не греть, сразу наливаем в чашку.
Второй случай существенно отличается от первого, т.к. жене не нужно мониторить состояние чайника, реагировать на изменения оперативно, или запоминать все состояния, это не является её приоритетом. Ей не нужно знать, что чайник вскипел, ровно в тот момент, когда это произошло. И я не шлю ей СМС: «чайник вскипел», а даже если я так сделаю, то она не бросит все, и не прибежит из магазина пить чай. Ей лишь надо узнать его актуальное состояние в тот момент, когда он понадобился, и быть уверенной, что состояние именно актуальное. И таких сущностей и процессов полно, когда своевременно знать о завершении операции надо только тому, кто операцию инициировал, а остальным нужно лишь актуальное состояние сущности в момент обращения. И ситуация, когда каждый находящийся в доме, имеет доступ к чайнику и может его согреть — это тоже естественно. За доступом к нему совершенно не надо следить и ограничивать его (хотя мы и можем это сделать при необходимости). Задач такого рода тоже полно. Это легко и эффективно решается с помощью ссылок и мутабельности.Source
28.06.2016 13:07Ну а в чём проблема то? Берём Elixir или Erlang, пишем GenServer Teapot. У которого есть состояние(наличие и температура воды) и кто угодно может послать ему сообщение и узнать актуальное состояние в любой момент времени.
ООП вообще на акторах реализуется даже лучше, чем на классах. И мутабельность для этого не нужна.
В плане практических бизнес-задач у ФЯП проблем никаких нет.
Единственная проблема в ФП — реализовывать алгоритмы, построенные на базе мутабельности и массивов. Какие-то из них может даже не получиться реализовать за ту же сложность. Но, это довольно узкий класс задач… вспомните, когда Вы прошлый раз Кнута перечитывали?Cryvage
28.06.2016 16:40Так я и не говорил, что в ФП это невозможно. Но чем тогда этот «GenServer Teapot, у которого есть состояние(наличие и температура воды) и кто угодно может послать ему сообщение и узнать актуальное состояние в любой момент времени» отличается от «public static class Teapot у которого есть состояние(наличие и температура воды) и кто угодно может обратиться к нему и узнать актуальное состояние в любой момент времени»?
Source
28.06.2016 23:15+1Отличается полной изоляцией и последовательной обработкой сообщений (методов в терминах ООП). Подробнее:
- Если в методе heat объекта Teapot произойдёт исключение, которое никто не перехватит, то упадёт вся программа. Если при обработке сообщения heat актора Teapot произойдёт исключение, то упадёт только он никак не затронув другие части программы. Причём стандартной практикой является наблюдение за акторами с помощью супервизора, который перезапустит актор Teapot в исходном состоянии и он снова сможет обрабатывать сообщения. За этим стоит целый подход к разработке ПО, под названием Let It Crash!
- Если два параллельных потока захотят сменить состояние объекта Teapot, то программа упадёт с race condition. Если два параллельных потока (процесса в терминах OTP) захотят сменить состояние актора Teapot, то эти смены будут применены последовательно, т.к. любое сообщение (вызов метода) попадает в очередь сообщений актора и он обрабатывает эту очередь по порядку.
Ну а в плане преимуществ, которые может дать ООП, ничем не отличается :-)
VolCh
28.06.2016 13:44ситуация, когда каждый находящийся в доме, имеет доступ к чайнику и может его согреть — это тоже естественно.
Не естественно. Естественно, если «каждый» — это единственный человек, бывающий в доме. А так, если кто-то уже греет себе чайник, то у кого-то ещё возможности его согреть прямо сейчас нет, надо или просто дождаться когда чайник согреется (возможно даже вылив всю воду себе, если тот, кто греет не заблокировал выливание воды) и воспользоваться результатом, или ждать когда закончится цикл согревания и инициировать новый (если усеешь вклиниться между другими), или прерывать процесс инициированный другим, доливать воды на двоих и запускать новый цикл.
Это лишь на бытовом уровне кажется, что каждый в любой момент может согреть себе чайник. Попытайтесь создать императивный алгоритм для управления «умным чайником» для семьи из трех человек, не имеющих привычки пить чай все вместе, но иногда пьющих и по одному, и по два, и по три.Cryvage
28.06.2016 16:12+2Естественно, чем сложнее бизнес-логика, тем сложнее окажется алгоритм. Дело в том, что все вопросы разграничения доступа к чайнику, на которые вы указываете, следуют из сущности чайника, и сценария его использования. А значит все эти конфликты придется разрешать в любом случае, не зависимо от парадигмы программирования. Чайник у нас, по логике предметной области, является общим ресурсом. В нашем приложении мы можем представить его как мутабельной, так и иммутабельной структурой. Но во втором случае, придется все равно синхронизировать иммутабельные копии. Мы просто будем имитировать мутабельность. Но зачем?
VolCh
28.06.2016 23:28Не придётся синхронизировать, моделируем реальный мир реально — чайник один и у него нет копий :) Сложности с ФП возникают как раз когда начинаем имитировать мутабельность состояния, вместо того, чтобы просто вернуть новое.
Source
28.06.2016 23:35+2По-моему Вы слегка путаете мутабельность данных с изменением состояния.
Мутабельность данных означает, что Вы можете полностью перезаписать значение переменной в ОЗУ и все переменные, указывающие на этот же адрес в памяти, также получат новое значение. Именно мутабельности данных нет в ФП, а состояние изменяется без проблем, просто оно не разделяемое, а по-настоящему инкапсулировано в лучших традициях ООП )))
Подумайте, знаете ли Вы хоть один императивный язык, поддерживающий инкапсуляцию в полной мере? Или метод одного объекта может вызвать метод другого объекта и передать ему часть своего состояния по ссылке? А ведь это прямое нарушение инкапсуляции, т.к. другой объект может спокойно и без каких-либо разрешений или уведомлений изменить значение по этой ссылке.
Source
24.06.2016 21:55+2Функциональный подход хорош тем, что позволяет взглянуть на решаемые задачи под другим углом.
Естественно, если ваша основная задача выжать максимум производительности, то вы пишете на C, тут без вариантов. Если же вы применяете какие-то высокоуровневые ЯП, то совсем не исключено, что ФП-решение покажет лучшую производительность на ваших задачах.
P.S. Кстати, какой смысл говорить о чистых языках как-будто о ФП вцелом, если из известных чистых есть только Haskell?Idot
25.06.2016 06:06А сколько времени занимает написание ФП корректного кода? Насколько это быстро на практике?
(Например, Delphi сам по себе язык не быстрый, но можно очень быстро написать код который будет работать корректно)
И ещё: имхо, ФП-код выглядит как красивый эффектный ребус (для меня). Насколько быстро этот ребус можно написать? И насколько углублённое знание лямбда-исчисления и прочей математики требуется чтобы писать быстро? И насколько скорость написания зависит от того насколько человек хорошо знает лямбда-исчисление и тому подобное? (на императивных языках возможно писать и не зная глубоко теорию)Source
26.06.2016 02:19Про Delphi — это тонкий троллинг или Вы до сих пор его в разработке используете?.. Честно говоря, ничего не знаю, про компонентно-ориентированное программирование или GUI на функциональных языках… Меня лично больше интересует область бэкенда для всяких веб- и mobile-приложений.
Скорость написания примерно такая же, как и на императивных языках, после того как осознаёшь функциональную парадигму и перестаёшь пытаться перетянуть туда императивные привычки.
И насколько углублённое знание лямбда-исчисления и прочей математики требуется чтобы писать быстро?
Просто не лезьте в Haskell и такие вещи как лямбда-исчисление, монады, функторы и т.д. Вас не потревожат )))
Т.е. ответ по существу — Вы можете вообще не знать что такое лямбда-исчисление и теория категорий, и прекрасно себя чувствовать на функциональных языках типа Elixir или Clojure, а также и на гибридных типа F#. Из ребусов только некоторые особенности записи могу вспомнить, но они скорее непривычные, чем сложные, и довольно легко осваиваются.Idot
26.06.2016 06:11Знаю тех кто его и сейчас в разработке использует. Даже по Москве hh.ru сейчас показал 93 вакансии. Если есть прекрасно работающий legacy-код на Delphi (а Delphi работает надёжно) — имеет смысл продолжать его поддерживать, а не переводить на другой язык.
Source
26.06.2016 13:00Ok. Я просто когда-то давно тоже программировал на Delphi, но практически все, кого я знал, перешли на C# в районе 2007-2009 годов. Хотя, косвенно hh.ru это подтверждает, по тому же C# почти в 8 раз больше вакансий )
chemistmail
26.06.2016 12:22+1Столько же на практике, разницы в скорости нет. Углубленного знания математики и лямбда счисления не требуется, но лишним не будет. Для меня OOP код выглядит зачастую как ребус и непонятное наслоение лишних абстракций. Все субъективно.
0xd34df00d
28.06.2016 03:43+2Быстрее, чем на плюсоподобных языках. Потому что язык выразительнее, потому что система типов строже, потому что repl есть, в конце концов.
У меня 13 лет опыта в C++ и лет 5, куда менее богатых на потраченное на язык время, в хаскеле.
Rulexec
25.06.2016 08:10Это проблемы недостаточной проницательности компиляторов. Можно без проблем написать на ФП тот же квиксорт, который будет работать с вектором и использовать только операции перестановки элементов местами. Компилятор должен увидеть, что копий массива не создаётся и что можно использовать тот же самый.
С хештаблицами то же самое. Это лишь массив списков. Если компилятор сможет увидеть, что к старым версиям таблицы не обращаются и существует только одна последняя — нет проблемы сгенерировать код равный императивному.
Со слабыми хештаблицами сложнее, ибо в ФП нет никакой памяти, объектов по указателям, ибо мы от всего этого абстрагировались. Нужно или вручную, или вводить в ЯП тип объектов, держащих значения, плюс тип слабых ссылок, конструктор которого принимает объект и любое значение и функцию, которая будет должна подменить значение и заменить следящий объект, если объект подвергается сборке мусора. Тогда делаем список на этих слабых ссылках, указывая фактором разрушения объект, хранящиеся в следующем элементе. Как вызывается коллбек — выбрасываем звено с этим объектом.qw1
25.06.2016 12:43Можно заложить в компилятор какие-то паттерны, которые он будет находить и заменять на императивные. Но, в общем случае эта задача, я считаю, не проще проблемы остановки алгоритма. Т.е. до появления сильного ИИ только человек сможет корректно решить её (по сути, переписать критичные куски на с++).
Saffron
25.06.2016 10:58+1Попробуйте реализовать построение суффиксного дерева на функциональном чистом языке за линейное время. Я вот ещё ни одной реализации не встречал. А на императивных «грязных» языках — запросто.
Нет, конечно, настоящий fortran программист может писать на fortran на любом языке. И в хаскеле можно напрямую обращаться к памяти и писать итеративные программы.
Но чем тогда хаскель отличается от си кроме чистоты? На си тоже можно передавать функции как аргументы. И возвращать тоже. Так что си — функциональный язык? Лисп и питон ещё ближе друг к другу. Почему одно считается функциональным языком, а другое — императивным?
Функциональный язык программирования — это типичный баззворд. Функциональный язык ничем не отличается по возможностям от нефункциональных. Разве что по удобству тех или синтаксических конструкций. В лиспе лямбда функцию можно записать как угодно, а в питоне только одной строкой. Разница не принципиальна.
Единственное отличие хаскеля, на которое всегда напирают — это чистота, а не функциональность. Но эту чистоту постоянно нарушают ради производительности. Кстати, чистые и мутирующие функции — это слишком грубое деление. Бывают языки с системой эффектов, где разнообразные нарушения чистоты классифицированы и контролируются по-отдельности. И для этого вовсе не обязательно быть функциональным языком.Source
26.06.2016 23:07+1Функциональный язык — тот, в котором основная парадигма функциональная. Языков, в которых совсем невозможно ФП, по-моему, уже и нет, даже Java не устояла. С ООП то же самое, ООЯП — тот, в котором основная парадигма объектно-ориентированная. Но языков, в которых невозможно ООП, тоже практически нет.
Другими словами, вопрос только в качестве, удобстве и полноте поддержки той или иной парадигмы в языке.
Попробуйте реализовать построение суффиксного дерева на функциональном чистом языке за линейное время. Я вот ещё ни одной реализации не встречал. А на императивных «грязных» языках — запросто.
Я уже несколько раз тут в комметах писал… не надо пытаться реализовывать императивные алгоритмы в функциональном стиле. Ничего хорошего из этого не получится. И это ни разу не аргумент против ФП.Saffron
27.06.2016 01:38+1> не надо пытаться реализовывать императивные алгоритмы в функциональном стиле
Так я и не требую реализовать конкретный алгоритм. Я говорю — попробуйте решить задачу с ограничением времени в O(n). Можно даже амортизацию применять. Я находил функциональные алгоритмы с временной сложностью O(n*log(n)). Принципиально медленнее.
> Другими словами, вопрос только в качестве, удобстве и полноте поддержки той или иной парадигмы в языке.
Вот это правильно. Но когда воспевают хвалу ФП, говорят не про удобство разработки, а про принципиальные возможности. Вроде доказательств, оптимизации и прочих серьёзных плюшек. А все эти плюшки происходят не от ФП, а от чистоты и ленивости. Которые не обязательны для ФП. И даже в самом-самом ФП языке хаскель на практике часто отказываются от ленивости и чистоты, чтобы получить скорость. Ленивость остаётся лишь местами. А это уже не так сильно отличается от совсем-совсем не ФП языков вроде С++, который может достигать ленивость и чистоту местами через boost.Source
28.06.2016 13:18-1Я говорю — попробуйте решить задачу с ограничением времени в O(n). Можно даже амортизацию применять. Я находил функциональные алгоритмы с временной сложностью O(n*log(n)). Принципиально медленнее.
Извините, но не буду тратить на это время. За 10 лет практического опыта, мне эту задачу ни разу не приходилось решать для реального проекта. Поэтому лично мне вообще не интересно какая у неё алгоритмическая сложность.
Если Вы в каждодневной работе часто сталкиваетесь с подобными задачами и сложность функциональных алгоритмов Вас не устраивает, то возможно под Ваши задачи лучше подойдёт С++.Saffron
01.07.2016 13:03+1> За 10 лет практического опыта, мне эту задачу ни разу не приходилось решать для реального проекта.
Мне тоже не приходилось, есть готовые библиотеки. Для си они имеют сложность O(n), для хаскеля — O(n*log(n))
> Если Вы в каждодневной работе часто сталкиваетесь с подобными задачами
Не сталкиваюсь. Один раз потребовалось, когда реализовывал свой diff. Но алгоритм классический, пусть и низкоуровневый. Имеет множество практических применений. И потому показателен — если за всё это время никто не смог написать на хаскеле чистый алгоритм, то значит это невообразимо сложно. А значит на практике нерешаемых задач окажется ещё больше, просто они все разные, не стандартизированы, и такой концентрации внимания не получили.
Так что надо понимать, что за чистоту приходится платить не только неудобными громоздкими конструкциями, но и асимптотикой.Source
01.07.2016 19:02Везде свои компромиссы. Увеличение алгоритмической сложности некоторых алгоритмов не делает задачи не решаемыми, но показывает, что для таких алгоритмов есть более подходящие инструменты. Да и FFI никто не отменял, всегда можно дёрнуть реализацию алгоритма на C, если именно это является узким местом. Только задач, которые упираются в это, на практике встречается не так уж много. Ну а тем, у кого практический опыт другой и подобные задачи сплошь и рядом, лучше всё писать на С/С++.
Другими словами, абстрактный выбор между функциональными и императивными языками — это бессмысленный холивар. Язык надо выбирать исходя из своих конкретных задач.Saffron
02.07.2016 09:03-1> Да и FFI никто не отменял, всегда можно дёрнуть реализацию алгоритма на C
И в этот момент программа на хаскеле перестаёт быть чистой. Что вполне допустимо с практической точки зрения. Но хоронит насмерть аргументы о том, что чистота спасёт мир. Не будет вам чистоты для практических задач. А значит и не будет означенных теоретических преимуществ на практике.Source
02.07.2016 14:57+21) Практические преимущества есть и без 100% чистоты… она не является самоцелью. Хотя может в Haskell и в Clean и является, я не в курсе, но в других функциональных языках с ней точно не носятся как с хрустальной вазой.
2) Необходимость использовать FFI на практике возникает крайне редко. И ничто не мешает скопировать аргументы и изменять in-place их копию, что вполне себе сэмулирует чистоту на уровне абстракции самой программы: «вызвали функцию, она вернула результат, никак не повлияв на свои аргументы». Все преимущества чистоты следуют сугубо из того, как это работает на верхнем уровне абстракции, а не из того, как это достигается на уровне ассемблера.Saffron
02.07.2016 15:53Практические преимущества есть даже у Java. И у всяких AspectJ и прочих извращений. Опять же системы эффектов позволяет практично, глубоко и необременительно для программиста контроллировать побочные эффекты выполнения: http://kcsrk.info/ocaml/multicore/2015/05/20/effects-multicore/
Остаётся только повторить, так в чём уникальность и неповторимость FP? Оно чуть удобнее в какой-то области задач? Подобное можно про каждую парадигму программирования сказать.Source
02.07.2016 18:55+1Остаётся только повторить, так в чём уникальность и неповторимость FP? Оно чуть удобнее в какой-то области задач? Подобное можно про каждую парадигму программирования сказать.
В принципе да, поэтому чем больше парадигм знаешь, тем лучше. Императивную хотя бы частично (процедурную, структурную, объектно-ориентированную на классах) знают все, декларативную — пока немногие.
По-моему глупо рассчитывать, что все задачи можно решить в рамках какой-то единственной парадигмы и при этом ни разу не загнать себя в дикие извращения. У каждой есть своя сфера применимости.
IIvana
26.06.2016 18:08+2Там и остальные комиксы неплохие, но для некоторых надо хоть немного быть в курсе предмета :)
https://ro-che.info/ccc/25
greabock
Из прочитанного понял только одно: в функциональщине хреново организована работа с кортежами. И все
десятьдевять пунктов спекулируют на этом факте.P.S.
Сам я не функциональщик, и возможно слабо понимаю предмет.
ServPonomarev
На императивных по архитектуре компьютерах не добиться хорошей производительности функционального кода.
qw1
Неизвестно, как делать настоящую функциональную архитектуру на текущей элементной базе.
Всё, что пробовали — так или иначе переложение на уровень ниже существующей програмной эмуляции.
У hardware есть состояние, и это хорошо мапится на императивщину.
А эффективно склонировать большой объём данных, изменив где-то во всей структуре 1 поле, это проблема.
kmikeru
Чёйта непонятно? FPGA — чем не функциональная архитектура?
Опять же, есть DSL на Haskell для программирования FPGA.
qw1
Как положить на FPGA замыкания и рекурсию? Эмуляцией через машину Тьюринга, видимо ))
potan
Замыкания и даже рекурсия — не самые главные особенности ФП. Основное — иммутабильность. На FPGA вполне можно делать потоковые системы, а которых вычислительные узлы не хранят состояние. Получается что-то близкое к функциональному реактивному программированию.
При желании, замыкания можно сделать через редукцию графов, а рекурсию — через Y-комбинатор.
qw1
Это всё компиляция функциональщины на другую архитектуру, если повезёт и программа сможет в каком-то частном случае выродиться в поток.
Но что делать, если программа генерирует много замыканий, которые отличаются друг от друга ленивой функцией, а позже их вызывает (например, на действия пользователя). Как это положить на FPGA?
potan
Не стоит расчитывать, что любая ФП программа или язык хорошо лягут на FPGA. Но есть значимое подмножество таких языков и аглоритмов. И императивные языки в общем случае для этого подходят хуже.
qw1
Эта ветка комментов не о том, как один определённый алгоритм ляжет на FPGA, а какая должна быть архитектура, чтобы любая программа работала на ней с минимумом накладных расходов.
Взять конкретную инженерную задачу — лисп-машина. Как её будет инженер решать на FPGA? Скорее всего, сделает обычный фон-неймановский процессор, на котором будет крутиться интерпретатор. Сделает програмный или аппаратный менеджер памяти, чтобы учитывать занятые и свободные cons-ы и мапить их на непрерывный массив адресов.
У вас есть другие идеи?
Idot
Насколько реализуема следующая идея?
evocatus
Послушайте FPGA-разработчика.
в FPGA максимальная возможная рабочая частота зависит от архитектуры. Иногда требуемая архитектура может просто не развестись. Это такая же пакость как сама рекурсия, которая упирается в глубину стека, которая конечна и непредсказуема.
В итоге если пытаться реализовывать функциональное программирование в FPGA, то кажущееся ускорение от одновременного вычисления результатов функций будет нивелироваться общим понижением тактовой частоты.
FPGA хороши для комбинаторной логики и небольших FSM (шифраторы/дешифраторы/кодировщики/конвертеры, в общем та область, где FPGA и ASIC и используются). Если логика по сути подразумевает развесистый конечный автомат (читай императивный алгоритм со сменой состояний), то не имеет никакого значения в прокрустово ложе каких пуристских абстракций вы будете пытаться это уместить — в итоге это отъест так много скорости (засчёт конвейеризации) и ресурсов (на хранение состояния, а точнее на реализацию разных возможных ветвей исполнения), что быстрее это работать не будет, если вообще будет реализуемо.
В итоге сначала начали реализовывать программно обычные процессорные ядра прямо в FPGA, а сейчас вовсю тренд на гибриды на одном кристалле ARM и FPGA.
По сути HDL, на которых ведётся разработка для ПЛИС — это как C с точки зрения Ada, но не как LISP или Haskell. На самом деле тут приходится думать о низком уровне и заниматься оптимизацией больше, чем при программировании на Си для компьютера.
potan
Вы знакомы с HDL Bluespec?
evocatus
Честно говоря, впервые слышу.
Но причём здесь очередной HDL? Он может быть более высокоуровневый, упрощать жизнь разработчику и пр., но это не отменяет того, что я написал выше.
ARad
Тогда что такое функциональная архитектура компьютера? И почему на ней не делают компьютеры?
potan
Делали, например, «машины редукции графов». Но на них императивный код сложно исполнять.
potan
При этом компиляторы императивный языков сначала создают вполне функциональный код с однократным присваиванием, а только потом генерируют из него императивный ассемблерный код.
Idot
Тогда два вопроса:
0. а какой должна быть архитектура компьютера для функционального кода?
1. и чем не годится преобразование LISP-style кода f(a,b) в Forth-Style код a b f с последующей компиляцией?
potan
Основные сложности в реализации доступа к контексту замыканий.
Idot
Можно чуточку пояснить чуточку подробнее?
Antervis
Статья скорее пытается сказать «в функциональных ЯП плохо организованы базовые алгоритмы». Аля «из гнилых бревен хорошей бани не построишь»