Эффективность чисто функционального программирования

Ответ 1

Согласно Pippenger [1996], при сравнении системы Lisp, которая является чисто функциональной (и имеет строгую оценочную семантику, а не ленив) к одному, который может мутировать данные, алгоритм, написанный для нечистого Lisp, который работает в O (n), может быть переведен на алгоритм в чистом Lisp, который выполняется в O (n log n) времени (на основе работы Бен-Амрам и Галил [1992] о моделировании памяти произвольного доступа с использованием только указателей). Pippenger также устанавливает, что существуют алгоритмы, для которых это лучшее, что вы можете сделать; существуют проблемы, которые представляют собой O (n) в нечистой системе, которые являются Ω (n log n) в чистой системе.

В этой статье есть несколько предостережений. Самое главное, что он не касается ленивых функциональных языков, таких как Haskell. Bird, Jones and De Moor [1997] демонстрируют, что проблема, построенная Pippenger, может быть решена на ленивом функциональном языке в O (n) времени, но они не устанавливают (и, насколько я знаю, никто не имеет), может ли ленивый функциональный язык решить все проблемы в том же асимптотическом времени работы, что и язык с мутацией.

Задача, построенная Пиппэндэром, требует, чтобы Ω (n log n) была специально сконструирована для достижения этого результата и не обязательно представляет практические, реальные проблемы. Есть несколько ограничений на проблему, которые немного неожиданны, но необходимы для доказательства работы; в частности, проблема требует, чтобы результаты вычислялись в режиме онлайн, не имея возможности получить доступ к будущему входу, и что вход состоит из последовательности атомов из неограниченного набора возможных атомов, а не набора фиксированного размера. И статья только устанавливает (нижнюю границу) результаты для нечистого алгоритма линейного времени работы; для задач, требующих большего времени работы, возможно, что дополнительный коэффициент O (log n), замеченный в линейной задаче, может быть "поглощен" в процессе дополнительных операций, необходимых для алгоритмов с большим временем работы. Эти разъяснения и открытые вопросы кратко рассматриваются Ben-Amram [1996].

На практике многие алгоритмы могут быть реализованы на чистом функциональном языке с той же эффективностью, что и на языке с изменяемыми структурами данных. Для хорошей ссылки на методы, используемые для эффективного использования функциональных структур данных, см. Крис Окасаки "Чисто функциональные структуры данных" [Okasaki 1998] (который является расширенной версией его тезиса [Okasaki 1996]).

Любой, кто нуждается в реализации алгоритмов на чисто функциональных структурах данных, должен прочитать Окасаки. Вы всегда можете получить в худшем случае замедление O (log n) на операцию, моделируя изменчивую память со сбалансированным двоичным деревом, но во многих случаях вы можете сделать значительно лучше, чем это, и Окасаки описывает много полезных методов: от амортизированных методов до реальных, которые постепенно амортизируют работу. Чисто функциональные структуры данных могут быть немного трудными для работы и анализа, но они обеспечивают множество преимуществ, таких как прозрачность ссылок, которые полезны при оптимизации компилятора, параллельных и распределенных вычислениях и в реализации таких функций, как управление версиями, отмена и откат.

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

Ссылки

• Бен-Амрам, Амир и Галил, Цви 1992. "На указателях против адресов" Журнал ACM, 39 (3), стр. 617-648, июль 1992 г.
• Бен-Амрам, Амир 1996. Заметки о сравнении Pippenger чистого и нечистого Lisp Неопубликованная рукопись, DIKU, Копенгагенский университет, Дания
• Птица, Ричард, Джонс, Герант и Де Мур, Oege 1997. "Больше поспешности, меньше скорости: ленивая и нетерпеливая оценка" Журнал функционального программирования 7, 5 с. 541-547, сентябрь 1997 г.
• Окасаки, Крис, 1996. "Чисто функциональные структуры данных" Кандидатская диссертация, Университет Карнеги-Меллона.
• Окасаки, Крис 1998. "Чисто функциональные структуры данных" Cambridge University Press, Cambridge, UK
• Pippenger, Nicholas 1996. "Pure Versus Impure Lisp" Симпозиум ACM по принципам языков программирования, стр. 104-109, январь 1996 г.

