L'uso di Haskell monade un odore di codice?

Question

Dio odio il termine "odore di codice", ma non riesco a pensare a nulla di più preciso.

Sto progettando un compilatore di lingua di alto livello & nel Whitespace nel mio tempo libero per informazioni sulla costruzione del compilatore, sulla progettazione del linguaggio e sulla programmazione funzionale (il compilatore viene scritto in Haskell).

Durante la fase di generazione del codice del compilatore, devo mantenere i dati "state" -ish mentre percorro l'albero della sintassi. Ad esempio, quando si compila le dichiarazioni di flusso di controllo ho bisogno di generare nomi unici per le etichette di saltare a (etichette generate da un contatore che è passato in, aggiornato, & restituito, e il vecchio valore del contatore non deve mai essere usato di nuovo). Un altro esempio è quando mi imbatto in letterali di stringa in linea nell'albero della sintassi, devono essere convertiti in modo permanente in variabili heap (in Whitespace, le stringhe vengono memorizzate al meglio nell'heap). Sto attualmente avvolgendo l'intero modulo di generazione del codice nella monade di stato per gestirlo.

Mi è stato detto che scrivere un compilatore è un problema adatto al paradigma funzionale, ma trovo che lo sto progettando più o meno nello stesso modo in cui lo progetterei in C (puoi davvero scrivere C in qualsiasi lingua - anche Haskell w/state monads).

Voglio imparare come pensare in Haskell (piuttosto, nel paradigma funzionale) - non in C con la sintassi di Haskell. Dovrei davvero cercare di eliminare/ridurre al minimo l'uso della monade di stato, o è un "modello di progettazione" legittimo e funzionale?

Answer 1

Direi che lo stato in generale non è un odore di codice, a patto che sia tenuto piccolo e ben controllato.

Ciò significa che l'utilizzo di monade come State, ST o personalizzate, o semplicemente avere una struttura dati contenente dati di stato che si passano in pochi punti, non è una cosa negativa.(In realtà, le monadi sono solo di aiuto nel fare esattamente questo!) Tuttavia, avendo uno stato che va dappertutto (sì, questo significa che, IO monade!) È un cattivo odore.

Un esempio abbastanza chiaro di questo è stato quando il mio team stava lavorando al nostro ingresso per lo ICFP Programming Contest 2009 (il codice è disponibile su git: //git.cynic.net/haskell/icfp-contest-2009). Abbiamo finito con parecchie parti modulari differenti a questo:

• VM: la macchina virtuale che ha eseguito il programma di simulazione
• Controllers: diverse serie di routine che leggono l'uscita del simulatore e generato nuovi ingressi di controllo
• Soluzione: generazione del file di soluzione in base all'output dei controller
• Visualizzatori: diversi set di routine che leggono sia le porte di input che di output e generato una sorta di visualizzazione o registro di ciò che stava accadendo come simulazione progresso

Ognuno di questi ha il proprio stato e tutti interagiscono in vari modi attraverso i valori di input e output della VM. Avevamo diversi controller e visualizzatori, ognuno dei quali aveva il suo diverso tipo di stato.

Il punto chiave qui era che gli interni di un particolare stato erano limitati ai loro moduli particolari, e ogni modulo non sapeva nulla nemmeno dell'esistenza dello stato per altri moduli. Qualsiasi insieme particolare di codice e dati stateful era in genere lungo solo alcune dozzine di righe, con una manciata di elementi di dati nello stato.

Tutto questo era incollato insieme in una piccola funzione di circa una dozzina di linee che non avevano accesso agli interni di nessuno degli stati, e che semplicemente chiamava le cose giuste nell'ordine corretto mentre passava attraverso la simulazione, e passato un numero molto limitato di informazioni esterne a ciascun modulo (insieme allo stato precedente del modulo, ovviamente).

Quando lo stato viene utilizzato in modo limitato e il sistema di tipi impedisce di modificarlo inavvertitamente, è piuttosto semplice da gestire. È una delle bellezze di Haskell che ti consente di farlo.

Una risposta dice "Non usare le monadi". Dal mio punto di vista, questo è esattamente al contrario. Le Monade sono una struttura di controllo che, tra le altre cose, può aiutare a ridurre al minimo la quantità di codice che tocchi stato. Se si considerano i parser monadici come esempio, lo stato dell'analisi (cioè, il testo che viene analizzato, il punto in cui ci si è immessi, eventuali avvisi accumulati, ecc.) Deve essere eseguito attraverso ogni combinatore utilizzato nel parser . Eppure ci saranno solo alcuni combinatori che manipolano direttamente lo stato; qualsiasi altra cosa usa una di queste poche funzioni. Questo ti consente di vedere chiaramente e in un unico punto tutta una piccola quantità di codice che può cambiare lo stato, e più facilmente ragionare su come può essere cambiato, rendendolo ancora più facile da gestire.

Answer 2

Beh, non utilizzare monadi. Il potere della programmazione funzionale è la purezza della funzione e il loro riutilizzo. C'è questo articolo che un mio professore ha scritto una volta ed è uno dei ragazzi che ha aiutato a costruire Haskell.

La carta si chiama "Why functional programming matters", suggerisco di leggerlo. È una buona lettura

Answer 3

cerchiamo di essere attenti sulla terminologia qui. Lo stato non è di per sé cattivo; le lingue funzionali hanno lo stato. Ciò che è un "odore di codice" è quando ti ritrovi a voler assegnare valori di variabile e modificarli.

Naturalmente, la monade di stato Haskell è lì solo per questo motivo - come con I/O, ti consente di fare cose non sicure e non funzionali in un contesto limitato.

Quindi, sì, probabilmente è un odore di codice.

Answer 4

Hai guardato Attribute grammars (AG)? (Maggiori informazioni su wikipedia e un article in Monad Reader)?

Con AG è possibile aggiungere attributi a un albero di sintassi. Questi attributi sono separati in sintetizzato e ereditato attributi.

attributi sintetizzati sono cose che si generano (o sintetizzare) dal vostro albero di sintassi, questo potrebbe essere il codice generato, o tutti i commenti, o qualsiasi altra cosa il vostro interesse.

attributi ereditati sono input per il vostro albero di sintassi, questo potrebbe essere l'ambiente o un elenco di etichette da utilizzare durante la generazione del codice.

Presso l'Università di Utrecht utilizziamo lo Attribute Grammar System (UUAGC) per scrivere i compilatori.Si tratta di un pre-processore che genera codice haskell (file .hs) dai file .ag forniti.

---

Anche se, se si sta ancora imparando Haskell, allora forse questo non è il momento di iniziare ad imparare un altro livello di astrazione più di questo.

In questo caso, si potrebbe scrivere manualmente il tipo di codice che attribuisce grammatiche generano per voi, per esempio:

data AbstractSyntax = Literal Int | Block AbstractSyntax 
        | Comment String AbstractSyntax 

compile :: AbstractSyntax -> [Label] -> (Code, Comments) 
compile (Literal x) _  = (generateCode x, []) 
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls 
          in (labelCode l code', comments) 
compile (Comment s ast) ls = let (code, comments') = compile ast ls 
          in (code, s : comments') 

generateCode :: Int -> Code 
labelCode :: Label -> Code -> Code 

Answer 5

ho scritto più compilatori in Haskell, e una monade stato è una soluzione ragionevole a molti problemi del compilatore. Ma tu vuoi tenerlo astratto --- non rendere evidente che stai usando una monade.

Ecco un esempio del Compilatore Haskell di Glasgow (che ho fatto non in scrittura, ho appena risolto alcuni bordi), dove costruiamo i grafici del flusso di controllo. Qui ci sono i modi principali per i grafici:

empyGraph :: Graph 
mkLabel  :: Label -> Graph 
mkAssignment :: Assignment -> Graph -- modify a register or memory 
mkTransfer :: ControlTransfer -> Graph -- any control transfer 
(<*>)  :: Graph -> Graph -> Graph 

Ma, come hai scoperto, il mantenimento di una fornitura di etichette uniche è noioso nel migliore dei casi, in modo da fornire queste funzioni così:

withFreshLabel :: (Label -> Graph) -> Graph 
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition 
      -> Graph -- code in the 'then' branch 
      -> Graph -- code in the 'else' branch 
      -> Graph -- resulting if-then-else construct 

Il L'intera cosa Graph è un tipo astratto, e il traduttore costruisce animatamente i grafici in modo puramente funzionale, senza essere consapevole del fatto che sta accadendo qualcosa di monadico. Quindi, quando il grafico è finalmente costruito, per trasformarlo in un tipo di dati algebrico da cui possiamo generare il codice, gli diamo una scorta di etichette univoche, eseguiamo la monade di stato e tiriamo fuori la struttura dei dati.

La monade di stato è nascosta sotto; anche se non è esposto al cliente, la definizione di Graph è qualcosa di simile:

type Graph = RealGraph -> [Label] -> (RealGraph, [Label]) 

o un po 'più accuratamente

type Graph = RealGraph -> State [Label] RealGraph 
    -- a Graph is a monadic function from a successor RealGraph to a new RealGraph 

Con la monade stato nascosto dietro uno strato di astrazione, non è maleodorante affatto!

Answer 6

E 'possibile che si può prendere un funtore applicativa invece di un monade:

http://www.haskell.org/haskellwiki/Applicative_functor

penso che il lavoro originale spiega meglio di wiki, però:

http://www.soi.city.ac.uk/~ross/papers/Applicative.html

Answer 7

In generale dovresti cercare di evitare lo stato ogni volta che è possibile, ma questo non è sempre pratico. Applicative rende il codice effetto più gradevole e più funzionale, in particolare il codice di attraversamento degli alberi può trarre vantaggio da questo stile. Per il problema della generazione dei nomi ora è disponibile un pacchetto piuttosto interessante: value-supply.

Answer 8

Non credo che l'uso della Monade di stato sia un odore di codice quando è utilizzato per modellare lo stato.

Se è necessario specificare lo stato tramite le proprie funzioni, è possibile eseguire esplicitamente lo , prendendo lo stato come argomento e restituendolo in ogni funzione. La Monade di stato offre una buona astrazione: passa lo stato per te e offre molte funzioni utili per combinare funzioni che richiedono uno stato. In questo caso, l'utilizzo della Monade di stato (o dei candidati) non è un odore di codice.

Tuttavia, se si utilizza la Monade di stato per emulare uno stile imperativo di programmazione mentre una soluzione funzionale sarebbe sufficiente, si stanno solo complicando le cose.