Чистая и безопасная для типов реализация конечного автомата на статически типизированном языке? - PullRequest
Новая
       29

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

25 голосов
/ 09 октября 2011

Я реализовал простой конечный автомат в 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;
}

Итак, я решил, что это проблема с системой сломанных типов Си. Поэтому я использовал язык с реальной системой типов (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 ())

Почему так сложно создать конечный автомат на статически типизированном языке? Я должен сделать ненужные накладные расходы также на статически типизированных языках. Динамически типизированные языки не имеют этой проблемы. Есть ли более простой способ сделать это на статически типизированном языке?

Ответы [ 11 ]

0 голосов
/ 09 октября 2011

Код 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
Страница:
...