Forma A-normal

En informática , la forma A-normal (abreviada ANF , a veces expandida como forma normal administrativa o como forma normal atómica ) es una representación intermedia de los programas en los compiladores de lenguajes de programación funcional . En ANF, todos los argumentos de una función deben ser triviales (constantes o variables). Es decir, la evaluación de cada argumento debe detenerse inmediatamente.

Sabry y Felleisen introdujeron ANF en 1992 ^[1] como una alternativa más simple al estilo de paso de continuación (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 de máquina para programas en CPS. Flanagan et al. ^[2] demostraron cómo los compiladores podrían usar ANF para lograr esos mismos beneficios con una transformación a nivel de fuente; en contraste, para los compiladores realistas la transformación CPS generalmente involucra fases adicionales, por ejemplo, para simplificar los términos CPS.

Consideremos el cálculo λ puro con constantes y expresiones let . La restricción ANF se aplica mediante

1. permitiendo que sólo valores (variables, constantes y términos λ) sirvan como operandos de aplicaciones de funciones, y
2. requiriendo que el resultado de una expresión no trivial (como una aplicación de función) sea capturado inmediatamente en una variable enlazada a let .

Las siguientes gramáticas BNF muestran cómo se podría modificar la sintaxis de las expresiones λ para implementar las restricciones de ANF:

Las variantes de ANF utilizadas en compiladores o en investigación a menudo también permiten registros, tuplas, funciones multiargumento, operaciones primitivas y expresiones condicionales.

La expresión:

f(g(x),h(y))

se escribe en ANF como:

sea ​​v0 = g(x) en
    sea ​​v1 = h(y) en
        f(v0,v1)

Imaginando el tipo de ensamblaje que produciría esta llamada de función:

;; sea v0 = g(x)
mover x a args[0]
Llamar g
mover resultado a temp[0]
;; sea v1 = h(y)
mover y a args[0]
Llama h
mover resultado a temp[1]
;; f(v0, v1)
mover temp[0] a args[0]
mover temp[1] a args[1]
Llamar f

Se pueden ver las similitudes inmediatas entre ANF y la forma compilada de una función; esta propiedad es parte de lo que hace que ANF sea una buena representación intermedia para optimizaciones en compiladores.

• Estilo de pase continuo
• Formulario de asignación única estática