Функциональное программирование и научные вычисления

Я прошу прощения, если это неопределенный вопрос, но здесь идет:

В последние несколько лет функциональному программированию уделялось много внимания в сообществе разработчиков программного обеспечения. Многие начали использовать такие языки, как Scala и Haskell, и заявили об успехе над другими языками программирования и парадигмами. Мой вопрос: как специалисты в области высокопроизводительных вычислений / научных вычислений, должны ли мы интересоваться функциональным программированием? Должны ли мы участвовать в этой мини-революции?

Каковы плюсы и минусы функционального программирования в области работы SciComp?

Я только немного поработал над функциональным программированием, так что ответьте на этот вопрос с недоверием.

Плюсы:

• Функциональное программирование выглядит очень математически; это хорошая парадигма для выражения некоторых математических понятий
• Есть хорошие библиотеки, доступные для таких вещей, как формальная проверка программ и доказательство теорем, поэтому можно писать программы, которые рассуждают о программах - этот аспект хорош для воспроизводимости
• Вы можете заниматься функциональным программированием на Python и C ++ с помощью лямбда-выражений; Вы также можете заниматься функциональным программированием в Julia и Mathematica.
• Не многие люди используют его, поэтому вы можете быть пионером. Так же, как были ранние последователи MATLAB, Python, R, а теперь Джулия, должны быть ранние последователи функционального программирования, чтобы он завоевал популярность

Минусы:

• Языки, которые обычно рассматриваются как функциональные языки программирования, такие как Haskell, OCaml (и другие диалекты ML) и Lisp, обычно считаются медленными по сравнению с языками, используемыми для научных вычислений, критически важных для производительности. OCaml, в лучшем случае, примерно вдвое быстрее, чем C.
• В этих языках отсутствует библиотечная инфраструктура по сравнению с языками, обычно используемыми в вычислительной науке (Fortran, C, C ++, Python); если вы хотите решить PDE, проще сделать это на языке, более широко используемом в вычислительной науке, чем тот, который не является таковым.
• Существует не так много сообщества вычислительных наук, использующего функциональные языки программирования, как использование процедурных языков, что означает, что вы не получите много помощи в изучении или отладке, и люди, вероятно, собираются дать вам дерьмо для используя его (заслуживаете ли вы этого или нет)
• Стиль функционального программирования отличается от стиля, используемого в процедурном программировании, которое обычно преподается на вводных курсах по информатике и в классах типа "MATLAB for Scientists and Engineers"

Я думаю, что многие из возражений в разделе «Минусы» могут быть преодолены. Как обычно обсуждается на этом сайте Stack Exchange, время разработки важнее, чем время выполнения. Даже если функциональные языки программирования работают медленно, если критически важные для производительности части можно делегировать более быстрому процедурному языку и если прирост производительности может быть продемонстрирован за счет быстрой разработки приложений, то их, возможно, стоит использовать. Здесь стоит отметить, что программы, реализованные на чистом Python, чистом MATLAB и чистом R, значительно медленнее, чем реализации этих же программ на C, C ++ или Fortran. Такие языки, как Python, MATLAB и R, популярны именно потому, что они обменивают скорость выполнения на производительность, и даже тогда, Python и MATLAB имеют средства для реализации интерфейсов к скомпилированному коду на C или C ++, так что критичный к производительности код может быть реализован для быстрого выполнения. Большинство языков имеют интерфейс с иностранными функциями для C, которого было бы достаточно для взаимодействия с большинством библиотек, представляющих интерес для специалистов в области вычислительной техники.

Должны ли вы быть заинтересованы в функциональном программировании?

Все зависит от того, что вы думаете, это круто. Если вы из тех людей, которые хотят нарушить соглашение и готовы пройти через процесс евангелизации людей о достоинствах всего, что вы хотите делать с функциональным программированием, я бы сказал, что пойти на это , Я хотел бы видеть, как люди делают классные вещи с функциональным программированием в вычислительной науке, если только по какой-либо другой причине, кроме как доказать, что все скептики неправы (и будет много скептиков). Если вы не тот человек, который хочет иметь дело с группой людей, спрашивающих вас: «Почему, черт возьми , вы используете функциональный язык программирования вместо (вставьте свой любимый процедурный язык программирования здесь)?», Тогда я бы не стал беспокоиться

