Mantener el estado en un mundo sin estado

Question

Estoy convirtiendo una gramática sin contexto en la Forma normal de Greibach (GNF). La transformación principal (de Hopcroft & Ullman) es una secuencia de iteraciones sobre las variables indexadas de la gramática. Es esencialmente "sin estado". He implementado como una secuencia de pliegues a través de los índices apropiados (la aplicación es bastante sencillo):

gnf :: Ord a => Set (Rule a) -> Set (Rule a) 
gnf rl = foldl step1 rl [1..maxIndex rl] 
where step1 rl' k = foldl step2 rl' [1..k - 1] 
     where step2 rl'' j = noLR k (subst rl'' k j) 

maxindex rl devuelve el índice máximo variable en un conjunto de reglas; subst rl k j realiza la sustitución en el k -reglas indexadas por las reglas cuyo lado derecho comienza con un j -variable indexada. Después de realizar gnf, debo realizar un pase final sobre la gramática en orden inverso.

El problema es noLR, que transforma una gramática con k reglas -indexed izquierda-recursivo. Esta es una función "con estado", ya que se debe generar una variable única para cada regla (o k-regla indexada) a la que se aplica noLR. Así que escribí una función de estado

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a)) 
noLR rl = do (n:ns) <- get; put ns; 
      let rl' = ... remove left recursion rl n ... 
       in return rl' 

puedo secuenciar junto al noLR con el fin de actualizar el n cuales noLR toma como parámetro. Estoy no seguro de cómo realizar noLR dentro de paso2 en la función anterior, sin embargo. Parece que no puedo usar el let ... en el esquema, porque el cálculo con estado está incrustado dentro de varias funciones recursivas.

Lo que quiero hacer es tener n haber algún tipo de variable global, similar a una rosca explícita de n, que puedo llamar y actualización dentro paso 2, por lo que escribí originalmente la función como un pliegue con eta -expansión (para n). ¿Alguien sabe cómo podría estructurar gnf dentro de la mónada de estado para lograr este tipo de efecto? Excepto por el último cálculo en el pliegue, nada más es "con estado", y solo me siento cómodo usando la mónada de estado con ejemplos "triviales". Estoy bastante perdido.

Answer 1

Para utilizar noLR con el tipo que ha dado, que tendrá que volver a escribir la función gnf lo largo de las siguientes líneas:

gnf :: Ord a => Set (Rule a) -> Set (Rule a) 
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) (... generate the initial state [Sym a] here ...) 
where step1 rl' k = foldM step2 rl' [1..k - 1] 
     where step2 rl'' j = noLR k (subst rl'' k j) 

existe su variable de estado durante todo el cálculo, y que el hecho tiene que hacerse explícito en el código.

Si todo lo que necesitas es que los nombres de las variables recién generadas no colisionen entre sí, entonces puedes hacer noLR puro generando un nuevo nombre de símbolo de los índices k y j - algo así como "foo_42_16" para k == 42 yj == 16. Si la gramática de entrada ya contiene nombres de símbolos de ese tipo, es posible que tenga problemas.

Si necesita que sus símbolos sean únicos dentro de la gramática, ¿por qué no decir exactamente eso?

newSymbol :: Set (Rule a) -> Sym a 
newSymbol rl = ... find a symbol name not used in rl ... 

Esto definitivamente no es eficiente, sin embargo, a menos que reemplace Conjunto (la regla a) por un tipo diferente que le permite implementar la operación newSymbol de manera más eficiente.

Answer 2

Intentaré reescribir noLR para ser puro. ¿Estás seguro de que no puedes reescribirlo para generar un símbolo que solo depende del nombre de la regla y su índice (o algo similar)?

noLR k j = noLR' k j $ newSymbol k j 
    where newSymbol k j = ... -- some concatenation of k and j 
      noLR' k j sym = ... -- your now pure function