Programación diferida y evaluación diferida
La programación diferida es un concepto general de retrasar el procesamiento de una función o solicitud hasta que el resultado sea realmente necesario. Hay muchas aplicaciones que emplean este concepto, algunas muy obvias y otras menos. Pensar en términos de programación diferida puede ayudarle a eliminar cálculos innecesarios de su código y también puede ayudarle a reestructurar su programa para hacerlo más orientado a los problemas.
Programación diferida simple en Scheme
La programación diferida es una técnica que retrasa la evaluación del código hasta que se necesita el valor resultante. Por ejemplo, en Scheme, la programación diferida se admite explícitamente mediante dos construcciones especiales. La forma especial de retraso de Scheme toma un bloque de código y, en lugar de ejecutarlo inmediatamente, almacena el código y los argumentos como una promesa. Si fuerza esta promesa a producir un valor, ejecutará este código. Luego, la promesa guarda el resultado para que cuando se solicite el valor en el futuro, el valor pueda devolverse inmediatamente sin tener que ejecutar el código nuevamente.
Aquí tienes un ejemplo sencillo de cómo el retraso y la fuerza trabajan juntos.
Listado 1. Ejemplo de uso de demora y fuerza
;;La multiplicación se guarda pero no se ejecuta
(define my-promise (delay (* 5 6 7 8 9)))
;;Nuevamente, guardado pero no ejecutado
(define another-promise (delay (sqrt 9)))
;; Fuerza la ejecución de la multiplicación. Guarda y devuelve el valor
(display (force my-promise))
(newline)
;;Esta vez, el la multiplicación no tiene que ejecutarse. Simplemente devuelve
;;el valor que se guardó previamente.
(display (force my-promise))
(newline)
;;Esto produce un error, porque se debe forzar el uso de la promesa
(display (+ my-promise (force another-promise)))
El uso de estas estructuras es muy sencillo, pero ¿para qué deben usarse? En general, la programación diferida se utiliza cuando la función llamada genera valores que no son requeridos por el programa que llama. Por ejemplo, suponga que tiene una función que calcula la media, la varianza y la desviación estándar de un conjunto de números.
Aquí hay una forma de implementar estas funciones:
Listado 2. Cálculo estadístico simple
(definir (cuadrado x) (* x x))
( definir ( calcular-estadísticas la-serie)
(let* (
(tamaño (longitud la-serie))
(suma (aplicar + la-serie) )
(media (/ tamaño de suma))
;la varianza es la suma de (x[i] - media)^2 para todos los valores de la lista
(varianza
(let* (
(lista-de-varianzas (mapa (lambda (x) (cuadrado (- x media))) la-serie)))
(/ (aplicar + lista de varianzas) tamaño)))
(desviación estándar (varianza sqrt)))
(desviación estándar de la varianza media del vector) ))
;Ejecutar el programa
(display (calcular-estadísticas '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(nueva línea)
Ahora supongamos que queremos calcular la desviación estándar solo bajo ciertas condiciones, pero esta función ya ha gastado mucha potencia de cálculo calculando la desviación estándar. Hay varias formas de solucionar este problema. Puede dividirlo en funciones separadas que calculan la media, la varianza y la desviación estándar. Sin embargo, este proceso de cálculo del promedio debe repetirse para cada función. Si necesita los tres valores al mismo tiempo, la media se calculará 3 veces, la varianza se calculará 2 veces y la desviación estándar se calculará una vez. Hay mucho trabajo extra innecesario en el medio. Ahora también puede exigir que la media se pase a la función de desviación estándar y obligar al usuario a llamar a la función de cálculo de la media por usted. Si bien esto funciona, da como resultado una API terrible: su interfaz utiliza demasiadas cosas específicas de implementación.
Una mejor manera de utilizar la evaluación diferida es retrasar el cálculo:
Listado 3. Cálculos estadísticos utilizando la evaluación diferida
(definir (cuadrado x) (* x x))
(definir (calcular-estadísticas la-serie)
(let* (
(tamaño (retraso (longitud la-serie)))
(media (retraso (/ (aplicar + la serie) (tamaño de la fuerza))))
; la varianza es la suma de (x[i] - media)^2
(varianza
(retraso
(let* (
(varianza-lista (mapa (lambda ( x) (cuadrado ( - x (fuerza media))))
la-serie)))
(/ (aplicar + lista de varianza) (tamaño de la fuerza)))) )
(desviación estándar (retraso (sqrt (variación de fuerza)))))
(desviación estándar de la varianza media del vector)))
;Ejecutar el programa
(definir estadísticas (calcular-estadísticas '(2 6 4 3 7 4 3 6 7 8 43 4 3 2 36 75 3)))
(definir media (fuerza (vector-ref estadísticas 0)))
(definir varianza (fuerza (vector-ref estadísticas 1)))
(definir stddev (fuerza (vector-ref estadísticas 2))))
(display (lista media varianza stddev))
(nueva línea)
En esta versión de calcular-estadísticas, el valor no se muestra hasta que realmente se necesita. Se realizan los cálculos y, lo que es igualmente importante, cualquier valor se calcula sólo una vez. Si solicita calcular la varianza primero, primero calcula y guarda la media y luego calcula y guarda la varianza. Si luego solicita un cálculo del promedio, simplemente devuelve ese valor ya que el promedio ya ha sido calculado. Si luego solicita el cálculo de la desviación estándar, utiliza el valor de varianza guardado y calcula la desviación estándar a partir de este valor. Ahora no se realizan cálculos innecesarios y la interfaz de la función está bien conservada.
En lenguajes orientados a objetos, este método de programación diferido también es muy fácil de implementar. En cualquier lugar donde necesite un conjunto de cálculos relacionados, cree una clase para contener valores intermedios. El constructor recibe los valores iniciales utilizados y todos los valores calculados se establecen en nulos. La fuerza ya no se usa aquí. En cambio, cada valor tiene un captador que verifica si el valor es nulo; si no es nulo, se realiza el cálculo;
El siguiente es un esqueleto de dicha clase en el lenguaje Java:
Listado 4. Representación formal de evaluación diferida en el lenguaje Java
clase pública StatisticsCalculator {
privado Listar la_series;
privado Doble media;
privado Tamaño entero;
privado Doble varianza;
privado Doble desviación_estándar;
p>Calculadora de estadísticas pública(Lista l)
{
the_series = l;
}
public int getSize()
{
if(size == null)
{
size = the_series.size();
}
tamaño de retorno;
}
público doble getStandardDeviation()
{
if( stddev == null)
{
stddev = Math.sqrt(getVariance());
}
return stddev;
}
...
...
}
Esta clase en sí misma puede ser utilizado como valor múltiple Se utiliza la promesa y el resultado del cálculo se retiene en la variable de instancia. Cada función determina si el código se ha ejecutado comprobando si el valor de la variable está vacío. Si la variable no tiene un valor cuando es necesario, se ejecuta el código y se guarda el cálculo. Tenga en cuenta que si nulo también está dentro del rango válido del valor, entonces se necesita un indicador auxiliar para indicar si el código se ha ejecutado, en lugar de simplemente verificar si el valor está vacío.
Como puede ver, se pueden utilizar técnicas de programación diferida para proporcionar API buenas y eficientes para funciones que devuelven valores relevantes. Además, en lenguajes que no admiten directamente la programación diferida, las técnicas de programación diferida también se pueden implementar a través de clases.
Lista indeterminada
Supongamos que tienes una lista de múltiplos de 5. Ahora quieres elevar al cuadrado todos los números de esta lista. Finalmente, queremos repetir los resultados del cálculo y mostrar todos los números con un valor cuadrado menor que 500. ¿Qué? ¿No puedes operar en una lista infinita? ¿Por qué no?
De hecho, quizás contrariamente al sentimiento intuitivo, si la lista infinita se basa en ciertas reglas de generación, entonces la lista infinita puede ocupar menos espacio para almacenar que la lista finita. En el ejemplo anterior, la lista original se genera según la regla X[i] = (i + 1) * 5, donde X[i] es el valor de la lista en el índice i. X[i] también se puede representar usando su valor anterior: X[i] = X[i-1] + 5;
Usando la fuerza y el retraso de Scheme, puede construir una secuencia numérica basada en esta regla:
Listado 5. Ejemplo de secuencia
;Esta es la regla generativa para la lista. par
;siendo el auto el siguiente valor y el cdr una promesa
;para el siguiente par
(define (my-generative -rule last-val)
(let (
;fórmula generativa basada en el valor anterior
(next-val (+ last-val 5)))
;poner el siguiente valor junto con una promesa para otro
(cons next-val (delay (my-generative-rule next-val)))))
;Dado que el cdr es una promesa de un par, en lugar de un par en sí,
;tenemos nuestras propias funciones para obtener el auto y el cdr.
(define (mystream -car the-stream) (car the-stream))
(define (mystream-cdr the-stream) (force (cdr the-stream)))
; lista
(definir múltiplos de cinco (contras 5 (retraso (mi-regla-generativa 5))))
;Mostrar el cuarto elemento de la lista
(display (mystream-car (mystream-cdr (mystream-cdr (mystream-cdr múltiplos de cinco)))))
(newline)
Ahora Quiero elevar al cuadrado todos los números. Para hacer esto, necesita una función que cree una nueva secuencia a partir de una secuencia existente y una regla de generación; es un poco como un mapa, pero para secuencias.
La función es la siguiente:
Listado 6. Mapeo específico de la transmisión
(definir (función mystream-map the-stream)
(contras
;;El primer valor será la función aplicada al auto
(función (car the-stream))
;;El resto de valores se almacenarán en una promesa
p>(retraso (función mystream-map (mystream-cdr the-stream)))))
(definir squared-stream (mystream-map (lambda ( x) (* x x)) múltiplos de cinco))
;Mostrar el cuarto elemento de esta nueva lista
(display (mystream-car (mystream-cdr (mystream- cdr (mystream-cdr squared-stream)))))
(newline)
Ahora, el problema restante es recorrer el flujo e imprimir los valores resultantes menores que 500:
Listado 7. Recorrer la secuencia
(let loop (
(remaining-stream squared-stream))
(if (>= (mystream-car-stream restante) 500)
#f
(begin
(display (mystream-car-stream-restante) )
( nueva línea)
(loop (mystream-cdr restante-stream)))))
Obviamente, hay muchas maneras de implementar este tipo de pequeño programa más directamente este objetivo. Sin embargo, incluso en este ejemplo, las secuencias pueden ayudarnos a ver el problema menos desde una perspectiva de implementación y más como una idea abstracta. Los flujos nos permiten centrarnos en el problema, no en la implementación. Los flujos simplifican el concepto y la implementación de algoritmos relacionados con la generación de elementos.
Los flujos que hemos comentado hasta ahora son muy útiles para aprender los conceptos detrás de los flujos. Sin embargo, las implementaciones pueden sufrir numerosos defectos. Primero, hay muchas situaciones en las que puede ser necesario un terminador. Esta implementación no proporciona tal mecanismo. Además, la secuencia que se presenta aquí se denomina secuencia impar y esta forma de secuencia es fácil de implementar. Pero este flujo puede provocar que se realicen más cálculos de los deseados, ya que se calculan todos los valores de la lista. Los flujos estándar se definen en SRFI-40, que aborda estos problemas y otros (consulte Recursos para obtener más detalles).
Volver al principio
Omitir variables de conversión
Hasta ahora, todos nuestros ejemplos de evaluación diferida han requerido que los valores intermedios se realicen por completo antes de que se puedan realizar los cálculos. realizarse. Parte de esto se debe a los requisitos del problema que estamos resolviendo, y parte se debe al retraso y la fuerza de las operaciones en sí.
Por ejemplo, considere el siguiente código:
(define val1 20)
(define val2 30)
(define val3 40)
(definir val4 0)
(definir val5 (retraso (* val1 val2)))
(definir val6 (retraso (* val4 val3)))
(define val7 (* (force val5) (force val6)))
En este ejemplo, sabemos que la respuesta es 0 porque sabemos que 0 multiplicado en cualquier momento es 0. Entonces, si bien este puede parecer un caso en el que se puede utilizar la evaluación diferida (ya que estamos tratando de reducir los cálculos innecesarios), el uso de retraso y fuerza en realidad no nos ayuda mucho.
En tales casos, para no generar resultados intermedios, se necesitan algunos algoritmos diferidos especiales para retrasar el procesamiento. Necesitamos implementar colas de solicitudes. Luego, al solicitar el resultado final, puede buscar en la cola valores que puedan ayudarlo a optimizar su procesamiento y usar esos valores para omitir el procesamiento de otros valores. En el ejemplo de multiplicación, un 0 omite todo el procesamiento.
El siguiente es un par de retardo/fuerza especial, específicamente adecuado para cálculos de multiplicación:
Listado 8. Par de retardo/fuerza dedicado simple
;Esto simplemente use una lista para realizar un seguimiento de los valores a multiplicar
(define (multiply-delay x y)
(let (
;convertir a listas si aún no lo están
(x-list (if (list? x) x (list x)))
(y-list (if (list? y) y ( lista y))))
;añadirlos juntos
(añadir lista x-lista y)))
(definir (multiplicar-fuerza mul - lista)
(let (
(tiene-cero? #f))
(para-cada
(lambda ( x )
(if (eqv? 0 x)
(set! has-zero? #f)
#f))
lista múltiple)
(si tiene cero?
0
(aplicar * lista múltiple))))
(definir a (multiplicar-retardo 23 54))
(definir b (multiplicar-retardo 0 5))
(definir c (multiplicar-retardo a b))
(definir d (multiplicar-retardo c 55)
(display (multiplicar-fuerza d))
(nueva línea)
Sin embargo, esto implementación También tiene sus propios problemas. Ahora las partes individuales ya no son vagas y ya no guardan valores.
Para lograr una optimización, hemos perdido las ventajas originales de retraso y fuerza. Por lo tanto, en lugar de mantener una larga lista de todos los parámetros, debemos almacenarlos por separado en cada promesa, para poder seguir obteniendo las ventajas anteriores. Lo que necesitamos es una bandera que indique si se ha calculado el valor. Si el valor ya se ha calculado, aquí solo hay un elemento que no es necesario calcular. De lo contrario, aparecen tanto el multiplicador como el multiplicando. El nuevo código es el siguiente:
Listado 9. Otra estructura diferida dedicada
;Las promesas no evaluadas tendrán la estructura ('val1 val2 retrasado)
;Evaluadas las promesas tendrán la estructura ('resultado forzado)
;Crear una promesa no evaluada
(definir (multiplicar-retraso x y)
(lista 'retrasado x y) )
(definir (promesa multiplicar-fuerza-nocero)
(si (¿par? promesa)
(si (eq? (promesa del automóvil) 'forzado )
;si la promesa ha sido forzada, simplemente devuelva el valor
(promesa cdr)
;de lo contrario, calcule el valor y conviértalo en un promesa "forzada"
(begin
(set-car! promesa 'forzada)
(set-cdr! promesa
( *
(multiply-force-nonzero (promesa caddr))
(multiply-force-nonzero (promesa caddr))))
;devolver lo forzado valor
(promesa cdr)))
;Esto es solo un número, así que devuélvalo
promesa))
Esta estructura Tiene todas las ventajas del retraso/fuerza ordinaria. Ahora bien, dado que la multiplicación es una operación bastante rápida de todos modos, esta operación completa puede ser una pérdida de tiempo, pero sigue siendo bastante bueno como ejemplo. Puede ahorrar mucho tiempo en operaciones más costosas, especialmente aquellas que pueden requerir cambios de contexto o importantes recursos de procesador.
Un uso popular de esta técnica es realizar operaciones de adición en cadenas. En lugar de asignar nuevo espacio cada vez que se realiza una operación de adición, simplemente mantiene una lista de cadenas que deben concatenarse. Luego, cuando se necesita la versión final de la cadena, solo es necesario asignar espacio para esta nueva cadena una vez. Esto ahorra múltiples llamadas a malloc y el tiempo de copiar cada cadena.
Evaluación diferida
Hasta ahora, nos hemos centrado en construcciones diferidas en lenguajes no diferidos.
Sin embargo, algunos lenguajes, como Haskell, realizan algunas operaciones diferidas como parte del proceso de evaluación normal. A esto se le llama evaluación perezosa. Los parámetros en la evaluación diferida no se evalúan hasta que se necesitan. Este tipo de programa en realidad se ejecuta en dirección inversa desde el final. Determina lo que necesita devolver y retrocede para determinar qué valores necesita para hacerlo. Básicamente, cada función se llama con una promesa para cada parámetro. Cuando el cálculo requiere un valor, ejecuta la promesa. Debido a que el código se ejecuta solo cuando se necesita un valor, esto se denomina llamada bajo demanda. En los lenguajes de programación tradicionales, se pasa un valor, no una promesa, por eso se llama llamada por valor.
La programación bajo demanda tiene varias ventajas. La transmisión se implementa automáticamente. Nunca se calculan valores innecesarios. Sin embargo, el comportamiento de los programas perezosos suele ser difícil de predecir. En un programa de llamada por valor, el orden de evaluación es predecible, por lo que cualquier cálculo basado en tiempo o secuencia es bastante fácil de implementar. Esto resulta bastante difícil en lenguajes perezosos, donde describir eventos con un orden inequívoco requiere construcciones especiales como las mónadas. Todo esto hace que la interacción con otros idiomas sea muy complicada.
Varios lenguajes realizan programación diferida de forma predeterminada, incluidos Haskell y Clean. Varios otros lenguajes también tienen versiones diferidas, incluidos Scheme, ML, etc.