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

  1. dopuszczając, aby tylko stałe, terminy λ i zmienne służyły jako argumenty aplikacji funkcji, oraz
  2. 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)

Zobacz też