Quali sono i vantaggi del parsing applicativo sull'analisi monadica?

Question

Sembra esserci un consenso sul fatto che dovresti usare Parsec come applicativo piuttosto che come monade. Quali sono i benefici dell'analisi applicativa sull'analisi monadica?

• stile
• prestazioni
• astrazione

è l'analisi monadica fuori?

Answer 1

La differenza principale tra l'analisi monodica e applicativa riguarda la modalità di gestione della composizione sequenziale. Nel caso di un parser applicativo, usiamo (<*>), mentre con una monade usiamo (>>=).

(<*>) :: Parser (a -> b) -> Parser a -> Parser b 
(>>=) :: Parser a -> (a -> Parser b) -> Parser b 

L'approccio monadica è più flessibile, perché permette la grammatica della seconda parte dipendere dal risultato del primo, ma raramente abbiamo bisogno di questo ulteriore flessibilità nella pratica.

Si potrebbe pensare che avere una certa flessibilità extra non possa far male, ma in realtà è possibile. Ci impedisce di fare analisi statiche utili su un parser senza eseguirlo. Ad esempio, supponiamo di voler sapere se un parser può corrispondere o meno alla stringa vuota e quali possono essere i possibili primi caratteri in una corrispondenza. Vogliamo funzioni

empty :: Parser a -> Bool 
first :: Parser a -> Set Char 

Con un parser applicativo, possiamo facilmente rispondere a questa domanda. (Sto imbrogliando un po 'qui Immaginate di avere un costruttore di dati corrispondente a (<*>) e (>>=) nel nostro parser candidato "lingue").

Tuttavia, con un parser monadico non sappiamo quale sia la grammatica della seconda parte senza conoscere l'input.

Consentendo più, siamo in grado di ragionare meno. Questo è simile alla scelta tra i sistemi di tipo dinamico e statico.

Ma qual è il punto di questo? A cosa potremmo usare questa conoscenza statica extra? Bene, possiamo ad esempio usarlo per evitare il backtracking in LL (1) parsing confrontando il prossimo carattere con il set first di ogni alternativa. Possiamo anche stabilire staticamente se ciò sarebbe ambiguo controllando se i set di first di due alternative si sovrappongono.

Un altro esempio è che può essere utilizzato per il recupero degli errori, come mostrato nel documento Deterministic, Error-Correcting Combinator Parsers di S. Doaitse Swierstra e Luc Duponcheel.

In genere, tuttavia, la scelta tra analisi parsing e applicativa è già stata effettuata dagli autori della libreria di analisi che si sta utilizzando. Quando una libreria come Parsec espone entrambe le interfacce, la scelta di quale utilizzare è puramente stilistica. In alcuni casi il codice applicativo è più facile da leggere rispetto al codice monadico e talvolta è il contrario.

Answer 2

Con Parsec il vantaggio dell'utilizzo di Applicative è proprio lo stile. Monad ha il vantaggio che è più potente: puoi implementare parser sensibili al contesto.

L'analisi UU di Doaitse Swierstra è più efficiente se utilizzata solo in modo applicativo.

Answer 3

Le Monade sono strettamente un'astrazione più funzionale di rispetto alle Richieste. Si potrebbe scrivere

instance (Monad m) => Applicative m where 
    pure = return 
    (<*>) = ap 

ma non c'è modo di scrivere

instance (Applicative a) => Monad a where 
    return = pure 
    (>>=) = ??? 

Quindi sì, è essenzialmente una questione di stile . Immagino che se usi return e ap, ci dovrebbe essere nessuna perdita di prestazioni sull'uso di pure e <*>. Poiché Applicative è un'interfaccia strettamente più piccola di Monad, ciò significa che a volte lo <*> può essere più ottimizzato di ap. (Ma con le intelligenti regole di riscrittura di GHC, spesso si ottengono le stesse ottimizzazioni a prescindere.)

L'analisi monodica è in corso?

Poiché le Monade sono un sottoinsieme di Applicativi, concluderei che l'analisi applicativa è un sottoinsieme di analisi monadica.

Answer 4

Il motivo principale che posso vedere preferire i parser applicativi rispetto ai parser monadici è lo stesso del motivo principale per preferire il codice applicativo rispetto al codice monadico in qualsiasi contesto: essendo meno potenti, gli applicativi sono più semplici da usare.

Questa è un'istanza di un più generale affermazione di ingegneria: utilizza lo strumento più semplice per eseguire il lavoro. Non utilizzare un carrello elevatore quando si eseguirà un carrello. Non utilizzare una sega da banco per tagliare i tagliandi. Non scrivere codice in IO quando potrebbe essere puro. Mantienilo semplice.

Ma a volte, è necessario la potenza aggiuntiva di Monad. Un segno sicuro di ciò è quando è necessario cambiare il corso del calcolo in base a ciò che è stato calcolato finora. In termini di analisi, ciò significa determinare come analizzare ciò che viene dopo in base a ciò che è stato analizzato finora; in altre parole, puoi costruire grammatiche sensibili al contesto in questo modo.

Answer 5

Se un parser è puramente applicativo, è possibile analizzarne la struttura e "ottimizzarlo" prima di eseguirlo. Se un parser è monadico, è fondamentalmente un programma completo di Turing e l'esecuzione di quasi tutte le analisi interessanti è equivalente a risolvere il problema di interruzione (cioè impossibile).

Oh, e sì, c'è una differenza stilistica troppo ...