在静态类型语言中干净且类型安全的状态机实现？

Question

我在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)

我想把它移植到C语言，因为速度不够快。但是C语言不允许我创建一个返回同类型函数的函数。我尝试定义这样的函数类型：typedef *fn(fn)()，但这行不通，所以我不得不使用结构体。现在代码看起来非常乱！

#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;
}

于是我觉得这是C语言类型系统的问题。于是我用了一个有真正类型系统的语言（Haskell），但同样的问题又出现了。我不能简单地这样做：

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

我得到了一个错误，Cycle in type synonym declarations。

所以我不得不像在C代码中那样，做一些包装，像这样：

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 ())

为什么在静态类型语言中实现状态机这么难？在静态类型语言中我还得增加不必要的开销。而动态类型语言就没有这个问题。有没有更简单的方法在静态类型语言中做到这一点？

Answer 1

你在Haskell代码中遇到的问题是，type只是引入了一个别名，这有点像C语言中的typedef。一个重要的限制是，类型的扩展必须是有限的，你不能给你的状态机提供无限的扩展。解决这个问题的方法是使用newtype：newtype是一个包装器，它只在类型检查时存在；它不会增加任何额外的开销（除了因为泛化而产生的那些无法去除的东西）。下面是你的签名，它可以通过类型检查：

newtype FN = FN { unFM :: (IO FN) }

请注意，每当你想使用FN时，必须先用unFN将其解包。每当你返回一个新函数时，记得用FN将其打包。

Answer 2

在Haskell中，处理这个问题的常用方法就是直接执行下一个状态：

type StateMachine = IO ()
a, b, c :: StateMachine
a = print "a()" >> b
b = print "b()" >> c
c = print "c()" >> a

你不需要担心这样会导致栈溢出或者其他问题。如果你一定要使用状态，那么你应该让数据类型更明确一些：

data PossibleStates = A | B | C
type StateMachine = PossibleStates -> IO PossibleStates
machine A = print "a()" >> return B
machine B = print "b()" >> return C
machine C = print "c()" >> return A

这样一来，编译器就会给你发出警告，提醒你有没有遗漏某些StateMachine的状态。

Answer 3

如果你使用 newtype 而不是 data，那么就不会增加额外的负担。而且，你可以在定义的时候就把每个状态的函数包裹起来，这样在使用这些函数的表达式中就不需要再处理了。

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

编辑: 我突然想到 runMachine 其实可以有更通用的形式；它是 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

编辑: 嗯，iterateM 会导致内存泄漏。也许 iterateM_ 会更好。

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

main = iterateM_ runState a

编辑: 如果你想在状态机中传递一些状态，可以使用相同的 State 定义，但把状态函数改成：

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