haskell - caracteristicas - perezoso nombre cientifico

Haskell: ¿En qué se diferencian los no estrictos y los perezosos?

Question

A menudo leo que perezoso no es lo mismo que no estricto, pero me cuesta entender la diferencia. Parece que se usan indistintamente, pero entiendo que tienen diferentes significados. Apreciaría algo de ayuda para entender la diferencia.

Tengo algunas preguntas que están dispersas sobre esta publicación. Resumiré esas preguntas al final de esta publicación. Tengo algunos fragmentos de ejemplo, no los probé, solo los presenté como conceptos. He agregado citas para evitar que las busque. Tal vez ayudará a alguien más adelante con la misma pregunta.

Def no estricto:

Se dice que una función f es estricta si, cuando se aplica a una expresión no determinante, tampoco termina. En otras palabras, f es estricto si el valor de f bot es | . Para la mayoría de los lenguajes de programación, todas las funciones son estrictas. Pero esto no es así en Haskell. Como un ejemplo simple, considere const1, la función constante 1, definida por:

const1 x = 1

El valor de const1 bot en Haskell es 1. Operativamente hablando, dado que const1 no "necesita" el valor de su argumento, nunca intenta evaluarlo y, por lo tanto, nunca queda atrapado en un cálculo no determinante. Por esta razón, las funciones no estrictas también se denominan "funciones diferidas" y se dice que evalúan sus argumentos "por pereza" o "por necesidad".

- Una introducción suave a Haskell: funciones

Me gusta mucho esta definición. Parece el mejor que pude encontrar para entender estricto. ¿Es const1 x = 1 flojo también?

No rigurosidad significa que la reducción (el término matemático para la evaluación) procede del exterior en,

entonces si tienes (a + (b c)) entonces primero reduces el +, luego reduces el interior (b c).

- Haskell Wiki: Lavy vs no estricto

El Wiki Haskell realmente me confunde. Entiendo lo que dicen sobre el pedido, pero no veo cómo (a+(b*c)) evaluaría de forma no estricta si fue aprobado _|_ ?

En una evaluación no estricta, los argumentos para una función no se evalúan a menos que realmente se utilicen en la evaluación del cuerpo de la función.

Bajo la codificación de la Iglesia, la evaluación perezosa de los operadores asigna a la evaluación no estricta de las funciones; por esta razón, la evaluación no estricta a menudo se denomina "floja". Las expresiones booleanas en muchos idiomas usan una forma de evaluación no estricta llamada evaluación de cortocircuito, donde la evaluación retorna tan pronto como se puede determinar que resultará un booleano no ambiguo, por ejemplo, en una expresión disyuntiva donde se encuentra verdadero, o en una expresión conjuntiva donde se encuentra falso, y así sucesivamente. Las expresiones condicionales también suelen usar evaluación diferida, donde la evaluación retorna tan pronto como se produce una rama inequívoca.

- Wikipedia: Estrategia de evaluación

Lazy Def:

La evaluación diferida, por otro lado, significa solo evaluar una expresión cuando sus resultados son necesarios (nótese el cambio de "reducción" a "evaluación"). Entonces, cuando el motor de evaluación ve una expresión, crea una estructura de datos thunk que contiene los valores necesarios para evaluar la expresión, más un puntero a la expresión misma. Cuando el resultado es realmente necesario, el motor de evaluación llama a la expresión y luego reemplaza el procesador con el resultado para referencia futura. ...

Obviamente, existe una gran correspondencia entre un thunk y una expresión parcialmente evaluada. Por lo tanto, en la mayoría de los casos, los términos "perezoso" y "no estricto" son sinónimos. Pero no del todo.

- Haskell Wiki: Lavy vs no estricto

Esto parece una respuesta específica de Haskell. Tomo que perezoso significa thunks y no estricto significa evaluación parcial. ¿Es esa comparación demasiado simplificada? ¿La pereza siempre significa que los thunks y los no estrictos siempre significan una evaluación parcial?

En la teoría del lenguaje de programación, la evaluación diferida o llamada por necesidad 1 es una estrategia de evaluación que retrasa la evaluación de una expresión hasta que realmente se requiera su valor (evaluación no estricta) y también evita las evaluaciones repetidas (intercambio).

- Wikipedia: Evaluación Lazy

