Il significato e la rilevanza della locuzione "Nessuna attuazione di terminazione" nella teoria del tipo

Question

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.

Answer 1

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).