Там было некоторое использование функциональных языков программирования для интенсивной работы моделирования. Количественная торговая фирма Jane Street использует OCaml для финансового моделирования и реализации своих торговых стратегий. OCaml также использовался в FFTW для генерации некоторого C-кода, используемого в библиотеке. Liszt является предметно-ориентированным языком, разработанным в Стэнфорде и реализованным в Scala, который используется для решения PDE. Функциональное программирование определенно используется в промышленности (не обязательно в вычислительной науке); это еще неизвестно, будет ли это взлететь в вычислительной науке.

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

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

Тем не менее, я надеюсь, что это может измениться. Я заметил тенденцию, что исследователи начинают понимать, что многие из этих микро-архитектурных оптимизаций могут быть автоматизированы (до некоторой степени). Это привело к появлению зоопарка технологии компиляции от источника к источнику, где пользователь вводит «спецификацию» вычислений, которую он хочет выполнить, а компилятор выводит код C или Fortran, который реализует эти вычисления с оптимизацией и параллелизмом, необходимыми для эффективной работы. использовать целевую архитектуру. Между прочим, это то, для чего функциональные языки хорошо приспособлены: моделирование и анализ языков программирования. Не случайно, что первыми основными приверженцами функциональных языков были разработчики компиляторов. За некоторыми заметными исключениями, я еще не видел, чтобы это на самом деле охватило, но идеи есть,

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

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

Еще одна вещь, о которой упоминает Джефф, это то, что время разработчика часто важнее времени выполнения. Я работаю в компании, которая создает SaaS с интенсивными вычислениями, и мы сначала провели тест производительности, сравнивая C ++ с Java. Мы обнаружили, что C ++ обеспечивает примерно 50% сокращение времени выполнения по сравнению с Java (это было для вычислительной геометрии, и цифры, скорее всего, будут варьироваться в зависимости от приложения), но мы все равно пошли с Java из-за важности времени разработчика и надеялись, что Оптимизация и будущие улучшения производительности оборудования помогут нам выйти на рынок. Я могу с уверенностью сказать, что если бы мы выбрали иначе, мы бы все равно не были в бизнесе.

Хорошо, но Java не является функциональным языком программирования, так что вы можете спросить, какое это имеет отношение к чему-либо? Что ж, позже, когда мы наняли больше сторонников функциональной парадигмы и наткнулись на необходимость паралеллизации, мы постепенно перенесли части нашей системы в Scala, которая сочетает в себе положительные аспекты функционального программирования с мощью императива и хорошо сочетается с Джава. Это очень помогло нам при увеличении производительности нашей системы с минимальной головной болью и, вероятно, продолжит получать выгоду от дальнейшего повышения производительности в аппаратном бизнесе, когда больше ядер будет загружено в процессоры будущего.

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

Джефф уже дал хороший обзор причин, к которым я мало что могу добавить, кроме того, чтобы подчеркнуть один из его пунктов: экосистема. Независимо от того, пропагандируете ли вы функциональное программирование или какую-либо другую парадигму, один из важных вопросов, которые вам необходимо решить, заключается в том, что существует огромное количество программного обеспечения, на которое может опираться каждый другой, и вам нужно переписать его. Примерами являются MPI, PETSc или Trilinos для линейной алгебры или любые библиотеки конечных элементов - все написано на C или C ++. В системе огромное количество инерции, возможно, не потому, что все думают, что C / C ++ на самом деле является лучшим языком для написания вычислительного программного обеспечения, а потому, что многие люди потратили годы своей жизни на создание чего-то полезного для много людей.

