transitions with condition?

[aborilov]

is any way to create transition with condition?

[glyph]

Sorry for the long lag time on responding to this. What do you mean?

[glyph]

Closing just because I'm not sure what the issue is, in case there is no response. Please feel free to reopen!

[aborilov]

I'm using https://github.com/tyarkoni/transitions#conditional-transitions for now and I use conditional-transitions a lot. Is there are a way to use condition with automat?

[glyph]

Formally speaking, it looks like "transitions" (and in particular conditional transitions in that library) implement an NFA rather than a DFA. Personally I think that DFAs are a lot easier to reason about, and, although automat doesn't yet really take advantage of them, DFAs have various additional formal properties you can use to make guarantees about a particular FSM. Also, nondeterminism in NFAs is often used to implement things that are better and more clearly represented as additional states in the DFA. For example, in the example in the docs for conditions, I think it would be a lot better to represent "matter" as a state machine of its own; in fact the property of matter in question is called its "state" and the change between them is called a transition so it would make a lot of sense to model it that way in your state machine as well.

All that said, NFAs do have their uses, so I'm not saying we should never implement them, simply that I want to be careful about adding this feature and I'd like to figure out a way to do it that gently encourages developers to use DFAs whenever possible. So I'm curious about your use-cases: what are you doing with conditions that is hard to model as a state machine? How would you like to see it implemented in automat?

[markrwilliams]

I'm chiming in merely as an interested user of automat.

I don't think "transitions"' conditions (say that 3 times fast) implement an NFA. An NFA can be in more than one state after a given input or even no inputs (so-called "free moves" or ε-transitions, where ε means "empty input".) The example transition from the link describes a transition from solid on heat to gas when is_flammable() returns True; and when is_flammable() returns False but is_really_hot() returns True, the transition is on heat from solid to liquid. As a diagram:

                                            +-----+
                                       True/| gas |
                                          / +-----+
      +-------+   heat   +--------------+/                      +--------+
      | solid |----------| is_flammable |                  True/| liquid |
      +-------+          +--------------+\                    / +--------+
                                          \                  /
                                      False\+---------------+
                                            | is_really_hot |
                                            +---------------+
                                                             \
                                                              \
                                                          False\+-----+
                                                                | ... |
                                                                +-----+

(The source seems to support this interpretation.)

No input in our alphabet puts the machine into both solid and liquid states, nor does any state transition occur without an input. So, not an NFA.

We could turn it into an NFA, but I find it hard to think about what that would mean without also requiring accept states. That's because I only know that an NFA has "guessed" correctly if the set of states it's in intersects with its set of accept states.

I agree that adding a state usually solves the use case for conditions. Indeed, minimizing if statements has been my goal while working with automat. I also find that automat's plain old Python object approach enables some remarkable flexibility.

To demonstrate, here's an automat approach to the linked-to transitions:

from automat import MethodicalMachine

class Matter(object):
    '''
    Everything is matter in our world, and all such matter can be
    heated.
    '''
    CHANGE_TEMPERATURE = 0

    def heat(self, temperature):
        if temperature >= self.CHANGE_TEMPERATURE:
            return self.sufficientHeat(temperature)
        else:
            return self.insufficientHeat(temperature)

class FlammableMatter(Matter):
    '''
    Some matter can be turned into a gas.
    '''
    _machine = MethodicalMachine()
    CHANGE_TEMPERATURE = 100.0

    @_machine.state(initial=True)
    def solid(self):
        pass

    @_machine.state()
    def gas(self):
        pass

    @_machine.input()
    def sufficientHeat(self, temperature):
        pass

    @_machine.input()
    def insufficientHeat(self, temperature):
        pass

    @_machine.output()
    def rarified(self, temperature):
        return True

    @_machine.output()
    def noChange(self, temperature):
        return False

    solid.upon(sufficientHeat, enter=gas, outputs=[rarified], collector=next)
    solid.upon(insufficientHeat, enter=solid, outputs=[noChange], collector=next)

class MeltableMatter(Matter):
    '''
    Some matter can be melted.
    '''
    _machine = MethodicalMachine()
    CHANGE_TEMPERATURE = 74.0

    @_machine.state(initial=True)
    def solid(self):
        pass

    @_machine.state()
    def liquid(self):
        pass

    @_machine.input()
    def sufficientHeat(self, temperature):
        pass

    @_machine.input()
    def insufficientHeat(self, temperature):
        pass

    @_machine.output()
    def liquified(self, temperature):
        return True

    @_machine.output()
    def noChange(self, temperature):
        return False

    solid.upon(sufficientHeat, enter=liquid, outputs=[liquified],
               collector=next)
    solid.upon(insufficientHeat, enter=solid, outputs=[noChange],
               collector=next)

Notes:

1. We have a common base class. I'm not the biggest fan of inheritance, but we can leverage it here because automat machines decorate plain old Python objects.
2. That base class implements a heat method that checks the condition and calls. While it may seem bad that the condition occurs outside our automat apparatus, I think that's a good thing. The machine does not assume anything about how it's used or called; rather, it ensures that it's been used or called correctly, raising an exception if not. Invalid or unexpected behaviors are either impossible or mechanical to correct. Supposing we've laid these machines out correctly, the only problem that heat can have is that it's not checking the temperature correctly. We can trust that invariants we care about are maintained by virtue of state accessibility or inaccessibility.

