7 ms·

Finite State Machines with Python Coroutines

80 points by arpitbbhayani 6y ago

sktrdie 6y ago
In newer version of Python, you can send values to Generators with generator.send(), which makes python Generators effectively coroutines.
- comfydragon 6y ago
  Generator send() was actually added way back in Python 2.5! [1] [1] https://docs.python.org/2.5/whatsnew/pep-342.html https://docs.python.org/2.5/whatsnew/pep-342.html
carapace 6y ago
You can use Brzozowski's derivatives of regular expressions[1] to lazily get a state machine from a RE. I made a simple FSM using a trampoline function[2] to imitate a kind of table-drive GOTO design.[3] [1] "Derivatives of Regular Expressions", Janusz A. Brzozowski https://dl.acm.org/doi/10.1145/321239.321249 https://dl.acm.org/doi/10.1145/321239.321249 [2] https://en.wikipedia.org/wiki/Trampoline_(computing)#High-level_programming https://en.wikipedia.org/wiki/Trampoline_(computing)#High-le... [3] http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expres...
BiteCode_dev 6y ago
For even more fun, use async def + await, and you save yourself the while loop since that what the asyncio.run() does for you.
- qqssccfftt 6y ago
  asyncio will get confused as to why youre yielding random things and it won't work
  - BiteCode_dev 6y ago
    No, you just wrap it in a Future.
    - qqssccfftt 6y ago
      So now you have even more confusing code. Good work!
OJFord 6y ago
Perhaps I'm missing it, but the only reason I can find in TFA for using coroutines here is that it's the most intuitive way of writing this FSM class. Is it really more intuitive than something like: class FSM: def __init__(self): self.current_state = self._start self.stopped = False def send(self, char): self.current_state(char) def does_match(self): if self.stopped: return False return self.current_state == self._q3 ... def _q2(self, char): if char == 'b': return if char == 'c' self.current_state = self._q3 self.stopped = True ... (Using names 'send' etc. from the article just for easier comparison.) This is basically the same except not using co-routines, and I don't see what advantage using them brings? Not using them has a clear advantage (IMO) that we don't have to initialise each state (`_create_q2()`) - which just seems strange to read, and a recipe for forgetting ('I just added a state for this, why are we still seeing this error...') since it essentially means a state is 'declared' in init, and defined in a method. But this is Python, and a compiler won't complain. Neither will your linter know^ that you should have called that method in `__init__`. ^(OK, you _might_ have a check that it's used anywhere ever, but there's a lot of good reasons for not having that - library code, abstractions, linter not clever enough to work out you have called things in a non-straightforward way, etc.)
- eternauta3k 6y ago
  I don't get it either. Normally you'd use coroutines to have an implicit state machine, without writing out explicit states.
  - glxxyz 6y ago
    Yes the regex-parsing FSM class in the article looks cleaner with a single coroutine: class FSM: def __init__(self): self.match = False self.current_state = self.create_state_machine() next(self.current_state) def does_match(self): return self.match def send(self, char): try: self.current_state.send(char) except StopIteration: self.match = False pass def create_state_machine(self): char = yield if char == 'a': while True: char = yield if char == 'b': pass elif char == 'c': self.match = True yield break else: break
sandGorgon 6y ago
@arpitbbhayani - this is very interesting. you are one step away from building "reliable functions" - the basis of Azure Durable Functions and Uber Cadence. https://docs.microsoft.com/en-us/azure/azure-functions/durable/durable-functions-orchestrations?tabs=csharp#reliability https://docs.microsoft.com/en-us/azure/azure-functions/durab... A durable function is a state machine that can be replayed.
deleted 6y ago
[deleted]

80 points by arpitbbhayani 6y ago

In newer version of Python, you can send values to Generators with generator.send(), which makes python Generators effectively coroutines.

comfydragon 6y ago
Generator send() was actually added way back in Python 2.5! [1] [1] https://docs.python.org/2.5/whatsnew/pep-342.html https://docs.python.org/2.5/whatsnew/pep-342.html

carapace 6y ago

You can use Brzozowski's derivatives of regular expressions[1] to lazily get a state machine from a RE. I made a simple FSM using a trampoline function[2] to imitate a kind of table-drive GOTO design.[3] [1] "Derivatives of Regular Expressions", Janusz A. Brzozowski https://dl.acm.org/doi/10.1145/321239.321249 https://dl.acm.org/doi/10.1145/321239.321249 [2] https://en.wikipedia.org/wiki/Trampoline_(computing)#High-level_programming https://en.wikipedia.org/wiki/Trampoline_(computing)#High-le... [3] http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html http://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expres...

BiteCode_dev 6y ago

For even more fun, use async def + await, and you save yourself the while loop since that what the asyncio.run() does for you.

qqssccfftt 6y ago
asyncio will get confused as to why youre yielding random things and it won't work
- BiteCode_dev 6y ago
  No, you just wrap it in a Future.
  - qqssccfftt 6y ago
    So now you have even more confusing code. Good work!

OJFord 6y ago

Perhaps I'm missing it, but the only reason I can find in TFA for using coroutines here is that it's the most intuitive way of writing this FSM class. Is it really more intuitive than something like: class FSM: def __init__(self): self.current_state = self._start self.stopped = False def send(self, char): self.current_state(char) def does_match(self): if self.stopped: return False return self.current_state == self._q3 ... def _q2(self, char): if char == 'b': return if char == 'c' self.current_state = self._q3 self.stopped = True ... (Using names 'send' etc. from the article just for easier comparison.) This is basically the same except not using co-routines, and I don't see what advantage using them brings? Not using them has a clear advantage (IMO) that we don't have to initialise each state (`_create_q2()`) - which just seems strange to read, and a recipe for forgetting ('I just added a state for this, why are we still seeing this error...') since it essentially means a state is 'declared' in init, and defined in a method. But this is Python, and a compiler won't complain. Neither will your linter know^ that you should have called that method in `__init__`. ^(OK, you _might_ have a check that it's used anywhere ever, but there's a lot of good reasons for not having that - library code, abstractions, linter not clever enough to work out you have called things in a non-straightforward way, etc.)

eternauta3k 6y ago
I don't get it either. Normally you'd use coroutines to have an implicit state machine, without writing out explicit states.
- glxxyz 6y ago
  Yes the regex-parsing FSM class in the article looks cleaner with a single coroutine: class FSM: def __init__(self): self.match = False self.current_state = self.create_state_machine() next(self.current_state) def does_match(self): return self.match def send(self, char): try: self.current_state.send(char) except StopIteration: self.match = False pass def create_state_machine(self): char = yield if char == 'a': while True: char = yield if char == 'b': pass elif char == 'c': self.match = True yield break else: break

sandGorgon 6y ago

@arpitbbhayani - this is very interesting. you are one step away from building "reliable functions" - the basis of Azure Durable Functions and Uber Cadence. https://docs.microsoft.com/en-us/azure/azure-functions/durable/durable-functions-orchestrations?tabs=csharp#reliability https://docs.microsoft.com/en-us/azure/azure-functions/durab... A durable function is a state machine that can be replayed.

deleted 6y ago

[deleted]