Clean and type-safe state machine implementation in a statically typed language?

c, haskell, language-agnostic, python, typing

Solution

If you use `newtype` instead of `data`, you don't incur any overhead. Also, you can wrap each state's function at the point of definition, so the expressions that use them don't have to:

import Control.Monad

newtype State = State { runState :: IO State }

a :: State
a = State $ print "a()" >> return b

b :: State
b = State $ print "b()" >> return c

c :: State
c = State $ print "c()" >> return a

runMachine :: State -> IO ()
runMachine s = runMachine =<< runState s

main = runMachine a

Edit: it struck me that `runMachine` has a more general form; a monadic version of `iterate`:

iterateM :: Monad m => (a -> m a) -> a -> m [a]
iterateM f a = do { b <- f a
                  ; as <- iterateM f b
                  ; return (a:as)
                  }

main = iterateM runState a

Edit: Hmm, `iterateM` causes a space-leak. Maybe `iterateM_` would be better.

iterateM_ :: Monad m => (a -> m a) -> a -> m ()
iterateM_ f a = f a >>= iterateM_ f

main = iterateM_ runState a

Edit: If you want to thread some state through the state machine, you can use the same definition for `State`, but change the state functions to:

a :: Int -> State
a i = State $ do{ print $ "a(" ++ show i ++ ")"
                ; return $ b (i+1)
                }

b :: Int -> State
b i = State $ do{ print $ "b(" ++ show i ++ ")"
                ; return $ c (i+1)
                }

c :: Int -> State
c i = State $ do{ print $ "c(" ++ show i ++ ")"
                ; return $ a (i+1)
                }

main = iterateM_ runState $ a 1

Problem

I implemented a simple state machine in Python: ``` import time def a(): print "a()" return b def b(): print "b()" return c def c(): print "c()" return a if __name__ == "__main__": state = a while True: state = state() time.sleep(1) ``` I wanted to port it to C, because it wasn't fast enough. But C doesn't let me make a function that returns a function of the same type. I tried making the function of this type: `typedef *fn(fn)()`, but it doesn't work, so I had to use a structure instead. Now the code is very ugly! ``` #include <stdio.h> #include <stdlib.h> #include <unistd.h> typedef struct fn { struct fn (*f)(void); } fn_t; fn_t a(void); fn_t b(void); fn_t c(void); fn_t a(void) { fn_t f = {b}; (void)printf("a()\n"); return f; } fn_t b(void) { fn_t f = {c}; (void)printf("b()\n"); return f; } fn_t c(void) { fn_t f = {a}; (void)printf("c()\n"); return f; } int main(void) { fn_t state = {a}; for(;; (void)sleep(1)) state = state.f(); return EXIT_SUCCESS; } ``` So I figured it's a problem with C's broken type system. So I used a language with a real type system (Haskell), but the same problem happens. I can't just do something like: ``` type Fn = IO Fn a :: Fn a = print "a()" >> return b b :: Fn b = print "b()" >> return c c :: Fn c = print "c()" >> return a ``` I get the error, `Cycle in type synonym declarations`. So I have to make some wrapper the same way I did for the C code like this: ``` import Control.Monad import System.Posix data Fn = Fn (IO Fn) a :: IO Fn a = print "a()" >> return (Fn b) b :: IO Fn b = print "b()" >> return (Fn c) c :: IO Fn c = print "c()" >> return (Fn a) run = foldM (\(Fn f) () -> sleep 1 >> f) (Fn a) (repeat ()) ``` Why is it so hard to make a state machine in a statically typed language? I have to make unnecessary overhead in statically typed languages as well. Dynamically typed languages don't have this problem. Is there an easier way to do it in a statically typed language?

Original source

Related problems