Código scala loop infinito

object Prop { 
    def simplify(prop : Prop) : Prop = { 
    prop match { 
     case Not(Or(a,b)) => simplify(And(Not(a),Not(b))) 
     case Not(And(a,b)) => simplify(Or(Not(a),Not(b))) 
     case Not(Not(a)) => simplify(a) 
     case _ => { 
     if (simplify(prop) == prop) prop 
     else prop 
     } 
    } 
    } 
}

Estoy bastante seguro de que tengo un bucle infinito causado por mi caso 'predeterminado'. Estoy usando recursividad en todos los casos. Lo cual debe ser, pero solo si la Prop puede simplificarse. Tan pronto como la Prop no se pueda simplificar, debería devolver todo.Código scala loop infinito

No veo cómo puedo probar para una mayor simplificación. (No tengo permitido usar otras bibliotecas, como se sugiere en el canal freenades #scala).

¿Alguien puede explicar si ES el 'caso _' que causa el bucle, y cómo resolverlo? ¿Cómo puedo probar una posible simplificación sin hacer un ciclo?

¡Gracias de antemano!

Fuente

2012-02-25 Sander

El problema es que estás tratando de hacer dos cosas en un paso que deben suceder en secuencia: aplicar la ley de De Morgan (y eliminar la doble negación) y simplificar recursivamente a los niños. Esta es la razón por la cual dejar caer un case And(a, b) => And(simplify(a), simplify(b)) en su match no funcionará.

intente lo siguiente:

val deMorganAndDoubleNegation: Prop => Prop = { 
    case Not(Or(a, b)) => And(Not(a), Not(b)) 
    case Not(And(a, b)) => Or(Not(a), Not(b)) 
    case Not(Not(a)) => a 
    case a => a 
} 

val simplify: Prop => Prop = deMorganAndDoubleNegation andThen { 
    case And(a, b) => And(simplify(a), simplify(b)) 
    case Or(a, b) => Or(simplify(a), simplify(b)) 
    case Not(a) => Not(simplify(a)) 
    case a => a 
}

Fuente

2012-02-25 23:11:47

Veo lo que quiere decir. Sin embargo, mi tarea me dice explícitamente que use un objeto complementario. Prop.simplify (Prop): Prop que devuelve una Proposición simplificada y equivalente al aplicar repetidamente la ley de Morgan y la elliminación de doble negación al argumento Proposition. La proposición resultante debe cumplir con los requisitos detallados a continuación. Además, su sugerencia no coincide por completo. mis profesores responden (tenemos un sistema para ejecutar nuestro trabajo en contra de una prueba) Ver: http://pastebin.com/WDuQKreD (también para el bacalao completo e por el momento) ¡Gracias de todos modos! – Sander

@Sander: Solo tiene que agregar casos a 'simplify' para las otras operaciones (también, lamento no haber entendido que esto es tarea, no habría sido tan directo en mi respuesta). –

@Sander: Además, tanto heredar de una clase de caso como tener una clase de caso con un constructor vacío son malas. 'rasgo Prop; case object True extends Prop' es mejor. –

Es bastante obvio lo que sucede y tiene razón con el valor predeterminado case. Si la entrada prop no coincide con ninguno de los casos está invocando:

simplify(prop)

con el mismo argumento. Como anteriormente causaba una llamada recursiva al simplify() y está llamando a su función con la misma entrada, ingresa simplify() nuevamente. Así que esto no es un bucle infinito, sino que nunca se termina la llamada recursiva:

...simplify(simplify(simplify(simplify(simplify(simplify(simplify(prop)))))))

Sin embargo, la solución (basado en su código) es simple:

if (simplify(prop) == prop) prop 
    else prop

simplemente reemplazarlo con ...

case _ => prop

Ambas ramas devuelven el mismo valor. Esto es realmente correcto si piensas si por un tiempo. Tienes un conjunto de optimizaciones. Si ninguno de ellos coincide con sus expresiones, significa que ya no se puede simplificar. Por lo tanto, lo está devolviendo tal como es.

BTW parece que está haciendo una simplificación de expresiones booleanas usando clases de casos. Podrías interesarte en mi article donde hago lo mismo pero con expresiones aritméticas.

Fuente

2012-02-25 21:59:33

Gracias por su respuesta. Intenté hacerlo. (Lo siento, presioné enter, y publicado sin querer). Pero en algunos casos, la simplificación da como resultado una cadena que contiene un nuevo Not (Not (a)) por ejemplo, por lo que volver a ejecutar simplify los eliminaría. Pero, no puedo hacer que vuelva a ejecutarlo cuando parece ser una nueva coincidencia en cualquiera de los casos anteriores ...: \ – Sander

@Sander: ¿puede mostrarnos la entrada que no está simplificando 'Not (Not (a)) ' Esto se puede solucionar llamando a 'simplify()' en términos separados como, e.g: para simplificar 'And (Not (Not (a)), b)' debe devolver 'And (simplify (Not (Not (a)), simplify (b))' (el patrón de simplificación es: 'And (a , b) => Y (simplifica (a), simplifica (b)) '. –

@Thomasz' No (Y (No (a), No (b))) 'Esto primero se simplificará a' O (No (No (a)), Not (Not (b))) 'por lo que puedo ver. El código debería volver a ejecutarse para eliminar el Not (Not (a)) recién creado y Not (Not (b)). – Sander

Sí, la carcasa predeterminada está causando el bucle. if (simplify(prop) == prop) prop es una línea problemática. No necesita probar si puede simplificarse aún más, ya que cuando se encuentra en el caso predeterminado se intentan todas las simplificaciones posibles.

Fuente

2012-02-25 22:06:44 mmmbell

Respuesta

Cuestiones relacionadas