Eficiencia de la progtwigción puramente funcional

¿Alguien sabe cuál es la peor desaceleración asintótica posible que puede ocurrir cuando se progtwig de forma puramente funcional en lugar de imperativa (es decir, permitiendo efectos secundarios)?

Aclaración del comentario de itowlson : ¿hay algún problema para el cual el algoritmo no destructivo mejor conocido sea asintóticamente peor que el algoritmo destructivo más conocido y, de ser así, en qué medida?

Según Pippenger [1996] , cuando se compara un sistema Lisp que es puramente funcional (y tiene una semántica de evaluación estricta, no floja) con uno que puede mutar datos, se puede traducir un algoritmo escrito para el Lisp impuro que se ejecuta en O ( n ) a un algoritmo en el Lisp puro que se ejecuta en el tiempo O ( n log n ) (basado en el trabajo de Ben-Amram y Galil [1992] sobre la simulación de memoria de acceso aleatorio usando solo punteros). Pippenger también establece que hay algoritmos para los cuales eso es lo mejor que puedes hacer; hay problemas que son O ( n ) en el sistema impuro que son Ω ( n log n ) en el sistema puro.

Hay algunas advertencias sobre este documento. Lo más significativo es que no aborda los lenguajes funcionales perezosos, como Haskell. Bird, Jones y De Moor [1997] demuestran que el problema construido por Pippenger se puede resolver en un lenguaje funcional perezoso en el tiempo O ( n ), pero no establecen (y hasta donde yo sé, nadie) si o no un lenguaje funcional perezoso puede resolver todos los problemas en el mismo tiempo de ejecución asintótico como un lenguaje con mutación.

El problema construido por Pippenger requiere que Ω ( n log n ) se construya específicamente para lograr este resultado, y no es necesariamente representativo de problemas prácticos del mundo real. Hay algunas restricciones sobre el problema que son un poco inesperadas, pero necesarias para que la prueba funcione; en particular, el problema requiere que los resultados se computen en línea, sin poder acceder a entradas futuras, y que la entrada consista en una secuencia de átomos de un conjunto ilimitado de átomos posibles, en lugar de un conjunto de tamaño fijo. Y el documento solo establece resultados (límite inferior) para un algoritmo impuro de tiempo de ejecución lineal; para problemas que requieren un mayor tiempo de ejecución, es posible que el factor adicional O (log n ) visto en el problema lineal pueda ser “absorbido” en el proceso de operaciones adicionales necesarias para algoritmos con tiempos de ejecución mayores. Ben-Amram explora brevemente estas aclaraciones y preguntas abiertas [1996] .

En la práctica, muchos algoritmos pueden implementarse en un lenguaje funcional puro con la misma eficacia que en un lenguaje con estructuras de datos mutables. Para una buena referencia sobre las técnicas a utilizar para implementar estructuras de datos puramente funcionales de manera eficiente, vea “Estructuras de datos puramente funcionales” de Chris Okasaki [Okasaki 1998] (que es una versión ampliada de su tesis [Okasaki 1996] ).

Cualquiera que necesite implementar algoritmos en estructuras de datos puramente funcionales debería leer Okasaki. Siempre se puede obtener, en el peor de los casos, una ralentización O (log n ) por operación simulando la memoria mutable con un árbol binario equilibrado, pero en muchos casos se puede hacer mucho mejor que eso, y Okasaki describe muchas técnicas útiles, desde técnicas amortizadas hasta reales. los que hacen el trabajo amortizado de manera incremental. Las estructuras de datos puramente funcionales pueden ser un poco difíciles de trabajar y analizar, pero ofrecen muchos beneficios, como la transparencia referencial, que son útiles para la optimización del comstackdor, la computación distribuida y paralela y la implementación de características como control de versiones, deshacer y deshacer.

Tenga en cuenta también que todo esto discute solo tiempos de ejecución asintóticos. Muchas técnicas para implementar estructuras de datos puramente funcionales le dan una cierta cantidad de desaceleración constante de los factores, debido a la contabilidad adicional necesaria para que funcionen, y los detalles de implementación del lenguaje en cuestión. Los beneficios de las estructuras de datos puramente funcionales pueden superar estas reducciones constantes de los factores, por lo que generalmente tendrá que hacer concesiones en función del problema en cuestión.

Referencias

  • Ben-Amram, Amir y Galil, Zvi 1992. “En punteros versus direcciones” Revista de la ACM, 39 (3), pp. 617-648, julio de 1992
  • Ben-Amram, Amir 1996. “Notas sobre la comparación de Pippenger de Pure y Impure Lisp” manuscrito no publicado, DIKU, Universidad de Copenhague, Dinamarca
  • Bird, Richard, Jones, Geraint y De Moor, Oege 1997. “Más prisa, menos velocidad: evaluación vaga versus ansiosa” Revista de progtwigción funcional 7, 5 págs. 541-547, septiembre de 1997
  • Okasaki, Chris 1996. Tesis doctoral “Estructuras de datos puramente funcionales” , Universidad Carnegie Mellon
  • Okasaki, Chris 1998. “Estructuras de datos puramente funcionales” Cambridge University Press, Cambridge, Reino Unido
  • Pippenger, Nicholas 1996. Simposio ACM “Pure Versus Impure Lisp” sobre Principios de lenguajes de progtwigción, páginas 104-109, enero de 1996

