Analisi parziali - che cos'è?

Question

Mi sono appena imbattuto nel termine parsing monoideo da un slide denominato "Introduzione ai mono" entro il Edward Kmett. La diapositiva utilizza haskell in tutto.

Ora durante la ricerca del termine non ho trovato altro che poche citazioni e il massimo dallo stesso autore. Quindi penso che questo termine potrebbe essere spiegato qui.

Quindi, è parsing monoideo qualcosa che è interessante e nuovo? Appare ovunque tranne che nella diapositiva a cui mi sono collegato? E soprattutto cosa è? La diapositiva stessa non sembra dare una definizione, né evidenziarlo più di tanto.

Answer 1

Inizierò con il modo in cui i parser di solito funzionano. In generale, un parser prende i token di input in ordine sequenziale. Ad un certo punto (in genere dopo che tutti i token sono esauriti), il parser restituisce l'output. Uno svantaggio di questo modello è che è intrinsecamente sequenziale: poiché il parser opera su una sequenza di token in ordine, non è ovvio come parallelizzare il processo.

Tuttavia, l'analisi può essere parallelizzata se si ha accesso a un'operazione in grado di combinare i risultati parziali parziali in un singolo risultato. Ad esempio, se la nostra lingua è rappresentabile con una grammatica context-free, allora potremmo analizzare ogni definizione di livello superiore separatamente e in parallelo, quindi assemblare i pezzi in seguito utilizzando l'operazione di combinazione.

L'analisi monodimensionale significa semplicemente che il parser ha accesso a una funzione di combinazione adeguata. Un monoide è una struttura con un elemento zero e un operatore associativo binario. Ad esempio, gli elenchi formano un monoid dove lo zero è la lista vuota e l'operatore associativo è la concatenazione. Ricorda che associatività significa (a++b)++c == a++(b++c). Succede che questa è la proprietà necessaria per garantire che siamo in grado di ricombinare i risultati di analisi in modo sensato. L'ordine esatto in cui le sub-parses vengono ricombinate non ha importanza, a patto che ogni sottoanalisi sia mantenuta nella corretta posizione della sequenza.

Naturalmente per scrivere effettivamente un parser parallelo, è necessario dividere i blocchi in modo appropriato. Se si desidera analizzare le definizioni di livello superiore in parallelo, è necessario essere in grado di riconoscere dove inizia quella definizione. Questa attività viene solitamente eseguita dallo stesso parser. Ricordo che gran parte delle sue diapositive trattano questo argomento. La suddivisione nelle definizioni di livello superiore è piuttosto grossolana; idealmente il nostro parser sarebbe in grado di partire da qualsiasi token arbitrario, quindi dare un senso ai pezzi più tardi quando viene applicato l'operatore monoid.

Purtroppo non riesco a dire se "l'analisi monoidale" sia nuova, in quanto non ho molta familiarità con la letteratura. Tuttavia, sospetto che qualsiasi modello o algoritmo per l'analisi parallela coinvolga una struttura monoid, anche se non è esplicitamente denominato. È risaputo da tempo che i monoidi sono adatti per la parallelizzazione dei problemi, quindi non sarei sorpreso se la tecnica fosse comune tra i ricercatori del parser.

Answer 2

Prova la sua altra presentazione allo this page, è il numero due dopo quello che stai leggendo. È qualcosa di nuovo e tutto ciò che posso realmente fare è parafrasare le sue diapositive e dirvi che è un tentativo di eseguire il parsing monadico (come Parsec) e utilizzare una struttura algebrica più debole in modo che ci sia più spazio per ristrutturare il calcolo. L'idea è di migliorare il parallelismo.

Modifica: i commenti sulla pagina suggeriscono che i due colloqui sono stati pianificati uno dopo l'altro, quindi forse la menzione sulla diapositiva che hai visto era un precursore del secondo discorso.