¿Algún idioma funcional admite dividir y conquistar de forma nativa?

Question

Lamento no poder encontrar una manera de expresar la pregunta con mayor claridad en el título, pero esencialmente, es esto: casi todos los lenguajes funcionales tienen construcciones que te permiten procesar una lista variable de argumentos mediante recursividad de cola , como en este pseudocódigo Erlang-ish que resume una lista de números:

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

Sin embargo, uno de los grandes atractivos de los lenguajes funcionales para mí es su paralelismo inherente. Y a pesar de que un problema como resumir una lista de números es, obviamente, bastante paralelizable, y casi seguro que sería manejado con mayor eficiencia por divide y vencerás, no conozco las características del lenguaje que hacen de esta una forma natural de programar. De hecho, a menos que el lenguaje tenga características que permitan leer la cantidad de argumentos basados ​​en una función y recuperar argumentos basados ​​en el índice, no veo cómo podría hacerlo . ¿Los lenguajes funcionales tienen características para fomentar la programación de divide y vencerás?

Answer 1

¿Los idiomas funcionales tienen características para fomentar la programación de divide y vencerás?

Sí: la capacidad de crear nuevas funciones de orden superior en las bibliotecas.

Una de las funciones más importantes, en las listas de todos modos, es foldr, que se puede paralelizar en principio cuando se aplica a un operador asociativo, aunque esto rara vez se hace en la práctica. ¿Por qué? Porque foldr está diseñado en torno al flujo de datos secuenciales.

La belleza de los lenguajes funcionales es que una vez que se reconoce este problema, podemos abordar el problema no mediante la introducción de nuevas características del lenguaje, pero haciendo un uso más inteligente de las características que ya tenemos. Para ver cómo, mira a Guy Steele's talk from August 2009, donde explica por qué foldr no es la función de biblioteca adecuado para la programación funcional en paralelo, y propone

• Un nuevo estilo de programación
• Una nueva representación de las listas
• Nueva mayores -ordenar funciones para bibliotecas

que están diseñadas para admitir la programación de divide y vencerás.

Lo que me pareció tan emocionante de esta charla es que no es necesario introducir nuevas características de idioma para admitir la programación de dividir y conquistar "de forma nativa". Es suficiente para tomar las primitivas que ya tenemos y utilizarlos para diseñar mejores bibliotecas.

Si tiene acceso a la biblioteca digital de ACM, puede ver el video de la conversación de Guy Organizing Functional Code For Parallel Execution, o como señala Ben Karel, puede ver video taken by Malcom Wallace en Vimeo.

Answer 2

Este tipo de cosas es bastante fácil de especificar en Ruby. En este ejemplo, dividimos un rango en grupos de tres y enviamos un método de suma para cada grupo. Luego sumamos las sumas parciales resultantes. Puede expandir esto bastante fácilmente para hacerlo multihilo.

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

Este ejemplo es un poco diferente de la suya, pero muestra el principio.

Answer 3

No estoy familiarizado con ningún idioma con patrones de tipo divide y vencerás. Como dices, es difícil imaginar cómo especificarías algo así.

Sin notación completamente nueva, creo que las funciones clásicas como partition son lo mejor que podemos hacer.

Answer 4

El paralelismo automático no es tan fácil como podría parecer. El problema con esto es que si el particionamiento se realiza automáticamente, existe el riesgo de particionar demasiado (demasiadas particiones), lo que agregaría demasiada sobrecarga, o subpartición, lo que no tomaría la ventaja adecuada de todos los núcleos en sus CPU. Calcular esto de forma estática (es decir, en tiempo de compilación) es bastante difícil, por lo que generalmente se deja al desarrollador anotar donde para paralelizar.

Ejemplos:

Haskell tiene el par combinator, que sirve como una anotación para crear una chispa , un cálculo que se convierte en un hilo cuando un núcleo de la CPU vuelve a estar disponible.

Data Parallel Haskell: define un tipo de datos de matriz paralela para permitir un estilo de paralelización más implícito, pero parece tener el costo de algunas limitaciones, y sigue siendo un código experimental.

(exención de responsabilidad: No soy un desarrollador Haskell)

El Task Parallel Library in .NET: puede hacer paralelización automática de datos, o se puede poner en práctica su propia Partitioner. Aún necesita saber cómo funciona la paralelización, o terminará con over- or underpartitioning. Reed Corpsey tiene un great series of articles on the TPL and PLINQ.

DryadLINQ se basa en PLINQ y agrega computación distribuida automática.

Ninguno de estos son realmente nativo de la lengua, pero son altamente integrado. Incluso hay un PLINQ integration module for F#.

Answer 5

Tenga una mirada en Manticore, su NESL predecesor, y su hermano de ZPL. Todos estos son al menos parcialmente lenguajes funcionales con construcciones paralelas para operar en todo el contenido de las estructuras de datos a la vez.