Il significato e la rilevanza della locuzione "Nessuna attuazione di terminazione" nella teoria del tipo
-
29-09-2020 - |
Domanda
Nel contesto di una discussione di Haskell https : //stackoverflow.com/questions/62509788/the-intuition-Behind-the-definition-of-the-co-reader-monad , mi è stato detto
.Non vi è alcuna implementazione terminata per il tipo polimorfico $ (e \ a a) \ a $
E che non potevamo avere una funzione di tipo $ ((e \ a a) \ a a) \ to e $ o una funzione di tipo < Span Class="Math-Container"> $ (r \ to x) \ to x $ , per questi non sarebbe "implementabile".
Questi tipi sono ben formati nello STLC, nel senso che possiamo costruirli utilizzando le regole di tipo-formazione. E non vedo perché non possiamo formare i termini di Lambda di questa forma, ad esempio $ \ Lambda c _ {(a \ to t) \ to t)}. \, B_A $ o $ \ lambda p_ {e \ to a}. \, b_a $ .
Cosa è quindi il problema? In particolare, qual è una "implementazione terminazione" nel contesto dello STLC? Credo che questo si riferisca al fatto che $ (e \ to \ bot) \ to bot $ non è costruttivamente equivalente a $ e $ , ma apprezzerei se qualcuno potesse scriverlo per me.
Soluzione
Puoi sempre Abitare un tipo di una variabile GRATUITA: il tipo $ \ tau $ è abitata dalla variabile gratuita <="container math"> $ x_ \ tau $ . Quando le persone parlano di "implementazione" di un tipo intendono a termine chiuso , I.e., uno senza variabili libere. Gli esempi che hai fornito contengono variabili libere, vale a dire $ B_A $ .
in pure semplicemente digitato $ \ Lambda $ -calculus Tutti i termini sono "terminando" nel senso che il calcolo è fortemente normalizzante , quindi qualunque riduzione che prendi, porteranno sempre alla forma normale (unica) normale.
in $ \ lambda $ -calculus esteso con definizioni ricorsive (come haskell) possiamo abitare ogni tipo $ \ Tau $ Con un termine chiuso, ad esempio in Haskell il tipo t
è abitato da a
definito come
a :: t
a = a
.
Una volta che abbiamo definizioni ricorsive, è facile scrivere termini chiusi che non terminano (o non hanno una forma normale).