Perché abbiamo bisogno di una notazione separata per П-tipi?

Question

Principale

Sono confuso sulla motivazione dietro la necessità di una notazione separata per i tipi di tipi, che puoi trovare nei sistemi di tipo da λ2. La risposta di solito va così: pensa a come si può rappresentare una firma della funzione di identità - può essere λa:type.λx:a.x o λb:type.λx:b.x. La parte sottile, dicono, è che queste due firme non solo not equal, non sono alfa-equivalenti come variabili di tipo a e b sono variabili gratuite all'interno delle loro astrazioni corrispondenti . Quindi, per superare questa fastidiosa questione sintattica, presentiamo П legante che gioca bene con la conversione alfa.

Quindi la domanda: perché è così? Perché non aggiustare la nozione di alfa-equivalenza?

Aggiorna z:

Oh, sciocco di me, λa:type.λx:a.x e λb:type.λx:b.x sono equivalenti alfa. Ma perché a:type -> a -> a e b:type -> b -> b non sono allora.

Aggiorna suc z:

Aha, Interessante, immagino che questo sia un perfetto esempio di cecità selettiva= D

Sto leggendo il libro Tipo teoria e prova formale e in Il capitolo sull'autore di Lambda2 motiva l'esistenza del П usando esattamente quel tipo di argomentazione - si può dire che \t:*.\v:t.v: * -> t -> t perché ciò rende due termini alfA-equivalente-\t:*.\v:t.v e \g:*.\v:g.v hanno tipi diversi, poiché i tipi corrispondenti non sono upha-equivalenti, dove i tipi simili t:* -> t -> t sono infatti alfa-invarianti. Mente la differenza tra t:* -> t -> t e * -> t -> t . Ma, non rende questo argomento un po 'banale, ed è anche qualcosa di significativo parlare di tipo a -> b in cui a e b sono associati a qualsiasi variabile quantificativa. Andrej Bauer ha indicato nei commenti che П è effettivamente assomiglia ad un'estrazione Lambda con alcune campane aggiuntive e fischietti.

Tutto sommato, ho finito con quello, grazie ragazzi .

Answer 1

Penso che abbiamo solo bisogno di ottenere alcune cose direttamente qui:

.
1. nell'espressione $ \ Lambda A: \ mathsf {type}. \ Lambda x: a. x $ La variabile $ A $ è vincolato (dalla classe esterna $ \ LAMBDA $ ). Le espressioni $ \ Lambda A: \ mathsf {type}. \ Lambda x: a. x $ e $ \ Lambda B: \ mathsf {type}. \ Lambda x: b. x $ sono $ \ alfa $ -equal.
2. L'espressione $ \ Lambda A: \ mathsf {type}. \ Lambda x: a. x $ è La funzione di identità, è non la firma della funzione di identità ".
3. Se per "firma della funzione di identità" intendi dire "il tipo della funzione di identità", quindi sarebbe qualcosa come $ \ pi_ {a: \ mathsf { genere}} . (A \ a a) $ o se si desidera solo tipi di prodotto, è $ \ pi_ {A: \ mathsf {type}} \ pi_ {x: A} A $ .

C'è ancora una domanda?

Forse questo ti aiuterà:

.
• Il tipo di funzione di identità $ \ Lambda x: a. X $ è $ a \ a $
• Il tipo di funzione di identità $ \ Lambda y: b. y $ è $ B \ a B $
• Le funzioni $ \ Lambda x: a. x $ e $ \ Lambda y: b. y $ sono diversi
• i tipi $ A \ a $ e $ B \ a B $ sono diversi .
• Il tipo di Polymorphic Funzione Identity $ \ Lambda c: \ mathsf {type}. \ Lambda z: c. Z $ è $ \ pi_ {c: \ mathsf {type}}. c \ a c $ .
• Le funzioni $ \ Lambda A: \ mathsf {type}. \ Lambda x: a. x $ e $ \ Lambda c: \ mathsf {type}. \ Lambda z: c. z $ sono $ \ alfa $ -equal
• i tipi $ \ PI_ {A: \ mathsf {type}}. A \ a $ e $ \ pi_ {c: \ mathsf {type}}. c \ to c $ $ \ alfa $ -

Supplementale: Dopo aver parlato con Alex Simpson su una tazza di tè, c'è un'altra cosa che posso dire. Non siamo Hai bisogno di Separato $ \ Lambda $ e $ \ PI $ Costruttori, poiché entrambi hanno precisamente la stessa forma sintattica (prendi due argomenti, vincolando una variabile). Infatti, se la mia memoria mi serve a destra, Automath usata la stessa notazione per $ \ Lambda $ -Abstrations e $ \ PI $ -Types. Ma il punto è che noi vuoi per utilizzare due costruttori diversi perché denotano concetti diversi .