De hecho, hay varios algoritmos y estructuras de datos para los que no se conoce ninguna solución puramente funcional asintóticamente eficiente (una implementable en cálculo lambda puro), incluso con pereza.

  • El sindicato antes mencionado
  • Tablas hash
  • Arrays
  • Algunos algoritmos de gráficos

Sin embargo, suponemos que en lenguajes “imperativos” el acceso a la memoria es O (1) mientras que en teoría eso no puede ser tan asintótico (es decir, para tamaños ilimitados de problemas) y el acceso a memoria dentro de un gran conjunto de datos es siempre O (log n) , que se puede emular en un lenguaje funcional.

Además, debemos recordar que en realidad todos los lenguajes funcionales modernos proporcionan datos mutables, y Haskell incluso lo proporciona sin sacrificar la pureza (la mónada ST).

Este artículo afirma que las implementaciones puramente funcionales conocidas del algoritmo de búsqueda de unión tienen una complejidad asintótica peor que la que publican, que tiene una interfaz puramente funcional pero que utiliza datos mutables internamente.

El hecho de que otras respuestas afirman que nunca puede haber ninguna diferencia y que, por ejemplo, el único “inconveniente” del código puramente funcional es que puede ser paralelizado, le da una idea de la información / objetividad de la comunidad de progtwigción funcional en estos asuntos .

EDITAR:

Los comentarios a continuación señalan que una discusión tendenciosa de los pros y los contras de la progtwigción funcional pura no puede provenir de la “comunidad de progtwigción funcional”. Buen punto. Quizás los defensores que veo son justos, para citar un comentario, “analfabetos”.

Por ejemplo, creo que esta publicación de blog está escrita por alguien que podría decirse que es representativo de la comunidad de progtwigción funcional, y dado que es una lista de “puntos para la evaluación perezosa”, sería un buen lugar para mencionar cualquier inconveniente que progtwigción perezosa y puramente funcional podría tener. Un buen lugar habría sido el reemplazo del siguiente (técnicamente cierto, pero sesgado hasta el punto de no ser divertido):

Si una función estricta tiene O (f (n)) complejidad en un lenguaje estricto, entonces tiene complejidad O (f (n)) en un lenguaje perezoso también. ¿Por que preocuparse? 🙂

Con un límite superior fijo en el uso de la memoria, no debería haber diferencia.

Esquema de prueba: dado un límite superior fijo en el uso de la memoria, uno debería poder escribir una máquina virtual que ejecute un conjunto de instrucciones imperativas con la misma complejidad asintótica que si realmente estuviera ejecutando en esa máquina. Esto es así porque puede administrar la memoria mutable como una estructura de datos persistente, dando a O (log (n)) lecturas y escrituras, pero con un límite superior fijo en el uso de la memoria, puede tener una cantidad fija de memoria, haciendo que estos decaimiento a O (1). Por lo tanto, la implementación funcional puede ser la versión imperativa que se ejecuta en la implementación funcional de la máquina virtual, por lo que ambas deben tener la misma complejidad asintótica.

Sugeriría leer sobre el rendimiento de Haskell , y luego echar un vistazo a las representaciones de los juegos de prueba para lenguajes funcionales vs. procedimientos / OO.

“Funcional” es un grupo de características diferentes, cada una de las cuales es útil independientemente, y se encuentra más útil para ver cada una de ellas individualmente.

Inmutabilidad

Ahora que estoy familiarizado con él, cada vez que puedo salir con la devolución de un resultado inmutable, siempre trato de hacerlo, incluso en un progtwig orientado a objetos. Es más fácil razonar sobre el progtwig si tiene datos de tipo de valor.

Funciones como tipos de primera clase

Lo que sea que quiera llamarlo, pasar delegates, acciones o funciones, es una forma muy práctica de resolver toda una clase de problemas del mundo real, como el “agujero en el patrón del medio”.

Poder componer funciones (por ejemplo, convertir Acción en solo una Acción también es bastante útil en algunos escenarios).

También deberíamos tener en cuenta la syntax de Lambda aquí, ya que solo obtendrá la syntax de Lambda cuando promocione funciones a tipos de primera clase. La syntax Lambda puede ser muy expresiva y concisa.

Mónadas

Esta es una construcción sutil pero muy poderosa. Es tan poderoso como la palabra clave yield utilizada para crear clases IEnumerable en C #. Básicamente, está construyendo una máquina de estado para usted bajo las sábanas, pero su lógica parece lineal.

Evaluación Lazy & Recursion

Los junté porque, aunque siempre están agrupados como características de la progtwigción funcional, se han abierto paso rápidamente en lenguajes por lo demás imperativos, y es difícil llamarlos más funcionales.

S-Expresiones

Supongo que no estoy seguro de dónde colocar esto, pero la capacidad de tratar el código no comstackdo como un objeto (e inspeccionarlo / modificarlo), como Lisp S-Expressions, o LINQ Expressions, es, de alguna manera, la herramienta más poderosa de progtwigción funcional. La mayoría de las nuevas interfaces “fluidas” de .NET y DSL utilizan una combinación de syntax lambda y expresiones LINQ para crear algunas API muy concisas. Sin mencionar Linq2Sql / Linq2Nhibernate donde su código C # se ejecuta “mágicamente” como SQL en lugar de como código C #.