O significado e a relevância da locução "de terminação de implementação" no tipo de teoria

Question

No contexto de uma discussão sobre Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, Foi-me dito que

Não há nenhuma terminação de implementação para o tipo polimórfico $(e \a) \us$

e que nós não poderíamos ter uma função do tipo $((e \a) \a) \a e$ ou uma função do tipo $(r \x) \x$, para estes, não seria "implementáveis".

Estes tipos estão bem formados na STLC, no sentido de que podemos construir-los usando as regras do tipo de formação.E eu não vejo por que não podemos formulário lambda termos desta forma, como $\lambda c_{((a ) )}.\, b_a$, ou $\lambda p_{n o a}.\,b_a$.

O que, portanto, é o problema?Especificamente, o que é uma "terminação de implementação" no contexto do STLC?Eu acredito que isso se relaciona com o fato de que $(e \a \bot) o \bot$ não é de forma construtiva, equivalente a $e$, mas eu agradeceria se alguém pudesse escreve isso para mim.

Answer 1

Você pode sempre habitam um tipo de uma variável livre:o tipo de $ au$ é habitada pela free variável $x_ au$.Quando as pessoas falam sobre a "implementação" de um tipo que significam fechado prazo, i.é., um sem variáveis livres.Os exemplos que você deu conter variáveis livres, nomeadamente $b_a$.

No pura simplesmente escreveu $\lambda$-cálculo de todos os termos são "terminar", no sentido de que o cálculo é fortemente normalizando, assim que o que reduções de você assumir o que sempre vai levar para a (única) forma normal.

No $\lambda$-cálculo estendida com recursiva definições (como Haskell) nós pode habitar cada tipo de $ au$ fechada a prazo, por exemplo, em Haskell o tipo de t é habitada por a definido como

a :: t
a = a

Uma vez que temos recursiva definições, é fácil escrever fechado termos que não terminar (ou não têm uma forma normal).