Saubere und typsichere Zustandsmaschinenimplementierung in einer statisch typisierten Sprache?

Ich habe eine einfache Zustandsmaschine in Python implementiert:

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)

Ich wollte es nach C portieren, weil es nicht schnell genug war. Aber C lässt mich keine Funktion erstellen, die eine Funktion desselben Typs zurückgibt. Ich habe versucht, die Funktion dieses Typs zu erstellen: typedef *fn(fn)(), aber es funktioniert nicht, also musste ich stattdessen eine Struktur verwenden. Jetzt ist der Code sehr hässlich!

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

Also dachte ich, es ist ein Problem mit dem kaputten Typsystem von C. Also habe ich eine Sprache mit einem echten Typsystem (Haskell) verwendet, aber das gleiche Problem tritt auf. Ich kann nicht einfach so etwas tun:

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

Ich bekomme den Fehler, Cycle in type synonym declarations.

Also muss ich einen Wrapper machen, so wie ich es für den C-Code gemacht habe:

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

Warum ist es so schwierig, eine Zustandsmaschine in einer statisch typisierten Sprache zu erstellen? Ich muss auch in statisch typisierten Sprachen unnötigen Overhead machen. Dynamisch typisierte Sprachen haben dieses Problem nicht. Gibt es einen einfacheren Weg, dies in einer statisch typisierten Sprache zu tun?

In Haskell lautet die Redewendung dafür einfach, weiterzumachen und den nächsten Zustand auszuführen:

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

Sie brauchen sich keine Sorgen zu machen, dass dadurch ein Stack überläuft oder ähnliches. Wenn Sie darauf bestehen, Zustände zu haben, sollten Sie den Datentyp expliziter machen:

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

Sie können dann Compiler-Warnungen zu allen erhalten StateMachine das vergaß einige Staaten.

Wenn du benutzt newtype Anstatt von data, entstehen Ihnen keine Kosten. Außerdem können Sie die Funktion jedes Zustands am Definitionspunkt umschließen, sodass die Ausdrücke, die sie verwenden, dies nicht tun müssen:

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

Bearbeiten: das fiel mir auf runMachine hat eine allgemeinere Form; eine monadische Version von 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

Bearbeiten: Hmm, iterateM verursacht ein Space-Leak. Vielleicht iterateM_ wäre besser.

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

main = iterateM_ runState a

Bearbeiten: Wenn Sie einen Zustand durch die Zustandsmaschine führen möchten, können Sie dieselbe Definition für verwenden Stateaber ändern Sie die Zustandsfunktionen in:

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

Das Problem mit Ihrem Haskell-Code ist, dass type führt nur ein Synonym ein, das what ziemlich ähnlich ist typedef in C tut. Eine wichtige Einschränkung ist, dass die Erweiterung des Typs endlich sein muss, Sie können Ihrer Zustandsmaschine keine endliche Erweiterung geben. Eine Lösung ist die Verwendung von a newtype: EIN newtype ist ein Wrapper, der nur für den Typprüfer existiert; Es gibt absolut keinen Overhead (ausgenommen Dinge, die aufgrund von Generalisierungen auftreten, die nicht entfernt werden können). Hier ist Ihre Unterschrift; es tippt:

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

Bitte beachten Sie, dass wann immer Sie eine verwenden möchten FNmüssen Sie es zuerst mit entpacken unFN. Immer wenn Sie eine neue Funktion zurückgeben, verwenden Sie FN es zu packen.

In den C-ähnlichen Systemen sind Funktionen keine Bürger erster Ordnung. Es gibt bestimmte Einschränkungen für den Umgang mit ihnen. Das war eine Entscheidung für Einfachheit und Schnelligkeit der Implementierung/Ausführung, die hängen blieb. Damit sich Funktionen wie Objekte verhalten, benötigt man im Allgemeinen Unterstützung für Closures. Diese werden jedoch von den Befehlssätzen der meisten Prozessoren natürlich nicht unterstützt. Da C so konzipiert wurde, dass es nahe am Metall liegt, gab es keine Unterstützung für sie.

Bei der Deklaration rekursiver Strukturen in C muss der Typ vollständig erweiterbar sein. Eine Folge davon ist, dass Sie in Struct-Deklarationen nur Zeiger als Selbstreferenzen haben können:

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

Außerdem muss jede von uns verwendete Kennung deklariert werden. Eine der Einschränkungen von Funktionstypen ist, dass man sie nicht vorwärts deklarieren kann.

Eine Zustandsmaschine in C funktioniert normalerweise, indem sie eine Zuordnung von ganzen Zahlen zu Funktionen vornimmt, entweder in einer switch-Anweisung oder in einer Sprungtabelle:

typedef int (*func_t)();

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

    int state = 0;

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

Alternativ könnten Sie Profilieren Sie Ihren Python-Code und versuchen Sie herauszufinden, warum Ihr Code langsam ist. Sie können die kritischen Teile nach C/C++ portieren und weiterhin Python für die Zustandsmaschine verwenden.

