Научная математика с функциональными языками?

Question

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

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

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

Обновление : похоже, что функциональные языки используются в символических вычислениях, например. в Mathematica. Но есть ли что-то несовместимое с числовыми вычислениями и функциональными алгоритмами? Или это просто так, поскольку императивные алгоритмы были изобретены первыми, никто не удосужился придумать функциональные эквиваленты?

Answer 1

В hackageDB есть библиотека Haskell для числовых вещей: hmatrix . Он взят из LAPACK, BLAS и GSL (Научная библиотека GNU).

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

Что касается следования функциональному стилю, то во многих случаях это невозможно. Для многих проблем не существует никаких (эффективных) функциональных подходов. Конечно, вы можете заставить такие алгоритмы работать, например, в Haskell, но они не будут сильно отличаться от написанных на Matlab, Fortran или C.

EDIT:

Это явная несовместимость , а также проблема, возникшая раньше:

1. Эффективные численные алгоритмы обычно требуют изменяемых данных. Хотя это возможно в чисто функциональной обстановке, это не так просто, как в императивных языках. Но две вычислительные модели совершенно эквивалентны.
2. Базовая машина (например, набор инструкций) всегда была и остается обязательной, за очень немногими исключениями (!). Алгоритмы с императивным кодированием легче анализировать и оптимизировать, если моделировать реальную машину.
3. Хотя основополагающая математика позволяет относительно легко выводить функциональные решения, вы не получите эффективного алгоритма (как в случае получения императивных решений непосредственно из математики). Поскольку большая часть усилий была и остается направлена ​​на императивные решения, функциональные аналоги просто неизвестны. Под функциональными аналогами я подразумеваю код, который правильно выражает функциональные намерения и стиль.
4. Существует довольно много императивного кода, который можно использовать повторно. Многое из этого можно перевести на функциональный язык с помощью преобразователей состояний, хотя это все равно будет выглядеть крайне необходимо.

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

Answer 2

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

Answer 3

Отличный вопрос!

Я являюсь одним из немногих пионеров в этой области уже несколько лет, и мы только недавно достигли того уровня, когда стало возможным получить производительность, подобную Fortran, и краткость, подобную Python, для широкого диапазона проблемы. Подробно изучив все доступные функциональные языки и их реализации, я решил сосредоточить свои усилия на нечистых функциональных языках статического типа: с открытым исходным кодом язык программирования OCaml и язык программирования Microsoft F # для .NET.

Моя книга OCaml для ученых охватывает научные вычисления с помощью языка программирования OCaml для Linux или Mac OS X. Моя книга F # для ученых охватывает научные вычисления с Язык программирования Microsoft F # с использованием Windows и Visual Studio. Моя компания также продает F # для числовых и F # для библиотек визуализации , которые полностью написаны на F # и широко используют функциональное программирование как для краткости, ясности и удобства обслуживания, так и для внешних целей. сделать библиотеку проще в использовании. Например, первоклассные функции позволяют вам действительно легко строить графики, например, построение функции синуса:

Plot([Function sin], (-5., 5.))

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

Мы добились больших успехов в написании кода для научных вычислений в функциональном стиле на языках OCaml и F #. В частности, F # облегчает написание высокопроизводительного параллельного кода, который является универсальным, без потери производительности для абстракции. Таким образом, вы можете реализовать QR-декомпозицию, которая работает для матриц любого типа (одинарная, двойная, сложная или даже символическая!) И даже превосходит производительность библиотек, настроенных производителем, таких как Intel MKL !

Наконец, я должен отметить, что Mathematica пошла каким-то образом, чтобы проложить этот путь задолго до того, как я это сделал. Однако их решение состояло в том, чтобы объединить огромную стандартную библиотеку числовых и символических функций, написанных на C, с традиционным императивным стилем и обеспечить довольно элементарный язык функционального программирования для вызова этих функций. Основным недостатком их подхода является то, что общий код, написанный на Mathematica (т. Е. Где время не тратится в основном на их стандартную библиотеку), примерно в 1000 раз медленнее, чем C.

Answer 4

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

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

Answer 5

Некоторые системы компьютерной алгебры (например, Maxima) используют языки на основе LISP для представления символических вычислений / синтаксических деревьев.

Примеры математических, функциональных языков:

http://en.wikipedia.org/wiki/J_(programming_language)

http://en.wikipedia.org/wiki/K_(programming_language)

В любом случае, есть несколько математических задач и алгоритмов, которые не могут быть сформулированы должным образом или эффективны в функциональном стиле. Эффективная реализация всегда будет обязательной. Пример: Сито Эратосфена

Answer 6

Определите «серьезно». Помните, что функциональные языки (кроме LISP) довольно новы - оригинальные документы Бэкса были только в конце 70-х годов, а функциональные языки производственной инженерии довольно новы. Хорошо известные и общепринятые числовые пакеты основаны на алгоритмах и кодах, начиная с конца 60-х и начала 70-х годов - BLAS был впервые опубликован в 1979 году. Поскольку для производственного использования люди склонны стремиться к хорошо известные и надежные пакеты, есть большой путь к старым кодам FORTRAN.

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

Answer 7

Я считаю, что Mathematica использует свой собственный функциональный язык.