Passing around impl-specific tokens in generic algorithms in a static/strong type system

Question

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.

Answer 1

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.