Por cada función imperativa, ¿hay una contraparte funcional con un rendimiento idéntico o incluso instrucciones?

Question

Actualmente, no he aprendido sobre un lenguaje funcional que puede lograr el mismo rendimiento que C / C ++. Y he aprendido que algunos idiomas que favorecen la programación funcional a la programación imperativa, como Scala y Rust, usan formas imperativas de implementar sus funciones de biblioteca para una mejor eficiencia.

Así que aquí llega mi pregunta, en los comptuters de hoy que ejecutan instrucciones imperativas, ¿es esta una limitación del compilador o la programación funcional? Por cada función imperativa sin efectos secundarios, ya sea en un idioma sin GC, como C / C ++ / óxido / ensamblaje o uno con GC, como Java, hay una contraparte funcional pura en Haskell, Scala, etc. que se puede compilar a Ejecutar con un rendimiento idéntico en el tiempo y el espacio (no solo asintóticos sino exactamente iguales) o incluso a las mismas instrucciones, con un compilador funcional óptimo que utiliza todas las técnicas de optimización modernas e incluso desconocidas, como la recursión de la cola, la pereza, el análisis estático, la verificación formal. , ¿y así sucesivamente?

Soy consciente de la equivalencia entre λ-computable y Turing computable, pero pero no pude encontrar una respuesta a esta pregunta en línea. Si hay, por favor, comparta un ejemplo del compilador o una prueba. Si no, por favor explique por qué y muestre un contador. ¿O es una pregunta abierta no trivial?

---

Ediciones complementarias según lo sugerido por Andrej Bauer :

Para ser más específicos, aquí hay 2 ejemplos que llevaron a pensar en esta pregunta.

Por ejemplo, la recursión de la cola y los acumuladores pueden mejorar el desempeño de algunas funciones recursivas para ser idénticas a una implementación imperativa utilizando for. En algunos casos, incluso pueden tener las mismas instrucciones.

Otro ejemplo es sobre la pereza en Haskell. La pereza puede ayudar a evitar la copia innecesaria de las estructuras de datos y mejorar el rendimiento. Sin embargo, la pereza deja las envolturas, los cierres, etc. en el tiempo de ejecución y aún no pueden hacer que el programa sea tan rápido como una implementación imperativa donde no haya tales cosas. Así que me pregunto si tales cosas se pueden quitar de manera estática antes del tiempo de ejecución durante la compilación.

Ediciones complementarias según lo sugerido por cercao :

La pregunta también se puede establecer de esta manera: existe un lenguaje que admite tanto la programación funcional y la programación imperativa, emparejada con un compilador optimizado, en el que cada función sin efectos secundarios implementados implementados puede ser reemplazada por un implementado puramente funcionalmente, sin costo de rendimiento o incluso compilado en las mismas instrucciones?

Answer 1

1. El rendimiento no es una propiedad del idioma, es una propiedad de programas específicos dentro de un idioma. Algunos idiomas pueden ser muy rápidos en algunas cosas y lentamente en otros.

   Por ejemplo, Chez-Scheme a veces puede encontrar el rendimiento comparable a C, no porque el idioma sea más eficiente, sino porque las prácticas defensivas que los programadores a menudo usan en C son menos necesarios en el esquema.

   Igualmente, hay momentos en que Haskell puede hacer un paralelismo o concurrencia muy eficiente, no porque sea más rápido que C, sino porque las garantías de inmutabilidad del lenguaje permiten al programador evitar cosas como cerraduras y otras técnicas de sincronización.

   y, el rendimiento varía de la implementación a la implementación. Puedo rodar a mano un intérprete C, pero ciertamente no será rápido. C no es rápido, GCC y Clang son.

2. ¿Qué se considera un lenguaje "funcional"? Cada lenguaje funcional práctico tiene algunas instalaciones para el estado mutable: Ocaml, Haskell, Scala, Lisp, esquema, etc. La recursión de la cola le da a algo aproximadamente equivalente a la mutación dentro de un bucle for a. Pero cuando esto no es suficiente, los idiomas funcionales le dan al programador acceso al estado mutable. En el caso de Haskell, esto está controlado por el sistema de tipo, por lo que nunca hay Estado mutable implícito , pero la mutación está muy permitida e incluso alentada en Haskell. Mira cualquier código Haskell, y verás el Io Monad en todas partes. Del mismo modo, las lenguas ML distinguen entre tipos generadores de T y ref T, por lo que puede decir los tipos de si una variable es mutable o no.

3. No hay un compilador "óptimo", gracias al teorema del arroz. Todos los compiladores, imperativos o funcionales, son "mejores esfuerzos:" Las aproximaciones conservadoras de uso para optimizar el código.

   Si tuvimos un compilador óptimo, la respuesta sería que todos los programas siempre corrían usando las instrucciones más eficientes posible, y no importaría qué idioma codificó su problema. La secuencia óptima de instrucciones que computan un problema no hace un problema. Depende del idioma de origen. Pero si tuviéramos esto, este compilador compilaría cada programa que no hubiera hallo en while(0), lo que significa que podríamos detectar programas que no se detecten, lo que es imposible.

4. para las máquinas de Turing y el cálculo Lambda, creo que es bastante trivial implementar un intérprete de cálculo de lambda para las máquinas de Turing que es asintóticamente equivalente a una máquina de Turing-Turing Universal. La complejidad de BIG-O no es lo que la gente quiere decir cuando dicen "los idiomas funcionales son lentos". Por lo general, están hablando de la cabeza constante, que es muy diferente. No tenemos una buena cantidad de maneras de modelar matemáticamente esto, por lo que normalmente terminamos utilizando experimentos para medir el rendimiento preciso.