parsing - font - Análisis monoidal: ¿qué es?
monoid font (2)
Comenzaré con la forma en que normalmente funcionan los analizadores. En general, un analizador toma tokens de entrada en orden secuencial. En algún momento (normalmente después de que todos los tokens están agotados), el analizador devuelve la salida. Una desventaja de este modelo es que es inherentemente secuencial: como el analizador opera en una secuencia de tokens en orden, no es obvio cómo paralelizar el proceso.
Sin embargo, el análisis se puede paralelizar si tenemos acceso a una operación capaz de combinar resultados de análisis parciales en un solo resultado. Por ejemplo, si nuestro lenguaje se puede representar con una gramática libre de contexto, podríamos analizar cada definición de nivel superior por separado y en paralelo, y luego ensamblar las piezas más adelante utilizando la operación de combinación.
El análisis monoidal simplemente significa que el analizador tiene acceso a una función de combinación adecuada. Un monoide es una estructura con un elemento cero y un operador asociativo binario. Por ejemplo, las listas forman un monoide donde el cero es la lista vacía y el operador asociativo es la concatenación. Recuerde que significa asociatividad (a++b)++c == a++(b++c) . Sucede que esta es la propiedad necesaria para garantizar que podamos recombinar los resultados del análisis de una manera sensata. No importa el orden exacto en el que se vuelvan a combinar los subprocesos, siempre que cada uno de ellos se mantenga en la ubicación de secuencia correcta.
Por supuesto, para escribir realmente un analizador paralelo, también es necesario dividir los trozos adecuadamente. Si desea analizar las definiciones de nivel superior en paralelo, es necesario poder reconocer dónde comienza esa definición. Esta tarea suele ser realizada por el propio analizador. Como recuerdo, una gran parte de sus diapositivas cubren este tema. La división en definiciones de nivel superior es bastante burda; idealmente, nuestro analizador podría comenzar desde cualquier token arbitrario, y luego dar sentido a las piezas cuando se aplique el operador monoide.
Desafortunadamente, no puedo decir si el "análisis monoidal" es nuevo, ya que no estoy muy familiarizado con la literatura. Sin embargo, sospecho que cualquier modelo o algoritmo para el análisis paralelo involucra una estructura monoide, incluso si no tiene un nombre explícito. Desde hace algún tiempo se sabe que los monoides son adecuados para problemas de paralelismo, por lo que no me sorprendería que la técnica fuera común entre los investigadores de análisis.
Me topé con el término análisis monoidal de una slide llamada "Introduction to Monoids" de Edward Kmett . La diapositiva utiliza haskell en todo.
Ahora, cuando busqué el término, no encontré nada más que unas pocas menciones al mismo y la mayoría del mismo autor. Así que creo que este término podría explicarse aquí.
Entonces, ¿el análisis monoidal es algo interesante y nuevo? ¿Aparece en alguna parte excepto en la diapositiva a la que he vinculado? Y lo más importante, ¿qué es? La diapositiva en sí no parece dar una definición ni resaltarla tanto.
Pruebe su otra presentación en esta página , es la número dos después de la que está leyendo. Es algo nuevo y lo único que puedo hacer es parafrasear sus diapositivas y decirle que es un intento de realizar un análisis monádico (como Parsec) y usar una estructura algebraica más débil para que haya más posibilidades de reestructurar el cálculo. La idea es mejorar el paralelismo.
Edit: los comentarios en la página sugieren que las dos charlas fueron programadas en forma consecutiva, así que quizás la mención en la diapositiva que viste fue un precursor para la segunda charla.