En informática , la forma A-normal (abreviado ANF ) es una representación intermedia de programas en compiladores funcionales introducidos por Sabry y Felleisen en 1992 [1] como una alternativa más simple al estilo de continuación-paso (CPS). Algunas de las ventajas de usar CPS como representación intermedia son que las optimizaciones son más fáciles de realizar en programas en CPS que en el lenguaje fuente, y que también es más fácil para los compiladores generar código máquina para programas en CPS. Flanagan y col. [2]mostró cómo los compiladores pueden utilizar ANF para lograr esos mismos beneficios con una transformación a nivel de fuente; por el contrario, para compiladores realistas, la transformación de CPS normalmente implica fases adicionales, por ejemplo, para simplificar los términos de CPS.
En ANF, todos los argumentos de una función deben ser triviales. Es decir, la evaluación de cada argumento debe detenerse de inmediato.
Este artículo trata de la definición básica expresada en términos del cálculo λ con reducción débil y expresiones let , donde la restricción es impuesta por
- permitiendo que solo constantes, términos λ y variables, sirvan como argumentos de aplicaciones de funciones, y
- requiriendo que el resultado de una expresión no trivial sea capturado por una variable let-bound o devuelto por una función.
Gramática
La siguiente gramática BNF describe el cálculo λ puro modificado para soportar las restricciones de ANF:
EXP :: = VAL | deje VAR = VAL en EXP | deje VAR = VAL VAL en EXPVAL :: = VAR | λ VAR. Exp
Las variantes de ANF utilizadas en compiladores o en investigación a menudo permiten constantes, registros, tuplas, funciones de múltiples argumentos, operaciones primitivas y también expresiones condicionales.
Ejemplos de
La expresion:
f (g (x), h (y))
está escrito en ANF como:
sea v0 = g (x) en sea v1 = h (y) en f (v0, v1)
Ver también
Referencias
- ^ Sabry, Amr; Felleisen, Matthias. "Razonamiento sobre programas en estilo continuación-pase" . Actas de la Conferencia ACM de 1992 sobre LISP y programación funcional, LFP'92 . San Francisco, CA, Estados Unidos. Sabry92 . Consultado el 15 de octubre de 2020 .
- ^ Flanagan, Cormac; Sabry, Amr; Duba, Bruce F .; Felleisen, Matthias. "La esencia de compilar con continuaciones" (PDF) . Actas ACM SIGPLAN 1993 Conf. sobre Diseño e Implementación de Lenguaje de Programación, PLDI'93 . Albuquerque, NM, Estados Unidos. Flanagan93 . Consultado el 16 de noviembre de 2012 .