Recursion with bitwise operators

I have the following method in java that simplify Nor expressions using recursion:

public Expression simplify() {
        // x ↓ T = F
        if (this.getRight().toString().equals("T")) {
            return new Val(false).simplify();
        }
        // T ↓ x = F
        if (this.getLeft().toString().equals("T")) {
            return new Val(false).simplify();
        }
        // x ↓ F = ~(x)
        if (this.getRight().toString().equals("F")) {
            return new Not(super.getLeft().simplify());
        }
        // F ↓ x = ~(x)
        if (this.getLeft().toString().equals("F")) {
            return new Not(super.getRight().simplify());
        }
        // x ↓ x = ~(x)
        if (this.getLeft().toString().equals(this.getRight().toString())) {
            return new Not(this.getRight().simplify());
        }
        return new Nor(this.getLeft().simplify(), this.getRight().simplify());
    }  

Now, when I want to simplify the expression (T ↓ y) ↓ y , it ouputs F ↓ y instead of ~(y).
How I need to change the recursion to output the right simplified expression?

Answer

Your case isn’t covered, so you get the default, all the way at the end: simplify the left, simplify the right, then return that.

The problem is, you simplify the left node, turning (T ↓ y) into F, and the right node (no change), but you then fail to continue applying the simplification: You simply return lhs ↓ rhs, without simplifying this.

A very simple debug run should have found this, no? Maybe next time try to read your code and step through it a little more before reaching for SO.

For what it’s worth, there are 2 significant improvements I’d make here:

I’d work inside out, that is almost by definition smarter, as your simplification rules all work only on non-complex nodes.

Thus, I’d take your left and right nodes, simplify those first, and THEN run your simplification rules. This then obviates the need to simplify the end result.

Thus, instead of passing super.getRight() in a million places, start off with:

Node left = getLeft().simplify();
Node right = getRight().simplify();

and then go through your rules, this time just using left and right (vs super.getLeft().simplify(). If none of your rules apply, no further simplification is going to help you out, so you can just return new Nor(left, right), and be done with it.

Second major update: toString() is a debugging / logging tool ONLY – programming your business logic vs. toString is neccessarily broken behaviour, even if it is not a straight up bug. Thus, checking ‘is the left node the node representing a constant TRUE value’ by way of getLeft().toString().equals("T") is bad code style and asking for trouble down the road.

There should be a proper way to check this. perhaps it is if (left.isConstantTrue()) or perhaps if (left.equals(Node.TRUE)), or maybe if (left instanceof Constant c && c.value) (that’s JDK16 syntax, it’s a mouthful without JDK16: if ((left instanceof Constant) && ((Constant) left).value).

None of these are dependent on the debugging aid code to never change, and for any other node to never print T either, and in general fixes your code to be idiomatic, instead of a thing that is going to trigger every linter tool out there.

Also, the super invokes are bizarre. You sometimes call super.getRIght, and other times you call this.getRight. In general, don’t specify this/super unless you have a specific reason. Why would you want to skip past any local override of getRight? You probably don’t / you may not even have an override, which makes super.getRight(), this.getRight() and just getRight() all 100% equivalent. Just write getRight() – that matches with your semantic intent, which is simply ‘get the Right node’, instead of ‘get the superclass impl of getRight, intentionally skipping past any custom modifications this instance has performed’.