python - qué - tipado sinonimo

Implementación de máquina de estados limpia y segura en un lenguaje estáticamente tipado?

Question

Implementé una máquina de estado simple en 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)

Quería portarlo a C, porque no fue lo suficientemente rápido. Pero C no me deja hacer una función que devuelva una función del mismo tipo. Intenté hacer la función de este tipo: typedef *fn(fn)() , pero no funciona, así que tuve que usar una estructura en su lugar. ¡Ahora el código es muy feo!

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

Así que pensé que era un problema con el sistema de tipos rotos de C. Así que utilicé un lenguaje con un sistema de tipo real (Haskell), pero ocurre el mismo problema. No puedo hacer algo como:

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

Aparece el error, Cycle in type synonym declarations .

Así que tengo que hacer un contenedor de la misma manera que lo hice para el código C de esta manera:

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

¿Por qué es tan difícil hacer una máquina de estados en un lenguaje estáticamente tipado? También tengo que hacer una sobrecarga innecesaria en lenguajes tipados estáticos. Los lenguajes con tipado dinámico no tienen este problema. ¿Hay una forma más fácil de hacerlo en un lenguaje estáticamente tipado?

Answer 1

Como de costumbre, a pesar de las excelentes respuestas ya presentes, no pude resistirme a intentarlo por mi cuenta. Una cosa que me molestó acerca de lo que se presenta es que ignora la entrada. Las máquinas de estado, con las que estoy familiarizado, eligen entre varias transiciones posibles basadas en la entrada.

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)

Aquí defino un tipo de State , que está parametrizado por un vocabulario de tipo vocab . Ahora definamos una forma en que podemos rastrear la ejecución de una máquina de estado alimentándola con entradas.

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

Ahora probemos en una máquina simple que ignora sus entradas. Tenga cuidado: el formato que he elegido es bastante detallado. Sin embargo, cada función que sigue se puede ver como un nodo en un diagrama de máquina de estado, y creo que encontrará que la verbosidad es completamente relevante para describir dicho nodo. He utilizado stateId para codificar en formato de cadena cierta información visual sobre cómo se comporta ese estado.

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
               }

Como las entradas no importan para esta máquina de estado, puede alimentarlo con cualquier cosa.

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

No stateA la salida, que también es muy detallada, pero se puede ver que se mueve claramente de stateA a stateB a stateC y de nuevo a stateA nuevamente. Ahora hagamos una máquina un poco más complicada:

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

Las posibles entradas y transiciones para cada nodo no deberían requerir más explicaciones, ya que están detalladas en el código. Te dejaré jugar con las traceMachine lessSipmleMachine inputs de traceMachine lessSipmleMachine inputs por ti mismo. Vea lo que ocurre cuando las inputs no son válidas (no se adhiere a las restricciones de "posibles entradas"), o cuando golpea un nodo objetivo antes del final de la entrada.

Supongo que la verbosidad de mi solución no responde a lo que básicamente preguntabas, que era reducir el cruft. Pero creo que también ilustra cuán descriptivo puede ser el código Haskell. A pesar de que es muy detallado, también es muy sencillo en la forma en que representa los nodos de un diagrama de máquina de estado.

Answer 2

El código de Python que publicó se transformará en una función recursiva, pero no se optimizará en la cola porque Python no tiene una optimización de la cola de llamadas, por lo que se acumulará desbordamiento en algún momento. Por lo tanto, el código Python está realmente roto, y tomaría más trabajo conseguirlo tan bueno como las versiones Haskell o C.

Aquí hay un ejemplo de lo que quiero decir:

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

cáscara:

$ 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

Answer 3

El problema con su código Haskell es que ese type solo introduce un sinónimo, que es bastante similar al typedef en C. Una restricción importante es que la expansión del tipo debe ser finita, no se puede dar una expansión finita de la máquina de estado. Una solución es usar un newtype : un newtype es un envoltorio que solo existe para el comprobador de tipos; no hay absolutamente ninguna sobrecarga (cosas excluidas que ocurren debido a una generalización que no se puede eliminar). Aquí está tu firma; él tipea:

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

Tenga en cuenta que cuando quiera usar un FN , primero debe desempaquetarlo con unFN . Siempre que devuelva una nueva función, use FN para embalarla.

Answer 4

En Haskell, la expresión idiomática es solo para seguir adelante y ejecutar el siguiente estado:

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

No necesita preocuparse de que esto desborde una pila o algo así. Si insiste en tener estados, debe hacer que el tipo de datos sea más explícito:

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

A continuación, puede obtener advertencias del compilador acerca de cualquier StateMachine que olvidó algunos estados.

Answer 5

En el tipo C, las funciones de los sistemas no son ciudadanos de primer orden. Existen ciertas restricciones para manejarlos. Esa fue una decisión por simplicidad y velocidad de implementación / ejecución que se estancó. Para que las funciones se comporten como objetos, generalmente se necesita soporte para cierres. Sin embargo, esos no son naturalmente compatibles con los conjuntos de instrucciones de los procesadores más completos. Como C fue diseñado para estar cerca del metal, no había soporte para ellos.

Al declarar estructuras recursivas en C, el tipo debe ser totalmente expandible. Una consecuencia de esto es que solo puede tener punteros como autorreferencias en declaraciones struct:

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

