A Lógica Afetiva Elementar pode ser usada como o sistema de tipo central de uma linguagem de programação prática?

9

A Lógica Afim Elementar é um sistema de tipos que captura a classe de termos λ que podem ser reduzidos no tempo elementar. Além disso, termos tipáveis ​​à EAL podem ser reduzidos usando o fragmento abstrato do algoritmo de Lamping, o que é particularmente interessante para mim porque estou explorando os correspondentes combinadores de interação.

Minha pergunta é: como alguém pode criar uma linguagem de programação prática usando o EAL como o sistema de tipos subjacente? Ou seja, que tipo de extensões (pontos de correção, polimorfismo, tipos dependentes, tipos de dados etc.) poderiam ser feitas no sistema de tipos principais sem afetar essa característica e que tal linguagem seria utilizável na prática ou seria de alguma forma também restritivo por razões que não conheço?

MaiaVictor
fonte
λfff
Woops, certo. Além disso, até onde eu entendo, também existem termos que podem ser reduzidos com o algoritmo abstrato, mas não têm um tipo EAL, certo? Portanto, embora todos os termos do EAL possam ser reduzidos sem o oracle, ainda há alguma incompatibilidade entre o algoritmo abstrato e o EAL. @DamianoMazza
MaiaVictor
Sim esta correto.
Damiano Mazza
11
"Enfim, ninguém proíbe que você tente ver o que você pode conseguir!" - 3 anos depois: sim, ninguém me proíbe, então eu o fiz! docs.formality-lang.org . Obrigado por toda sua ajuda :)
MaiaVictor

Respostas:

10

Algo muito semelhante, mas usando a lógica afim da luz (LAL) em vez da EAL, foi tentada há alguns anos por Baillot, Gaboardi e Mogbil (você pode encontrar o artigo aqui ). Eu acho que o trabalho deles pode ser facilmente generalizado para a EAL, que é um sistema mais liberal.

Quanto aos recursos dessa linguagem, você tem polimorfismo nativamente (EAL é uma restrição da lógica linear de segunda ordem). Até onde eu sei, ninguém olhou para os tipos dependentes, mas não vejo por que eles não deveriam funcionar. De fato, o EAL sem tipo funciona tão bem quanto o EAL digitado, porque suas propriedades de normalização não dependem dos tipos.

list A:=nil|A  list AforNatNatNat aqui é o tipo de número inteiro da igreja).

dbl:NatNatdbl n_=2n_ dblexppróprio iterado. Portanto, qualquer linguagem de programação baseada no EAL precisará ter algum tipo de mecanismo que proíba certas definições por iteração; é difícil imaginar como essa restrição não resultaria em uma linguagem que pareça estranha para o programador. Enfim, ninguém proíbe que você tente ver o que você pode conseguir!

De qualquer forma, se você estiver interessado na relação entre avaliação ótima, EAL e lógicas leves em geral, sugiro que você dê uma olhada nos trabalhos de Coppola do início até meados dos anos 2000.

Damiano Mazza
fonte