¿Los lenguajes de programación funcionales tienen más oportunidades de optimizar el tiempo de compilación?

10

Estaba leyendo el libro "Programación funcional para el mundo real". Comenzó con la comparación entre los lenguajes de programación imperativos y funcionales. Y estableció cómo los "valores" y las "expresiones" en la programación funcional son diferentes de las "variables" y las "funciones" de la programación imperativa. De la discusión, desarrollé una idea que:

Los lenguajes de programación funcional tienen más oportunidades de optimizar el tiempo de compilación que sus contrapartes imperativas.

¿Es verdad?

functional-programming compilation Gulshan
fuente

Respuestas:

16

Los lenguajes de programación funcional optimizan mucho más el tiempo de compilación. Una de las razones es la pureza: la concurrencia es trivial porque no hay estado. Por lo tanto, el compilador puede tomar dos ramas y hacerlas coincidir fácilmente sin cambiar el comportamiento del programa.

Al mismo tiempo, el compilador puede calcular de antemano cualquier cosa que pueda calcularse sin estado (es decir, cualquier cosa que no sea monádica en Haskell), pero tales cálculos podrían ser costosos y, por lo tanto, probablemente solo se hagan parcialmente.

Además, todo lo que no se necesita computacionalmente se puede optimizar completamente fuera del programa.

alternativa
fuente
1
+1: La programación libre de efectos secundarios es muy, muy fácil de optimizar.
S.Lott
@mathepic: en realidad, la paralelización (en Haskell) ocurre tanto en tiempo de compilación como en tiempo de ejecución. El tiempo de compilación decide si vale la pena crear un fragmento (semilla de subproceso) y el tiempo de ejecución procesa los fragmentos como puede, dependiendo de la cantidad de subprocesos que haya especificado. Si solo especifica un solo hilo, los fragmentos se crean, pero se procesan uno tras otro.
Matthieu M.
2
@mathepic: otro uso de la pureza -> pereza y la ausencia de cómputo. Si puede demostrar que el valor no es necesario, elimine el cálculo por completo. Si puede ser necesario, use un vago perezoso. Si sabe que será necesario, calcúlelo directamente (para evitar la sobrecarga perezosa). La pureza es (simplemente) increíble :)
Matthieu M.
@Matthieu buen punto
alternativa
1
@Masse Incluso la mónada IO es pura. Es solo que el resultado de "ejecutar" la mónada IO no lo es.
alternativa
7

En principio, es probable que haya más posibilidades de optimización del tiempo de compilación para lenguajes funcionales que para sus contrapartes imperativas.

Sin embargo, es más interesante si se implementan realmente en los compiladores actuales y qué tan relevantes son estas optimizaciones en la práctica (es decir, el rendimiento final del código idiomático 'vida real (TM)' en un entorno de producción, con una configuración de compilador predecible a priori).

por ejemplo, las presentaciones de Haskell para el infame juego de pruebas de lenguaje de computadora (por malo que sea, pero no es que haya, por el momento, algo significativamente mejor por ahí) dan la impresión de que se ha invertido una cantidad significativa de tiempo en Las optimizaciones manuales, que se enfrentan a la afirmación sobre "posibles optimizaciones del compilador debido a insert some property about FP languages here", hacen que parezca que las optimizaciones son (al menos actualmente) más una posibilidad teórica que una realidad relevante.

Sin embargo, me alegraría que se demuestre que estoy equivocado en este punto.

