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?
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