А-нормальная форма - A-normal form

В Информатика, А-нормальная форма (сокращенно ANF) является промежуточное представление из программы в функциональные компиляторы представленный Сабри и Felleisen в 1992 году[1] как более простая альтернатива стиль передачи (CPS). Некоторые из преимуществ использования CPS в качестве промежуточного представления состоят в том, что оптимизацию программ на CPS легче выполнять, чем на исходном языке, а также компиляторам легче генерировать Машинный код для программ в CPS. Flanagan et al.[2] показал, как компиляторы могут использовать ANF для достижения тех же преимуществ с помощью одного преобразования на уровне исходного кода; Напротив, для реалистичных компиляторов преобразование CPS обычно включает дополнительные этапы, например, для упрощения терминов CPS.

В ANF все аргументы к функция должно быть тривиальным. То есть оценка каждого аргумента должна быть немедленно остановлена.

В этой статье рассматривается основное определение, выраженное в терминах λ-исчисление со слабой редукцией и let-выражения, где ограничение вводится

  1. позволяя использовать только константы, λ-члены и переменные в качестве аргументов для приложений функций, и
  2. требуя, чтобы результат нетривиального выражения был захвачен позвольте связать переменная или возвращается из функции.

Грамматика

Следующее BNF грамматика описывает чистый λ-исчисление модифицирован для поддержки ограничений ANF:

EXP ::= ВАЛ | пусть VAR = VAL в EXP | пусть VAR = VAL VAL в EXPVAL ::= VAR | λ VAR. EXP

Варианты ANF, используемые в компиляторах или в исследованиях, часто позволяют использовать константы, записи, кортежи, функции с несколькими аргументами, примитивные операции и условные выражения.

Примеры

Выражение:

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

записывается в ANF как:

пусть v0 = g (x) в пусть v1 = h (y) в f (v0, v1)

Смотрите также

Рекомендации

  1. ^ Сабри, Амр; Фелляйзен, Матиас. «Рассуждения о программах в стиле продолжения». Материалы конференции ACM 1992 года по LISP и функциональному программированию, LFP'92. Сан-Франциско, Калифорния, США. Sabry92. Получено 2020-10-15.
  2. ^ Фланаган, Кормак; Сабри, Амр; Дуба, Брюс Ф .; Фелляйзен, Матиас. «Суть компиляции с продолжениями» (PDF). Труды ACM SIGPLAN 1993 Conf. по проектированию и реализации языков программирования, PLDI'93. Альбукерке, Нью-Мексико, США. Фланаган93. Получено 2012-11-16.