Alexander Battisti
fuente
1
La razón de las optimizaciones manuales en Haskell tiene más que ver con el hecho de que ciertas operaciones "sencillas" son algo lentas (desde una perspectiva de complejidad) en Haskell. Por ejemplo, supongamos que desea obtener el último elemento de una lista. En Java, esa es una operación bastante simple; en Haskell, el enfoque ingenuo requiere que recorra toda la lista hasta llegar al final (debido a la naturaleza perezosa de las listas), lo que la convierte en una operación O (n). Que de (en parte), donde optimizaciones manuales vienen en.
mipadi
2
Estoy seguro de que hay razones válidas para las optimizaciones enrolladas a mano de Haskell, pero ser necesarias para operaciones "sencillas" da la impresión de que las mayores oportunidades para optimizar el código (actualmente) solo son relevantes en teoría.
Alexander Battisti
66
Es más la diferencia entre la optimización de algoritmos y la optimización del código generado. Tomemos un ejemplo de C: si estoy escribiendo un algoritmo de búsqueda, puedo escribir un algoritmo ingenuo que simplemente recorre una lista, o puedo usar la búsqueda binaria. En ambos casos, el compilador optimizará mi código, pero no convertirá un algoritmo de búsqueda ingenuo en una búsqueda binaria. Muchas de las optimizaciones manuales en el código Haskell tienen más que ver con la optimización de los algoritmos, en lugar de optimizar el código generado.
mipadi
2
@mipadi, pero parece que la versión sencilla del algoritmo de Haskell no es tan buena como la versión sencilla de los algoritmos de otros idiomas. (Sospecho que debido al desajuste entre el modelo funcional y la arquitectura de la computadora) Incluso si es bueno para generar código, no es suficiente para superar este problema.
Winston Ewert
>> malo como podría ser << - ¿Sabes si es malo o no? ¿Qué quieres decir con sugerir que es "malo"? Por favor sea especifico.
igouy
2

En estilo funcional, el flujo de valores a través de un programa es muy, muy visible (tanto para el compilador como para el programador). Esto le da al compilador mucha libertad de acción para decidir dónde almacenar los valores, cuánto tiempo mantenerlos, etc.

En un lenguaje imperativo, el compilador promete al programador un modelo en el que la mayoría de las variables corresponden a ubicaciones reales en la memoria que permanecen durante una vida útil definida. Potencialmente, cualquier declaración puede leer (o escribir en) cualquiera de estas ubicaciones, por lo que el compilador solo puede reemplazar ubicaciones de memoria con asignación de registros, fusionar dos variables en una única ubicación de almacenamiento o realizar optimizaciones similares después de realizar un minucioso análisis de dónde más en el programa se puede hacer referencia a esa variable.

Ahora, hay dos advertencias:

  • La comunidad del lenguaje de programación ha dedicado (¿desperdiciado?) Un gran esfuerzo durante los últimos cincuenta años para desarrollar formas inteligentes de hacer este análisis. Hay trucos bien conocidos como el registro de colores y demás para hacer algunos de los casos más fáciles de hacer la mayor parte del tiempo; pero esto genera compiladores grandes y lentos, y una compensación constante de la complejidad de la compilación por la calidad del código resultante
  • Al mismo tiempo, la mayoría de los lenguajes de programación funcionales tampoco son puramente funcionales; muchos de los programas de realidad lo que tiene que hacer, al igual que responden a E / S son inherentemente no funcional, por lo que no compilador puede estar completamente libre de estos trucos, y hay un lenguaje que evita por completo - incluso Haskell, que es un poco demasiado puro para mi gusto (Your Mileage May Vary) solo puede controlar y eliminar las partes no funcionales de su código, no evitarlas por completo.

Pero para responder a la pregunta general, sí, un paradigma funcional le da al compilador mucha libertad para optimizar que no tiene en un entorno imperativo.

jimwise
fuente
Todo en Haskell es funcional, es solo que maines una función de transformación de estado en lugar de algo que usa el estado en sí.
alternativa
Sí y no: conceptualmente, es bastante correcto decir que un programa Haskell es una función pura sobre las interacciones del usuario con ese programa (y el estado del generador de números aleatorios del sistema, y ​​la latencia de la red hoy en día, y cualquier otra inherentemente entradas no funcionales a las que responde el programa), pero en la práctica es una distinción sin diferencia.
jimwise
@jimwise La transparencia referencial es una gran diferencia.
alternativa
Excepto que realmente no lo tienes, al menos para el propósito discutido aquí. El punto de operaciones como IO, o generación de números aleatorios, es que deberían devolver un valor diferente cada vez que se invocan con las mismas entradas, y esto limita inherentemente el razonamiento sobre ellos funcionalmente, ya sea para el programador o el compilador.
jimwise
1
@mathepic Sí, por supuesto, puede ver conceptualmente la aleatoriedad o la entrada del usuario (o la latencia de la red o la carga del sistema) como una secuencia infinita o una función de estado a estado, pero no es una vista que se preste a un razonamiento útil sobre el comportamiento del programa al usted o su compilador: Bob Harper cubre este terreno bien en una publicación reciente en su blog sobre el nuevo plan de estudios de CS de programación funcional de CMU.
jimwise