5

I have written a simple class hierarchy to represent terms in Scala. Terms are recursive data types, e.g., a Sum and a Multiplication consist of the left-hand-side (lhs), which is a Term, and the right-hand-side (rhs), which is also a Term.

Scala's pattern matching makes it easy to check if a Term has a given structure. For instance, here's a method that returns t3 from the Term if it is structured as t1 * (t2 + t3):

def fetchT3(t: Term): Option[Term] = Some(t).collect {
  case Multiplication(t1, Sum(t2, t3)) => t3
}

Now I want to write the same in Java, but the lack of pattern matching makes it difficult. Usage of the instanceof operator if frowned upon, but I haven't found a real alternative. Here's what I have come up with so far:

public static <T> Optional<T> maybeAs(final Object obj, final Class<T> clazz) {
    try {
        return Optional.of(clazz.cast(obj));
    } catch (ClassCastException exc) {
        return Optional.empty();
    }
}

The fetchT3 method from above can then be written as:

public Optional<Term> fetchT3(final Term t) {
    return maybeAs(t, Multiplication.class).flatMap(mult ->
            maybeAs(mult.rhs, Sum.class).map(sum ->
                    sum.rhs
            )
    );
}

What I dislike about this approach is that first, it's using Exceptions for situations which are not truly exceptional, and second, it will become hard to read when terms are deeply nested. Using exceptions can be avoided by writing one method for each class (maybeAsSum, maybeAsMultiplication, …) and then using instanceof, which would one the other hand introduce code redundancy. Either way, casting classes is usually seen as a symptom of poor design in Java, but I don't know a way around it.

So my question is, would you consider this as an example of acceptable usage of class casting, or do you see a better method to check the term structure?

  • 1
    The usual OO approach is to use the visitor pattern which will avoid dynamic type checks, but that is probably overkill for something like this. – Lee Aug 25 '17 at 12:43
  • Pattern matching is a glorified instanceof in this case and has all its disadvantages. – Basilevs Aug 25 '17 at 18:45
  • @Basilevs: Are you referring to low performance? – Giorgio Aug 25 '17 at 19:11
  • No, conditional runtime dispatch – Basilevs Aug 25 '17 at 19:12
  • 1
    Runtime dispatch can't be verified in design time. Casting pattern matching is only helpful on sealed hierarchies. – Basilevs Sep 20 '17 at 18:52
2

It's been a while since I looked at Scala so I apologize if I miss the point here but one thing that you can do (that is not sexy) to do an instanceof is to create an enum type which enumerates all the kinds of Terms like so:

public enum Kind
{
    MULTIPLICATION, SUM; // etc.
}

And then on your Term class/interface:

Kind kind();

You can then use a switch statement or == to determine the type of the term. I'd argue though that instanceof seems appropriate in this case especially if you have Terms that are specializations of other Terms as instanceof may work as you want it to for that.

Performance of instanceof is not an issue. It's one of the fastest operations in the JVM, IIRC. It should be as fast, if not faster, than retrieving the class from an object and comparing. The reason it is discouraged is that it was often used in lieu of polymorphism by those who did not get it and also in equals implementations when it would break transitivity. This resulted in some nasty stuff.

1

You could implement a method for comparing the structure of Terms. This method would compare the subterms as well recursivelly.

static bool BothNull(Term a, Term b) { return a==null && b==null;}
static bool BothNotNull(Term a, Term b) { return a!=null && b!=null;}

class Term {

    Term rhs;
    Term lhs;
    Object value;

    Term(Object value){ this.value = value }

    bool HasEqualStructure(Term otherTerm) {
        bool sameType = this.GetType() == otherTerm.GetType();

        bool sameRhsType = BothNull(rhs, otherTerm.rhs)
                           || BothNotNull(rhs, otherTerm.rhs)
                              && rhs.HasEqualStructure(otherTerm.rhs);

        bool sameLhsType = BothNull(lhs, otherTerm.lhs)
                           || BothNotNull(lhs, otherTerm.lhs)
                              && lhs.HasEqualStructure(otherTerm.lhs);

        return sameType && sameRhsType && sameLhsType;
    }

    bool CopyValues(Term otherTerm) {
        if (HasEqualStructure(this, otherTerm)) {
            this.value = otherTerm.value;
            CopyValues(rhs, otherTerm.rhs);
            CopyValues(lhs, otherTerm.lhs);
            return true;
        }
        else
        {
            return false;
        }
    }
}

Then, in order to check for some very specific structure, you create a new Term instance with the structure you want and pass to this method, which ignores the values and only compares the types of the terms.

Does this work for your case?

EDIT: edited above code to also be able to fetch stuff from the structures.

The query could be implemented like this:

//t1 * (t2 + t3)
Sum s = new Sum(new Term(23), new Term(89));
Multiplication m = new Multiplication(new Term(123), s);

Term queryTerm = m;
Object t3Pointer = s.rhs;

Term actualRuntimeTerm = SomeActualTermOfYourApp();

if (queryTerm.CopyValues(actualRuntimeTerm))
    Console.WriteLine("T3 = {0}", t3Pointer);
}
  • This wouldn't allow to fetch terms nested inside other terms, like I did with the term t3. – helios35 Aug 25 '17 at 19:33
  • Yes, my example was just to compare the structures. But you could implement another logic in a similar way to fetch what you want, once you validate the structure. For instance, you could create another method like this, but that also copies the values from one Term to another. Then, you create a variable that points to T3 in you query Term, and call the method. After the method stops processing, your variable will point to T3's value copied. I'm not sure I was clear enough, but does this help you? – Emerson Cardoso Aug 25 '17 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.