El significado y la relevancia de la locución '' no terminan la implementación '' en la teoría de los tipos

Question

En el contexto de una discusión de Haskell https : //stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-de-the-co-reader-monad , me dijeron que

No hay una implementación de terminación para el tipo polimorfo $ (e \ a a) \ a $

y que no podríamos tener una función del tipo $ (((e \ a a) \ a a) \ a e $ o una función del tipo < Span Class="Math-contenedor"> $ (r \ a x) \ a x $ , porque estos no serían '' implementables ''.

Estos tipos están bien formados en el STLC, en el sentido de que podemos construirlos utilizando las reglas de formación de tipo. Y no veo por qué no podemos formar términos de lambda de esta forma, como $ \ lambda c _ {((a \ a t) \ a t)}. \, b_a $ , o $ \ lambda p_ {e \ a A}. \, b_a $ .

¿Qué es, por lo tanto, el problema? Específicamente, ¿qué es una '' implementación terminante '' en el contexto del STLC? Creo que esto se relaciona con el hecho de que $ (e \ to \ bot) \ to \ bot $ no es constructivo equivalente a $ E $ , pero apreciaría si alguien pudiera deletrear esto.

Answer 1

Puede siempre habitable por una variable libre: el tipo $ \ tau $ está habitado por la variable libre $ x_ \ tau $ . Cuando las personas hablan de "implementación" de un tipo, significan un término cerrado , es decir, uno sin variables libres. Los ejemplos que le dio contienen variables libres, a saber, $ b_a $ .

en puro Simply-typed $ \ lambda $ -calculus Todos los términos están "terminando" en el sentido de que el cálculo se normaliza. , por lo que las reducciones que tome, siempre llevarán a la forma normal (única).

en $ \ lambda $ -calculus extendido con definiciones recursivas (como Haskell) Podemos habitar cada tipo $ \ tau $ con un término cerrado, por ejemplo, en Haskell, el tipo t está habitado por a definido como

a :: t
a = a

Una vez que tenemos definiciones recursivas, es fácil escribir términos cerrados que no terminan (o no tienen una forma normal).