Как представить простой конечный автомат в Ocaml?

Ответ 1

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

Предположим, что ваши переходы запускаются по строкам:

type event = string

module EventMap = Map.Make(struct
    type t = event
    let compare = compare
  end)

type state = {
  state_info : ...; (* the content of that state, id, comment, etc. *)
  mutable state_transitions : state EventMap.t;
}

let next_state current_state event =
  try
    EventMap.find event current_state.state_transitions
  with Not_found -> current_state

Здесь я предположил, что неизвестные события остаются в одном состоянии, но вы можете иметь состояние ошибки в записи...

Ответ 2

Это зависит от того, как вы должны управлять FSM, например, если вам нужно сохранить его состояние и продолжить позже, или если вы просто хотите его немедленно выполнить. В последнем случае тривиально делать это как кучу хвостовых рекурсивных функций.

Например, предположим, что regexp C((A|B)*CD)* - следующие взаимно-рекурсивные функции являются прямой реализацией соответствующего FSM, который распознает список, соответствующий этому регулярному выражению (если я не ошибся:)):

type alphabet = A | B | C | D

let rec s1 = function
  | C :: rest -> s2 rest
  | _ -> false

and s2 = function
  | [] -> true
  | (A | B) :: rest -> s2 rest
  | C :: rest -> s3 rest
  | _ -> false

and s3 = function
  | D :: rest -> s2 rest
  | _ -> false

Каждая функция соответствует точно одному состоянию автомата и реализует его функцию перехода. Применение s1 : alphabet list -> bool будет запускать FSM в аргументе.

PS: Обратите внимание, как это приложение, демонстрирующее преимущество и элегантность оптимизации хвостового вызова...

Ответ 3

Существует отличный ответ, который демонстрирует выразительность и элегантность OCaml в представлении конечного конечного автомата здесь:

автоматы в ocaml

Для более серьезного использования вы можете попытаться взглянуть на некоторую библиотеку конечных автоматов, такую ​​как fsm библиотека здесь.

Ответ 4

Недавно я создал модуль FSM в OCaml, который вы можете найти здесь

У меня есть некоторые особые требования к моей реализации FSM, которые могли бы не совсем приятно смотреть на некоторые из других, упомянутых здесь, однако, я думаю, что способ, которым вы объявляете сам FSM, является добрым и декларативным. Особое требование состоит в том, что мне нужно иметь возможность генерировать код в HDL (язык описания аппаратных средств) из декларативного описания FSM в дополнение к возможности имитировать операцию FSM в версии OCaml. Из-за этого мне нужно было использовать предикатные выражения вместо функций перехода (в противном случае, как бы преобразовать функцию в строку?) Поэтому в основном вы хотите сосредоточиться на модуле FSM там, там есть функции create и eval_fsm.

Вот пример использования:

(*********************************************************
 * FSM testing *******************************************
*)

(* inputs to the FSM *)
let full         = Var({name ="full"; value  = F});;
let ten_minutes  = Var({name = "ten_minutes"; value = F});;
let empty        = Var({name = "empty"; value = F});;
let five_minutes = Var({name = "five_minutes"; value =F});;


(* T is true,    F is false *)
let _ = 
  assign full         F ;
  assign ten_minutes  F ;
  assign empty        F ;
  assign five_minutes F ;;

(* outputs from the FSM *)
let water_on     = Var({name = "water_on";    value = F});;
let agitate      = Var({name = "agitate";     value = F});;
let drain        = Var({name = "drain"  ;     value = F});;
let start_timer  = Var({name = "start_timer"; value = F});;
let motor_on     = Var({name = "motor_on";    value = F});;
let washed       = Var({name = "washed";    value = F});;
let soap         = Var({name = "soap";        value = F});;

let reset_actions = 
  assign water_on      F;
  assign agitate       F;
  assign drain         F;
  assign start_timer   F;
  assign motor_on      F;;

module WashStates = 
  struct
   type t =  START | FILL | WASH | DRAIN |  RINSE | SPIN | STOP
     deriving(Show, Enum)    
   let start_state = START
  end 

module LogicExp = 
  struct
    type t     = boolean Logic.bexp
    type var_t = boolean Logic.variable
    let eval_exp exp = to_bool (Logic.eval exp)
    let var_to_s     = var_to_s
  end

module WashFSM = FSM(WashStates)(LogicExp) 

open WashStates

(* declare the state table *)
(*   CS,   PREDICATE,               NS,    ACTIONs *)
let my_fsm = [
  (START, Const(T),                 FILL, [(water_on,   T); 
                                           (soap,       T)]);
  (FILL,  Bop(And,full,soap),       WASH, [(water_on,   F);
                                           (agitate,    T);
                                           (washed,     T);
                                           (start_timer,T)]);
  (WASH,  ten_minutes,              DRAIN,[(agitate,    F);
                                           (start_timer,F); 
                                           (empty,      T)]); 
  (DRAIN, Bop(And,empty,soap),      FILL, [(drain,      F); 
                                           (soap,       F);
                                           (water_on,   T)] );
  (FILL,  Bop(And,full,Not(soap)),  RINSE,[(water_on,   F); 
                                           (soap,       F);
                                           (empty,      F);
                                           (agitate,    T)]);
  (RINSE, ten_minutes,              DRAIN, [(agitate,   F);
                                            (empty,     T)] );
  (DRAIN, Bop(And,empty,Not(soap)), SPIN,  [(motor_on,  T);
                                            (start_timer,T)]);
  (SPIN,  five_minutes,             STOP,  [(water_on,  F);
                                            (drain,     F);
                                            (start_timer,F);
                                            (motor_on,  F)]);
  (STOP,  Const(T),                 STOP,  [(motor_on,  F)]);
];; 


let st_table, current_state = WashFSM.create my_fsm in

let _ = assign full T in
let current_state = WashFSM.eval_fsm st_table current_state  in
let _ = assign ten_minutes T in
let current_state = WashFSM.eval_fsm st_table current_state  in
let current_state = WashFSM.eval_fsm st_table current_state  in
let _ = (assign ten_minutes F);(assign empty T) in
let current_state = WashFSM.eval_fsm st_table current_state  in

let _ = assign five_minutes T in
let current_state = WashFSM.eval_fsm st_table current_state  in
let _ = assign five_minutes F in
let _ = assign ten_minutes T in
let current_state = WashFSM.eval_fsm st_table current_state  in
let current_state = WashFSM.eval_fsm st_table current_state  in
let _ = assign five_minutes T in
let _ = WashFSM.eval_fsm st_table current_state  in
(*...and so on...*)

(Пожалуйста, извините окончания ";;" - я хотел иметь возможность вырезать и вставлять этот код в REPL)

Некоторая часть используемого здесь кода находится в Logic project на моем github (fsm.ml является частью этого проекта). Выражение предиката оценивается либо T, либо F (true или false). Если true, то переход осуществляется из текущего состояния в следующее состояние. Const T означает всегда переход. Выражение, такое как:

Bop(And, full, soap) 

Означает, что если и full, и soap являются T (true), тогда выражение оценивается как true.