Что такое A-нормальная форма?

Ответ 1

См. Административная нормальная форма.

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

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

Грамматика

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

EXP ::= VAL VAL
     |  let VAR = EXP in EXP
VAL ::= ? VAR . EXP
     |  VAR

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

Фланаган, Кормак; Сабри, Амр; Дуба, Брюс Ф., Феллеисен, Маттиас. "Сущность компиляции с продолжением" , вероятно, является окончательным источником.

Также были найдены заметки о cs252r: Расширенное функциональное программирование.

Ответ 2

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

Вот интересный обзор в этот независимо интересный документ на строгом промежуточном языке для составления ленивых функциональных языков. Раздел 3.1 и след., И особенно рисунок 7, который дает небольшую шаговую оперативную семантику для строгого языка в административной нормальной форме.