Come funziona un compilatore Haskell?

StackOverflow https://stackoverflow.com/questions/4385160

Domanda

Dove posso trovare qualche carta / doc / qualunque cosa che descrive come un compilatore Haskell funziona davvero? Ho letto un bel po 'dei documenti di GHC, ma si fermò dopo aver ottenuto un mal di testa. Quindi, qualcosa che non richiede un dottorato di ricerca per capire e non è scritto nel tu sei-supposto-to-be-già-familiarità-con-it stile sarebbe preferibile. Non è un problema se è molto lungo e richiede un po 'di tempo per capire, però.

PS:. Più interessante sarebbe qualcosa su GHC, ma tutto è ok

È stato utile?

Soluzione

È possibile ottenere una risposta dalla bocca del cavallo! Simon Peyton Jones (wizard GHC) ha scritto un libro che spiega come implementare linguaggi di programmazione funzionale. E 'disponibile gratuitamente on-line dal momento che è ormai fuori stampa: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/

Naturalmente, GHC è andata avanti dal momento che il libro è stato scritto, ma è ancora molto rilevante.

Altri suggerimenti

Sei alla ricerca di informazioni in particolare sulla compilazione lazy-valutazione? V'è il libro di Simon Peyton-Jones di cui parla Max Bolingbroke, anche il libro che descrive l'implementazione di Clean è in linea:

http://wiki.clean.cs.ru.nl/Functional_Programming_and_Parallel_Graph_Rewriting

Se si dispone di un'affiliazione universitaria e volete qualcosa di più piccolo si potrebbe cercare di ottenere questi libri (Henderson & Diller sono certamente fuori stampa):

Antoni Diller "Compilazione Funzione Lingue" ISBN 0 471 92027 4

Peter Henderson "programmazione funzionale applicazione e l'attuazione" ISBN 0-13-331579-7

AJT Davie "Introduzione alla programmazione funzionale Sistemi utilizzando Haskell" ISBN 0 521 27724 8

Diller ha un compilatore completo per un linguaggio pigro (implementato in Pascal) tramite riduzione combinatore. Questa è stata la tecnica di realizzazione inventato da David Turner per SASL. Henderson ha molte parti di un compilatore per LISPkit una miniatura, variante artificiale di Lisp. Dettagli Davie un po 'di macchinari per la compilazione di un linguaggio pigro, per esempio, c'è una descrizione dei thats STG molto più breve di libro di Simon Peyton-Jones (STG è la SPJ macchina astratta utilizzata per Haskell).

Gli sviluppatori Clean hanno un bel po 'di informazioni sull'attuazione SAPL (un semplice applicativo lingua) se si guarda attraverso la loro lista delle pubblicazioni:

https://clean.cs.ru.nl/Publications

Infine ci sono un certo numero di carte che documentano aspetti della Utrecht Haskell Compiler UHC (e EHC). Penso che la maggior parte delle informazioni è come è organizzato il compilatore (con grammatiche attributo e "Shuffle") e come i sistemi di tipo (ci sono vari livelli di sistema di tipo in EHC) sono implementati, piuttosto che come il 'compilation' back-end lavori.

Purtroppo, ho il sospetto che quello che stai cercando non esiste. la teoria del compilatore e la teoria formale del linguaggio sono argomenti abbastanza complessi in Computer Science, e Haskell è in alcun modo un punto di partenza.

In primo luogo, si dovrebbe probabilmente ottenere una buona messa a terra:

Ho il sospetto nulla spiegare nulla circa la struttura interna di Haskell richiederebbe una sostanzialmente migliore comprensione degli argomenti di cui sopra che dire, C sarebbe.

Ho preso un singolo corso sul tema fino ad ora, quindi non ho la letteratura formale per raccomandare, ma sono sicuro che esistono molte buone fonti.

I compilatori sono un soggetto enorme e sarebbe impossibile spiegare loro in interezza qui. Ma ecco una panoramica per un compilatore generale. Speriamo che questo vi darà una certa comprensione che può rendere la lettura le cose specificamente GHC un po 'più facile da capire.

compilatori generalmente lavoro da una serie di trasformazioni in 2 parti, il front-end e back-end.

La prima trasformazione si sta trasformando testo normale in qualcosa di un po 'più facile da attraversare. Questo in sé è di solito diviso in 2 parti:

analisi lessicale o Tokenizzazione - L'atto di trasformare il testo normale in piccoli pezzi (in genere gli operatori, identificatori, letterali ecc).

analisi sintattica o l'analisi - Girando questi piccoli pezzi in una struttura ad albero. (Tipicamente un AST, un Abstract Syntax Albero )

Il passo successivo è l'analisi semantica. In questa fase, un compilatore di solito aggiungere informazioni alla AST (come le informazioni tipo) e costruire una tabella dei simboli. Con questo si conclude il front-end.

La successiva trasformazione trasforma l'AST in un IR, un intermedio Rappresentazione . Questo è generalmente, al giorno d'oggi un modulo SSA, un'assegnazione statica singola .

Questo è poi ottimizzato, tramite costante di propagazione, analisi del codice morto, Vettorizzazione etc.

L'ultima trasformazione è la generazione di codice. Trasformare il IR in codice macchina. Questo può essere molto complicato. A volte è anche indicato come abbassamento.

Per ulteriori informazioni vi consiglio questa pagina wikipedia .

Wikipedia ha una buona - leggibile - panoramica delle parti interne del GHC (simile a @ di dan_waterworth spiegazione, ma specifiche per Haskell e GHC):

http://en.wikipedia.org/wiki/Glasgow_Haskell_Compiler#Architecture

Uno dei migliori lavori su questo argomento che ho letto è:

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top