Поддерживают ли какие-либо функциональные языки «разделяй и властвуй» изначально?

Question

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

sumup(0,A) -> A.
sumup(N,A) -> sumup(N) + A.

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

Answer 1

Есть ли у каких-либо функциональных языков функции, способствующие программированию "разделяй и властвуй"?

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

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

Красота функциональных языков в том, что как только эта проблема распознается, мы можем решить эту проблему не путем введения новых языковых функций, а путем более разумного использования функций, которые у нас уже есть. Чтобы узнать, как это сделать, посмотрите выступление Гая Стила за август 2009 года , где он объясняет, почему foldr не является подходящей библиотечной функцией для параллельного функционального программирования, и предлагает

• Новый стиль программирования
• Новое представление списков
• Новые функции высшего порядка для библиотек

, все они предназначены для поддержки программирования «разделяй и властвуй».

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

Если у вас есть доступ к цифровой библиотеке ACM, вы можете посмотреть видео выступления Гая Организация функционального кода для параллельного выполнения , или, как указывает Бен Карел, вы можете увидеть видео, снятое Malcom Wallace. на Vimeo.

Answer 2

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

Примеры:

Haskell имеет комбинатор par , который служит аннотацией для создания spark , вычисления, которое превращается в поток, когда становится доступным ядро ​​ЦП.

Data Parallel Haskell : определяет тип данных параллельного массива, чтобы обеспечить более неявный стиль распараллеливания, но, похоже, это обходится некоторыми ограничениями и все еще является экспериментальным кодом.

( отказ от ответственности: я не разработчик на Haskell )

Параллельная библиотека задач в .NET : Вы можете выполнить автоматическое распараллеливание данных или создать собственный Partitioner . Вам все еще нужно знать, как работает распараллеливание, иначе вы получите с чрезмерным или недостаточным разделением . У Рида Корпси есть большая серия статей о TPL и PLINQ .

DryadLINQ основывается на PLINQ и добавляет автоматические распределенные вычисления.

Ни один из них на самом деле не является родным для языка, но они тесно интегрированы. Есть даже модуль интеграции PLINQ для F # .

Answer 3

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

Answer 4

Я не знаком ни с какими языками с шаблонами типа «разделяй и властвуй». Как вы говорите, трудно представить, как бы вы указали что-то подобное.

Без дико новой записи, я думаю, классические функции, такие как partition, - лучшее, что мы можем сделать.

Answer 5

Подобные вещи довольно легко определить в Ruby. В этом примере мы разбиваем диапазон на группы по три и отправляем метод суммы для каждой группы. Затем мы суммируем полученные частичные суммы. Вы можете легко расширить это, чтобы сделать его многопоточным.

(1..10).each_slice(3).map{ |x| x.inject :+ }.inject(:+)

Этот пример немного отличается от вашего, но показывает принцип.