Análisis de rigor

En informática , el análisis de rigor se refiere a cualquier algoritmo utilizado para demostrar que una función en un lenguaje de programación funcional no estricto es estricta en uno o más de sus argumentos. Esta información es útil para los compiladores porque las funciones estrictas se pueden compilar de manera más eficiente. Por lo tanto, si se demuestra que una función es estricta (usando análisis de rigor) en tiempo de compilación, se puede compilar para usar una convención de llamada más eficiente sin cambiar el significado del programa que la contiene.

fTenga en cuenta que se dice que una función diverge si devuelve : operacionalmente, eso significaría que causa una terminación anormal del programa adjunto (por ejemplo, falla con un mensaje de error) o que se repite infinitamente. La noción de "divergencia" es significativa porque una función estricta es aquella que siempre diverge cuando se le da un argumento que diverge, mientras que una función perezosa (o no estricta) es aquella que puede o no divergir cuando se le da tal argumento. El análisis de rigor intenta determinar las "propiedades de divergencia" de las funciones, lo que identifica algunas funciones que son estrictas. ${\displaystyle \{\bot \}}$f

Enfoques para el análisis de rigor.

Interpretación abstracta directa

El análisis de rigor se puede caracterizar como una interpretación abstracta directa que aproxima cada función en el programa mediante una función que asigna las propiedades de divergencia de los argumentos a las propiedades de divergencia de los resultados. En el enfoque clásico iniciado por Alan Mycroft , la interpretación abstracta utilizó un dominio de dos puntos donde 0 denota el conjunto considerado como un subconjunto del argumento o tipo de retorno, y 1 denota todos los valores del tipo. ^[1] ${\displaystyle \{\bot \}}$

Análisis de la demanda

El compilador Glasgow Haskell (GHC) utiliza una interpretación abstracta hacia atrás conocida como análisis de demanda para realizar análisis de rigor, así como otros análisis de programas. En el análisis de la demanda, cada función se modela mediante una función desde las demandas de valor del resultado hasta las demandas de valor de los argumentos. Una función es estricta en un argumento si una demanda de su resultado conduce a una demanda de ese argumento. ^[2]

Análisis de rigor basado en proyecciones.

El análisis de rigor basado en proyecciones, introducido por Philip Wadler y RJM Hughes , utiliza proyecciones de rigor para modelar formas más sutiles de rigor, como la rigurosidad principal en un argumento de lista. (Por el contrario, el análisis de demanda de GHC sólo puede modelar la rigurosidad dentro de los tipos de productos, es decir, tipos de datos que sólo tienen un único constructor ). Una función se considera estricta si , ¿dónde está la proyección que evalúa en cabeza su argumento de lista? ^[3] ${\displaystyle f}$ ${\displaystyle f=f\circ \pi }$ ${\displaystyle \pi }$

En la década de 1980 hubo una gran cantidad de investigaciones sobre el análisis de rigor.

Referencias

1. Mycroft, Alan (1980). "La teoría y la práctica de transformar la llamada por necesidad en llamada por valor". Apuntes de conferencias en informática: proc. 4to Internacional Síntoma. sobre programación, vol. 83 . Springer-Verlag.
2. "El comentario de GHC: analizador de demanda en GHC" . Consultado el 12 de febrero de 2014 .
3. Wadler, P.; RJM Hughes (1987). "Proyecciones para análisis de rigor". Programación funcional y arquitectura informática; LNCS 274 . Springer-Verlag.