Como você codifica o algoritmo abstrato de Lamping usando combinadores de interação?

10

Os combinadores de interação foram propostos como um alvo de compilação para o cálculo λ antes. Esse documento implementa o cálculo λ completo. Sabe-se também que é possível otimizar codificações de interação-rede do cálculo λ para o subconjunto de termos λ que é tipável por EAL. Esse artigo implementa esse subconjunto do cálculo λ, traduzindo termos λ tipáveis ​​para EAL em redes de interação que são sem dúvida mais complexas do que combinadores de interação, pois eles usam um alfabeto infinito de rótulos para agrupar duplicadores.

Gostaria de saber se é possível combinar as duas propostas. Ou seja, existe alguma codificação para o algoritmo abstrato - ou seja, termos-λ que são tipáveis ​​pela EAL - como combinadores de interação?

MaiaVictor
fonte

Respostas:

6

Não conheço nenhuma implementação do algoritmo de Lamping diretamente nos combinadores de interação. Eu sei que a presença de rótulos inteiros é um recurso necessário do algoritmo de Lamping, mesmo para termos tipificados pela EAL, porque os rótulos refletem o aninhamento das chamadas caixas exponenciais nas redes de prova, e o algoritmo de Lamping é essencialmente a execução de redes de prova usando a geometria da interação, como observado pela primeira vez por Gonthier, Abadi e Lévy . Portanto, a questão de implementar o algoritmo nos combinadores de interação se resume a representar caixas exponenciais em redes de prova usando os combinadores. Isso foi essencialmente o que Mackie e Pinto fizeram em seu trabalho.

λ) No entanto, não acredito que essa simplificação tenha um impacto notável nas implementações do combinador de interação. Isso ocorre porque as caixas são um recurso global (elas identificam sub-redes arbitrariamente grandes a serem duplicadas / apagadas), enquanto os combinadores de interação (como qualquer sistema de rede de interação) são completamente locais (a redução modifica apenas as sub-redes delimitadas); portanto, o desafio é representar tais recursos globais localmente. Agora, a duplicação / exclusão global no EAL é idêntica à da lógica linear completa, e é por isso que não espero que uma implementação combinadora de interação do EAL seja radicalmente diferente da proposta por Mackie e Pinto.

Damiano Mazza
fonte