Ejemplos imperativos

Sé que la mayoría de la gente dice que olvide la programación imperativa cuando aprenda un lenguaje funcional. Sin embargo, me gustaría saber si estos califican como no estrictos, perezosos, ambos o ninguno? Por lo menos, proporcionaría algo familiar.

Cortocircuito

f1() || f2()

C #, Python y otros lenguajes con "rendimiento"

public static IEnumerable Power(int number, int exponent)
{
    int counter = 0;
    int result = 1;
    while (counter++ < exponent)
    {
        result = result * number;
        yield return result;
    }
}

- MSDN: rendimiento (c #)

Devolución de llamada

int f1() { return 1;}
int f2() { return 2;}

int lazy(int (*cb1)(), int (*cb2)() , int x) {
    if (x == 0)
        return cb1();
    else
        return cb2();
}

int eager(int e1, int e2, int x) {
    if (x == 0)
         return e1;
    else
         return e2;
}

lazy(f1, f2, x);
eager(f1(), f2(), x);

Preguntas

Sé que la respuesta está justo frente a mí con todos esos recursos, pero no puedo entenderlo. Parece que la definición se descarta fácilmente como implícita u obvia.

Sé que tengo muchas preguntas. Siéntase libre de responder cualquier pregunta que considere relevante. Agregué esas preguntas para la discusión.

• ¿Es const1 x = 1 también flojo?
• ¿Cómo es la evaluación desde "adentro" no estricta? ¿Es porque adentro permite reducciones de expresiones innecesarias, como en const1 x = 1 ? Las reducciones parecen ajustarse a la definición de perezoso.
• ¿La pereza siempre significa " thunks" y " no estricta" significa siempre una evaluación parcial ? ¿Es esto solo una generalización?
• ¿Los siguientes conceptos imperativos son perezosos, no estrictos, ambos o ninguno?
  • Cortocircuito
  • Usando rendimiento
  • Pasar devoluciones de llamada para retrasar o evitar la ejecución
• Es un subconjunto perezoso de no estricto o viceversa, o son mutuamente excluyentes. Por ejemplo, ¿es posible ser no estricto sin ser perezoso o perezoso sin ser no estricto ?
• ¿Es el no-rigor de Haskell alcanzado por la pereza?

¡Gracias SO!

Answer 1

Esto comenzó como una actualización, pero comenzó a ser largo.

La pereza / Call-by-need es una versión memorada de call-by-name donde, si se evalúa el argumento de la función, ese valor se almacena para usos posteriores. En una configuración "pura" (sin efectos), esto produce los mismos resultados que llamada por nombre; cuando el argumento de la función se usa dos o más veces, la llamada por necesidad es casi siempre más rápida.
Ejemplo Imperativo - Aparentemente esto es posible. Hay un interesante artículo sobre Lazy Imperative Languages . Dice que hay dos métodos. Uno requiere cierres, el segundo usa reducciones gráficas. Como C no admite cierres, necesitarás pasar explícitamente un argumento a tu iterador. Puede envolver una estructura de mapa y, si el valor no existe, calcular de otra forma el valor devuelto.
Nota : Haskell implementa esto mediante "punteros al código que se reemplazan por un valor la primera vez que se ejecutan" - luqui.
Esta es una llamada por nombre no estricta, pero con intercambio / memorización de los resultados.

Llamada por nombre: en la evaluación de llamada por nombre, los argumentos para una función no se evalúan antes de que se llame a la función, sino que se sustituyen directamente en el cuerpo de la función (utilizando sustitución que evita la captura) y luego se deja evaluados cada vez que aparecen en la función. Si un argumento no se usa en el cuerpo de la función, el argumento nunca se evalúa; si se usa varias veces, se vuelve a evaluar cada vez que aparece.
Ejemplo imperativo: devoluciones de llamada
Nota: Esto no es estricto ya que evita la evaluación si no se usa.

No estricto = En una evaluación no estricta, los argumentos a una función no se evalúan a menos que realmente se utilicen en la evaluación del cuerpo de la función.
Ejemplo imperativo : cortocircuito
Nota : _ | _ parece ser una forma de comprobar si una función no es estricta

Entonces una función puede ser no estricta pero no floja. Una función que es floja es siempre no estricta. Call-by-Need se define en parte por Call-By-Name que está parcialmente definido por Non-Strict

Un extracto de "Lenguas Imperativas Lacias"

2.1. SEMÁNTICA NO ESTRICTA VS. EVALUACIÓN PERJUDICIAL Primero debemos aclarar la distinción entre "semántica no estricta" y "evaluación perezosa". Las semánticas no estrictas son aquellas que especifican que una expresión no se evalúa hasta que una operación primitiva lo necesite. Puede haber varios tipos de semántica no estricta. Por ejemplo, las llamadas de procedimiento no estrictas no evalúan los argumentos hasta que se requieren sus valores. Los constructores de datos pueden tener una semántica no estricta, en la que los datos compuestos se ensamblan a partir de piezas no evaluadas. La evaluación diferida, también llamada evaluación diferida, es la técnica que normalmente se usa para implementar una semántica no estricta. En la sección 4, los dos métodos comúnmente utilizados para implementar la evaluación diferida son muy brevemente resumidos.

LLAMAR POR VALOR, LLAMAR POR RETRASO Y LLAMAR POR NOMBRE "Llamar por valor" es el nombre general usado para llamadas de procedimiento con semántica estricta. En call por valuelanguages, cada argumento de una llamada de procedimiento se evalúa antes de realizar la llamada de procedimiento; el valor se pasa al procedimiento o a la expresión que lo rodea. Otro nombre para llamar por valor es evaluación "ansiosa". La llamada por valor también se conoce como evaluación de "orden de aplicación", porque todos los argumentos se evalúan antes de que se les aplique la función. "Llamar por perezoso" (usando la terminología de William Clinger en [8] ]) es el nombre dado a las llamadas a procedimientos que usan una semántica estricta. En los lenguajes con llamadas de llamada por procedimiento diferido, los argumentos no se evalúan antes de ser sustituidos en el cuerpo del procedimiento. La evaluación Call by perezoso también se conoce como evaluación de "orden normal", debido al orden (más externo a más interno, de izquierda a derecha) de la evaluación de una expresión. "Call by name" es una implementación particular de call by perez, utilizada en Algol -60 [18]. Los diseñadores de Algol-60 pretendían que los parámetros de llamada por nombre se sustituyeran físicamente en el cuerpo del procedimiento, entre paréntesis y con cambios de nombre adecuados para evitar conflictos, antes de que se evaluara el cuerpo.

