Alguém usou a defuncionalização polimórfica de Pottier e Gauthier em um compilador modular?

15

Defuncionalização é uma transformação de programa que converte programas de ordem superior em programas de primeira ordem. A idéia é que, dado um programa, há apenas muitas abstrações lambda finitas, para que você possa substituir cada lambda por um id e cada aplicativo de função com uma chamada para um procedimento de aplicação que se ramifique nesse id. Às vezes, isso é usado em compiladores para linguagens funcionais, mas sua aplicabilidade é limitada pelo fato de que a defuncionalização é uma transformação de todo o programa (você deve conhecer estaticamente todas as funções do programa) e, portanto, apenas os compiladores de todo o programa fazem uso de isto.

No entanto, Pottier e Gauthier possuem um algoritmo de desfuncionalização de tipo polimórfico usando uma digitação mais sofisticada envolvendo GADTs. Agora, dada a codificação, é possível adicionar um caso abrangente ao tipo de dados lambda que não é uma tag, mas que contém uma função de ordem superior. Isso significa que deve ser possível usar a codificação para desfuncionalizar módulo por módulo.

Alguém já fez isso e me indicou um compilador usando essa idéia? (Os compiladores de brinquedos estão bem e de fato são os preferidos.)

Neel Krishnaswami
fonte

Respostas:

6

Uma abordagem é descrita por

Georgios Fourtounis e Nikolaos S. Papaspyrou. 2013. Suporte à compilação separada em um compilador desfuncionalizado. SLATE 2013.

Como @gasche menciona:

Uma abordagem diferente para o problema seria considerar que cada módulo pode definir seu próprio tipo de "funções desfuncionalizadas" e expedidor / manipulador.

nEu0 0<Eu<nn-Eu

Blaisorblade
fonte
4

Agora, dada a codificação, é possível adicionar um caso abrangente ao tipo de dados lambda que não é uma tag, mas que contém uma função de ordem superior. Isso significa que deve ser possível usar a codificação para desfuncionalizar módulo por módulo.

Você poderia elaborar um pouco mais sobre o que você quer dizer aqui? Eu não entendo como adicionar um caso base (isso seria ao tipo de dados, à correspondência de padrões da função de despacho ou a ambos?) Ajuda a modularidade da maneira que você descreveu; a propósito, por que você quer dizer exatamente com base "módulo por módulo"?

Eu posso imaginar um "caso base" sendo usado, dentro de um determinado módulo / programa, para defuncionalização seletiva : você teria um construtor adicional para o seu tipo de função reificada que não é um tag, mas simplesmente incorpora todas as 'a -> 'bfunções, de modo que a função de empacotamento nesse construtor, em vez de atribuir uma marca reificada, impediria sua defuncionalização.

Uma abordagem diferente para o problema seria considerar que cada módulo pode definir seu próprio tipo de "funções desfuncionalizadas" e expedidor / manipulador. Funções do módulo M1teriam tipoM1.arrow e seriam aplicadas usando M1.applyetc. Embora isso funcione bem para o uso de primeira ordem das funções, não vejo bem como você pode estendê-lo à função de ordem superior (o que não deveria ser necessário). saber de onde vem o argumento funcional): se você agrupar uma função com seu despachante, estará reinserindo o domínio das chamadas de função indiretas.

Por fim, no artigo, você mencionou uma rápida referência à abordagem de todo o programa em relação à modular, mas não vejo como isso se relaciona à sua proposta. O que eles descrevem é expresso em termos de "extensões abertas" de funções e tipos de dados (funções e tipos que podem ser definidos em vários módulos independentes). Essa é principalmente uma maneira de ML para descrever o fato de que você pode adiar a combinação de análises / transformações de módulos independentes no tempo do link, relaxando a necessidade de transformação de todo o programa.

gasche
fonte