Le sens et la pertinence de la locution « aucune implémentation de terminaison » dans la théorie des types

Question

Dans le contexte d'une discussion sur Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, On m'a dit que

Il n'y a pas d'implémentation de fin pour le type polymorphe $(e \à a) \à a$

et qu'on ne pouvait pas avoir de fonction de type $((e \à a) \à a) \à e$ ou une fonction de type $(r \à x) \à x$, car ceux-ci ne seraient pas « implémentables ».

Ces types sont bien formés dans le STLC, dans le sens où nous pouvons les construire en utilisant les règles de formation de types.Et je ne vois pas pourquoi nous ne pouvons pas former des termes lambda de cette forme, comme $\lambda c_{((a o t) o t)}.\, b_a$, ou $\lambda p_{e o a}.\,b_a$.

Quel est donc le problème ?Plus précisément, qu'est-ce qu'une « implémentation finale » dans le contexte du STLC ?Je crois que cela est lié au fait que $(e \à \bot) \à \bot$ n'est pas constructivement équivalent à $e$, mais j'apprécierais que quelqu'un puisse m'expliquer cela.

Answer 1

Tu peux toujours habiter un type par une variable libre :le type $ au$ est habité par la variable libre $x_ au$.Quand les gens parlent de « mise en œuvre » d’un certain type, ils entendent mandat fermé, c'est-à-dire un sans variables libres.Les exemples que vous avez donnés contiennent des variables libres, à savoir $b_a$.

Dans pur simplement tapé $\lambda$-calcul tous les termes sont "terminatifs" dans le sens où le calcul est fortement normalisant, donc quelles que soient les réductions que vous effectuez, elles conduiront toujours à la forme normale (unique).

Dans $\lambda$-calcul étendu avec des définitions récursives (telles que Haskell) nous pouvons habiter tous les types $ au$ avec un terme fermé, par exemple en Haskell le type t est habité par a défini comme

a :: t
a = a

Une fois que l’on dispose de définitions récursives, il est facile d’écrire des termes fermés qui ne se terminent pas (ou n’ont pas de forme normale).