LLAMAR POR LAZY VS. LLAMAR POR NECESIDAD La llamada por necesidad es una extensión de llamada por pereza, provocada por la observación de que una evaluación diferida podría optimizarse recordando el valor de una expresión demorada determinada, una vez forzada, de modo que no es necesario volver a calcular el valor si se necesita nuevamente. La evaluación de llamada por necesidad, por lo tanto, amplía la llamada por métodos perezosos mediante el uso de la memoria para evitar la necesidad de una evaluación repetida. Friedman y Wise se encontraban entre los principales defensores de la evaluación llamada por necesidad, proponiendo "suspensiones suicidas" que se autodestruyeron cuando se evaluaron por primera vez, reemplazándose con sus valores.

Answer 2

No estricto y perezoso, aunque informalmente intercambiable, se aplica a diferentes dominios de discusión.

No estricto se refiere a la semantics : el significado matemático de una expresión. El mundo al que se aplica no estricto no tiene ningún concepto del tiempo de ejecución de una función, el consumo de memoria o incluso una computadora. Simplemente habla sobre qué tipos de valores en el mapa de dominio a qué tipos de valores en el codominio. En particular, una función estricta debe mapear el valor ⊥ ("abajo" - ver el enlace semántico arriba para más información sobre esto) a ⊥; una función no estricta está permitida para no hacer esto.

Lazy se refiere al comportamiento operativo: la forma en que se ejecuta el código en una computadora real. La mayoría de los programadores piensan en los programas operacionalmente, por lo que esto es probablemente lo que estás pensando. La evaluación diferida se refiere a la implementación mediante thunks: punteros al código que se reemplazan por un valor la primera vez que se ejecutan. Observe las palabras no semánticas aquí: "puntero", "primera vez", "ejecutado".

La evaluación diferida da lugar a una semántica no estricta, por lo que los conceptos parecen estar muy juntos. Pero como señala FUZxxl, la pereza no es la única forma de implementar una semántica no estricta.

