Чистая и надежная реализация конечного автомата на статически типизированном языке?

Ответ 1

Если вы используете 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

Изменить: Hmm, 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

Ответ 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, который забыл некоторые состояния.

Ответ 3

В системах типа С-типа функции не являются гражданами первого порядка. Существуют определенные ограничения на их обработку. Это было решение для простоты и скорости выполнения/исполнения, которые застряли. Чтобы функции функционировали как объекты, обычно требуется поддержка замыканий. Тем не менее, они, естественно, не поддерживаются наборами инструкций большинства процессоров. Поскольку 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/С++ и продолжать использовать Python для конечного автомата.

Ответ 4

Проблема с вашим кодом Haskell заключается в том, что type вводит только синоним, который очень похож на то, что делает typedef в C. Одним из важных ограничений является то, что расширение типа должно быть конечным, вы не можете дать конечное расширение вашей государственной машины. Решение использует newtype: A newtype - это оболочка, которая существует только для проверки типа; есть абсолютно нулевые накладные расходы (исключается материал, который возникает из-за обобщения, которое невозможно удалить). Вот ваша подпись; это typechecks:

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

Обратите внимание, что всякий раз, когда вы хотите использовать FN, вам сначала нужно распаковать его, используя unFN. Всякий раз, когда вы возвращаете новую функцию, используйте FN для ее упаковки.

Ответ 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
      [email protected](GoalState _) -> do
        putStrLn "Goal state reached:"
        print s'
        putStrLn "Input remaining:"
        print xs
      _ -> traceMachine s' xs

Теперь попробуйте попробовать на простой машине, которая игнорирует ее входные данные. Будьте осторожны: формат, который я выбрал, довольно многословный. Тем не менее, каждая следующая функция может рассматриваться как node в диаграмме конечного автомата, и я думаю, вы найдете, что многословие будет полностью релевантным для описания такого node. Я использовал 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. :)"

Возможные входы и переходы для каждого node не требуют дополнительного объяснения, поскольку они подробно описаны в коде. Я позволю вам играть с traceMachine lessSipmleMachine inputs для себя. Посмотрите, что произойдет, если inputs недействителен (не придерживается ограничений "возможных входов" ) или когда вы достигли цели node до конца ввода.

Я полагаю, что многословие моего решения вроде не справляется с тем, что вы в основном задавали, а именно, чтобы сократить крутизну. Но я думаю, что это также иллюстрирует, как описательный код Haskell может быть. Несмотря на то, что это очень многословно, это также очень просто, поскольку он представляет узлы диаграммы конечных машин.

Ответ 6

Невозможно сделать государственные машины в 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)

Удачи.

Ответ 7

Вы можете получить тот же эффект в 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);
    }
}

Ответ 8

Что вы хотите, это рекурсивный тип. Различные языки имеют разные способы сделать это.

Например, в OCaml (статически типизированный язык) существует необязательный флаг compiler/interpreter -rectypes, который позволяет поддерживать рекурсивные типы, позволяя вам определять такие вещи как:

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

Хотя это не "уродливо", как вы жаловались на примере C, то, что происходит под ним, остается тем же. Компилятор просто беспокоится об этом для вас, а не заставляет вас писать его.

Как указывали другие, в Haskell вы можете использовать newtype, и никаких "накладных расходов" не будет. Но вы жалуетесь на то, что нужно явно обернуть и развернуть рекурсивный тип, который является "уродливым". (Аналогично вашему примеру, нет "служебных" ресурсов, поскольку на уровне машины структура из 1 члена идентична его члену, но она "уродливая".)

Еще один пример, который я хочу упомянуть, - Go (другой статически типизированный язык). В Go конструктор type определяет новый тип. Это не простой псевдоним (например, typedef в C или type в Haskell), но создает полноценный новый тип (например, newtype в Haskell), потому что у такого типа есть независимый "набор методов" методов которые вы можете определить на нем. Из-за этого определение типа может быть рекурсивным:

type Fn func () Fn

Ответ 9

Ваша проблема была прежде: Рекурсивное объявление указателя функции в C

Перегрузка оператора С++ может быть использована, чтобы скрыть механику того, что по существу совпадает с вашими решениями C и Haskell, как описывает Херб Саттер в GotW # 57: Рекурсивные декларации.

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.

Ответ 10

Пример в 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)

Что касается вопроса "почему так сложно реализовать государственные машины с использованием функций в статически типизированных языках?": это потому, что тип a и друзей немного странный: функция, которая возвращает функцию, которая возвращает функцию, возвращающую функцию...

Если я удалю Cont из моего примера, компилятор F # жалуется и говорит:

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

Еще один ответ показывает решение в OCaml, тип вывода которого достаточно силен, чтобы исключить необходимость объявления Cont, которое показывает, что статическая типизация не виновата, а не отсутствие мощного вывода типа во многих статически типизированных языках.

Я не знаю, почему F # не делает этого, я бы предположил, возможно, это сделает алгоритм определения типа более сложным, медленным или "слишком мощным" (ему удастся вывести тип неправильно введенных выражений, в случае сбоя в более поздней точке, приведя сообщения об ошибках, которые трудно понять).

Обратите внимание, что приведенный вами пример Python небезопасен. В моем примере b представляет семейство состояний, параметризованных целым числом. В нетипизированном языке легко сделать ошибку и вернуть b или b 42 вместо правильной лямбда и пропустить эту ошибку до тех пор, пока код не будет выполнен.

Ответ 11

Выведенный вами код Python будет преобразован в рекурсивную функцию, но оптимизация хвоста не будет оптимизирована, потому что у Python нет оптимизации хвостового вызова, поэтому в какой-то момент он будет переполняться потоком. Таким образом, код Python действительно сломан и потребует больше работы, чтобы получить его так же хорошо, как версии Haskell или C.

Вот пример того, что я имею в виду:

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

оболочки:

$ 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