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

Question

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

Answer 1

Смотрите административную нормальную форму.

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

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

грамматика

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

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

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

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

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

Answer 2

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

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