A-normalna forma
W informatyce forma A-normalna (w skrócie ANF ) jest pośrednią reprezentacją programów w kompilatorach funkcjonalnych. W ANF wszystkie argumenty funkcji muszą być trywialne (stałe lub zmienne). Oznacza to, że ocena każdego argumentu musi zostać natychmiast zatrzymana.
ANF został wprowadzony przez Sabry'ego i Felleisena w 1992 roku jako prostsza alternatywa dla stylu podań kontynuacyjnych (CPS). Niektóre zalety używania CPS jako reprezentacji pośredniej polegają na tym, że optymalizacje są łatwiejsze do wykonania w programach w CPS niż w języku źródłowym, a kompilatorom łatwiej jest również generować kod maszynowy dla programów w CPS. Flanagan i in. pokazał, jak kompilatory mogą wykorzystać ANF do osiągnięcia tych samych korzyści za pomocą jednej transformacji na poziomie źródła; z kolei w przypadku realistycznych kompilatorów transformacja CPS zazwyczaj obejmuje dodatkowe fazy, na przykład w celu uproszczenia terminów CPS.
Ten artykuł dotyczy podstawowej definicji wyrażonej za pomocą rachunku λ ze słabą redukcją i wyrażeniami let , gdzie ograniczenie jest wymuszane przez
- dopuszczając, aby tylko stałe, terminy λ i zmienne służyły jako argumenty aplikacji funkcji, oraz
- wymaganie, aby wynik nietrywialnego wyrażenia był przechwytywany przez zmienną let-bound lub zwracany z funkcji.
Gramatyka
Poniższa gramatyka BNF opisuje czysty rachunek λ zmodyfikowany w celu obsługi ograniczeń ANF:
EXP ::= WARTOŚĆ | niech VAR = VAL w EXP | niech VAR = VAL VAL w EXP VAL ::= VAR | λ VAR . DO POTĘGI
Warianty ANF używane w kompilatorach lub w badaniach często pozwalają również na stałe, rekordy, krotki, funkcje wieloargumentowe, operacje prymitywne i wyrażenia warunkowe.
Przykłady
Ekspresja:
f(g(x),h(y))
jest zapisany w ANF jako:
niech v0 = g(x) w niech v1 = h(y) w f(v0,v1)