Infinite loop scala code

Question

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
      }
    }
  }
}

I'm pretty sure I've an infinite loop caused by my 'default' case. I'm using recursion in all cases. Which is meant to be, but, only if the Prop can be simplified. As soon as the Prop can't be simplified, it should return the whole thing.

I don't see how I can test for any further simplification. (I'm not allowed to use other libraries, as suggested in freenodes #scala channel).

Can someone explain whether it IS the 'case _' causing the loop, and how to solve it? How can I test for possible simplification without making a loop?

Thanks in advance!

Answer 1

It is pretty obvious what happens and you are right with the default case. If your input prop does not match any of the cases you are invoking:

simplify(prop)

with the same argument. Because previously it caused recursive call to simplify() and you are calling your function with the same input, it enters simplify() again. So this is not an infinite loop but rather never terminated recursive call:

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

However the fix (based on your code) is simple:

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

just replace it with...

 case _ => prop

Both branches return the same value. This is actually correct if you think about if for a while. You have a set of optimizations. If none of them matched your expressions it means it can no longer be simplified. Hence you are returning it as-is.

BTW looks like you are doing boolean expressions simplification using case classes. You might by interested in my article where I do the same but with arithmetic expressions.

Answer 2

The problem is that you're trying to do two things in one step that need to happen in sequence—applying De Morgan's law (and removing double negation) and recursively simplifying any children. This is why just dropping a case And(a, b) => And(simplify(a), simplify(b)) into your match won't work.

Try the following:

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
}