As it's written, the automata's invariants are:

1) that insufficient heat does not change an automaton's state, and sufficient heat does. 2) that sufficient heat does change an automaton's state, permanently, and subsequent heating is impossible.

A consequence of this is that we can continue to heat up a Matter automaton until its state has changed. After that, more heat is a problem:

>>> f = FlammableMatter()
>>> f.heat(98)
False
>>> f.heat(99)
False
>>> f.heat(100)
True
>>> f.heat(101)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "auto.py", line 9, in heat
    return self.sufficientHeat(temperature)
  File "/home/mrw/.virtualenvs/3b48cc9341edd108/local/lib/python2.7/site-packages/automat/_methodical.py", line 93, in sufficientHeat
    collector = self.collectors[transitioner._state]
KeyError: <MethodicalState(machine=<automat._methodical.MethodicalMachine object at 0x7f2599fe8790>, method=<function gas at 0x7f259885c758>, serialized=None)>
>>> m = MeltableMatter()
>>> m.heat(70)
False
>>> m.heat(71)
False
>>> m.heat(74)
True
>>> m.heat(74)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "auto.py", line 9, in heat
    return self.sufficientHeat(temperature)
  File "/home/mrw/.virtualenvs/3b48cc9341edd108/local/lib/python2.7/site-packages/automat/_methodical.py", line 93, in sufficientHeat
    collector = self.collectors[transitioner._state]
KeyError: <MethodicalState(machine=<automat._methodical.MethodicalMachine object at 0x7f259885a610>, method=<function liquid at 0x7f259885ca28>, serialized=None)>

Maybe that's not what we want - maybe you only get one shot to heat up something that can melt. Let's make that an invariant:

class MeltableMatter(Matter):
    '''
    Some matter can be melted.
    '''
    _machine = MethodicalMachine()
    CHANGE_TEMPERATURE = 74.0

    @_machine.state(initial=True)
    def solid(self):
        pass

    @_machine.state()
    def liquid(self):
        pass

    @_machine.state()
    def unheatableSolid(self):
        pass

    @_machine.input()
    def sufficientHeat(self, temperature):
        pass

    @_machine.input()
    def insufficientHeat(self, temperature):
        pass

    @_machine.output()
    def rarified(self, temperature):
        return True

    @_machine.output()
    def noChange(self, temperature):
        return False

    solid.upon(sufficientHeat, enter=liquid, outputs=[rarified],
               collector=next)
    solid.upon(insufficientHeat, enter=unheatableSolid, outputs=[noChange],
               collector=next)
    unheatableSolid.upon(sufficientHeat, enter=unheatableSolid, outputs=[noChange],
                         collector=next)
    unheatableSolid.upon(insufficientHeat, enter=unheatableSolid, outputs=[noChange],
                         collector=next)

And now you can only heat a solid once:

>>> doesNotMelt = MeltableMatter()
>>> doesNotMelt.heat(70)
False
>>> doesNotMelt.heat(100)
False
>>> melts = MeltableMatter()
>>> melts.heat(100)
True

Or can you? There's still a transition that could be applied. If it's obvious, then I've made a point with all these examples!

Regardless, I'm not convinced of the utility of NFA support. If you do add it, @glyph, it would make the most sense to also add accept states. But neither would help with conditions as "transitions" implements them.

[aborilov]

@glyph my use case is vending-machine algorithm, where I need to count coins, and as I understand, DFAs are not capable of counting. https://github.com/aborilov/kiosk/blob/master/kiosk/kiosk.py#L95 My state transition table not done yet, but already looks scary :) I will happily use automat if I can.

[glyph]

While it may seem bad that the condition occurs outside our automat apparatus, I think that's a good thing. The machine does not assume anything about how it's used or called; rather, it ensures that it's been used or called correctly, raising an exception if not. Invalid or unexpected behaviors are either impossible or mechanical to correct. Supposing we've laid these machines out correctly, the only problem that heat can have is that it's not checking the temperature correctly. We can trust that invariants we care about are maintained by virtue of state accessibility or inaccessibility.

This is a perfect encapsulation of how I personally would use automat, and how I would implement conditions. My previous comment was definitely wrong about NFA vs. DFA: what Automat really implements is a finite state transducer, specifically a Mealy machine. Mealy machines have only inputs, outputs, and states; the transition function is a mapping of (input, state) to outputs.

In particular, the idiom would be to make certain inputs private methods, and then to make public methods which examine the relevant conditional state (counters, flags, etc) public methods which then call those private methods to provide the right input depending on state.

Grouping in additional logical constructs, like conditions, is open-ended. If conditions why not loops? If loops why not counters, comparisons, entry and exit functions, and so on? Any extra stuff makes it harder to reason about the state machine in terms of its core properties of inputs, states, and outputs. So I'm not totally opposed to adding more things, but there would have to be a clear motivation for a reason to do it within the state machine itself rather than inside application code.