Haskell ha un tipo di esecuzione "di fatto"?

Question

Ecco il mio dilemma: Quando il programma Haskell viene compilato, viene generato un codice macchina eseguibile binario che può essere eseguito su una CPU fisica. Quando il programma Haskell viene interpretato, la CPU fisica esegue operazioni sui dati dalle posizioni di memoria. L'esecuzione avviene realisticamente in un periodo di tempo la cui durata dipende dalla velocità della CPU.

Poiché i dati sono stati inseriti nella memoria da un compilatore che garantisce che ogni variabile sia fortemente tipizzata, significa che Haskell ha effettivamente un tipo di esecuzione o no?

Chiarificazione: Per "tipo di runtime" intendo: il tipo (in senso teorico-tipo) di una variabile nel momento in cui il programma viene eseguito su un processore fisico raggiungibile/identificabile dal compilatore di lingua in lingua tempo di compilazione.

Answer 1

"Run-time tipi" utilizzati per qualsiasi programma compilato, a prescindere dalla lingua di partenza, sono i tipi nativamente supportati dal processore di destinazione: tipicamente interi (con e senza segno), puntatori (in realtà solo un uso particolare di numeri interi) e numeri a virgola mobile (in genere IEEE754). Il compilatore traduce tutte le operazioni nel programma sorgente in una serie equivalente di operazioni utilizzando questi tipi di base supportati da hardware.

I tipi di dati più sofisticati (come gli elenchi di Haskell) sono rappresentati in fase di esecuzione come strutture di dati create da tipi di base. Ad esempio, ciascun nodo in una lista può essere rappresentato da una coppia di puntatori: uno per il valore detenuto da quel nodo (o un thunk per calcolarlo) e uno per il nodo successivo (o un thunk). Il controllo di tipo statico del compilatore consente di garantire che a ciascuna di queste strutture dati di runtime sia consentito l'accesso solo tramite codice che gestirà correttamente. Ad esempio, una regione di memoria che contiene una coppia di puntatori per un nodo elenco non verrà erroneamente considerata come un thunk per calcolare un intero, poiché il compilatore consente solo di passare l'elenco a funzioni che prevedono un argomento lista.

Answer 2

Le funzionalità del linguaggio Haskell sono progettate per supportare completa cancellazione tipo. L'idea è che le regole di battitura garantiscono quel codice che passa il controllo di tipo ha le seguenti due proprietà :

1. un valore è di un tipo non è mai passata ad una funzione che si aspetta un altro tipo
2. A funzione che sostiene di gestire valori in qualche tipo gestirà qualsiasi valore possibile in questo tipo

I 2i residenza nasce ampliando. Ovviamente le funzioni parziali come fromJust e head non gestiscono alcun valore possibile; esplodono in runtime se danno il valore sbagliato. Ma esplodono in un modo "ben definito", dopo aver controllato le ipotesi da cui dipendono. Non è possibile scrivere codice che tenti di accedere alla sottostruttura in valori che potrebbero non avere quella sottostruttura, che potrebbe causare errori di segmentazione o interpretare pezzi di memoria casuali come se fossero un tipo diverso di dati.

Quindi, dopo che il controllo del tipo ha avuto esito positivo, non è necessario memorizzare alcuna informazione sul tipo nel programma compilato. Mi limito a buttare via i tipi. Ho già provato che se generassi codice che eseguisse ciecamente operazioni sui dati assumendo che fosse della forma richiesta, nulla sarebbe in realtà andato storto.

Tempo di esempio!

data Foo = Foo Int String 
data Bar = Bar Int String 

I valori di Foo e Bar saranno probabilmente rappresentati in memoria in modo identico ; una volta che tutti i valori sono corretti, tutte le informazioni necessarie per definire questi valori sono Int e String in ciascun caso. Se si dovesse esaminare un dump di memoria di un programma Haskell in esecuzione, non sarebbe possibile stabilire se un determinato oggetto di memoria contenente un riferimento a un Int e un String era uno Foo o uno Bar (o addirittura uno (Int, String) o qualsiasi altro tipo di singolo costruttore con due campi che sono Int e String rispettivamente).

Quindi no, i tipi Haskell non esistono in fase di esecuzione, in nessuna forma.

---

Ovviamente si può rompere queste proprietà utilizzando gli elementi pericolosi, come unsafeCoerce; Sto parlando di "normale" codice Haskell qui.

2 O forse no. Haskell-the-language non fornisce alcuna garanzia sulla rappresentazione in fase di esecuzione, e sarebbe perfettamente possibile che memorizzasse i campi in un ordine diverso o facesse qualcos'altro che potesse distinguere i due. Ma presumo che, in assenza di qualsiasi ragione per fare diversamente, tratta questi due tipi allo stesso modo.

Answer 3

Le informazioni sul tipo di runtime si trovano comunemente nelle implementazioni di linguaggi OOP, che contengono un "tag di tipo" con ogni oggetto. Avere tali informazioni consente, ad esempio, di scrivere codice come

void foo(Object o) { 
    if (o instanceof SomeClass) { 
    ... 
    } 
} 

che è una forma di controllo del tipo di runtime. Il "tag type" viene spesso fornito gratuitamente, poiché ogni oggetto ha bisogno di un puntatore alla Virtual Method Table e solo questo identifica il tipo di runtime dell'oggetto.

In Haskell, tuttavia, non è necessario un tag di questo tipo o per i puntatori ai VMT. Il linguaggio è stato progettato senza alcun tipo di operatore instanceof in modo che le implementazioni non debbano fornire alcun tipo di tag in fase di esecuzione. Ciò porta anche ad una teoria sottostante più interessante, dal momento che otteniamo garanzie di parametricità sul codice, note anche come "teoremi gratis!". Per esempio la seguente funzione

f :: [a] -> [a] 
f = .... -- whatever 

può non essere implementato in modo che f [1,2] = [2,3]. Ciò è dovuto al fatto che non esiste, in modo dimostrabile, alcun modo di produrre 3 per f. L'intuizione è che f deve produrre un a e non può controllare che a=Int in fase di esecuzione (nessun tag di tipo), quindi l'output di f può includere solo elementi trovati nel suo input. Questa garanzia viene solo dalla digitazione sopra riportata, senza nemmeno preoccuparsi di come lo strumento f sia effettivamente implementato.

Se si vuole veramente un instanceof equivalente, è possibile utilizzare Typeable per questo:

f :: Typeable a => [a] -> [a] 
f [] = [] 
f (x:xs) = case cast x of 
      Just (y :: Int) -> [2,3] 
      Nothing   -> x:x:xs 

Ciò restituirà [2,3] su tutte le liste non vuote se interi. In fase di esecuzione, verrà passato un tag di tipo che consente di verificare a=Int.

Answer 4

No.Una proprietà fondamentale di Haskell è che newtype dichiarazioni, come

newtype MyInt = MyInt Int 

non hanno spese generali di run-time, il che significa che il costruttore MyInt può letteralmente tornare lo stesso argomento (qualunque cosa sia) che è stato passato, e il compilatore lo tratterò come un tipo diverso. (Se si guarda il codice compilato, dopo l'ottimizzazione non si vedranno istruzioni per implementare la chiamata alla funzione MyInt, anche.) Ciò significa che qualsiasi tipo di tempo di esecuzione 'de-factor' di un oggetto in Haskell verrà definito solo fino all'equivalenza tra uno newtype e la sua implementazione.