Wie üblich konnte ich trotz der bereits vorhandenen großartigen Antworten nicht widerstehen, es selbst auszuprobieren. Eine Sache, die mich an dem, was präsentiert wird, gestört hat, ist, dass Eingaben ignoriert werden. Zustandsmaschinen – die mir vertraut sind – wählen zwischen verschiedenen möglichen Übergängen basierend auf der Eingabe.

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)

Hier definiere ich einen Typ Statedie durch einen Vokabulartyp parametrisiert wird vocab. Lassen Sie uns nun einen Weg definieren, wie wir die Ausführung einer Zustandsmaschine verfolgen können, indem wir ihr Eingaben zuführen.

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

Versuchen wir es jetzt auf einer einfachen Maschine, die ihre Eingaben ignoriert. Seien Sie gewarnt: Das von mir gewählte Format ist ziemlich ausführlich. Jede folgende Funktion kann jedoch als Knoten in einem Zustandsmaschinendiagramm betrachtet werden, und ich denke, Sie werden feststellen, dass die Ausführlichkeit für die Beschreibung eines solchen Knotens völlig relevant ist. Ich habe verwendet stateId um einige visuelle Informationen darüber, wie sich dieser Zustand verhält, im Zeichenfolgenformat zu codieren.

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
               }

Da die Eingaben für diese Zustandsmaschine keine Rolle spielen, können Sie sie mit allem füttern.

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

Ich werde die Ausgabe nicht einschließen, die auch sehr ausführlich ist, aber Sie können deutlich sehen, dass sie sich bewegt stateA zu stateB zu stateC und zurück zu stateA wieder. Lassen Sie uns nun eine etwas kompliziertere Maschine bauen:

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. :)"

Die möglichen Eingaben und Übergänge für jeden Knoten sollten keiner weiteren Erläuterung bedürfen, da sie im Code ausführlich beschrieben sind. Ich lasse dich mitspielen traceMachine lessSipmleMachine inputs für sich selbst. Sehen Sie, was wann passiert inputs ungültig ist (entspricht nicht den Beschränkungen für “mögliche Eingaben”) oder wenn Sie vor dem Ende der Eingabe auf einen Zielknoten treffen.

Ich nehme an, die Ausführlichkeit meiner Lösung verfehlt irgendwie das, was Sie im Grunde gefragt haben, nämlich die Cruft zu reduzieren. Aber ich denke, es zeigt auch, wie anschaulich Haskell-Code sein kann. Obwohl es sehr ausführlich ist, ist es auch sehr einfach, wie es Knoten eines Zustandsmaschinendiagramms darstellt.

Es ist nicht schwer, Zustandsmaschinen in Haskell zu bauen, wenn man erst einmal erkennt, dass sie es sind nicht Monaden! Eine Zustandsmaschine wie die, die Sie wollen, ist ein Pfeil, ein Automatenpfeil, um genau zu sein:

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

Dies ist eine Funktion, die einen Eingabewert nimmt und einen Ausgabewert zusammen mit einer neuen Version von sich selbst erzeugt. Dies ist keine Monade, weil Sie nicht schreiben können join oder (>>=) dafür. Sobald Sie dies in einen Pfeil verwandelt haben, werden Sie entsprechend feststellen, dass es unmöglich ist, ein zu schreiben ArrowApply Beispiel dafür.

Hier sind die Instanzen:

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)

Habe Spaß.

Was Sie wollen, ist ein rekursiver Typ. Verschiedene Sprachen haben unterschiedliche Möglichkeiten, dies zu tun.

Beispielsweise gibt es in OCaml (einer statisch typisierten Sprache) ein optionales Compiler/Interpreter-Flag -rectypes Dies ermöglicht die Unterstützung rekursiver Typen, sodass Sie Dinge wie die folgenden definieren können:

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

Obwohl dies nicht “hässlich” ist, wie Sie in Ihrem C-Beispiel bemängelt haben, passiert was unterhalb ist immer noch das gleiche. Der Compiler kümmert sich einfach darum, anstatt Sie zu zwingen, es zu schreiben.

Wie andere bereits betont haben, können Sie in Haskell verwenden newtype und es wird keinen “Overhead” geben. Aber Sie beschweren sich darüber, dass Sie den rekursiven Typ explizit ein- und auspacken müssen, was “hässlich” ist. (Ähnlich wie bei Ihrem C-Beispiel; es gibt keinen “Overhead”, da auf Maschinenebene eine 1-Mitglieder-Struktur mit ihrem Mitglied identisch ist, aber “hässlich”.)

Ein weiteres Beispiel, das ich erwähnen möchte, ist Go (eine weitere statisch typisierte Sprache). In Go, die type Konstrukt definiert einen neuen Typ. Es ist kein einfacher Alias ​​(wie typedef in C bzw type in Haskell), sondern erstellt einen vollwertigen neuen Typ (wie newtype in Haskell), da ein solcher Typ einen unabhängigen “Methodensatz” von Methoden hat, die Sie darauf definieren können. Aus diesem Grund kann die Typdefinition rekursiv sein:

type Fn func () Fn