Wie Sie repräsentieren eine einfache finite-state-Maschine in Ocaml?

Es hängt davon ab, wie Sie zum Betrieb des FSM, z.B., wenn Sie brauchen, um in der Lage sein, zu speichern, seinen Zustand und später fortsetzen, oder wenn Sie nur wollen, führen Sie es sofort. Im letzteren Fall ist es trivial, um es zu tun, als ein Bündel von tail-rekursiven Funktionen.

Nehmen wir beispielsweise an, die regexp C((A|B)*CD)* -- die folgenden sich gegenseitig rekursive Funktionen sind eine direkte Umsetzung von der jeweiligen FSM erkennt, dass eine Liste mit dazu passenden regexp (wenn ich Sie nicht machen keine Fehler 🙂 ):

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

Jeder Funktion entspricht genau einem Zustand des Automaten und setzt die transition-Funktion. Die Anwendung s1 : alphabet list -> bool läuft die FSM auf das argument.

PS: Beachten Sie, wie dies ist eine Anwendung zu demonstrieren, den nutzen und die Eleganz der tail-call-Optimierung...

Habe ich vor kurzem erstellt eine FSM-Modul in OCaml die Sie hier finden können hier

Habe ich einige spezielle Anforderungen für meine FSM-Implementierung, die es nicht ganz so schön zu sehen wie einige der anderen hingewiesen, dass hier, aber ich denke, die Art und Weise erklären Sie die FSM selbst ist ganz nett und erklärend. Die Besondere Anforderung ist, dass ich in der Lage sein, code zu erzeugen, in HDL (hardware description language) aus einer deklarativen Beschreibung der FSM sind neben der Fähigkeit zur Simulation der FSM operation in den OCaml-version. Weil ich brauchte, um Prädikat-Ausdrücke statt des übergangs Funktionen (andernfalls würde, wie ich zu übersetzen, eine Funktion, um einen string?) Dies vor allem, die Sie konzentrieren sich auf die FSM-Modul es und die erstellen und eval_fsm Funktionen gibt.

Hier ist ein Beispiel der Verwendung:

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

(Bitte entschuldigen Sie die ";;" enden - ich wollte in der Lage sein, um cut & fügen Sie diesen code in REPL)

Einige der code hier ist in der Logic-Projekt auf meinem github (fsm.ml ist Teil des Projekts). Der Prädikat-Ausdruck ist entweder T oder F (true oder false). Wenn true, dann wird der übergang gemacht wird vom gegenwärtigen Zustand in den nächsten Zustand. Const T bedeutet immer der übergang. Ein Ausdruck wie:

Bop(And, full, soap) 

Bedeutet, dass, wenn beide voll und Seife sind T (true), dann wird der Ausdruck zu true ausgewertet wird.