А-нормальная форма
 |
В информатике промежуточное А-нормальная форма (сокращенно ANF расширяемая как административная нормальная форма ) — это представление программ , иногда в функционального программирования языков компиляторах . В ANF все аргументы функции . должны быть тривиальными (константами или переменными) То есть оценка каждого аргумента должна немедленно прекратиться.
ANF был представлен Сабри и Феллейзеном в 1992 году. [1] как более простая альтернатива стилю передачи продолжения (CPS). Некоторые из преимуществ использования CPS в качестве промежуточного представления заключаются в том, что оптимизацию программ на CPS легче выполнять, чем на исходном языке, а также что компиляторам легче генерировать машинный код для программ на CPS. Фланаган и др. [2] показал, как компиляторы могут использовать ANF для достижения тех же преимуществ с помощью одного преобразования на уровне исходного кода; напротив, для реалистичных составителей преобразование CPS обычно включает дополнительные этапы, например, для упрощения терминов CPS.
Грамматика
[ редактировать ]Рассмотрим чистое λ-исчисление с константами и let-выражениями . Ограничение ANF обеспечивается
- позволяя только значениям (переменным, константам и λ-термам) служить операндами приложений функций и
- требуя, чтобы результат нетривиального выражения (например, приложения функции) был немедленно зафиксирован в переменной, привязанной к let .
Следующие грамматики BNF показывают, как можно изменить синтаксис λ-выражений для реализации ограничений ANF:
| Оригинал | АНФ |
|---|---|
EXP ::= λ VAR . EXP
| EXP EXP
| VAR
| CONST
| let VAR = EXP in EXP
CONST ::= f | g | h
|
EXP ::= VAL
| let VAR = VAL in EXP
| let VAR = VAL VAL in EXP
VAL ::= VAR
| CONST
| λ VAR . EXP
CONST ::= f | g | h
|
Варианты ANF, используемые в компиляторах или в исследованиях, часто допускают записи, кортежи, функции с несколькими аргументами, примитивные операции и условные выражения.
Примеры
[ редактировать ]Выражение:
f(g(x),h(y))
записывается в ANF как:
let v0 = g(x) in
let v1 = h(y) in
f(v0,v1)
Представьте себе, какую сборку будет производить этот вызов функции:
;; let v0 = g(x) move x into args[0] call g move result into temp[0] ;; let v1 = h(y) move y into args[0] call h move result into temp[1] ;; f(v0, v1) move temp[0] into args[0] move temp[1] into args[1] call f
Можно увидеть непосредственное сходство между ANF и скомпилированной формой функции; это свойство является частью того, что делает ANF хорошим промежуточным представлением для оптимизации компиляторов.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Сабри, Амр; Феллизен, Матиас. «Рассуждения о программах в стиле продолжения-прохождения». Материалы конференции ACM 1992 года по LISP и функциональному программированию, LFP'92 . Сан-Франциско, Калифорния, США. CiteSeerX 10.1.1.22.7509 . Сабры92.
- ^ Фланаган, Кормак; Сабри, Амр; Дуба, Брюс Ф.; Феллизен, Маттиас. «Суть компиляции с продолжениями» (PDF) . Материалы конференции ACM SIGPLAN 1993 г. по проектированию и реализации языков программирования, PLDI'93 . Альбукерке, Нью-Мексико, США. Фланаган93 . Проверено 16 ноября 2012 г.
 | Эта языкам программирования, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |