Differenza tra Haskell e Idris: Riflessione di Runtime/Compiletime negli universi di tipo

Question

Quindi in Idris è perfettamente valido scrivere quanto segue.

item : (b : Bool) -> if b then Nat else List Nat 
item True = 42 
item False = [1,2,3] // cf. https://www.youtube.com/watch?v=AWeT_G04a0A 

Senza la firma del tipo, questo sembra un linguaggio digitato in modo dinamico. Ma, in effetti, Idris è tipicamente tipizzato. Il tipo di calcestruzzo item b può essere determinato solo durante l'esecuzione.

Si tratta, ovviamente, di un programmatore Haskell che comunica: Il tipo di item b nel senso Idris viene fornito durante la compilazione, è if b then Nat ....

Ora la mia domanda: Ho ragione a concludere che in Haskell, il confine tra il runtime e il compiletime corre esattamente tra il mondo dei valori (False, "foo", 3) e il mondo dei tipi (Bool, String , Integer) mentre in Idris, il confine tra il runtime e il compilerime attraversa universi?

Inoltre, ho ragione di assumere che anche con tipi dipendenti Haskell (utilizzando DataKinds e TypeFamilies, cfr this article) nell'esempio precedente è impossibile in Haskell, perché Haskell contrariamente a Idris non consente valori di perdite di liquido del tipo -livello?

Answer 1

Sì, hai ragione di osservare che la distinzione di tipi contro valori in Idris non è in linea con la distinzione tra compiletime e runtime e compiletime. È una buona cosa. È utile avere valori che esistono solo a compiletime, proprio come nelle logiche di programma abbiamo "variabili fantasma" usate solo nelle specifiche. È utile anche avere rappresentazioni di tipi in fase di esecuzione, consentendo la programmazione generica dei tipi di dati.

In Haskell, DataKinds (e PolyKinds) scriviamo

type family Cond (b :: Bool)(t :: k)(e :: k) :: k where 
    Cond 'True t e = t 
    Cond 'False t e = e 

e in un futuro non troppo lontano, saremo in grado di scrivere

item :: pi (b :: Bool) -> Cond b Int [Int] 
item True = 42 
item False = [1,2,3] 

ma fino a che la tecnologia è implementata, dobbiamo accontentarci di falsi singleton di tipi di funzione dipendenti, come questo:

data Booly :: Bool -> * where 
    Truey :: Booly 'True 
    Falsey :: Booly 'False 

item :: forall b. Booly b -> Cond b Int [Int] 
item Truey = 42 
item Falsey = [1,2,3] 

Si può arrivare abbastanza lontano con un tale falso, ma sarebbe tutto molto più facile se avessimo avuto la cosa reale.

Fondamentalmente, il piano per Haskell è quello di mantenere e separare forall e pi, supportando rispettivamente il polimorfismo parametrico e ad hoc. I lambda e le applicazioni che vanno con forall possono ancora essere cancellati nella generazione del codice di runtime, proprio come adesso, ma quelli per pi vengono mantenuti. Avrebbe anche senso avere le astrazioni di tipo runtime pi x :: * -> ... e lanciare il nido di complessità dei ratti che è Data.Typeable nella pattumiera.

Answer 2

Ora la mia domanda: Ho ragione a concludere che in Haskell, il confine tra il runtime e il compiletime corre esattamente tra il mondo dei valori (False, "foo", 3) e il mondo dei tipi (Bool, String, Integer) mentre in Idris, il confine tra il runtime e il complemento attraversa universi?

Idris viene compilato in Epic (UPDATE: no, non è più compila a Epis come Spearman dice nel commento qui sotto):

Nessun controllo semantico, se non per vedere se i nomi sono compresi nel campo --- it si presume che il linguaggio di livello superiore abbia eseguito typechecking, e in ogni caso Epic non dovrebbe fare supposizioni su il sistema di tipi di livello superiore o eventuali trasformazioni applicate. Le annotazioni di tipo sono obbligatorie, ma danno solo suggerimenti al compilatore (potrei cambiarlo).

Quindi i tipi non sono importanti denotazionalmente, cioè il significato di un termine non dipende dal suo tipo. Inoltre alcune cose a livello di valore possono essere cancellate, ad es. in Vect n A (dove Vect è il tipo di liste con lunghezza nota staticamente) n (la lunghezza) possono essere cancellati, because

Esistono metodi descritti da Brady, McBride e McKinna in BMM04 per rimuovere gli indici dei dati strutture, sfruttando il fatto che le funzioni che operano su di esse hanno già una copia dell'indice appropriato o l'indice può essere rapidamente ricostruito se necessario.

La cosa qui è che pi in Idris agisce per i tipi di quasi nello stesso modo in cui forall in Haskell: sono entrambi parametrico (anche se, questi parametricities sono diversi) in questo caso. Un compilatore può usare i tipi per ottimizzare il codice, ma in entrambi i linguaggi il flusso di controllo non dipende dai tipi, ovvero non puoi dire if A == Int then ... else ... (anche se, se A è in forma canonica, allora sai staticamente se è Int o no e quindi can scrive A == Int, ma ciò non influisce sul flusso di controllo, perché tutte le decisioni vengono eseguite prima del runtime). Il tipo concreto di item b non ha importanza in fase di esecuzione.

Tuttavia come pigworker dice che non è necessariamente parametrico nei tipi. Così come non deve necessariamente essere non parametrico nei valori. Tipo livello - livello di valore e parametrico - non parametrico sono dicotomie completamente ortogonali. Vedere la risposta this per i dettagli.

Così Haskell e Idris sono diversi nel modo in cui trattano valore cose livello WRT runtime/compilazione dei contenuti (perché in Idris è possibile contrassegnare un argomento con . per renderlo cancellabile), ma in cui trattano i tipi più o meno nella stessa maniera.