Qual é a diferença entre normalização A e normalização K em compiladores?

7

A forma normal administrativa é uma representação intermediária do programa na qual cada instrução imediata tem um nome. É usado no GHC e no OCaml .

A forma normalizada de K é uma representação intermediária na qual cada instrução consiste em uma atribuição e operação. É usado no MLKit, Min-Caml e GoCaml.

Tanto a normalização A quanto a normalização K envolvem a geração de uma expressão let com uma continuação.

A normalização A e K-normalização parecem ser exatamente a mesma transformação. Qual a diferença entre eles, de modo que eles merecem nomes diferentes?

programming-languages compilers Verdadeiramente não estrito
fonte

Respostas:

2

Até onde minha busca me levou; O K-Normal Form é inspirado no A-Normal Form , mas instrumentado para uso na Storage Mode Analysis , que é uma análise estática de programa usada para inferir diretivas de gerenciamento de memória para programas funcionais.

O termo parece originar-se da seguinte publicação: L. Birkedal, M. Tofte e M. Vejlstrup. Da inferência de região às máquinas von Neumann, através da inferência de representação de região.

Uma cópia da publicação pode ser obtida no momento da redação deste documento na página da faculdade de L.Birkedal, em publicações .

soren-n
fonte
2
Embora a origem do termo seja interessante, não vejo diretamente como isso explica a diferença. Você poderia esclarecer qual é exatamente a diferença entre os dois procedimentos de normalização? (se houver?)
Lagarto discreto
11
De acordo com o documento ( cs.cmu.edu/afs/cs/user/birkedal/pub/rri-popl96.ps.gz ), o formato K-normal liga cada expressão intermediária a uma variável, mas não lineariza as ligações let porque isso impediria a inferência da região.
Verdadeiramente não estrito
11
Ainda não atualizei a resposta, pois meu entendimento atual é que a linearização de let-bindings não faz parte da definição de ANF, portanto, não tenho certeza se isso é uma diferença. Outra possível diferença mencionada no artigo é que os termos devem ser digitados, mas se isso é apenas uma questão em relação ao sistema de tipos fornecido no artigo, também não está claro para mim.
Soren-n