Os termos da lógica combinatória são sempre maiores?

9

Portanto, existe um algoritmo para converter termos de cálculo lambda em lógica combinatória usando combinadores SK. Produz coisas que explodem de tamanho. Eu gostaria de saber mais sobre essa explosão de tamanho. No entanto, não consigo pensar em um algoritmo melhor. Eu ouvi falar de linguagens funcionais sendo praticamente compiladas em combinadores, então parece que um algoritmo melhor deve existir. Eu procurei o artigo de David Turner sobre o assunto e ele basicamente diz para aplicar algumas otimizações e que elas causam uma "melhoria considerável".

"Melhoria considerável" significa que o tamanho cai para apenas um aumento polinomial? Existe uma maneira conhecida de converter termos lambda em lógica combinatória com apenas um aumento polinomial (ou menor?) De tamanho? Se esse algoritmo existe, é prático?

Jake
fonte
o papel é de 1979. há muito mais moderno / recente pensamento / tecnologia sobre como traduzir código em lógica por exemplo, com FPGAs e GPUs e geralmente não estaria baseado em linguagens funcionais ....
vzn
Você pode me apontar para eles?
Jake
a pesquisa que você cita é mais "prova de princípio" teórica ... seria melhor se você citasse o conceito / seção sobre "aumento polinomial no tamanho", que parece ser o foco da sua pergunta ... você está interessado na teoria geral de conversão de código em lógica / circuitos, do lado teórico ou aplicado, ou teoria de fazê-lo com eficiência, ou ambos? a questão é muito transversais em seus diferentes aspectos ... talvez pode descobrir mais em Ciência da Computação via Chat
vzn
1) existe uma maneira de importar isso para um bate-papo? Não consigo entender isso. 2) Não há nenhuma seção sobre aumento polinomial de tamanho e esse é o meu problema. Na verdade, não diz nada de substancial (nem posso encontrar essas referências) sobre quanto é o aumento de tamanho.
Jake
os comentários podem ser importados para o bate-papo após um limiar de comentários postados separados. isso não é necessário para iniciar um bate-papo. Em um aumento polinomial, poderia ser um conceito de "boato" ou "folclore" sobre essa linha de pesquisa, não tenho certeza. mas onde você ouviu coisas como "produz coisas que explodem em tamanho"; seria útil para ser mais específico etc ...
vzn

Respostas:

4

não é um especialista nisso, mas aqui estão dois artigos históricos que parecem ser intimamente relevantes para a questão e é possivelmente uma área de pesquisa semi-ativa. Turner propôs um conjunto de combinadores que podem ser reduzidos a combinadores SK. este próximo artigo argumenta que os combinadores Turner, mesmo não reduzidos a combinadores SK, levam a uma explosão exponencial (e que presumivelmente a redução aos termos SK seria ainda maior). mas o segundo artigo diz que existe um algoritmo eficiente de espaço O (n log n) baseado nos combinadores Turner. (parece que talvez tenham sido feitas alegações sobre a eficiência polinomial que não são totalmente demonstradas / não comprovadas e, portanto, são consideradas conjecturas ...

vzn
fonte
11
perfeito! Encontrei este artigo também depois de procurar esses dois documentos. sciencedirect.com/science/article/pii/002001908790161X Obrigado!
Jake