Perché scrivere un compilatore in un linguaggio funzionale è più semplice?

Question

Ho pensato a questa domanda molto a lungo, ma davvero non riuscivo a trovare la risposta su Google e una domanda simile su Stackoverflow. Se c'è un duplicato, mi dispiace per quello.

Un sacco di persone sembrano dire che scrivere compilatori e altri strumenti linguistici in linguaggi funzionali come OCaml e Haskell è molto più efficiente e più facile quindi scrivendoli in linguaggi imperativi.

È vero? E se è così - perché è così efficiente e facile da scrivere in lingue funzionali invece che in un linguaggio imperativo, come C? Inoltre, non è più lento uno strumento linguistico in una lingua funzionale, quindi in un linguaggio di basso livello come C?

Answer 1

Spesso un compilatore lavora molto con gli alberi. Il codice sorgente viene analizzato in un albero di sintassi. Quell'albero potrebbe quindi essere trasformato in un altro albero con annotazioni di tipo per eseguire il controllo dei tipi. Ora potreste convertire quell'albero in un albero contenente solo elementi del linguaggio di base (convertendo le notazioni sintattiche simili a zucchero in una forma coniugata). Ora puoi eseguire varie ottimizzazioni che sono fondamentalmente trasformazioni sull'albero. Dopodiché probabilmente creerai un albero in una forma normale e poi eseguirai un iterazione su quell'albero per creare il codice target (assembly).

linguaggio funzionale hanno caratteristiche come pattern-matching e un buon supporto per la ricorsione efficiente, che lo rendono facile lavorare con gli alberi, è per questo che stanno generalmente considerate buone lingue per la scrittura di compilatori.

Answer 2

Un sacco di attività del compilatore sono la corrispondenza del modello sulle strutture ad albero.

Sia OCaml che Haskell dispongono di funzionalità di corrispondenza del modello potenti e concise.

È più difficile aggiungere la corrispondenza del modello alle lingue imperative, poiché qualsiasi valore valutato o estratto per adattarlo al modello deve essere privo di effetti collaterali.

Answer 3

Un fattore importante da considerare è che una grande parte di qualsiasi progetto di compilazione è quando è possibile auto-ospitare il compilatore e "mangiare il proprio cibo per cani". Per questo motivo quando si guardano linguaggi come OCaml in cui sono progettati per la ricerca linguistica, tendono ad avere grandi funzionalità per problemi di tipo compilatore.

Nel mio ultimo lavoro compilatore abbiamo usato OCaml esattamente per questo motivo mentre manipolavo il codice C, era solo lo strumento migliore per l'attività. Se i ragazzi di INRIA avessero costruito OCaml con priorità diverse, non avrebbe potuto essere così adatto.

Detto questo, i linguaggi funzionali sono lo strumento migliore per risolvere qualsiasi problema, quindi ne consegue logicamente che sono lo strumento migliore per risolvere questo particolare problema. QED.

/me: esegue la scansione di nuovo ai miei compiti Java un po 'meno con gioia ...

Answer 4

Vedi anche

F# design pattern

FP gruppi cose 'di funzionamento', mentre OO raggruppa le cose 'per tipo ', e' by operation 'è più naturale per un compilatore/interprete.

Answer 5

Sembra che a tutti sia sfuggito un altro motivo importante. È abbastanza facile scrivere un linguaggio specifico di dominio incorporato (EDSL) per i parser che assomigliano molto (E) a BNF nel codice normale.Combinatori di parser come Parsec sono abbastanza facili da scrivere in linguaggi funzionali utilizzando funzioni di ordine superiore e composizione di funzioni. Non solo più facile ma molto elegante.

Fondamentalmente si rappresentano le più semplici parser più generica, come solo le funzioni e si dispone di operazioni speciali (tipicamente funzioni di ordine superiore), che consentono di comporre questi parser primitive in più complicate, parser più specifici per la grammatica.

Questo non è l'unico modo per realizzare strutture parer ovviamente.

Answer 6

Fondamentalmente, un compilatore è una trasformazione da un set di codice a un altro - dalla sorgente all'IR, dall'IR all'IR ottimizzato, dall'IR all'assembly, ecc. Questo è esattamente il genere di linguaggio funzionale delle cose per cui è progettato - una pura funzione è solo una trasformazione da una cosa all'altra. Le funzioni imperative non hanno questa qualità. Sebbene tu possa scrivere questo tipo di codice in una lingua imperativa, le lingue funzionali sono specializzate per questo.

Answer 7

Una possibilità è che un compilatore tende ad avere a che fare con molta attenzione con tutta una serie di casi d'angolo. Ottenere il codice giusto è spesso reso più facile dall'uso di schemi di progettazione che strutturano l'implementazione in modo parallelo alle regole che implementa. Spesso questo finisce per essere un modello dichiarativo (pattern matching, "where") piuttosto che imperativo (sequencing, "when") e quindi più facile da implementare in un linguaggio dichiarativo (e la maggior parte di essi è funzionale).