¿Qué algoritmos se pueden expresar usando un lenguaje funcional total con operadores paralelos de datos?

Imagine un lenguaje de programación funcional cuyos únicos tipos de datos son escalares numéricos y anidaciones arbitrarias de matrices. El lenguaje carece de cualquier medio de iteración ilimitada, por lo que no se permite lo siguiente:

• bucles explícitos (de todos modos, sin mucho uso sin efectos secundarios)
• recursividad
• funciones arbitrarias de primera clase (sin combinador y)

Sin embargo, el lenguaje tiene:

• funciones de nivel superior
• Ángulo léxico dejar enlaces
• flujo de control de ramificación
• funciones escalares comunes de matemática y lógica
• algún constructor de matriz simple como fill (n, x) que crea una matriz de n elementos con valores idénticos x
• lo más importante: un conjunto restringido de operadores de orden superior que realizan iteraciones estructuradas paralelas (como mapear, reducir, escanear, todos los pares).

Para ser más específico sobre los operadores paralelos de datos:

• y = mapa (f, x) => y [i] = f [i]
• y = reducir (f, a, x) => y = f (a, f (y [p [0]], f (y [p [1]], ...))) para alguna permutación p
• y = exploración (f, a, x) => y [i] = reducir (f, a, y [0 ... i-1])
• y = todos los pares (f, x, y) => y [i, j] = f (x [i], y [j])

También podríamos tener otros operadores, pero para calificar deberían tener un tiempo de ejecución polinómico, ser implementables bajo algún modelo razonable de cómputo paralelo de datos y usar como máximo espacio polinómico.

Obviamente, hay algunas construcciones que no se pueden expresar en este lenguaje, como:

while f(x) > tol:
    x <- update(x)   

¿Qué podemos expresar en este sistema? ¿Estamos limitados solo a problemas de búsqueda en FP? ¿Podemos capturar todos los algoritmos de tiempo polinomiales? Además, ¿hay algún conjunto mínimo de operadores para esta clase?

Es posible que desee ver el antiguo lenguaje de programación NESL que tomó en serio estas ideas. El lenguaje se basa en operaciones en colecciones, esencialmente listas y listas de listas, etc., pero creo que también se consideraron árboles y gráficos, a través de codificaciones difíciles. Parte de la investigación realizada en ese proyecto (a mediados de la década de 1990) podría ayudar a responder su pregunta. La tesis doctoral (disponible como libro) Guy E. Blelloch. Modelos vectoriales para computación paralela de datos. MIT Press, 1990 puede proporcionar algunas respuestas. Fue hace algún tiempo desde que lo miré.

El trabajo realizado sobre el formalismo Bird-Meertens (BMF) también se incluye en esta categoría, al igual que el lenguaje Charity . Desde la página de Wikipedia de Charity dice que el lenguaje no está completo, pero puede expresar la función de Ackermann, lo que significa que es más que recursivo primitivo. Tanto BMF como Charity involucran operadores como pliegues y escaneos (catamorfismos, anamorfismos, etc.), y tienen sus raíces en la teoría de categorías.

En resumen, la respuesta imprecisa es que puedes expresar mucho.

Mi otra respuesta señaló fallas en el idioma tal como está. En esta respuesta, daré más detalles sobre los problemas con la coexistencia de pliegues y despliegues en un lenguaje total. Luego propondré una resolución y mostraré que todos los problemas en P (y de hecho muchos más) pueden resolverse en este lenguaje extendido.

Plegar en un idioma total consume listas:

fold :: (a -> b -> b) -> b -> List a -> b

El despliegue en un lenguaje total genera flujos, que son potencialmente ilimitados:

unfold :: (b -> Maybe (a, b)) -> b -> Stream a

Desafortunadamente, las listas y las transmisiones viven en mundos diferentes, por lo que estos operadores no pueden estar compuestos. Necesitamos una correspondencia parcial:

stream :: List a -> Stream a
list :: Int -> Stream a -> List a

El operador de flujo incrusta una lista en un flujo acotado. La función de lista extrae los primeros n elementos (o menos si la secuencia termina antes) en una lista. Así tenemos la siguiente ecuación:

for all xs :: List a, xs == list (length xs) (stream xs)

Como una optimización de la eficiencia, podemos eliminar por completo los flujos como una estructura de datos intermedia:

unfoldList :: Int -> (b -> Maybe (a, b)) -> b -> List a

Ahora esbozaré una prueba de que esto (con los otros operadores ya implicados en la pregunta original) nos permite simular cualquier algoritmo de tiempo polinómico.

Por definición, un lenguaje L está en P cuando hay una máquina de Turing M y un polinomio p tal que la pertenencia de x en L se puede decidir ejecutando M en la mayoría de las iteraciones p (n) donde n = | x |. Según un argumento estándar, el estado de la cinta de la máquina en la iteración k puede codificarse con una lista de longitud como máximo 2k + 1, aunque la cinta de la máquina sea infinita.

La idea ahora es representar la transición de M como una función de listas a listas. La ejecución de la máquina se realizará desplegando el estado inicial con la función de transición. Esto genera una secuencia de listas. La suposición de que L está en P significa que no necesitamos mirar más allá de los elementos p (n) en la secuencia. Por lo tanto, podemos componer el despliegue list p(n)para obtener una lista finita. Finalmente, lo doblamos para verificar si la respuesta al problema de decisión fue sí o no.

En términos más generales, esto muestra que siempre que tenemos un algoritmo cuyo tiempo de terminación puede estar limitado por una función computable en el lenguaje, podemos simularlo. Esto también sugiere por qué algo como la función de Ackermann no se puede simular: es su propio límite, por lo que hay un problema de huevo y gallina.

Es un lenguaje muy entorpecido. Intente programar la función factorial:

fact 0 = 1
fact n = n * fact (n-1)

El problema es que su idioma solo tiene pliegues pero no despliega. La forma natural de expresar factorial es componer un despliegue de n en la lista [1, 2, ..., n] con el plegamiento que lo derriba mientras se multiplica.

¿Está realmente interesado en este lenguaje específico o en la programación funcional total en general? Es obvio que su idioma puede, como máximo, expresar algoritmos de tiempo polinómico. El Sistema F (cálculo lambda polimórfico) puede expresar monstruos como la función de Ackermann con facilidad. Incluso si su interés está en los algoritmos de tiempo polinomial, con frecuencia necesita el espacio del codo superpolinomial para expresarlos de forma natural.

Editar: Como señala Dave, NESL es uno de los lenguajes de programación seminal funcional de datos paralelos, pero está muy lejos de ser total (ni siquiera lo intenta). La familia APL tenía una trayectoria paralela de evolución y tiene un subconjunto algebraico total (evite los operadores de punto fijo). Si el foco de su pregunta es la totalidad, David Turner ha escrito algunos buenos documentos en esta área, aunque no específicamente en la programación de datos paralelos.