26

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

为什么用静态类型语言制作状态机这么难?我还必须在静态类型语言中产生不必要的开销。动态类型语言没有这个问题。有没有更简单的方法可以用静态类型语言来做到这一点?

4

11 回答 11

22

在 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忘记某些状态的编译器警告。

于 2011-10-08T22:26:43.083 回答
15

如果您使用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
于 2011-10-08T22:30:48.077 回答
11

在类 C 类型系统中,函数不是一阶公民。处理它们有一定的限制。这是为了实现/执行的简单性和速度而做出的决定。为了让函数表现得像对象,通常需要支持闭包。然而,大多数处理器的指令集并不自然地支持这些。由于 C 被设计为靠近金属,因此没有支持它们。

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

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 作为状态机。

于 2011-10-08T21:57:34.043 回答
11

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

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

请注意,无论何时您想使用FN,都必须先使用unFN. 每当你返回一个新函数时,使用FN它来打包它。

于 2011-10-08T22:07:05.140 回答
6

像往常一样,尽管已经有了很好的答案,但我还是忍不住自己尝试了一下。关于所呈现的内容困扰我的一件事是它忽略了输入。状态机——我熟悉的那些——根据输入在各种可能的转换之间进行选择。

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一个到另一个stateBstateC返回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 代码的能力。尽管它非常冗长,但它在如何表示状态机图的节点方面也非常简单。

于 2011-10-09T04:45:31.967 回答
4

一旦你意识到它们不是单子,在 Haskell 中制作状态机并不难!像你想要的状态机是一个箭头,准确地说是一个自动机箭头:

newtype State a b = State (a -> (b, State a b))

这是一个函数,它接受一个输入值并产生一个输出值以及一个新版本的自身。这不是一个单子,因为你不能为它写join或写(>>=)。等效地,一旦你把它变成了一个箭头,你就会意识到不可能ArrowApply为它写一个实例。

以下是实例:

import Control.Arrow
import Control.Category
import Prelude hiding ((.), id)

instance Category State where
    id = State $ \x -> (x, id)

    State f . State g =
        State $ \x ->
            let (y, s2) = g x
                (z, s1) = f y
            in (z, s1 . s2)

instance Arrow State where
    arr f = let s = State $ \x -> (f x, s) in s
    first (State f) =
        State $ \(x1, x2) ->
            let (y1, s) = f x1
            in ((y1, x2), first s)

玩得开心。

于 2011-10-12T10:01:24.040 回答
3

您可以在 C 中获得与在 Python 代码中相同的效果,只需声明函数返回(void*)

#include "stdio.h"

typedef void* (*myFunc)(void);

void* a(void);
void* b(void);
void* c(void);

void* a(void) {
    printf("a()\n");
    return b;
}

void* b(void) {
    printf("b()\n");
    return c;
}

void* c(void) {
    printf("c()\n");
    return a;
}

void main() {
    void* state = a;
    while (1) {
        state = ((myFunc)state)();
        sleep(1);
    }
}
于 2011-10-08T23:56:44.237 回答
3

你想要的是一个递归类型。不同的语言有不同的方法来做到这一点。

例如,在 OCaml(一种静态类型语言)中,有一个可选的编译器/解释器标志-rectypes支持递归类型,允许您定义如下内容:

let rec a () = print_endline "a()"; b
and b () = print_endline "b()"; c
and c () = print_endline "c()"; a
;;

尽管这并不像您在 C 示例中所抱怨的那样“丑陋”,但下面发生的事情仍然是一样的。编译器只是为你担心,而不是强迫你把它写出来。

正如其他人指出的那样,在 Haskell 中您可以使用newtype并且不会有任何“开销”。但是您抱怨必须显式包装和解包递归类型,这是“丑陋的”。(与您的 C 示例类似;没有“开销”,因为在机器级别,一个 1 成员结构与其成员相同,但它是“丑陋的”。)

