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

Question

Я читал о различных промежуточных формах, но не могу получить информацию об А-нормальных формах, кроме википодобных записей. Кто-нибудь здесь знает об этом или имеет хорошие ресурсы об этом?

Answer 1

См. Обычная административная форма .

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

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

Грамматика

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

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

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

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

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

Answer 2

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

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