Estou ciente de que o Cálculo de Construções está fortemente normalizando, o que significa que toda expressão tem um normal, pois não pode ser beta, reduzida ainda mais. Portanto, de fato, essa é a expressão mais eficiente que calcula o mesmo valor da expressão original.
Mas, em certos casos, a normalização pode reduzir uma expressão pequena a uma expressão enorme (em termos de tamanho).
Existe uma forma menor de expressões? Um formulário que calcula o mesmo valor com o menor tamanho.
Em outras palavras, em vez de uma forma normal com eficiência de tempo, uma forma com eficiência de espaço.
lambda-calculus
reductions
typed-lambda-calculus
normalization
calculus-of-constructions
user47376
fonte
fonte
Nesse sentido, sabe-se como reduzir os termos não digitados da maneira ideal, reduzindo o compartilhamento o máximo possível. Isso é explicado aqui: https://stackoverflow.com/a/41737550/2059388 e a citação relevante é J. Um algoritmo de J. Lamping para uma redução ideal do cálculo lambda . Há poucas dúvidas de que o teorema do cálculo não tipificado possa ser estendido ao CIC.
Uma outra questão relevante é a quantidade de informações de tipo que podem ser apagadas ao realizar a conversão de tipos, ou mesmo como realizar uma conversão eficiente, que é um campo ativo de pesquisa, veja, por exemplo , a tese de Mishra-Linger .
fonte
Deixe-me insistir no ponto de vista abordado pela resposta de Cody.
Essa mesma sintaxe pode ser usada para provar que, ao contrário da intuição ingênua, a resposta à pergunta acima é sim: o número de etapas mais à esquerda na forma normal é uma medida de custo razoável, mesmo que o tamanho exploda, porque de fato, existe outra maneira de representar a mesma computação (usando substituições explícitas lineares) na qual:
Tudo isso é explicado no artigo de Accattoli e Dal Lago "A redução beta é invariante, de fato" (LICS 2014 e, então, acho que há uma versão mais recente do diário).
fonte