使用静态类型语言清理和类型安全的状态机实现？

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

如果您使用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一种更为一般的形式; monadic版本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

Answer 3

在C类型系统中,功能不是一阶公民.处理它们有一定的限制.这是对简单性和执行/执行速度的决定.为了使函数像对象一样,通常需要支持闭包.然而,大多数处理器的指令集自然不支持这些.由于C设计为接近金属,因此不支持它们.

在C中声明递归结构时,类型必须完全可扩展.这样做的结果是,您只能在struct声明中将指针作为自引用:

struct rec;
struct rec {
    struct rec *next;
};

我们使用的每个标识符也必须声明.函数类型的一个限制是,无法转发声明它们.

C中的状态机通常通过在switch语句或跳转表中进行从整数到函数的映射来工作:

typedef int (*func_t)();

void run() {
    func_t table[] = {a, b, c};

    int state = 0;

    while(True) {
        state = table[state]();
    }
}

或者,您可以分析Python代码并尝试找出代码缓慢的原因.您可以将关键部分移植到C/C++并继续使用Python作为状态机.

Answer 4

你的Haskell代码的问题是,type它只引入了一个同义词,它与typedefC中的代码非常相似.一个重要的限制是,类型的扩展必须是有限的,你不能给你的状态机有限扩展.解决方案是使用newtype:A newtype是一个只对类型检查器存在的包装器; 绝对零开销(由于无法删除的泛化而导致排除的东西).这是你的签名; 它的类型:

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

请注意,无论何时您想使用FN,都必须先使用打开包装unFN.每当您返回一个新功能时,请使用FN它来打包它.

Answer 5

像往常一样,尽管已经有了很好的答案,但我忍不住为自己尝试.令我困惑的一件事是它忽略了输入.状态机 - 我熟悉的 - 根据输入在各种可能的转换之间进行选择.

data State vocab = State { stateId :: String
                         , possibleInputs :: [vocab]
                         , _runTrans :: (vocab -> State vocab)
                         }
                      | GoalState { stateId :: String }

instance Show (State a) where
  show = stateId

runTransition :: Eq vocab => State vocab -> vocab -> Maybe (State vocab)
runTransition (GoalState id) _                   = Nothing
runTransition s x | x `notElem` possibleInputs s = Nothing
                  | otherwise                    = Just (_runTrans s x)

这里我定义了一个类型State,它由词汇表类型参数化vocab.现在让我们定义一种方法,通过提供输入来跟踪状态机的执行.

traceMachine :: (Show vocab, Eq vocab) => State vocab -> [vocab] -> IO ()
traceMachine _ [] = putStrLn "End of input"
traceMachine s (x:xs) = do
  putStrLn "Current state: "
  print s
  putStrLn "Current input: "
  print x
  putStrLn "-----------------------"
  case runTransition s x of
    Nothing -> putStrLn "Invalid transition"
    Just s' -> case s' of
      goal@(GoalState _) -> do
        putStrLn "Goal state reached:"
        print s'
        putStrLn "Input remaining:"
        print xs
      _ -> traceMachine s' xs

现在让我们在一台忽略其输入的简单机器上试一试.请注意:我选择的格式相当冗长.但是,后面的每个函数都可以被视为状态机图中的一个节点,我认为你会发现详细程度与描述这样一个节点完全相关.我曾经习惯用stateId字符串格式编码一些有关该状态行为的可视信息.

data SimpleVocab = A | B | C deriving (Eq, Ord, Show, Enum)

simpleMachine :: State SimpleVocab
simpleMachine = stateA

stateA :: State SimpleVocab
stateA = State { stateId = "A state. * -> B"
               , possibleInputs = [A,B,C]
               , _runTrans = \_ -> stateB
               }

stateB :: State SimpleVocab
stateB = State { stateId = "B state. * -> C"
               , possibleInputs = [A,B,C]
               , _runTrans = \_ -> stateC
               }

stateC :: State SimpleVocab
stateC = State { stateId = "C state. * -> A"
               , possibleInputs = [A,B,C]
               , _runTrans = \_ -> stateA
               }

由于输入对于此状态机无关紧要,因此您可以将其输入任何内容.

ghci> traceMachine simpleMachine [A,A,A,A]

我将不包括输出,这也很详细,但你可以清楚地看到它从移动stateA到stateB要stateC再换stateA一次.现在让我们制作一个稍微复杂的机器:

lessSimpleMachine :: State SimpleVocab
lessSimpleMachine = startNode

startNode :: State SimpleVocab
startNode = State { stateId = "Start node. A -> 1, C -> 2"
                  , possibleInputs = [A,C]
                  , _runTrans = startNodeTrans
                  }
  where startNodeTrans C = node2
        startNodeTrans A = node1

node1 :: State SimpleVocab
node1 = State { stateId = "node1. B -> start, A -> goal"
              , possibleInputs = [B, A]
              , _runTrans = node1trans
              }
  where node1trans B = startNode
        node1trans A = goalNode

node2 :: State SimpleVocab
node2 = State { stateId = "node2. C -> goal, A -> 1, B -> 2"
              , possibleInputs = [A,B,C]
              , _runTrans = node2trans
              }
  where node2trans A = node1
        node2trans B = node2
        node2trans C = goalNode

goalNode :: State SimpleVocab
goalNode = GoalState "Goal. :)"

每个节点的可能输入和转换不需要进一步解释,因为它们在代码中详细描述.我会让你traceMachine lessSipmleMachine inputs自己玩.查看inputs无效时发生的情况(不遵守"可能的输入"限制),或者在输入结束前点击目标节点时发生的情况.

我认为我的解决方案的冗长程度有点像你基本上要求的那样,这是为了减少这个问题.但我认为它也说明了Haskell代码的描述.即使它非常冗长,它在表示状态机图的节点方面也非常简单.