Я думаю, что большинство вычислительных людей согласятся с тем, что есть много смысла в том, чтобы пробовать новые языки программирования и оценивать их пригодность для этой проблемы. Но это будет трудное и одинокое время, потому что вы не сможете добиться результатов, которые будут конкурировать с тем, что делают все остальные. Это также может дать вам репутацию человека, который начал следующий шаг к другой парадигме программирования. Эй, C ++ потребовалось всего 15 лет, чтобы заменить Фортран!

Краткое резюме таково, что

1. Численные вычисления используют изменчивость / побочные эффекты для достижения большинства своих ускорений и сокращения распределения (многие структуры функционального программирования имеют неизменные данные)
2. Ленивая оценка может быть грубой для использования с числовыми кодами.
3. Либо вы разрабатываете пакет, в котором снижение производительности до самых низких уровней действительно имеет значение (C / Fortran или теперь Julia) (в них вы также можете редактировать код ассемблера при необходимости), либо вы пишете скрипт, который использует эти быстрые библиотеки так что вы в основном заботитесь о времени разработки (и поэтому вы выбираете Julia / MATLAB / Python / R). Функциональные языки, как правило, находятся в странном среднем положении, что полезно в других дисциплинах, но не так полезно здесь.
4. Большинство числовых алгоритмов для дифференциальных уравнений, оптимизации, числовой линейной алгебры и т. Д. Написаны / разработаны / доказаны с точки зрения сходимости, т.е. у вас есть приближение и вы хотите получить . Естественным стилем реализации этих алгоритмов является цикл. (Есть некоторые алгоритмы, написанные рекурсивно, как некоторые многосеточные алгоритмы, но они встречаются гораздо реже.)х н + $x_n$$x_{n+1}$

Эти факты вместе делают функциональное программирование не нужным большинству пользователей.

Я думаю, что интересно отметить, что использование функционального программирования в вычислительной науке не является новым. Например, эта статья 1990 года показала, как повысить производительность числовых программ, написанных на Лиспе (возможно, самом раннем функциональном языке программирования), используя частичную оценку. Эта работа была частью цепочки инструментов, использованной в статье 1992 года Дж. Дж. Суссмана (из известности SICP ) и Дж. Мудрости, которая предоставила числовые доказательства хаотического поведения Солнечной системы . Более подробную информацию об аппаратном и программном обеспечении, участвующем в этих вычислениях, можно найти здесь .

R является функциональным языком, а также языком статистики (а теперь и машинного обучения) и фактически языком номер 1 для статистики. Хотя это не язык HPC: он не используется для традиционного «вычисления чисел», такого как физическое моделирование и т. Д. Но его можно использовать для работы на массивных кластерах (например, через MPI) для массового моделирования статистики (MCMC) машинного обучения.

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

