¿Cuál es el uso práctico de la pereza como función incorporada de lenguaje?

Question

Es bastante obvio por qué un lenguaje de programación funcional que quiere ser perezoso debe ser puro. Estoy viendo la pregunta inversa: si un idioma quiere ser puro, ¿hay una gran ventaja en ser flojo? Un argumento, hecho por uno de los diseñadores de Haskell, es que elimina la tentación; tal vez, pero estoy tratando de sopesar las ventajas más concretas.

Dado que desea hacer una programación funcional, ¿en qué casos la pereza incorporada le permite expresar las cosas de forma más clara, simple o concisa?

Dicho simplemente: ¿Por qué es la pereza tan importante que desea construirla en el idioma?

_{(estoy en busca de casos de uso más orientadas hacia una aplicación más que una demo - Sé que usted puede hacer cosas como la producción de una lista infinita de números primos al filtrar una lista infinita de números naturales, pero que escribe que plano almuerzo diez veces' ...)}

Answer 1

"Nada se evalúa hasta que se necesita en otro lugar" es una metáfora simplificada que no cubre todos los aspectos de la evaluación perezosa (por ejemplo, no menciona los fenómenos de rigurosidad).

Desde el punto de vista teórico, hay 3 maneras de hacerlo cuando se diseña un lenguaje puro (por supuesto, si se basa en algún tipo de cálculo lambda y no en modelos de evaluación más exóticos): estricto, no estricto y total.

Cada uno de ellos tiene sus ventajas y desventajas, por lo que debe leer los trabajos de investigación correspondientes.

El total de idiomas son puros de los tres. En los otros dos, la no terminación se puede ver como un efecto secundario, por lo que los analizadores de rigor y de totalidad deben construirse para mantener una implementación eficiente. Ambos análisis son indecidibles, por lo que los analizadores nunca pueden ser completos.

Sin embargo, el total de idiomas es menos expresivo: es imposible completar un total de idioma. Un enfoque frecuente para obtener una expresividad suficientemente buena es tener un sistema de prueba integrado para la recursión bien fundamentada, que no es mucho más fácil de construir que los analizadores para lenguajes no totales.

Desde el punto de vista práctico, la semántica no estricta le permite definir más fácilmente las abstracciones de control, ya que las estructuras de control son esencialmente no estrictas. En un lenguaje estricto, todavía necesita algunos lugares con semántica no estricta. P.ej. La construcción if tiene una semántica no estricta incluso en lenguajes estrictos.

Si su lenguaje es estricto, las estructuras de control son un caso especial. En contraste, un lenguaje no estricto puede ser uniformemente no estricto, no tiene una necesidad inherente en construcciones estrictas.

En cuanto a "quién escribe ese diez veces antes del almuerzo" - cualquiera que use Haskell para sus proyectos lo hace. Creo que desarrollar un proyecto que no sea de juguete usando un lenguaje (un lenguaje no estricto en su caso) es una mejor manera de comprender sus ventajas y desventajas.

continuación se presentan algunos casos de uso genérico para la pereza ilustradas por ejemplos no juguete:

1. casos cuando el flujo de control es difícil de predecir. Piense en las gramáticas de atributos cuando, sin pereza, debe realizar una clasificación topológica de los atributos para resolver las dependencias. Reordenar su código cada vez que se cambia el gráfico de dependencia no es práctico. En Haskell puede implementar el formalismo de gramática de atributos sin una clasificación explícita, y hay al menos dos implementaciones reales en Hackage. Las gramáticas de atributos tienen una amplia aplicación en la construcción de compiladores.

2. El enfoque "generar y buscar" para resolver muchos problemas de optimización. En un lenguaje estricto, debe intercalar generación y búsqueda, en Haskell solo crea funciones de búsqueda y generación separadas, y su código permanece sintácticamente modular, pero intercalado en tiempo de ejecución. Piense en el problema del vendedor ambulante (TSP), cuando genera todos los recorridos posibles y luego busca a través de ellos usando un algoritmo de rama y límite. Tenga en cuenta que la ramificación de un algoritmo limitado solo inspecciona ciertas primeras ciudades de un recorrido, solo se generan las partes necesarias de las rutas. El TSP tiene varias aplicaciones incluso en su formulación más pura, como la planificación, la logística y la fabricación de microchips. Ligeramente modificado, aparece como un sub-problema en muchas áreas, como la secuenciación de ADN.

3. código Lazy tiene flujo de control no modular, por lo que una sola función puede tener muchos flujos de control posibles, dependiendo del entorno en el que se ejecuta en. Este fenómeno puede ser visto como una especie de 'polimorfismo flujo de control', control tan perezoso las abstracciones de flujo son más genéricas que sus contrapartes estrictas, y una biblioteca estándar de funciones de orden superior es mucho más útil en un lenguaje perezoso. Piense en generadores, bucles e iteradores de listas de Python: en la lista de Haskell, las funciones cubren los tres casos de uso, con flujo de control que se adapta a diferentes escenarios de uso debido a la pereza. No está limitado a las listas: piense en Data.Arrow e iteratees, versiones perezosas y estrictas de State monad, etc. También tenga en cuenta que el flujo de control no modular es una ventaja y una desventaja, ya que dificulta el razonamiento sobre el rendimiento.

4. Las estructuras de datos perezosas posiblemente infinitas son útiles más allá de los ejemplos de juguetes. Vea trabajos de Conal Elliott sobre cómo memorizar funciones de orden superior usando tries. Las estructuras de datos infinitas aparecen como espacios de búsqueda infinitos (ver 2), bucles infinitos y generadores que nunca agotan en el sentido de Python (ver 3).

Answer 2

Mac OS X Core imagen es un buen ejemplo práctico de la evaluación perezosa.

Básicamente, Core Image le permite crear un gráfico acíclico dirigido de generadores de imágenes y filtros. En realidad, no se realiza ninguna evaluación hasta el último paso del proceso: materialización. Cuando solicita materializar un gráfico de Imagen Principal, el marco de imagen final se propaga hacia atrás a través de las transformaciones del gráfico, minimizando así la cantidad de valores reales de píxeles que deben evaluarse.

Answer 3

Hay una extensa discusión de este punto en el clásico de Hughes Why Functional Programming Matters. En esto, Hughes argumenta que la pereza permite una modularidad mejorada, usando una cantidad de ejemplos accesibles.