Lack of support for final states.

[thundergolfer]

I am currently using this library to implement some algorithms from a Computing Theory textbook, and though this library is great and full of features, you can't designate a set of 'final' or 'accepting' states which are needed for representing DFAs and NFAs in a theoretical context.

You may not want to incorporate this sort of thing into core.py but do you think it could find a place in the package? I might be better off forking and re-configuring this for theoretical use.

[aleneum]

Hello @thundergolfer,

I am glad that you bring this up. It is on my (personal) discussion list for transitions since solving #128 will be a big step towards concurrent states where 'final' states may also be required. I think we could add a _create_state method to Machine similar to Machine._create_transition or Machine._create_event. This would at least allow things like this:

from transitions import Machine, State
states = ['A', 'B', {'name': 'C', 'final': True}]
class FinalState(State):
    def __init__(self, name, on_enter=None, on_exit=None,
                 ignore_invalid_triggers=False, final=False):
        self.final = final
        super(FinalState, self).__init__(name, on_enter, on_exit, ignore_invalid_trigger)

class FinalMachine(Machine):
    def _create_state(*args, **kwargs):
        return FinalState(*args, **kwargs)

m = FinalMachine(states=states, initial='C')
print m.get_state(m.state).final
>>> True

But let's wait for more feedback. Other approaches or ideas will be appreciated.

[aleneum]

FYI:

HierarchicalMachine has a _create_state method. So this should be a working example:

from transitions.extensions.nesting import HierarchicalMachine, NestedState
states = ['A', 'B', {'name': 'C', 'final': True}]


class FinalState(NestedState):
    def __init__(self, *args, **kwargs):
        self.final = kwargs.pop('final', False)
        super(FinalState, self).__init__(*args, **kwargs)

class FinalMachine(HierarchicalMachine):
    @staticmethod
    def _create_state(*args, **kwargs):
        return FinalState(*args, **kwargs)

m = FinalMachine(states=states, initial='C')
print m.get_state(m.state).final

Nevertheless, it might be useful to also have _create_state in Machine

[aleneum]

Another approach I was thinking about is to check whether a state acts as a transition source. If the state cannot be left it is implicitly a final state whereas a final state with possible transitions cannot be that final.

Class Machine(object): 
    ...
    def final(self, model): # method is bound to the model(s)
        for ev in self.events:
            if model.state in ev:
                return False
        return True

[thundergolfer]

@aleneum : This wouldn't work there are non-final states with no outgoing transitions, and final states with outgoing transitions. At least there are in the Finite State Machines I am playing with in my Computing Theory textbook.

A non-final state with no outgoing transitions is sometimes used as a 'fail' state, for example.

[aleneum]

Yeah, makes sense. Flickers of memories of computer linguistic seminars come back to my mind :).
So we need a set of failed and accepted states. These could be either added to the Machine or to the states themselves

Machine(..., initial='A', accepted=['D'], failed=['C'])

One could also think about how the library should handle a failed state.
Throwing a MachineError would be one solution.

[aleneum]

I spent some more time thinking about this and right now I could also see this work within the model. If you consider the machine just being 'responsible' for managing transitions and letting the model add meaning and actions to states, this would make sense in my eyes:

class FSAModel(object):
    def __init__(self, accepted, failed):
        self.accepted_states = accepted
        self.failed_states = failed

    # possibility A
    def check_state(self):
        if self.state in self.accepted_states:
            print("Weee")
        elif self.state in self.failed_states:
            raise Error('Failstate reached!')

     # possibility B
     @property
     def accepted(self):
         return self.state in self.accepted_states

...
states = ['A', 'B', 'C', 'F']
model = FSAModel(accepted=['A'], failed=['F'])
machine = Machine(model, states=states, after_state_change='check_state', initial='A')
machine.accepted # True
model.to_F() # raises Error

Maybe in this case one could think of an 'implicit' definition of failed states like if self.state has no transition and self.state not in self.accepted.

@tyarkoni, @wtgee: What do you think?

[thundergolfer]

@aleneum: I think an implicit definition of failed states works fine.

Would the FSAModel be an extension module of the package?

[aleneum]

The transitions package does not include models for now. I am not sure if @tyarkoni plans to add an extension module for model mixins. Since there is potential for reusing things like FSAModel it might be a thing to consider.

[tyarkoni]

I don't have any principled objection to model mixins, and actually kind of like the idea. I also like the idea of handling accepted and rejected states in the model rather than in Machine. That said, I think if we were to add a model mixin, it should probably be something more generic, and support arbitrary tags on model states--and then final/rejected states can just be a special case. For example, here's a TaggableModel mixin that's basically just a more generic version of the above example:

from collections import defaultdict

class TaggableModel(object):

    def __init__(self, tags, callbacks=None):
        # tags is a dict with the tag as key, and a list of state names as vals
        self.tags = tags
        self.tagged_states = defaultdict(list)
        for tag, state in self.tags.items():
            self.tagged_states[state].append(tag)

    def has_tag(self, tag):
        return tag in self.tagged_states[self.state]

We could easily add dynamic tag checking for all passed tags--e.g., model.final_tag() would be the same as model.has_tag(final). And init could potentially have a callbacks dict as another argument, where keys are tags and values are bound methods to call whenever the model enters a state that matches the key. For example, {'reject': 'throw_hissy_fit' } would be equivalent to (and could be implemented as) a call to model.on_enter_reject('throw_hissy_fit').

[tyarkoni]

Alternatively, we could also inherit from State, rather than having a model mixin. We could have a TaggableState class that takes an extra tags argument, which is a dict where keys are tag names, and values are (optional) methods to trigger when entering the state. The main downside of this approach is redundancy--it would be a bit annoying to specify the same behavior for the 'final' tag in multiple states. So I think I prefer to do this just once, via the model.

[aleneum]

I close this for now. This might be a part of a model module extension outlined in #146. Feel free to reopen this issue if necessary.