Ответ 2

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

• Вышеупомянутый union-find
• Хэш-таблицы
• Массивы
• Некоторые алгоритмы графа
• ...

Однако мы предполагаем, что в "императивных" языках доступ к памяти - O (1), тогда как в теории, которая не может быть так асимптотически (т.е. для неограниченных размеров проблем) и доступа к памяти в огромном наборе данных, всегда O ( log n), которые могут быть эмулированы на функциональном языке.

Кроме того, мы должны помнить, что на самом деле все современные функциональные языки предоставляют изменчивые данные, а Haskell даже обеспечивает его, не жертвуя чистотой (монада ST).

Ответ 3

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

Тот факт, что другие ответы утверждают, что никогда не может быть никакой разницы, и что, например, единственный "недостаток" чисто функционального кода состоит в том, что он может быть распараллелен, дает вам представление об информированности/объективности сообщества функционального программирования по этим вопросам,

РЕДАКТИРОВАТЬ:

Комментарии ниже указывают на то, что предвзятое обсуждение плюсов и минусов чистого функционального программирования может исходить не из "сообщества функционального программирования". Хорошая точка зрения. Возможно, защитники, которых я вижу, просто, чтобы процитировать комментарий, "неграмотный".

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

Если строгая функция имеет сложность O (f (n)) в строгом языке, то она также имеет сложность O (f (n)) на ленивом языке. Зачем беспокоиться? :)

Ответ 4

С фиксированной верхней границей использования памяти не должно быть разницы.

Доказательство эскиза: Учитывая фиксированную верхнюю границу использования памяти, нужно иметь возможность написать виртуальную машину, которая выполняет набор обязательных инструкций с той же асимптотической сложностью, как если бы вы фактически выполняли на этой машине. Это связано с тем, что вы можете управлять изменчивой памятью как постоянной структурой данных, предоставляя O (log (n)) чтение и запись, но с фиксированной верхней границей использования памяти вы можете иметь фиксированный объем памяти, распад до O (1). Таким образом, функциональная реализация может быть императивной версией, выполняемой в функциональной реализации VM, и поэтому они должны иметь одинаковые асимптотические сложности.

Ответ 5

Я бы предложил прочитать о производительности Haskell, а затем взглянуть на тесты производительности игр для функциональных языков или процедурных /OO.

Ответ 6

"Функциональный" - это набор различных функций, каждый из которых независимо полезен, и его более полезно рассматривать каждый отдельно.

Неизменность

Теперь, когда я знаком с этим, в любой момент, когда я могу уйти с возвратом неизменяемого результата, я всегда стараюсь это делать даже в объектно-ориентированной программе. Легче рассуждать о программе, если у вас есть данные типа значения.

Функции как типы первого класса

Независимо от того, что вы хотите назвать, передача делегатов, действий или функций - это действительно удобный способ решения целого класса реальных проблем, таких как "дыра в среднем шаблоне".

Возможность компоновки функций (например, включение Action в просто действие также весьма полезно в некоторых сценариях.

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

Монады

Это тонкая, но очень мощная конструкция. Он так же эффективен, как ключевое слово yield, используемое для создания классов IEnumerable в С#. По сути, он создает для вас машину состояний, но ваша логика выглядит линейной.

ленивая оценка и рекурсия

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

S-выражения

Я думаю, я не уверен, где это сделать, но способность обрабатывать некомпилированный код как объект (и проверять/изменять его), например Lisp S-Expressions или LINQ Expressions, является, в некотором смысле, самый мощный инструмент функционального программирования. Большинство новых "беглых" интерфейсов .NET и DSL используют комбинацию синтаксиса лямбда и LINQ Expressions для создания некоторых очень сжатых API. Не говоря уже о Linq2Sql/Linq2Nhibernate, где ваш код С# "магически" выполняется как SQL, а не как код С#.