Pergunta sobre o "Tutorial implementação de dependência digitado cálculo lambda"

Question

Eu tenho uma leve técnicas de luta com este maravilhoso tutorial.Na página 5 do tutorial fala sobre como escrever regras para Simplesmente Digitado Lambdas e apresenta a seguir o juízo que podem ser retirados através de regras na figura 3.

Eu era incapaz de provar nem id nem const pelo mesmo motivo.Tomemos, por exemplo, o id exemplo.

• Dizer que eu estou procurando no tipo de regra de verificação CHK.Ele diz que, para check types Eu primeiro deve efectuar inferência e, em seguida, comparar o resultado com o que eu esperava.
• Para fazer a inferência sobre a aplicação, eu tenho que usar o APP regra que imediatamente me força para inferir o tipo do lado esquerdo da candidatura, nomeadamente (id :: α -> α)
• Para fazer isso, eu estou usando o ANN regra que me força a verificação de que α -> α é um tipo (e eu posso provar que não há problema).Então eu tenho esse nu id símbolo e tem que provar que é tipo a ser α -> α.
• Finalmente, aqui está um problema.A fim de fazer o que eu tenho para usar var de regra, o que requer o tipo de id a ser definido no contexto de Gama explicitamente, mas isso não é feito, portanto, a prova está caindo aos pedaços.

Answer 1

$\mathsf{id}$ e $\mathsf{const}$ não são variáveis de cálculo, mas um açúcar sintático para $\lambda x ightarrow x$ e $\lambda x ightarrow \lambda y ightarrow x$ respectivamente.Isto é afirmado no final do §2.2 e sutilmente transmitida pelo uso de uma fonte sem serifa, em vez de itálico (esta é uma convenção tipográfica de um documento, não uma convenção comum).

Assim, por exemplo, o tipo de julgamento $$ \alpha ::\ast, y ::\alpha \vdash (\mathsf{id} ::\alpha ightarrow \alpha) \:y :: ightarrow \alpha $$ é também o tipo de julgamento $$ \alpha ::\ast, y ::\alpha \vdash (\lambda x ightarrow x ::\alpha ightarrow \alpha) \:y :: ightarrow \alpha .$$ É uma notação diferente para o mesmo objecto matemático.