Si está interesado en aprender más sobre esta distinción, le recomiendo el enlace de arriba. Leerlo fue un punto de inflexión en mi concepción del significado de los programas de computadora.

Answer 3

Sí, aquí hay un uso poco claro de la terminología, pero los términos coinciden en la mayoría de los casos independientemente, por lo que no es un gran problema.

Una diferencia importante es cuando se evalúan los términos . Existen múltiples estrategias para esto, que van desde un espectro "lo más pronto posible" hasta "solo en el último momento". El término evaluación ansiosa a veces se usa para estrategias que se inclinan hacia el primero, mientras que la evaluación perezosa se refiere a una familia de estrategias que se inclina fuertemente hacia el segundo. La distinción entre la "evaluación perezosa" y las estrategias relacionadas tienden a involucrar cuándo y dónde se retiene el resultado de evaluar algo, en lugar de arrojarlo a un lado. La técnica familiar de memorización en Haskell de asignar un nombre a una estructura de datos e indexarla se basa en esto. Por el contrario, un lenguaje que simplemente empalma expresiones entre sí (como en la evaluación "llamada por nombre") podría no ser compatible con esto.

La otra diferencia es qué términos se evalúan , que van desde "absolutamente todo" a "lo menos posible". Como ningún valor realmente utilizado para calcular el resultado final no se puede ignorar, la diferencia aquí es cuántos términos superfluos se evalúan. Además de reducir la cantidad de trabajo que el programa tiene que hacer, ignorar los términos no utilizados significa que no se producirán los errores que hubieran generado. Cuando se hace una distinción, el rigor se refiere a la propiedad de evaluar todo lo considerado (en el caso de una función estricta, por ejemplo, esto significa los términos a los que se aplica. No necesariamente significa sub-expresiones dentro de los argumentos) , aunque no estricto significa evaluar solo algunas cosas (ya sea retrasando la evaluación o descartando los términos por completo).

Debería ser fácil ver cómo estos interactúan de maneras complicadas; las decisiones no son en absoluto ortogonales, ya que los extremos tienden a ser incompatibles. Por ejemplo:

• Una evaluación muy estricta impide cierta ansiedad; si no sabe si se necesitará un término, no puede evaluarlo todavía.

• Una evaluación muy estricta hace que el no afán sea algo irrelevante; Si está evaluando todo, la decisión de cuándo hacerlo es menos importante.

Sin embargo, existen definiciones alternativas. Por ejemplo, al menos en Haskell, una "función estricta" se define a menudo como aquella que fuerza sus argumentos lo suficiente como para que la función evalúe | cada vez que cualquier argumento lo hace; tenga en cuenta que según esta definición, id es estricta (en un sentido trivial), porque forzar el resultado de id x tendrá exactamente el mismo comportamiento que forzar x solo.

Answer 4

Si hablamos de jerga general de informática, entonces "perezoso" y "no estricto" son generalmente sinónimos: representan la misma idea general, que se expresa de diferentes maneras para diferentes situaciones.

Sin embargo, en un contexto particular particular especializado, pueden haber adquirido diferentes significados técnicos. No creo que puedas decir algo preciso y universal sobre cuál es la diferencia entre "perezoso" y "no estricto" en la situación donde hay una diferencia que hacer.

Answer 5

Un ejemplo para un modelo de evaluación, que no es ni estricto ni perezoso: una evaluación optimista , que da un poco de aceleración, ya que puede evitar una gran cantidad de errores "fáciles":

La evaluación optimista significa que, incluso si una subexpresión puede no ser necesaria para evaluar la superexpresión, aún evaluamos parte de ella utilizando alguna heurística. Si la subexpresión no termina lo suficientemente rápido, suspendemos su evaluación hasta que realmente se necesite. Esto nos da una ventaja sobre la evaluación lenta si la subexpresión se necesita más tarde, ya que no necesitamos generar un procesador. Por otro lado, no perdemos demasiado si la expresión no finaliza, ya que podemos abortar lo suficientemente rápido.

Como puede ver, este modelo de evaluación no es estricto : si se evalúa algo que arroja _ | _, pero no es necesario, la función aún terminará, ya que el motor aborta la evaluación. Por otro lado, es posible que se evalúen más expresiones de las necesarias, por lo que no es completamente vago .