El significado y la relevancia de la locución '' no terminan la implementación '' en la teoría de los tipos
-
29-09-2020 - |
Pregunta
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.
Solución
Puede siempre habitable por una variable libre: el tipo $ \ tau $ está habitado por la variable libre
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).