Cálculo de construções: comprima a expressão para a menor forma

11

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.

user47376
fonte

Respostas:

8

λ

nn¯nsucc0MMM

t,u:natnattunNtn¯sn¯

natnat

S:nat×natnatnNMS(M,n¯)1¯Tn0¯n

Z1,,Zkλx:nat.0λx:nat.0λx:nat.0λx:nat.0

M

u:=λx:nat.S(M,x)
Mun¯0¯nλx:nat.0MuZ1,,ZkMZ1,,Zk

β

Andrej Bauer
fonte
Como você calcula Z1, .. Zk?
user47376
Você não precisa. Ou seja, o algoritmo que estou descrevendo está lá fora, e não sabemos exatamente o que é, mas isso é irrelevante. Na verdade, não estou tentando executar o algoritmo, só preciso que ele exista para mostrar que seu algoritmo não existe.
Andrej Bauer
Sim, mas o seu argumento diz que, se o meu algoritmo existir, podemos resolver o problema da parada. Para determinar se uma máquina de turing M interrompe seu algoritmo normaliza u e verifica se é uma de Z1, .. Zk. Portanto, ele precisa ser capaz de enumerá-las, caso contrário não poderá ser interrompido.
user47376
Z1,,ZkkZkZ[i]
7

(λx:T.C x x) uβC u u
u

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 .

cody
fonte
6

Deixe-me insistir no ponto de vista abordado pela resposta de Cody.

λλλλ

Mf

Mx¯l(|x|)f(x)¯
l(|x|)l(n)=O(nk)kf

λΘ(n)Θ(2n)λλ

λλ

λ

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:

  1. o tamanho não explode;
  2. λ

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).

λ

Damiano Mazza
fonte
O que eu tinha em mente é, por exemplo, um termo que desdobra um milhão de etapas para gerar uma lista de um milhão de elementos. Isso normaliza a lista real, que é a representação mais eficiente desse valor (é o resultado final real, não são necessárias outras etapas). Mas o próprio termo desdobrado pode ser muito pequeno.
user47376
β
Sim, é impossível como Andrej disse. Isso respondeu à minha pergunta.
user47376