Análisis monoidal - ¿qué es eso?

Question

Acabo de tropezar con el término análisis monoidal de un slide llamado "Introducción a los monoides" por Edward Kmett. La diapositiva usa haskell en todas partes.

Ahora cuando busco el término no encontré más que unas pocas menciones de él y la mayoría del mismo autor. Entonces creo que este término podría explicarse aquí.

Entonces, ¿es monoidal que analiza algo que es interesante y nuevo? ¿Aparece en cualquier lugar, excepto en la diapositiva a la que me he vinculado? Y lo más importante, ¿qué es? El deslizamiento en sí no parecía dar una definición ni destacarlo demasiado.

Answer 1

Comenzaré con cómo los analizadores usualmente funcionan. En general, un analizador toma tokens de entrada en orden secuencial. En algún momento (generalmente después de que todos los tokens están agotados), el analizador devuelve el resultado. 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 parciales parciales en un solo resultado. Por ejemplo, si nuestro lenguaje es representable con una gramática libre de contexto, entonces podríamos analizar cada definición de nivel superior por separado y en paralelo, luego ensamblar las piezas más tarde 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 asociatividad significa (a++b)++c == a++(b++c). Sucede que esta es la propiedad necesaria para garantizar que podamos recombinar resultados de análisis de forma sensata. No importa el orden exacto en que los submodos se recombinan, siempre que cada sub-parse se mantenga en la ubicación de secuencia correcta.

Por supuesto, para escribir realmente un analizador paralelo, es necesario dividir los trozos de manera apropiada también. Si desea analizar definiciones de nivel superior en paralelo, es necesario poder reconocer dónde comienza esa definición. Esta tarea generalmente la realiza el analizador en sí. Según recuerdo, una gran parte de sus diapositivas cubren este tema. Dividir en las definiciones de nivel superior es bastante grueso; lo ideal sería que nuestro analizador sintáctico pudiese partir de cualquier token arbitrario, luego tener sentido de las piezas más tarde cuando se aplica el operador monoide.

Desafortunadamente no puedo decir si el "análisis monoidal" es nuevo, ya que no estoy particularmente familiarizado con la literatura. Sin embargo, sospecho que cualquier modelo o algoritmo para el análisis paralelo implica una estructura monoide, incluso si no se nombra explícitamente. Hace tiempo que se sabe que los monoides son adecuados para paralelizar problemas, por lo que no me sorprendería que la técnica sea común entre los investigadores analizadores.

Answer 2

Pruebe su otra presentación en this page, es la número dos después de la que está leyendo. Es algo nuevo y todo lo que puedo hacer es parafrasear sus diapositivas y decirte que es un intento de tomar un análisis sintáctico monádico (como Parsec) y usar una estructura algebraica más débil para que haya más margen para reestructurar el cálculo. La idea es mejorar el paralelismo.

Editar: los comentarios en la página sugieren que las dos charlas fueron programadas una detrás de la otra, por lo que tal vez la mención en la diapositiva que viste fue un precursor para la segunda charla.