如何在Ocaml中表示一个简单的有限状态机?

16

我以前在C++和Java中编写过一些状态机,但从未在像Ocaml这样的函数式语言中编写过。

问题是我不知道是否可以只是改编自面向对象语言版本的代码,因为在Ocaml中,记录和变体比类更强大;

因此,我需要一个基于事件驱动的有限状态机(分层的,就像UML中的那样),易于配置。

能否有经验的人发布一个简单的示例?只是为了避免最常见的陷阱。

谢谢 :)

编辑 16/03:是否可能不使用可变状态来实现?并且我想将其适当地封装在名称为“FSM”的模块或类下,我应该选择哪个?


可能是OCaml中的自动机的重复问题。 - Marcin
4个回答

12

这取决于您必须如何操作FSM,例如,如果您需要能够存储其状态并稍后继续,或者如果您只想立即执行它。在后一种情况下,将其作为一堆尾递归函数执行是微不足道的。

例如,假设正则表达式为C((A|B)*CD)*——以下相互递归的函数是实现FSM的直接方法,该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:请注意,这是一个应用程序,展示了尾调用优化的好处和优雅之处...

9
通常,您需要创建一个与自动机状态相对应的记录,并为触发转换到另一个状态的事件创建另一种类型。在状态记录中,您可以使用映射来查找每个事件的新状态。
假设您的转换是由字符串触发的:
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

在此,我假设未知事件保持在相同的状态,但您可能会在记录中遇到错误状态...


这是否可以在不可变状态下完成?我想恰当地将其封装在名为“FSM”的模块或类中,我应该选择哪一个? - codablank1

8

这里有一个很好的答案展示了OCaml在表示有限状态机方面的表现力和优雅性:

OCaml中的有限状态自动机

对于更严肃的应用,你可以尝试查看一些有限状态机库,比如fsm库。


7
我最近在OCaml中创建了一个FSM模块,您可以在这里找到。
对于我的FSM实现,我有一些特殊的要求,这可能使它看起来不太好看,正如其他人在这里指出的那样,但是,我认为声明FSM本身的方式很好,很声明式。特殊要求是,我需要能够从FSM的声明性描述中生成HDL(硬件描述语言)代码,除了能够在OCaml版本中模拟FSM的操作之外。因此,我需要使用谓词表达式而不是转换函数(否则,我如何将函数翻译成字符串?)因此,主要关注FSM模块以及其中的createeval_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中

这里使用的一些代码可以在我的github上的Logic project中找到(fsm.ml是该项目的一部分)。 谓词表达式评估为T或F(真或假)。 如果为真,则从当前状态转换到下一个状态。 Const T表示始终转换。 例如:

Bop(And, full, soap) 

如果fullsoap都是T(真),则表达式的值为真。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接