programming languages - ten - ¿Qué es la llamada por necesidad?

top programming languages 2019

Question

Quiero saber lo que es llamada por necesidad.

Aunque busqué en wikipedia y lo encontré aquí: http://en.wikipedia.org/wiki/Evaluation_strategy , pero no pude entenderlo correctamente. Si alguien puede explicar con un ejemplo y señalar la diferencia con la llamada por valor, sería una gran ayuda.

Answer 1

Imagina una función:

fun add(a, b) {
  return a + b
}

Y luego lo llamamos:

 add(3 * 2, 4 / 2)

En un lenguaje de llamada por nombre, esto se evaluará de modo que:

1. a = 3 * 2 = 6
2. b = 4 / 2 = 2
3. return a + b = 6 + 2 = 8

La función devolverá el valor 8 .

En una llamada por necesidad (también llamada lenguaje perezoso) esto se evalúa así:

1. a = 3 * 2
2. b = 4 / 2
3. return a + b = 3 * 2 + 4 / 2

La función devolverá la expresión 3 * 2 + 4 / 2 . Hasta ahora casi no se han gastado recursos computacionales. La expresión completa se computará solo si se necesita su valor; digamos que queremos imprimir el resultado.

¿Por qué es esto útil? Dos razones. Primero, si accidentalmente incluye un código muerto, no pesa su programa y, por lo tanto, puede ser mucho más eficiente. En segundo lugar, permite hacer cosas geniales como el cálculo eficiente con listas infinitas:

fun takeFirstThree(list) {
  return [list[0], list[1], list[2]]
}

takeFirstThree([0 ... infinity])

Un lenguaje de llamada por nombre colgaría allí tratando de crear una lista desde 0 hasta el infinito. Un lenguaje perezoso simplemente devolverá [0,1,2] .

Answer 2

Supongamos que tenemos la función

square(x) = x * x

Y queremos evaluar el square(1+2) .

En call-by-value , hacemos

1. square(1+2)
2. square(3)
3. 3*3
4. 9

En llamada por nombre , hacemos

1. square(1+2)
2. (1+2)*(1+2)
3. 3*(1+2)
4. 3*3
5. 9

Note que ya que usamos el argumento dos veces, lo evaluamos dos veces. Eso sería un desperdicio si la evaluación del argumento tomara mucho tiempo. Ese es el problema que las correcciones de llamada por necesidad.

En Call-by-Need , hacemos algo como lo siguiente:

1. square(1+2)
2. let x = 1+2 in x*x
3. let x = 3 in x*x
4. 3*3
5. 9

En el paso 2, en lugar de copiar el argumento (como en llamada por nombre), le damos un nombre. Luego, en el paso 3, cuando notamos que necesitamos el valor de x , evaluamos la expresión para x . Sólo entonces sustituimos.

Por cierto, si la expresión del argumento produce algo más complicado, como un cierre, podría haber más cambios de orden para eliminar la posibilidad de copiar. Las reglas formales son algo complicadas de escribir.

Observe que "necesitamos" valores para los argumentos de operaciones primitivas como + y * , pero para otras funciones adoptamos el enfoque de "nombrar, esperar y ver". Diríamos que las operaciones aritméticas primitivas son "estrictas". Depende del lenguaje, pero generalmente la mayoría de las operaciones primitivas son estrictas.

Tenga en cuenta también que "evaluación" todavía significa reducir a un valor. Una llamada de función siempre devuelve un valor, no una expresión. (Una de las otras respuestas se equivocó). OTOH, los lenguajes perezosos generalmente tienen constructores de datos perezosos, que pueden tener componentes que se evalúan según la necesidad, es decir, cuando se extraen. Así es como puede tener una lista "infinita": el valor que devuelve es una estructura de datos perezosa. Pero la llamada por necesidad frente a la llamada por valor es un problema aparte de las estructuras de datos perezosas frente a las estrictas. Scheme tiene constructores de datos perezosos (flujos), aunque dado que Scheme es llamada por valor, los constructores son formas sintácticas, no funciones ordinarias. Y Haskell es llamada por nombre, pero tiene formas de definir tipos de datos estrictos.

Si ayuda a pensar en implementaciones, entonces una implementación de llamada por nombre es envolver cada argumento en un thunk; cuando se necesita el argumento, llama al procesador y usa el valor. Una implementación de Call-by- Need es similar, pero el thunk es la memorización; solo ejecuta el cálculo una vez, luego lo guarda y luego devuelve la respuesta guardada.

Answer 3

Un ejemplo simple, pero ilustrativo:

function choose(cond, arg1, arg2) {
   if (cond)
      do_something(arg1);
   else
      do_something(arg2);
}

choose(true, 7*0, 7/0);

Ahora digamos que estamos usando la estrategia de evaluación de entusiasmo, entonces calcularíamos ambos 7*0 y 7/0 con entusiasmo. Si es una estrategia evaluada perezosa (llamada por necesidad), entonces solo enviaría las expresiones 7*0 y 7/0 a la función sin evaluarlas.

¿La diferencia? esperaría ejecutar do_something(0) porque el primer argumento se usa, aunque en realidad depende de la estrategia de evaluación:

Si el lenguaje se evalúa con entusiasmo, entonces, como se indicó, evaluará primero 7*0 y 7/0 , y ¿qué es 7/0 ? Error de división por cero.

Pero si la estrategia de evaluación es perezosa, verá que no necesita calcular la división, llamará do_something(0) como esperábamos, sin errores.

En este ejemplo, la estrategia de evaluación perezosa puede evitar que la ejecución produzca errores. De manera similar, puede evitar que la ejecución realice una evaluación innecesaria que no utilizará (de la misma manera que no usó 7/0 aquí).