Además, cada identificador que utilizamos debe ser declarado. Una de las restricciones de los tipos de función es que uno no puede reenviarlos.

Una máquina de estado en C generalmente funciona haciendo una asignación de enteros a funciones, ya sea en una declaración de cambio o en una tabla de salto:

typedef int (*func_t)();

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

    int state = 0;

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

Alternativamente, podrías crear un perfil de tu código Python e intentar averiguar por qué tu código es lento. Puede portar las partes críticas a C / C ++ y seguir utilizando Python para la máquina de estado.

Answer 6

Lo que quieres es un tipo recursivo. Los diferentes idiomas tienen diferentes formas de hacer esto.

Por ejemplo, en OCaml (un lenguaje de tipo estático), hay un indicador optativo de compilador / intérprete, que permite la compatibilidad con tipos recursivos, lo que le permite definir cosas como esta:

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

Aunque esto no es "feo" como usted se quejó en su ejemplo C, lo que sucede debajo sigue siendo el mismo. El compilador simplemente se preocupa por eso en lugar de forzarte a escribirlo.

Como otros han señalado, en Haskell puedes usar newtype y no habrá ningún "overhead". Pero te quejas de tener que envolver y desenvolver explícitamente el tipo recursivo, que es "feo". (De manera similar con su ejemplo C, no hay "gastos generales" ya que a nivel de máquina una estructura de 1 miembro es idéntica a su miembro, pero es "fea").

Otro ejemplo que quiero mencionar es Ir (otro lenguaje estático). En Go, la construcción de type define un nuevo tipo. No es un alias simple (como typedef en C o type Haskell), sino que crea un nuevo tipo completo (como newtype en Haskell) porque dicho tipo tiene un "conjunto de métodos" independiente que puedes definir en él . Debido a esto, la definición de tipo puede ser recursiva:

type Fn func () Fn

Answer 7

No es difícil hacer máquinas de estado en Haskell, ¡una vez que te das cuenta de que no son mónadas! Una máquina de estado como la que quieres es una flecha, una flecha de autómata para ser exactos:

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

Esta es una función que toma un valor de entrada y produce un valor de salida junto con una nueva versión de sí mismo. Esto no es una mónada, porque no puede escribir join o (>>=) para ello. Equivalentemente, una vez que haya convertido esto en una flecha, se dará cuenta de que es imposible escribir una instancia de ArrowApply para él.

Aquí están las instancias:

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)

Que te diviertas.

Answer 8

Puede obtener el mismo efecto en C que en el código Python; solo declare que las funciones devuelven (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);
    }
}

Answer 9

Si usa newtype lugar de data , no incurre en gastos generales. Además, puede ajustar la función de cada estado en el punto de definición, por lo que las expresiones que los utilizan no tienen por qué:

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

Editar : me sorprendió que runMachine tenga una forma más general; una versión monádica de 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

Editar : Hmm, iterateM causa una fuga de espacio. Quizás iterateM_ sería mejor.

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

main = iterateM_ runState a

Editar : si desea enhebrar algún estado a través de la máquina de estados, puede usar la misma definición para State , pero cambie las funciones de estado a:

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 10

Su problema se ha tenido antes: Declaración recursiva de puntero a función en C

La sobrecarga del operador de C ++ se puede utilizar para ocultar la mecánica de lo que es esencialmente lo mismo que sus soluciones C y Haskell, como describe Herb Sutter en GotW # 57: Declaraciones recursivas .

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

Pero este negocio con funciones tendrá, con toda probabilidad, un rendimiento peor que el equivalente con estados numéricos. Debería usar una instrucción switch o una tabla de estado, porque lo que realmente quiere en esta situación es un equivalente semántico estructurado a goto .

Answer 11

Un ejemplo en F #:

type Cont = Cont of (unit -> Cont) let rec a() = printfn "a()" Cont (fun () -> b 42) and b n = printfn "b(%d)" n Cont c and c() = printfn "c()" Cont a let rec run (Cont f) = let f = f() run f run (Cont a)

Con respecto a la pregunta "¿por qué es tan difícil implementar máquinas de estado usando funciones en lenguajes tipados estáticamente?": Eso es porque el tipo de a y amigos es un poco raro: una función que devuelve una función que devuelve una función que retorna Una función...

Si elimino Cont de mi ejemplo, el compilador de F # se queja y dice:

Expecting ''a but given unit -> ''a. The resulting type would be infinite when unifying ''a and unit -> ''a.

Otra respuesta muestra una solución en OCaml, cuya inferencia de tipo es lo suficientemente fuerte como para eliminar la necesidad de declarar Cont, que muestra que la tipificación estática no es la culpable, más bien la falta de inferencia de tipo potente en muchos lenguajes estáticos.

No sé por qué F # no lo hace, supongo que esto podría hacer que el algoritmo de inferencia de tipo sea más complicado, más lento o "demasiado poderoso" (podría llegar a inferir el tipo de expresiones incorrectamente tipadas, fallar en una punto posterior dando mensajes de error que son difíciles de entender).

Tenga en cuenta que el ejemplo de Python que dio no es realmente seguro. En mi ejemplo, b representa una familia de estados parametrizados por un número entero. En un lenguaje sin tipo, es fácil cometer un error y devolver b o b 42 lugar de la lambda correcta y omitir ese error hasta que se ejecute el código.