Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was interested in solving several unrelated problems using generic graph search techniques, so after some fiddling around I came up with the following design: have each problem implement a generic "Problem" interface which has an initial state, and several methods that take in states and moves, and return new states and moves. For example, I can getMoves(state), applyMove(state, move), or check isGoal(state). All of the problem specific details are then in one place, and the generic algorithms can pass around states and moves as generic "tokens" that they don't really care about, using the Problem instance to evaluate their properties. The Problems are also consequently stateless (or what state they have is immutable), which makes their behaviour very easy to reason about.

This was all fine and good in a dynamic/duck type system (JavaScript), but in migrating the idea to a static/strict type system (Java), I've run into some issues.

The most immediate problem was that these "tokens" could really be anything. Arrays, objects, maps, strings, whatever. Javascript didn't care, because the algorithms just passed them around as black-boxes, and the Problems assumed they were being given their own tokens. In Java this is not the case. The first most natural solution is to have all the "tokens" implement some empty State or Move interface. This already has some problems, as if my state is just some data structure, then I need to extend or wrap the structure, but that's basically fine.

The next problem is that the tokens are implementation specific, so every time they're given to the Problem, they need to be cast into what they actually are. Lots of casting strikes me as a red flag, so this seems like a bad (certainly unpleasant) approach.

To avoid all the casting, I briefly considered something involving tons of templates (State<ChessProblem>, Move<ChessProblem>), but that seemed like a headache which might not even fix the problem.

Is there some "proper"/standard way to accomplish this in stricter type systems? Is this just a bad pattern to use in them (or a bad pattern overall)? Any insights would be appreciated. Also, while I am using Java, if other static/strict languages have novel tools for this sort of thing, I'd love to hear about them.

share|improve this question
    
Why can't you make the graph be generic and take a state type parameter again? That seems like a fairly obvious and idiomatic solution. –  Telastyn Feb 23 at 18:08
    
I'm not sure I follow, could you elaborate (note that the graph is largely implicit, as it may be far too large to explicitly compute). –  Gankro Feb 23 at 18:10

1 Answer 1

up vote 1 down vote accepted

I think you're almost there. Instead of having the States being generic, I would change the definitions of Problems. I assume you are currently thinking of something like this:

interface State {
}

interface Problem {
    public State foo(State s);
}

class ConcreteState implements State {
    ...
}

class ConcreteProblem implements Problem {
    // cannot narrow the argument type due to LSP
    @Override
    public ConcreteState foo(State s) {
        ConcreteState state = (ConcreteState) s;
        ...
        return state;
    }
}

We now make the Problem interface generic, and obtain the following:

interface State {
}

interface Problem<S extends State> {
    public S foo(S s);
}

class ConcreteState implements State {
    ...
}

class ConcreteProblem implements Problem<ConcreteState> {
    @Override
    public ConcreteState foo(ConcreteState s) {
        ...
    }
}

For full benefits, care has to be taken that the State does not leave the Problem, e.g. by storing it externally. This means that the Problem should probably also be used as a State-factory.

share|improve this answer
    
Ah! Brilliant! The algorithms do indeed store the states/moves, though (graph search generally needs to remember where it's been and where it's going). I suppose I could make the algorithms generic as well? –  Gankro Feb 23 at 18:19
    
@Gankro Yes, this pattern allows you to vary the parameter types in a type-safe manner without violating the LSP. My examples uses only one class and one parameter, but it can be extended arbitrarily. Note that in simple cases it's sufficient to make only a single method generic, e.g. public <S extends State> S foo(S state). –  amon Feb 23 at 18:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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