[Перевод] Недостатки чистого функционального программирования
От автора: перевод статьи «Функциональное программирование непопулярно, потому что оно странное» вызвал бурное обсуждение. В нескольких комментариях весьма справедливо замечалось, что при обсуждении недостатков функционального программирования хорошо бы опираться на современные и развитые функциональные языки (в оригинальной статье примеры были на шаблонах C++) и что Хаскель, например, последние пять лет широко используется в индустрии. В связи с этим я хотел бы обратить внимание на две очень предметные статьи из другого блога (от автора книги F# for Scientists): (i) «Недостатки чистого функционального программирования» и (ii) «Почему Хаскель так мало используется в индустрии». Перевод первой из них я как раз и хотел бы представить ниже.
С 90х годов использование словарей в разработке побило все рекорды. Словари теперь—стандартная коллекция, которую каждый разработчик ожидает найти в своей стандартной библиотеке.
Чисто функциональные или персистентные структуры данных, типа тех, что можно найти в небезызвестной монографии Окасаки—отличный инструмент. В частности, персистентность, которую они предоставляют, означает, что вы можете обращаться к старым версиям коллекций, не беспокоясь о том, как коллекции модифицируются. Во многих случаях (особенно в задачах типа логического программирования или написания компиляторов) это может сделать решения короче и проще—частично потому, что сделает слежение за изменениями тривиальным. Но за персистентность нужно заплатить большую цену в смысле производительности: чисто функциональные словари обычно примерно в 10 раз медленнее, чем хорошо реализованные хэш-таблицы, и я видел случаи, когда разница достигала 40 раз. Для некоторых приложений это непозволительно медленно.
Более того, большинство функциональных языков (OCaml, Haskell, Scala) неспособны выразить быструю изменяемую generic хэш-таблицу, потому что у них нет убийственной комбинации из reified generics, типов-значений (value types) и быстрого write barrier для сборщика мусора.
ВНИМАНИЕ! Остерегайтесь людей которые пытаются утверждать, что чисто функциональные словари Хаскеля быстрые, сравнивая их с изменяемыми хэш-таблицами того же самого Хаскеля. Правильный вывод из такого сравнения: это изменяемые хэш-таблицы Хаскеля медленные.
В императивном языке со сборкой мусора отношения между узлами и ребрами графа можно выразить с помощью слабых хэш-таблиц. Сборщик мусора соберет за вас недостижимые подграфы. Поскольку чисто функциональных слабых хэш-таблиц не существует, в чистом функциональном языке вам придется писать свою сборку мусора (прим. перев. я так понимаю, в смысле удалять недостижимые подграфы руками).
Впрочем, это не самый серьезный недостаток, учитывая то, что большинство разработчиков никогда не пользовались слабыми хэш-таблицами…
По определению, неизменяемые коллекции не могут поддерживать мутабельность, в том числе и потокобезопасную. Так что, если вы хотите shared изменяемую коллекцию (такую как in-memory базу данных), то чисто функционального решения не существует.
Функциональное программирование—отличный инструмент для некоторых типов задач, но, по моим наблюдениям, алгоритмы на графах—то место, где чисто функциональные решения часто хуже и с точки зрения простоты кода, и с точки зрения производительности.
Сравните алгоритм Прима на 12 строчках Питона и алгоритм Прима на 20 строчках Хаскеля. А и почему, собственно, Хаскель использует алгоритм Прима в библиотеке? Наверное, потому что алгоритм Крускала основывается на структуре данных «система непересекающихся множеств» (union-find collection, aka Disjoint-set data structure), а в функциональных языках нет ее эффективной реализации.
Помимо алгоритмов на графах, существует много областей computer science, в которых 65 лет научной литературы фокусировались почти полностью на императивных решениях. Следовательно, программисты на императивных языках могут стоять на плечах гигантов и пользоваться этими наработками, в то время как программистам на функциональных языках часто приходиться начинать с нуля. В конце концов, всего пару лет назад мемоизация в Хаскеле была темой кандидатской диссертации.
Однажды я предложил нескольким программистам на Хаскеле (и у некоторых из них были диссертации по этому языку) написать на нем эффективную параллельную быструю сортировку (quicksort)—и вот что из этого вышло.
Примерно в 1960 году МакКарти изобрел Лисп. Основной структурой данных был односвязный список. Каждый элемент списка аллоцировался отдельно в куче. Все современные функциональные языки развились из этой идеи. В 70х Scheme использовал по сути ту же стратегию представления данных, что и Лисп. В 80х, SML добавил немного распаковывания (unboxing) в связи с включением в язык кортежей (tuples), аллоцируемых в куче как цельные блоки памяти. В 90х OCaml добавил еще немного распаковывания в связи с включением в язык распакованных массивов действительных чисел. Хаскель добавил возможность распаковывать определенные типы данных. Но по сегодняшний день ни у одного функционального языка нет по умолчанию распакованных кортежей (прим. перев. судя по всему, автор выбрал почему-то такой способ сказать «кортежей, по умолчанию расположенных на стеке»). Даже F#, основанный на .Net, в котором можно создавать любые типы-значения (value types), все еще использует запакованные кортежи .Net. Следовательно, все современные функциональные языки несут на себе бремя частых аллокаций памяти в куче без всякой на то необходимости. Следовательно, они нагружают свои сборщики мусора намного больше, чем нужно. Это серьезная проблема не только потому, что это делает однопоточный код медленным, но и потому, что сборщик мусора—совместно используемый ресурс и, как следствие, нагрузка на сборщик мусора ведет к плохой масштабируемости параллельных программ.
Нужно заметить, что объявление такого поведения «недостатком» может быть спорным. Xavier Leroy из сообщества OCaml считает, что представление данных в OCaml по образу Лиспа—это преимущество, потому что это основа отличной производительности OCaml в среде для автоматического доказательства теорем Кок (Coq). Ксавье заявляет, что «стратегия Ocaml для символьных вычислений близка к оптимальной». Функциональные языки часто оптимизированы для высокопроизводительных чисто функциональных коллекций за счет низкой производительности императивных коллекций. С учетом того, что императивные коллекции в основном быстрее, это ведет к искусственно заниженному потолку производительности почти всех функциональных языков.
Сегодня есть две причины писать параллельные программы. Первая—это писать объективно быстрые решения. Вторая—делать медленные решения не такими медленными. В большинстве случаев параллельное программирование на функциональном языке—вариация второй причины. Почти никто в среде высокопроизводительных вычислений (high performance computing), то есть на суперкомпьютерах, не запускает напрямую функциональный код. Если разработчик на функциональном языке параллелизует программу, в большинстве случаев он делает это не для того, чтоб добиться отличной абсолютной производительности, а чтоб улучшить ту скорость, что у него есть.
Чистые функциональные языки типа Хаскель разработаны, чтоб скрыть от программиста работу с памятью и временем. Это дает программисту вид на программу с высоты птичьего полета, но делает очень сложным оценку того, сколько памяти будет потреблять программа на Хаскеле и сколько времени она будет выполняться, прежде чем получит результат. В параллельном программировании всегда очень важно убедиться, что выигрыш от параллелизации перевесит административные затраты на параллельное выполнение кода. В Хаскеле это очень тяжело. На самом деле, настолько тяжело, что опубликованное исследование о параллельном выполнении Хаскеля очень избирательно предоставляет результаты о степени параллелизации, которая максимизирует производительность, при том что эту степень нельзя предсказать заранее без того, чтоб не прогнать программу много раз. По моему опыту, в языках типа С++ параллелизация самыми стандартными методами часто дает предсказуемый выигрыш в скорости, в отличие от Хаскеля, где производительность не предсказуема.
ВНИМАНИЕ! Остерегайтесь людей, которые говорят о масштабируемости программ без учета абсолютной производительности. Вы можете улучшить масштабируемость почти любой параллельной программы путем бессмысленного вычисления множеств Мандельброта после каждой строчки кода без всякой на то причины, потому что большая часть вычислений будет происходить в невероятно параллельном коде. Масштабируемость—необходимое, но не достаточное условие. Нужно обяэательно смотреть и на абсолютную производительность.
Я занимаюсь функциональным программированием уже больше 20 лет. Десятилетиями существовала социальная пропасть между программистами на функциональных языках и теми, кто решал настоящие задачи. Слава богу, эта проблема начала рассасываться вместе с тем, как функциональные языки типа Scala, Clojure и F# начали использоваться для настоящих задач;, но много лет в сообществе функционального программирования преобладали именно высокомерные снобы, что делало очень трудным получение настоящих решений для настоящих проблем. Причиной для этого было то, что многие сообщества (особенно Лисп), на десятилетия преданные забвению и предоставленные сами себе, имели очень развитые (но неправильные) аргументы о том, почему их язык (Лисп) такой хороший. Мне потребовалось много лет, чтоб понять, что не так в этих аргументах.
Если вы критикуете производительность хэш-таблиц в Хаскеле (более свежая критика здесь), то вы можете получить абсолютно дикие советы от светил сообщества—например, они могут буквально посоветовать вам просто отключить сборку мусора.
Долгое время сообщество функционального программирования потрясало замечательно короткими реализациями алгоритмов решета Эратосфена и quicksort. Их даже годами преподавали студентам. И только спустя многие годы пришло понимание, что эти реализации не соответствуют исходным алгоритмам. Мелисса О'Нил (Melissa O«Neill) даже опубликовала научную статью, исправляющую решето Эратосфена в Хаскеле. В частности, ее настоящее решето требует в сто раз больше кода, чем ошибочная оригинальная версия. То же справедливо и для quicksort’а, где «элегантная» двухстрочная версия на Хаскеле более чем в 1000 раз медленнее версии Сэджвика на C, потому что Хаскель делает глубокую копию списков на каждом вызове quicksort’а, портя к чертям асимптотическую сложность оригинального алгоритма Хоара.
Смотрите также «Почему Хаскель так мало используется в индустрии», где подробно опровергается страница «Хаскель в индустрии».
От автора: статью «Почему Хаскель так мало используется в индустрии» я тоже надеюсь когда-нибудь перевести, потому что она пытается опровергнуть мнение о том, что Хаскель последние пять лет широко используется в индустрии. Но надо заметить, что (судя по комментариям к оригинальной версии на английском) она не так однозначна и автор сам, кажется, кое-где сгущает краски.
