How to implement general state machine without dynamic types?

help
1

This is a basic question relating to how to live without dynamic types/interfaces (as they exist in e.g. Golang).

I'd like to implement some general state machine code that allows a user to just specify state transitions and validation functions. The general state machine code needs to loop over new messages and run the transitions in a loop, such as:

loop {
  msg = listen(chan)
  state_machine.verify(msg)
  state_machine = state_machine.process(msg)   // transition
  if state_machine.state.end_state() {
     break;
   }
  }

The caller of this code basically populates the types for state_machine.state and implements the corresponding functions and the general code above can be applied to any state machine.

I think in Golang this would be implemented using interfaces; the state_machine struct would have a state field which satisfies an interface that includes verify and process and then state_machine.process would act on the specific type that happened during the run time.

I am vaguely familiar with how Rust's type system is more strict and that as a consequence, this is not possible directly in Rust (a la Golang interfaces). What would be the closest way? If there is any code that implements a general state machine like this, please link. Also what are the benefits of not having dynamic types.

2

One approach would be something like this:

trait StateMachine<Message>: Sized {
    type VerifyErr: std::error::Error;
    fn initial()->Self;
    fn verify(&self, msg: Message)->Result<Message, Self::VerifyErr>;
    fn process(self, msg: Message)->Self;
    fn is_done(&self)->bool;

    fn process_many(mut self, msgs: impl Iterator<Item=Message>)
        ->Result<Self, Self::VerifyErr> {
        for msg in msgs {
            let msg = self.verify(msg)?;
            self = self.process(msg);
            if self.is_done() { break; }
        }
        Ok(self)
    }
}

enum MyStateMachine {
    State1,
    State2(u32),
    // ...
}

impl StateMachine<u32> for MyStateMachine {
    // ...
}
2 Likes
3

Rust does have a form of interfaces for dynamic types. But they are called "traits". The main difference from Go (as I understand it) and for example TypeScript is that Rust uses a nominal type system instead of a (partially) structural type system. So the caller will have to implement a State<Message> (assuming generic over message type) trait that you define, and then you can use Box<dyn State<Message>> inside your state machine to erase the actual type. Or have the whole state machine behind a trait object, like above. But with only a state trait, it could be a bit like this:

trait State<Message> {
    type Error;

    fn verify(&self, message: &Message) -> Result<(), Self::Error>;
    fn process(self, message: Message) -> Self;
    fn end_state(&self) -> bool;
}
3 Likes