我想提的另一个例子是 Go(另一种静态类型语言)。在 Go 中,type构造定义了一个新类型。它不是一个简单的别名(如typedef在 C 或typeHaskell 中),而是创建一个成熟的新类型(如newtype在 Haskell 中),因为这种类型有一个独立的“方法集”,您可以在其上定义方法。因此,类型定义可以是递归的:

type Fn func () Fn
于 2011-10-09T13:20:38.810 回答
2

您的问题以前曾遇到过:C 中函数指针的递归声明

正如 Herb Sutter 在GotW #57: Recursive Declarations中所描述的那样,C++ 运算符重载可用于隐藏与 C 和 Haskell 解决方案基本相同的机制。

struct FuncPtr_;
typedef FuncPtr_ (*FuncPtr)();

struct FuncPtr_
{
  FuncPtr_( FuncPtr pp ) : p( pp ) { }
  operator FuncPtr() { return p; }
  FuncPtr p;
};

FuncPtr_ f() { return f; } // natural return syntax

int main()
{
  FuncPtr p = f();  // natural usage syntax
  p();
}

但是这种具有功能的业务很可能会比具有数字状态的业务表现更差。您应该使用switch语句或状态表,因为在这种情况下您真正想要的是与goto.

于 2011-10-08T22:15:49.477 回答
1

F# 中的一个示例:

类型 Cont = Cont of (unit -> Cont)

让记录 a() =
    printfn "a()"
    续 (fun () -> b 42)

和 bn =
    printfn "b(%d)" n
    续

和 c() =
    printfn "c()"
    续

让REC运行(续f)=
    让 f = f()
    运行 f

运行(续)

关于“为什么在静态类型语言中使用函数实现状态机这么难?”的问题:那是因为 ofa和friends 的类型有点奇怪:一个函数,当返回一个函数时返回一个函数,该函数返回一个功能...

如果我从示例中删除 Cont,F# 编译器会抱怨并说:

期待 'a 但给定的单位 -> 'a。当统一 'a 和 unit -> 'a 时,结果类型将是无限的。

另一个答案显示了 OCaml 中的一个解决方案,其类型推断足够强大,可以消除声明 Cont 的需要,这表明静态类型不是罪魁祸首,而是在许多静态类型语言中缺乏强大的类型推断。

我不知道为什么 F# 不这样做,我猜这可能会使类型推断算法更复杂、更慢或“太强大”(它可以设法推断类型错误的表达式的类型,但在稍后给出难以理解的错误消息)。

请注意,您提供的 Python 示例并不安全。在我的示例中,b表示由整数参数化的状态族。在无类型语言中,很容易出错并返回bb 42而不是正确的 lambda 并错过该错误,直到代码被执行。

于 2011-10-11T09:07:08.333 回答
-6

您发布的 Python 代码将被转换为递归函数,但不会进行尾调用优化,因为 Python 没有尾调用优化,所以它会在某些时候堆栈溢出。所以 Python 代码实际上已经损坏,并且需要更多的工作才能使其与 Haskell 或 C 版本一样好。

这是我的意思的一个例子:

所以.py:

import threading
stack_size_bytes = 10**5
threading.stack_size(10**5)
machine_word_size = 4

def t1():
    print "start t1"
    n = stack_size_bytes/machine_word_size
    while n:
        n -= 1
    print "done t1"

def t2():
    print "start t2"
    n = stack_size_bytes/machine_word_size+1
    while n:
        n -= 1
    print "done t2"

if __name__ == "__main__":
    t = threading.Thread(target=t1)
    t.start()
    t.join()
    t = threading.Thread(target=t2)
    t.start()
    t.join()

贝壳:

$ python so.py
start t1
done t1
start t2
Exception in thread Thread-2:
Traceback (most recent call last):
  File "/usr/lib/python2.7/threading.py", line 530, in __bootstrap_inner
    self.run()
  File "/usr/lib/python2.7/threading.py", line 483, in run
    self.__target(*self.__args, **self.__kwargs)
  File "so.py", line 18, in t2
    print "done t2"
RuntimeError: maximum recursion depth exceeded
于 2011-10-08T23:10:30.957 回答