Какие-либо функциональные языки поддерживают делить-и-побеждать исходно?
Я сожалею, что не мог выяснить способ выразить вопрос более ясно в заголовке, но по существу, это - это: почти все функциональные языки имеют конструкции, которые позволяют Вам обрабатывать список переменных аргументов через хвостовую рекурсию, как в этом псевдокоде Erlang-выхода, который подводит итог списка чисел:
sumup(0,A) -> A.
sumup(N,A) -> sumup(N) + A.
Однако одно из больших обращений функциональных языков мне является их свойственным параллелизмом. И даже при том, что проблема, такая как подведение итогов список чисел очевидно довольно parallelizable, и был бы почти наверняка наиболее эффективно обработан делить-и-побеждать, я не знаю о функциях языка, которые делают это естественным способом программировать. На самом деле, если язык не имеет функции, которые позволяют читать количество аргументов, базирующихся к функции и получать аргументы на основе индекса, я не вижу, как можно было сделать это. Какие-либо функциональные языки имеют функции для поощрения программирования делить-и-побеждать?
5 ответов
Есть ли у каких-либо функциональных языков особенности, поощряющие программирование «разделяй и властвуй»?
Да: возможность создавать новые функции высшего порядка в библиотеках.
Одной из наиболее важных таких функций, в любом случае для списков, является foldr , которая в принципе может быть распараллелена при применении к ассоциативному оператору, хотя на практике это редко делается. Почему? Поскольку foldr разработан для последовательного потока данных.
Прелесть функциональных языков заключается в том, что как только эта проблема будет обнаружена, мы сможем решить ее не путем введения новых языковых функций, а путем более разумного использования уже имеющихся у нас функций. Чтобы узнать, как это сделать, посмотрите доклад Гая Стила от августа 2009 г. , где он объясняет, почему foldr не является подходящей библиотечной функцией для параллельного функционального программирования, и предлагает
- новое программирование style
- Новое представление списков
- Новые функции высшего порядка для библиотек
, которые все предназначены для поддержки программирования «разделяй и властвуй».
Что меня поразило в этом выступлении, так это то, что нет необходимости вводить новые языковые функции для поддержки программирования «разделяй и властвуй» «изначально». Достаточно взять примитивы, которые у нас уже есть, и использовать их для разработки лучших библиотек.
Если у вас есть доступ к цифровой библиотеке ACM, вы можете посмотреть видео выступления Гая Организация функционального кода для параллельного выполнения , или, как указывает Бен Карел, вы можете увидеть видео, снятое Малкомом Уоллесом на Vimeo.
Автоматический параллелизм не так прост, как может показаться. Проблема заключается в том, что если разделение выполняется автоматически, существует риск переразбиения (слишком много разделов), что добавит слишком много накладных расходов, или недоразбиения, что не позволит должным образом использовать все ядра в ваших процессорах. Выяснить это статически (т.е. во время компиляции) довольно сложно, поэтому обычно разработчик сам указывает где распараллеливать.
Примеры:
В Haskell есть par комбинатор, который служит аннотацией для создания spark, вычисления, которое превращается в поток, когда становится доступным ядро процессора.
Data Parallel Haskell: определяет тип данных параллельного массива, чтобы позволить более неявный стиль распараллеливания, но, похоже, это достигается ценой некоторых ограничений, и это все еще экспериментальный код.
(оговорка: я не разработчик Haskell)
Библиотека Task Parallel Library в .NET: может выполнять автоматическое распараллеливание данных, или вы можете реализовать свой собственный Partitioner. Вам все равно нужно знать, как работает распараллеливание, иначе в итоге вы получите пере- или недоразбиение. У Рида Корпси есть отличная серия статей о TPL и PLINQ.
DryadLINQ основан на PLINQ и добавляет автоматические распределенные вычисления.
Ни одна из этих функций не является родной для языка, но они тесно интегрированы. Существует даже модуль интеграции PLINQ для F#.
Я не знаком ни с одним языком с шаблонами типа "разделяй и властвуй". Как вы говорите, трудно представить, как можно указать что-то подобное.
Без дико новых обозначений, я думаю, классические функции типа partition - это лучшее, что мы можем сделать.
Подобные вещи довольно легко задать в Ruby. В этом примере мы разбиваем диапазон на группы по три и отправляем метод sum на каждую группу. Затем мы суммируем получившиеся частичные суммы. Вы можете легко расширить этот пример и сделать его многопоточным.
(1..10).each_slice(3).map{ |x| x.inject :+ }.inject(:+)
Этот пример немного отличается от вашего, но показывает принцип.
Взгляните на Manticore , его предшественник NESL и его родственный брат ZPL. Все они, по крайней мере, частично являются функциональными языками с параллельными конструкциями для одновременной работы со всем содержимым структур данных.