В Julia вы также можете программировать в функциональном стиле (рядом с процедурным и их разновидностью OO (multi-dispatch)), но это не чисто (базовые структуры данных являются изменяемыми (кроме кортежей), хотя есть некоторые библиотеки с неизменяемыми функциональные структуры данных. Что еще более важно, это намного медленнее, чем процедурный стиль, поэтому он мало используется.

Я бы не назвал Scala функциональным языком, а скорее объектно-функциональным гибридом. Вы можете использовать множество функциональных концепций в Scala. Scala важен для облачных вычислений из-за Spark ( https://spark.apache.org/ ).

Обратите внимание, что современный Fortran на самом деле имеет некоторые элементы функционального программирования: он имеет строгую семантику указателей (в отличие от C), вы можете иметь чистые (без побочных эффектов) функции (и пометить их как таковые), и вы можете иметь неизменяемость. Он даже имеет умную индексацию, где вы можете указать условия для матричных индексов. Этот запрос подобен и обычно встречается только на языке высокого уровня, таком как R LINQ в C # или через функции фильтра более высокого порядка в функциональных языках. Так что Fortran совсем не так уж плох, у него даже есть довольно современные функции (например, совместные массивы), которых нет во многих языках. Фактически, в будущих версиях Fortran я бы предпочел добавить больше функциональных возможностей, чем OO-функций (что сейчас обычно происходит), потому что OO в Fortran действительно неуклюжий и уродливый.

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

Единственный минус в том, что вы должны обдумать этот новый тип мышления: может потребоваться некоторое время, чтобы узнать то, что вы должны знать. Другие в домене SciComp на самом деле не используют эти языки, что означает, что вы не можете получить такую ​​большую поддержку :(

Если вас интересуют функционально-научные языки, я разработал один https://ac1235.github.io

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

Con : отсутствие языковой поддержки в C / C ++ / Fortran

По крайней мере, в C ++ этот недостаток исчезает - в C ++ 14/17 добавлены мощные средства поддержки функционального программирования. Возможно, вам придется написать некоторый код библиотеки / поддержки самостоятельно, но язык будет вашим другом. В качестве примера приведем библиотеку (Warning: Plug), которая делает неизменяемые многомерные массивы в C ++: https://github.com/jzrake/ndarray-v2 .

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

Вот мое резюме того, что я считаю профессионалами:

Плюсы :

• правильность
• Понятность
• Спектакль

С точки зрения корректности , функциональные программы явно корректны : они вынуждают вас правильно определять минимальное состояние ваших физических переменных и функцию, которая продвигает это состояние вперед во времени:

int main()
{
    auto state = initial_condition();

    while (should_continue(state))
    {
        state = advance(state);
        side_effects(state);
    }
    return 0;
}

Решение уравнения в частных производных (или ОДУ) идеально подходит для функционального программирования; вы просто применяете чистую функцию ( advance) к текущему решению, чтобы сгенерировать следующее.

По моему опыту, программное обеспечение для физического моделирования в целом обременено плохим управлением государством . Обычно каждый этап алгоритма работает на некотором фрагменте общего (эффективно глобального) состояния. Это затрудняет или даже делает невозможным обеспечение правильного порядка операций, оставляя программное обеспечение уязвимым для ошибок, которые могут проявляться как ошибки сегмента, или, что еще хуже, в терминах ошибок, которые не приводят к сбою кода, но бесшумно нарушают целостность его науки. выход. Попытка управлять общим состоянием в физическом моделировании также препятствует многопоточности, что является проблемой в будущем, поскольку суперкомпьютеры стремятся к большему количеству ядер, а масштабирование с использованием MPI часто достигает максимума при ~ 100 тыс. Задач. Напротив, функциональное программирование делает параллелизм разделяемой памяти тривиальным из-за неизменности.

Производительность также улучшается в функциональном программировании из-за ленивой оценки алгоритмов (в C ++ это означает генерацию множества типов во время компиляции - часто по одному для каждого приложения функции). Но это уменьшает накладные расходы на доступ к памяти и ее распределение, а также устраняет виртуальную диспетчеризацию, позволяя компилятору оптимизировать весь алгоритм, просматривая сразу все функциональные объекты, которые его составляют. На практике вы будете экспериментировать с различным расположением точек оценки (где результат алгоритма кэшируется в буфер памяти), чтобы оптимизировать использование ресурсов ЦП и памяти. Это довольно просто из-за высокой локализации (см. Пример ниже) этапов алгоритма по сравнению с тем, что вы обычно видите в модуле или коде на основе классов.

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

Ниже приведен пример advanceфункции, адаптированной из кода конечного объема с использованием ndarray-v2пакета. Обратите внимание на to_sharedоператоры - это те оценки, на которые я ссылался ранее.

auto advance(const solution_state_t& state)
{
    auto dt = determine_time_step_size(state);
    auto du = state.u
    | divide(state.vertices | volume_from_vertices)
    | nd::map(recover_primitive)
    | extrapolate_boundary_on_axis(0)
    | nd::to_shared()
    | compute_intercell_flux(0)
    | nd::to_shared()
    | nd::difference_on_axis(0)
    | nd::multiply(-dt * mara::make_area(1.0));

    return solution_state_t {
        state.time + dt,
        state.iteration + 1,
        state.vertices,
        state.u + du | nd::to_shared() };
}