Appendice 2: Codice sviluppato.
Comprende tutto il codice utilizzato da Politically Correct, eccetto lo strumento di
inferenza dei tipi e Paxion. Dei compilatori sono presenti le definizioni Ocamlyacc e
Ocamllex, e non i file da queste generati.
(*miscFun.mli*)
(** Varia utilita'.*)
(** Contiene una raccolta di funzioni generiche utilizzate in tutto il progetto. Contiene anche la definizione degli insiemi di elementi piu' utilizzati dai vari algoritmi.*)
module NTset : sig
type elt = string (**/**)
type t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
(** Insieme di simboli non terminali di CFG.*) module Tset :
sig
type elt = string (**/**)
type t = NTset.t val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
(** Insieme di simboli terminali di una CFG.*) module Qset :
sig
type elt = int (**/**)
type t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
(** Insieme di stati di un automa. *) module Sset :
sig
type elt = string (**/**)
type t = NTset.t val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t
val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
(** Insieme di simboli utilizzati da un automa, sia per rappresentare stringhe di input che per simboli nello stack di un PDA.*)
module QSset : sig
type elt = Qset.t (**/**)
type t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
(** Insieme di insiemi di stati di un automa. Utilizzato per la conversione da NFA a DFA.*)
module QSQset : sig
type elt = Qset.elt * Sset.elt * Qset.elt (**/**)
type t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool
val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
(** Insieme di terne <stato, simbolo, stato>, utilizzato nella conversione da PDA a CFG.*)
(** Stampa a video una lista di stringhe.*) val print_stringlist : string list -> unit (** Stampa a video una lista di interi.*) val print_intlist : int list -> unit (** Non effettua nulla.*)
val skip : unit
(** Stampa a video un valore booleano.*) val print_bool : bool -> unit
(** Data una lista e un intero n, rende la lista composta da tutte le permutazioni di n elementi della lista fornita. Ad esempio permutate [[a,b,c]] 2 -> [[[a,b],[a,c],[b,c]]].*)
val permutate : 'a list -> int -> 'a list list
(** Date due liste, fornisce il prodotto cartesiano di queste. Ad
esempio cartesianCombine [[a,b]] [[1,2,3]] -> [([a,1),(a,2),(a,3),(b,1), (b,2),(b,3)]].*)
val cartesianCombine : 'a list -> 'b list -> ('a * 'b) list (** Fornisce un intero non presente nell'insieme fornito*) val freshint : Qset.t -> int
(** Dato un intero, rende la stringa corrispondente. Es: genString 3 -> C; genString 28 -> AB.*)
val genString : int -> string
(** Converte un numero float in una rappresentazione di orario: hh:mm:ss.cc.*)
(*miscFun.ml*)
let print_stringlist ls = let rec innerprint l = match l with s::tail when tail = [] -> print_string (s);innerprint tail | s::tail -> print_string (s^"; ");innerprint tail
| [] -> print_string "]"; in print_string "[";innerprint ls
let print_intlist ls = let rec innerprint l = match l with s::tail when tail = [] -> print_int (s);innerprint tail
| s::tail -> print_int (s);print_string "; ";innerprint tail | [] -> print_string "]"; in
print_string "[";innerprint ls let skip = print_string ""
let print_bool b = if b then print_string "true" else print_string "false"
module NTset = Set.Make(struct type t = string let compare = compare end)
module Tset = NTset
module Qset = Set.Make(struct type t = int let compare = compare end) module Sset = Tset
module QSset = Set.Make(struct type t = Qset.t let compare = compare end)
module QSQset = Set.Make(struct type t = (Qset.elt * Sset.elt * Qset.elt) let compare = compare end);;
let permutate q n=
let rec generatePerm p =
let rec incrPointers curr don = if (curr = List.length p) then if don then [] else [-1] else if don
then (List.nth p curr)::(incrPointers (curr+1) true) else
if (List.nth p curr = ((List.length q) -1)) then 0::(incrPointers (curr+1) false)
else ((List.nth p curr)+1)::(incrPointers (curr+1) true) in let newPointer = incrPointers 0 false in
if List.hd (List.rev newPointer) = -1 then []
else
let rec generateValue p = match p with
i::tail -> (List.nth q i)::(generateValue tail) | [] -> [] in
(generateValue newPointer)::generatePerm newPointer in let rec generatePointer i =
if i=n then [] else
then -1::generatePointer (i+1) else 0::generatePointer (i+1) in let initialPointer = generatePointer 0 in generatePerm initialPointer;;
(*rende una lista che e' il prodotto cartesiano di due liste*) let rec cartesianCombine l1 l2 = match l1 with
e::tail -> let rec scan e l = match l with e1::tail -> (e,e1)::scan e tail
| []->[] in
List.append (scan e l2) (cartesianCombine tail l2) | [] -> [];;
let freshint (s:Qset.t) = try
(Qset.max_elt s)+1 with Not_found -> 1
let rec genString i = if i/26 = 0
then Char.escaped (Char.chr (i+65))
else (genString ((i/26)-1))^(Char.escaped (Char.chr ((i mod 26)+ 65)))
let convertTime (time:float):string =
let hours = int_of_float (time /. 3600.0) in
let mins = int_of_float ((mod_float time 3600.0)/.60.0) in
let secs = time -. (float_of_int (hours*3600)) -. (float_of_int (mins*60)) in
(string_of_int hours)^":"^(string_of_int mins)^":"^ (string_of_float secs);;
(*evaluator.mli*)
type label = string type evar = string type policy = string type action = string type location = int type plan =
Empty
| SChoice of label * location * plan | SComp of plan * plan
type heffect = Epsilon | Sigma
| HVar of label | HEvent of action
| Seq of heffect * heffect | Choice of heffect * heffect | HFrame of policy * heffect | Mu of label * heffect | HLoc of location * heffect | PSel of (plan * heffect) list
type htype = TUnit | TBool | TVar of tvar | Arrow of htype * heffect * htype
and tvar = string type expr =
Unit
| Bool of bool | Var of evar
| Abs of evar * evar * expr | App of expr * expr
| If of expr * expr * expr | Frame of policy * expr | Event of action
| Wait of location | Req of label * htype type net_service =
NEmpty
| NServ of location * expr * htype | NSeq of net_service * net_service
type constrain = HType of htype | HEffect of heffect type type_env = (evar * constrain) list
val empty_type_env : type_env module Cset :
sig
type elt = constrain * constrain type t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
module Vset : sig
type elt = htype type t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
module Hset : sig
type elt = heffect type t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool
val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t end
type constraint_set = Cset.t type elt = constrain * constrain type t = Cset.t
val empty : t
val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool
val iter : (elt -> unit) -> t -> unit
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t
val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int
val elements : t -> elt list val min_elt : t -> elt
val max_elt : t -> elt val choose : t -> elt
val split : elt -> t -> t * bool * t exception WrongConstrainedType
exception SubstitutionError of htype * htype * htype exception RecursiveConstraint of constrain * constrain exception UnificationError of elt
exception TypeNotFound of htype
exception NotCompatibleType of htype * htype exception NotCombinableType of htype * htype exception NotValidPlan of plan
exception NotSubUnificable of htype * htype val compatible : htype -> htype -> bool
val sub_combine : plan -> htype -> htype -> htype val combine : plan -> htype -> htype -> htype val sub_uni : htype -> htype -> htype
type htype_solution = (htype * htype) list
type heffect_solution = (heffect * heffect) list type ct_solution = (constrain * constrain) list val new_tvar : unit -> htype
val new_hvar : unit -> heffect
val gamma : type_env -> evar -> constrain val constraint_to_htype : constrain -> htype val constraint_to_heffect : constrain -> heffect val appear : expr -> expr -> bool
val fv : constrain -> Vset.t * Hset.t val set_choose : t -> elt * t
val occurs_free_heffect : Hset.elt -> heffect -> bool val occurs_htype : htype -> htype -> bool
val occurs_heffect : heffect -> heffect -> bool val is_variable : constrain -> bool
val subst_heffect : heffect -> heffect -> heffect -> heffect
val subst_heffect_ct : constrain -> heffect -> heffect -> constrain val subst_htype : htype -> htype -> htype -> htype
val subst_htype_ct : constrain -> htype -> htype -> constrain val subst_ct : constrain -> constrain -> constrain -> constrain val subst_cset : constraint_set -> constrain -> constrain -> t val unify : constraint_set -> ct_solution * ct_solution
val l_min : location -> location -> bool val build_rcset :
htype -> heffect ->
label -> htype -> location -> net_service -> htype * heffect * t * t val infer :
type_env * expr * location * net_service -> heffect * htype * t * t val set_map : (elt -> elt) -> t -> t
val compose_map : 'a list -> 'a list -> 'a list
val apply_map_ct : (constrain * constrain) list -> constrain -> constrain
val apply_map_cset :
(constrain * constrain) list ->
(constrain * constrain) list -> constraint_set -> t val bounds : heffect -> t -> heffect
val mgs_h : constraint_set -> ct_solution
val mgs : constraint_set * constraint_set -> ct_solution * ct_solution val simplify_heffect : heffect -> heffect
val simplify_htype : htype -> htype
val switch_list : ('a * 'b) list -> ('b * 'a) list val plan_to_string : plan -> string
val list_to_string :
('a * 'b) list -> ('a -> string) -> ('b -> string) -> string -> string val heffect_to_string : heffect -> label
val htype_to_string : htype -> tvar val expr_to_string : expr -> evar
val service_to_string : net_service -> string val heffect_from_solution :
(constrain * constrain) list -> heffect -> heffect
val htype_from_solution : (constrain * constrain) list -> htype -> htype val evaluate : expr -> location -> net_service -> heffect * htype
(*evaluator.ml*)
(* Begin Tipi *) type label = string type evar = string type policy = string type action = string type location = int type plan =
Empty
| SChoice of label * location * plan | SComp of plan * plan
type heffect = Epsilon | Sigma
| HVar of label | HEvent of action
| Seq of heffect * heffect | Choice of heffect * heffect | HFrame of policy * heffect | Mu of label * heffect | HLoc of location * heffect | PSel of ((plan * heffect) list)
type htype = TUnit | TBool
| TVar of tvar
| Arrow of htype * heffect * htype and tvar = string
type expr = Unit
| Bool of bool | Var of evar
| Abs of evar * evar * expr | App of expr * expr
| If of expr * expr * expr | Frame of policy * expr | Event of action
| Wait of location | Req of label * htype type net_service = NEmpty
| NServ of location * expr * htype | NSeq of net_service * net_service type constrain =
HType of htype | HEffect of heffect
type type_env = (evar * constrain) list let empty_type_env : type_env = []
module Cset = Set.Make(struct type t = (constrain * constrain) let compare = compare end)
module Vset = Set.Make(struct type t = htype let compare = compare end) module Hset = Set.Make(struct type t = heffect let compare = compare end)
type constraint_set = Cset.t include Cset
exception WrongConstrainedType
exception SubstitutionError of htype * htype * htype exception RecursiveConstraint of constrain * constrain exception UnificationError of elt
exception TypeNotFound of htype
exception NotCompatibleType of htype * htype exception NotCombinableType of htype * htype exception NotValidPlan of plan
exception NotSubUnificable of htype * htype let rec compatible rho tau =
match (rho,tau) with
| t1, t2 when t1 = t1 -> true | TVar x, _ -> false
| _ , TVar x -> true
| Arrow(t,_,t'), Arrow(t1,_,t1') -> if (compatible t t1) then (compatible t' t1') else false
| _,_ -> false
let rec sub_combine (p : plan) rho tau = if (compatible rho tau) then
match (rho,tau) with | TUnit,TUnit -> TUnit | TBool,TBool -> TBool
| Arrow(r0,HFrame(phi, _),r1),Arrow(t0,h,t1) -> Arrow((sub_combine p r0 t0),PSel([p,HFrame(phi,h)]),(sub_combine p r1 t1))
else raise (NotCompatibleType(rho,tau)) let combine (p : plan) rho tau =
match (rho,tau) with
| Arrow(r0,HFrame(phi, _),r1),Arrow(t0,h,t1) -> (match p with
| SChoice(r,l,Empty) -> let h' = HLoc(l,HFrame(phi, Seq(Sigma,h))) in
let sel = PSel([p,h']) in
let s = (sub_combine p r1 t1) in Arrow(t0, sel, s)
| _ -> raise (NotValidPlan p)) | _,_ -> raise (NotCombinableType (rho, tau))
let rec sub_uni t t' = match t,t' with | TUnit,TUnit -> TUnit | TBool,TBool -> TBool | TVar(x),TBool -> TBool | TBool,TVar(x) -> TBool | TVar(x),TUnit -> TUnit | TUnit, TVar(x) -> TUnit
| Arrow(t0,h,t1),Arrow(t0',h',t1') -> Arrow((sub_uni t0 t0'), Choice (h,h') ,(sub_uni t1 t1'))
| _,_ -> raise (NotSubUnificable(t,t')) type htype_solution = (htype * htype) list
type heffect_solution = (heffect * heffect) list type ct_solution = (constrain * constrain) list let new_tvar =
let i = ref 0 in fun() ->
i := !i + 1;
TVar("t_"^ string_of_int !i) let new_hvar =
let i = ref 0 in fun() ->
i := !i + 1;
HVar("h_"^ string_of_int !i)
let rec gamma (g:type_env) (e:evar) = match g with
| [] -> HType(new_tvar())
| (e', c)::tl -> if e' = e then c else (gamma tl e) let constraint_to_htype c = match c with | HType t -> t | _ -> raise WrongConstrainedType let constraint_to_heffect h = match h with
| HEffect heff -> heff
| _ -> raise WrongConstrainedType
(* End Tipi *)
(* Begin Inferenza Vincoli *) let rec appear e e' =
match (e,e') with
| x, y when x = y -> true
| x, Abs(z,y,e1) -> appear x e1
| x, App(e1, e2) -> (appear x e1) or (appear x e2) | x, Frame(p, e1) -> appear x e1
| x, If(e1, e2, e3) -> (appear x e1) or ((appear x e2) or (appear x e3))
| _ -> false
let rec fv ct = match ct with
| HType t -> (match t with
| TVar _ -> (Vset.singleton t, Hset.empty)
| Arrow(t1, h, t2) -> let (v1, h1) = fv (HType t1) in let (v2, h2) = fv (HType t2) in let (vh, hh) = fv (HEffect h) in let v3 = Vset.union v1 (Vset.union
v2 vh) in
let h3 = Hset.union h1 (Hset.union h2 hh) in
(v3, h3) | _ -> (Vset.empty, Hset.empty)) | HEffect h -> (match h with
| HVar _ -> (Vset.empty, Hset.singleton h)
| Seq(h1, h2) -> let (vs, hs) = fv (HEffect h1) in let (vs', hs') = fv (HEffect h2) in (Vset.empty, Hset.union hs hs') | Choice(h1, h2) -> let (vs, hs) = fv (HEffect h1) in let (vs', hs') = fv (HEffect h2) in (Vset.empty, Hset.union hs hs') | HFrame(p, h1) -> fv (HEffect h1)
| Mu(l, h1) -> let (vs, hs) = fv (HEffect h1) in (Vset.empty, Hset.remove (HVar(l)) hs) | _ -> (Vset.empty, Hset.empty))
let set_choose s = let e = choose s in (e, remove e s)
let occurs_free_htype (t : htype) tau = let (v, h) = fv(HType tau) in (Vset.mem t v)
let occurs_free_heffect (h : heffect) heff = let (v, h') = fv(HEffect heff) in (Hset.mem h h')
let rec occurs_htype (t : htype) tau = match tau with
| tau when t = tau -> true
| Arrow(t1, h, t2) -> (occurs_htype t t1) or (occurs_htype t t2) | _ -> false
let rec occurs_heffect (h : heffect) heff = match heff with
| heff when h = heff -> true
| Seq(h1, h2) -> (occurs_heffect h h1) or (occurs_heffect h h2) | Choice(h1, h2) -> (occurs_heffect h h1) or (occurs_heffect h h2) | HFrame(p, h1) -> (occurs_heffect h h1)
| Mu(l, h1) -> (occurs_heffect h h1) | _ -> false
let is_variable cons = match cons with
| HType(TVar _) -> true | HEffect(HVar _) -> true | _ -> false
let rec subst_heffect heff heff' h = match heff with
| h' when h' = h -> heff'
| Choice(h1,h2) -> Choice((subst_heffect h1 heff' h),(subst_heffect h2 heff' h))
| Seq(h1,h2) -> Seq((subst_heffect h1 heff' h),(subst_heffect h2 heff' h))
| HFrame(l, h1) -> HFrame(l, (subst_heffect h1 heff' h)) | Mu(h', hh) -> (match (heff, h) with
subst_heffect hh heff' h)
| _, _ -> Mu(h', subst_heffect hh heff' h)) | _ -> heff
let rec subst_heffect_ct ct heff' h = match ct with
| HEffect(heff) -> HEffect(subst_heffect heff heff' h) | HType(tau) -> (match tau with
| Arrow(t1, heff, t2) -> let HType(tt1) = subst_heffect_ct (HType(t1)) heff' h in
let HType(tt2) = subst_heffect_ct (HType(t2)) heff' h in
HType(Arrow(tt1, (subst_heffect heff heff' h), tt2))
| _ -> HType(tau))
let rec subst_htype tau tau' b = match b with
| TVar t -> (match tau with
| TVar t' when t' = t -> tau'
| Arrow(t1,h,t2) -> Arrow((subst_htype t1 tau' b),h,(subst_htype t2 tau' b))
| _ -> tau)
| _ -> raise (SubstitutionError(tau, tau', b))
let rec subst_htype_ct ct tau' t = match ct with
| HEffect h -> HEffect h
| HType(tau) -> HType(subst_htype tau tau' t)
let subst_ct const const' ct = match (const', ct) with
| HType(tau'), HType(t) -> subst_htype_ct const tau' t
| HEffect(heff'), HEffect(h) -> subst_heffect_ct const heff' h | _ -> ct
let rec subst_cset (c : constraint_set) const' ct : constraint_set = if is_empty c then empty else
let (e, c1) = set_choose c in match e with
| (t1, t2) -> let s = singleton((subst_ct t1 const' ct), (subst_ct t2 const' ct)) in
let s' = (subst_cset c1 const' ct) in (union s s')
let rec unify (c : constraint_set) : (ct_solution * ct_solution) = if is_empty c then [],[] else
let (x, c') = set_choose c in match x with
| HType tau, HType t when is_variable (HType t) -> if occurs_htype t tau then
raise (RecursiveConstraint ((HType t), (HType tau))) else
let (tu, hu) = unify(subst_cset c' (HType(tau)) (HType(t))) in
([HType(tau), HType(t)] @ tu), (hu)
| HType t, HType tau when is_variable (HType t) -> if occurs_htype t tau then
raise (RecursiveConstraint ((HType t), (HType tau))) else
let (tu, hu) = unify(subst_cset c' (HType(tau)) (HType(t))) in
([HType(tau), HType(t)] @ tu), (hu)
| HType(Arrow(t1,h1,t2)), HType(Arrow(t1',h2,t2')) ->
unify(add (HEffect h1, HEffect h2) (add (HType t1, HType t1')
(add (HType t2, HType t2') c')))
| HEffect heff, HEffect h when is_variable (HEffect h) ->
let (tu, hu) = unify(subst_cset c' (HEffect heff) (HEffect h)) in
([HEffect(heff), HEffect(h)] @ tu), (hu)
| HEffect h, HEffect heff when is_variable (HEffect h) ->
let (tu, hu) = unify(subst_cset c' (HEffect heff) (HEffect h)) in
([HEffect(heff), HEffect(h)] @ tu), (hu)
| HEffect(Seq(h1,h2)), HEffect(Seq(h1',h2')) -> unify(add (HEffect h1, HEffect h1') (add (HEffect h2, HEffect h2') c'))
| HEffect(Choice(h1,h2)), HEffect(Choice(h1',h2')) -> unify(add (HEffect h1, HEffect h1')
(add (HEffect h2, HEffect h2')c'))
| HEffect(HFrame(l,h)), HEffect(HFrame(l',h')) when l = l' -> unify(add (HEffect h, HEffect h') (add (HEffect h', HEffect h) c'))
| _ -> unify c'
let l_min (l:location) (s:location) = if (l < s) then true else false
let rec build_rcset tau heff r rho l w = match w with
| NEmpty -> tau, heff, empty, empty
| NServ(l', e, tau') -> if((l_min l l') & (compatible rho tau')) then let t = combine (SChoice(r, l', Empty)) rho tau' in
match t with
| Arrow(t0, h, t1) -> (tau, heff, singleton((HType t),(HType tau)), singleton((HEffect h),(HEffect heff)))
| _ -> (tau, heff, singleton((HType t),(HType tau)), empty)
else (tau, heff, empty, empty)
n in
let (x', y', cset', hcset') = build_rcset tau heff r rho l n' in
(tau, heff, (union cset cset'), (union hcset hcset')) let rec infer ((g:type_env), (e:expr), (l:location), (w:net_service)) : (heffect * htype * constraint_set * constraint_set) =
match e with
| Unit -> (Epsilon, TUnit, empty, empty) | Bool b -> (Epsilon, TBool, empty, empty) | Var e -> let ct = gamma g e in
let t = constraint_to_htype ct in
(Epsilon, t, singleton(ct, (HType(TVar e))), empty) | Abs(z,x,e1) -> let t = new_tvar() in
let t' = new_tvar() in let h = new_hvar() in
let g1 = (x,HType(t))::(z,HType(Arrow(t,h,t')))::g in let (h1,t1,c1,hc1) = infer (g1, e1, l, w) in
(Epsilon, Arrow(t,h,t1), (add(HType(t1),HType(t')) c1), (add((HEffect h1), (HEffect(h))) hc1))
| Event a -> (HEvent(a), TUnit, empty, empty)
| Frame(phi, e1) -> let (h, t, c, hc) = infer (g, e1, l, w) in (HFrame(phi,h), t, c, hc)
| If(e1, e2, e3) -> let (hg, tg, cg, hcg) = infer (g, e1, l, w) in let (h2, t2, c2, hc2) = infer (g, e2, l, w) in let (h3, t3, c3, hc3) = infer (g, e3, l, w) in let t = new_tvar() in
let c = add (HType(tg), HType(TBool)) (add (HType (t2),HType(t)) (add (HType(t3),HType(t)) (union(union cg c2) c3))) in let hc = (union(union hcg hc2) hc3) in
(Choice(h2, h3), t, c, hc) | App(e1, e2) -> let (h1, t1, c1, hc1) = infer (g, e1, l, w) in let (h2, t2, c2, hc2) = infer (g, e2, l, w) in let t = new_tvar() in
let h = new_hvar() in
let c = add (HType(t1),(HType(Arrow(t2,h,t)))) (union c1 c2) in
(Seq(h1, (Seq(h2,h))), t, c, (union hc1 hc2)) | Req(r, rho) -> let tau = new_tvar() in
let heff = new_hvar() in
let (_, _, c, hc) = build_rcset tau heff r rho l w in (Epsilon, tau, c, hc)
(** Va costruito correttamente il caso Req *) (* End Inferenza Vincoli *)
(* Begin Sostituzioni *)
let set_map f s = fold (fun x s -> (add(f x) s)) s empty let compose_map a b = a@b
let rec apply_map_ct soln const = match soln with
| (a, b)::tl -> subst_ct (apply_map_ct tl const) a b | _ -> const
let rec apply_map_cset soln solh (c : constraint_set) = if is_empty c then empty
else let ((t1, t2), c') = set_choose c in
add (apply_map_ct solh (apply_map_ct soln t1), apply_map_ct solh (apply_map_ct soln t2)) (apply_map_cset soln solh c')
(* End Sostituzioni *)
(* Begin Variabili libere *)
(* End Variabili libere *)
(* Begin MGS_h *)
let rec bounds h hc =
let hc' = filter (fun ( _ , h2) -> if h2 = HEffect(h) then true else false) hc in
if is_empty hc' then Epsilon else
let ((h1, h2), hc1) = set_choose hc' in match (h1, hc1) with
| HEffect h1', empty -> h1'
| HEffect h1', hc2 -> Choice(h1', bounds h hc2) | _ -> raise WrongConstrainedType
let rec mgs_h (hc : constraint_set) : ct_solution = if is_empty hc then []
else
let (x, cc) = set_choose hc in let (_, h) = x in
let (HEffect(HVar hv)) = h in
let p = [HEffect (Mu(hv, (bounds (HVar hv) hc))), HEffect (HVar hv)] in
compose_map (mgs_h(apply_map_cset [] p (diff hc (filter (fun (he, h') -> if h' = h then true else false) hc)))) p
(* End MGS_h *) (* Begin Unify *)
let mgs (c, hc) = let (ts, hs) = unify c in (ts, mgs_h(apply_map_cset ts hs hc))
(* Begin Simplification *)
let rec simplify_heffect h = match h with
| Seq(h1,h2) -> let sh1 = (simplify_heffect h1) in let sh2 = (simplify_heffect h2) in if sh1 = Epsilon then sh2 else
if sh2 = Epsilon then sh1 else Seq(sh1, sh2) | Choice(h1,h2) -> let h1' = simplify_heffect h1 in
let h2' = simplify_heffect h2 in
if h1' = h2' then h1' else Choice(h1', h2') | HFrame(l, h1) -> HFrame(l, (simplify_heffect h1))
| Mu(l, h') -> let (vs, hs) = fv(HEffect (simplify_heffect h')) in if (Hset.mem (HVar l) hs) then Mu(l, simplify_heffect h') else simplify_heffect h'
| h' -> h'
let rec simplify_htype t = match t with
| Arrow(t1, h, t2) -> Arrow(simplify_htype t1, simplify_heffect h, simplify_htype t2)
| tau -> tau
let rec switch_list l = match l with
| [] -> []
| (x,y)::tl -> (y,x)::(switch_list tl)
(* End Simplification *) (* Begin Text Converter *) let rec plan_to_string p = match p with
| Empty -> "Empty"
| SChoice(r, l, p') -> r^"["^(string_of_int l)^"]."^(plan_to_string p') | SComp(p1, p2) -> "("^plan_to_string p1 ^" | "^ plan_to_string p2^")" let rec list_to_string l f g c =
match l with
| (x,y) :: [] -> (f x)^" "^c^" "^(g y)
| (x,y) :: tl -> (f x)^" "^c^" "^(g y)^", "^(list_to_string tl f g c) | [] -> ""
| _ -> "NCL"
let rec heffect_to_string h = match h with
| Epsilon -> "Epsilon" | Sigma -> "Sigma" | HVar l -> l
| HEvent a -> a^"()"
| Seq(h1, h2) -> "("^(heffect_to_string h1)^" ^ "^(heffect_to_string h2)^")"
| Choice(h1, h2) -> "("^(heffect_to_string h1)^" + "^(heffect_to_string h2)^")"
| HFrame(p, h1) -> p^"["^(heffect_to_string h1)^"]" | Mu(l, h1) -> "mu "^l^"."^(heffect_to_string h1)
| PSel(l) -> "{"^(list_to_string l plan_to_string heffect_to_string "|>")^"}"
let rec htype_to_string t = match t with
| TUnit -> "Unit" | TBool -> "Bool" | TVar v -> v
| Arrow(t1, h, t2) -> "("^(htype_to_string t1)^")--"^(heffect_to_string h)^"->("^(htype_to_string t2)^")"
let rec expr_to_string e = match e with
| Unit -> "*"
| Bool b -> if b then "true" else "false" | Var ev -> ev
| Abs(z,x,e1) -> z^"("^x^").{"^(expr_to_string e1)^"}"
| App(e1, e2) -> (expr_to_string e1)^" ("^(expr_to_string e2)^")" | If(e1, e2, e3) -> "if ("^(expr_to_string e1)^") then {"^
(expr_to_string e2)^"} else {"^(expr_to_string e3)^"}" | Frame(p, e1) -> p^"["^(expr_to_string e1)^"]"
| Event a -> a
| Wait l -> "wait "^(string_of_int l)
| Req(l, tau) -> "req( "^l^", "^(htype_to_string tau)^")" let rec service_to_string serv =
match serv with | NEmpty -> "0"
| NServ(loc,exp,htype) -> ""^(string_of_int loc)^":"^(expr_to_string exp)^","^(htype_to_string htype)
| NSeq(s1,s2) -> (service_to_string s1)^"+"^(service_to_string s2) (* End Text Converter *)
(* Begin Evaluator *)
let heffect_from_solution sol h =
let h' = apply_map_ct sol (HEffect h) in match h' with
| HEffect hh -> hh
| _ -> raise WrongConstrainedType
let htype_from_solution sol t =
let t' = apply_map_ct sol (HType t) in match t' with
| HType tt -> tt
| _ -> raise WrongConstrainedType
let evaluate e l w =
let (h, t, c, hc) = infer([], e, l, w) in let (solt, solh) = mgs(c, hc) in
let heff = simplify_heffect (heffect_from_solution (compose_map solt solh) h) in
let tau = simplify_htype (htype_from_solution (compose_map solt solh) t) in
(heff, tau)
let (h, t) = evaluate e l w in let se = expr_to_string e in let sh = heffect_to_string h in let st = htype_to_string t in ("0, "^sh^" |- "^se^" : "^st) (* End Evaluator *) (* Begin Example *) (* let l = 0;;
let f = Abs("f","x1", Event("dd"));; let g = Abs("g","x2", Unit);;
let w = NSeq((NServ(1, f, Arrow(TVar("tau"), HEvent("dd"), TUnit))), (NServ(2, g, Arrow(TVar("tau"), Epsilon, TUnit))));;
let expr = Req("r", Arrow(TUnit, HFrame("phi", Epsilon), TUnit));; (* End Example *)
(* Begin Main *)
let main() =
let s = evaluate_to_string expr l w in print_string(s);
exit 0;; main();; *)
(* End Main *)
(* Begin Control Main
let constraint_to_string c = match c with
| HType t -> htype_to_string t | HEffect h -> heffect_to_string h let rec print_constraint_set c = if is_empty c then () else let (x, c') = set_choose c in match x with | t, t' -> print_string((constraint_to_string t)^" = "^ (constraint_to_string t')^" "); print_constraint_set c' | _ -> ()
let rec print_solution sol = match sol with
| (HType(t), HType(t'))::tl -> print_string((htype_to_string t)^ " = " ^(htype_to_string t')^" ");
print_solution tl;
| (HEffect(h), HEffect(h'))::tl -> print_string((heffect_to_string h)^ " = " ^(heffect_to_string h')^" ");
print_solution tl; | [] -> print_string(" END ")
let main() = try
let s = evaluate_to_string expr in print_string(s);
let (h, t, c, hc) = infer([], expr) in let (st, sh) = mgs(c, hc) in print_string(" C: "); print_constraint_set c; print_string(" HC: "); print_constraint_set hc; print_string(" sigma: "); print_solution st; print_string(" <=: "); print_solution sh;
with UnificationError (t, t') -> print_string("UnificationError "^ (constraint_to_string t)^" = "^(constraint_to_string t'));
exit 0;; main();;
(*checker.ml*) open MiscFun open Automata open Grammar open GrammarBase open Memories open Bpa open HistoryChecker open Evaluator open AutomataScanner open HistoryScanner open LambdaScanner open ServiceScanner let main =
let len = Array.length Sys.argv in if ( len < 5 || len > 7)
then (exit 0;);
let hisFilename = Sys.argv.(1) in let polFilename = Sys.argv.(2) in let verbose =
try
int_of_string (Sys.argv.(3))
with Failure(a) -> print_string "PD!";3 in let l = int_of_string (Sys.argv.(4)) in
let local = if l = 0
then false else true in let his =
if (len = 5)
then scanHistory (open_in hisFilename)
else (let location = int_of_string (Sys.argv.(5)) in let serviceFilename = Sys.argv.(6) in
print_string "netserv\n";
let netservice = scanService (open_in serviceFilename) in print_string "lambda\n";
let expr = scanLambda (open_in hisFilename) in if(verbose>0)
then (print_string ("Evaluating expression "^(expr_to_string expr)^" in location "^(Sys.argv.(5))^" with net service "^
(service_to_string netservice)^"\n"););
let (h,t) = evaluate expr location netservice in if(verbose>0)
then ( let se = expr_to_string expr in let sh = heffect_to_string h in let st = htype_to_string t in
print_string ("Result: 0, "^sh^" |- "^se^" : "^st););
match t with
Arrow(t1,h,t2) -> h) in if (verbose>0)
then (print_string "Initial History:\n";print_string ((heffect_to_string his)^"\n"););
let policies = scanAutomata (open_in polFilename) in
let rec printLabelled automata = match automata with (l,nfa)::tail -> print_string (l^":\n");print_nfa
nfa;print_string "\n"; printLabelled tail; |[] -> skip in
if (verbose>0)
then (print_string "\nInitial Policies:\n";printLabelled policies;print_string "\nCheck Started!\n\n");
let result = check his policies local verbose in if (verbose>0)
then (print_string ("\n\n<===========>\nworking plans: "^planlist_to_string result););
result;; (*
let main = let expr = Abs
("z","x", If (Var("x"), Event("alpha"), If (Var("x"), App(Var("z"), App(Var("z"),Event("beta")) ), Frame("phi",App(Var("z"),Var("x")))))) in let expr = Frame("rho",App(
Abs ("z","x", If(Var("x"),Event("alpha"),App(Var("z"), App(Var("z"),Event("beta")))) ),Event("gamma")) ) in
let s = evaluate_to_string expr 0 NEmpty in print_string(s);;*)
main;;
(*historyChecker.mli*)
(** File principale del progetto. Contiene le funzioni di conversione e la funzione di controllo *) open MiscFun open Automata open Grammar open GrammarBase open Memories open Bpa open Evaluator open History
(** Politiche etichettate: necessarie per associare gli automi alle specifiche politiche.*)
type labelledPolicy = policy * nfa
(** Converte una history expression in un processo BPA*) val his2bpa : heffect -> int -> bpa
(** Converte un processo BPA in una CFG in CNF*) val bpa2cfg : bpa -> int -> grammar
(** Converte una CFG in GNF in un PDA (accettazione per pila vuota)*) val cfg2pda : grammar -> int -> pda
(** Converte un PDA (accettazione per pila vuota) in una CFG*) val pda2cfg : pda -> int -> grammar
(** Confronta una history expression con un NFA*)
val check : heffect -> labelledPolicy list -> bool -> int -> plan list (** Converte una lista di piani in una stringa*)
(*historyChecker.ml*) open MiscFun open Automata open Grammar open GrammarBase open Memories open Bpa open History open Evaluator
(*Converte una lista di piani in una stringa*) let rec planlist_to_string pl = match pl with
p::tail -> (plan_to_string p)^"\n"^planlist_to_string tail |[] -> "";;
(*Conversion: from History to BPA *)
let his2bpa (his:heffect) (verbose:int):bpa = if (verbose>0)
then print_string "Converting History Expression into BPA process..."; if (verbose>2)
then print_string ("\nInitial Heffect: "^(heffect_to_string his) ^"\n");
let g = new gamma in
let rec h2b curHis = match curHis with Epsilon -> (BPAEpsilon,Delta.empty) | HEvent(a) -> (BPAEvent(a),Delta.empty) | HVar(l) -> (try
(BPAVar(g#get(l)),Delta.empty)
with Not_found -> (BPAVar(String.uppercase l),Delta.empty))
| Seq(h1,h2) -> let bpa1 = h2b h1 in let bpa2 = h2b h2 in (match (bpa1,bpa2) with ((p1,d1),(p2,d2)) -> (BPASeq (p1,p2),Delta.union d1 d2))
| Choice(h1,h2) -> let bpa1 = h2b h1 in let bpa2 = h2b h2 in (match (bpa1,bpa2) with ((p1,d1),(p2,d2)) -> (BPAChoice (p1,p2),Delta.union d1 d2))
| HFrame(p,h) -> h2b (Seq(Seq(HEvent("o-"^p),h),HEvent("c-"^p))) | HLoc(l,h) -> raise NoMoreLocsAtThisPoint (*A questo punto, la history doveva avere gia' le location separate.*)
| Mu(l,h) -> (let bl = String.uppercase l in g#add l bl;
let de = h2b h in
match de with (p,d) -> (BPAVar(bl),Delta.union d (Delta.singleton (bl,p))))
| PSel(p) -> raise NoMorePlanAtThisPoint in (*La history doveva essere linearizzata prima*)
let result = h2b his in if (verbose>1)
then print_string("\nResulting BPA: \n\n"^(bpa_to_string result)); if (verbose>0)
then print_string "done!\n\n"; result;;
(*Conversion: from BPA to CFG*)
let bpa2cfg (b:bpa) (verbose:int):grammar = if (verbose>0)
then print_string "Converting BPA process into CFG grammar (CNF)..."; match b with (process,delta) ->
let mem = new labelMemory in
(*Primo scan del BPA, per cercare tutti i nomi di variabili usati*) (let rec scanForLabels p = match p with
BPAEpsilon -> skip
| BPAEvent(a) -> mem#addT a | BPAVar(l) -> mem#addNT l
| BPASeq(p1,p2) -> scanForLabels p1;scanForLabels p2
| BPAChoice(p1,p2) -> scanForLabels p1;scanForLabels p2 in scanForLabels process; (*Vengono cercate tutte le label nel processo*)
let rec labelsInDelta d = match d with
(lab,proc)::tail -> scanForLabels proc;labelsInDelta tail
| [] -> skip in
labelsInDelta (Delta.elements delta)); if (verbose>1)
then
(print_string "\nT set: ";print_stringlist (Tset.elements mem#getTSet);
print_string "\nNT set: ";print_stringlist (NTset.elements mem#getNTSet););
let rec convertProcess (p:bpaProcess) (currSymb:NTset.elt) = match p with
BPAEpsilon -> Pset.singleton (currSymb,GEpsilon)
| BPAEvent(a) -> Pset.singleton (currSymb,T(a,GEpsilon)) | BPAVar(l) -> Pset.singleton (currSymb, NT(l,GEpsilon)) | BPASeq(p1,p2) ->
let nt1 = mem#freshNT in let nt2 = mem#freshNT in
Pset.add (currSymb,NT(nt1,NT(nt2,GEpsilon)))
(Pset.union (convertProcess p1 nt1) (convertProcess p2 nt2)) | BPAChoice(p1,p2) -> let nt1 = mem#freshNT in let nt2 = mem#freshNT in Pset.add (currSymb,NT(nt1,GEpsilon)) (Pset.add (currSymb,NT(nt2,GEpsilon))
(Pset.union (convertProcess p1 nt1) (convertProcess p2 nt2))) in
let rec convertDelta d = match d with
(lab,proc)::tail -> Pset.union (convertProcess proc lab) (convertDelta tail)
|[] -> Pset.empty in let starting = mem#freshNT in
let prod = Pset.union (convertProcess process starting) (convertDelta (Delta.elements delta)) in
let result = (mem#getNTSet,mem#getTSet,prod,starting) in if (verbose>1)
then (print_string "\nResulting Grammar: \n"; print_grammar result;print_string "\n";);
if (verbose>0)
then print_string "done!\n\n"; result;;
let cfg2pda (cfg:grammar) (verbose:int):pda = if (verbose>0)
then print_string "Converting CFG into PDA..."; if (verbose>2)
then (print_string "Initial CFG:\n";print_grammar cfg;); match cfg with (v,t,p,s) ->
let q = 0 in
let prodList = Pset.elements p in let rec rightTostack r = match r with GEpsilon -> []
| T(a,tail) -> a::(rightTostack tail) | NT(a,tail) -> a::(rightTostack tail) in
let convertNTset v =
let rec innerConvert vList = match vList with s::tail -> Sset.add s (innerConvert tail) | [] -> Sset.empty in
innerConvert (NTset.elements v) in let convertTset v =
let rec innerConvert vList = match vList with s::tail -> Sset.add s (innerConvert tail) | [] -> Sset.empty in
innerConvert (Tset.elements v) in
let rec generateDelta pList = match pList with
(l,T(a,gamma))::tail -> (q,a,l,q,(rightTostack gamma)):: (generateDelta tail)
| (l,r)::tail -> generateDelta tail | [] -> [] in
let delta = generateDelta prodList in
let pda = ((Qset.singleton q),(convertTset t),(convertNTset v), delta, q, s, Qset.empty) in
if (verbose>1)
then (print_string "\nGenerated PDA: \n";print_pda pda;); if (verbose>0)
then print_string "done!\n\n"; pda;;
let pda2cfg (pda) (verbose:int):grammar = if (verbose>0)
then print_string "Converting PDA into CFG..."; if (verbose>2)
then (print_string "Initial PDA:\n";print_pda pda;print_string "\n"); let table = new pdaAss in
match pda with (q,alpha,stack,delta,q0,s0,final) -> let s = "S" in
(*table#buildTab;*)
let prod = (s,NT(table#getByQ (q0,s0,(Qset.choose final)),GEpsilon)) in
if (verbose >1)
then (print_prods [prod];); table#addProd prod;
let guard deltaEntry = match deltaEntry with (q,sy,st,p,ststr) when ststr = [] -> true |(q,sy,st,p,ststr) -> false in
let partition = List.partition guard delta in match partition with
(withEpsilon,withoutEpsilon)->
let rec addEpsilon pr = match pr with (q,sy,st,p,ststr)::tail ->
if (String.compare sy "" != 0)
then (let prod = (table#getByQ(q,st,p),T (sy,GEpsilon)) in
if (verbose>1)
then (print_prods [prod];); table#addProd prod;addEpsilon tail;)
else (let prod = (table#getByQ (q,st,p),GEpsilon) in
if (verbose>1)
then (print_prods [prod];); table#addProd prod;addEpsilon tail;)
|[] -> skip; in if(verbose>1)
then (print_string "\nWith Empty Stack:\n";); addEpsilon withEpsilon;
let rec addWOEpsilon pr = match pr with (q1,sy,st,p,ststr)::tail ->
let stLen = List.length ststr in if (verbose>1)
then (print_string "Current Converting Transition ";print_PDAtrans (q1,sy,st,p,ststr););
let permTab = permutate (Qset.elements q) stLen in
let rec scanPerm perm = match perm with currStat::tail ->
let stackn i = List.nth ststr i in
let statn i = List.nth currStat i in
let currLen = List.length currStat in
let rec genRight i = if i = stLen then GEpsilon else
if i = 0 then NT (table#getByQ(p,stackn i,statn i),genRight (i+1))
else NT (table#getByQ(statn (i-1),stackn i, statn i),genRight (i+1)) in
if (String.compare sy "" != 0) then (let prod =
(
table#getByQ (q1,st,List.nth currStat (currLen-1)),
T(sy,genRight 0) ) in if (verbose>1) then (print_prods [prod];); table#addProd prod;)
else (let prod = (
table#getByQ (q1,st,List.nth currStat (currLen-1)),
(genRight 0) ) in
if (verbose>1) then (print_prods [prod];); table#addProd prod; ); scanPerm tail; |[] -> skip in scanPerm permTab; addWOEpsilon tail; |[] -> skip in addWOEpsilon withoutEpsilon;
let rec convertAlpha aList = match aList with s::tail -> Tset.add s (convertAlpha tail) | [] -> Tset.empty in
let t = convertAlpha(Sset.elements alpha) in let prod = table#getProd in
let g = (table#getV,t,prod,s) in if (verbose>1)
then (print_string "Symb"; table#printConversion;
print_string "Pruning unuseful productions:";); let useful = usefulSymbols g 0 in
let rec purgeUnuseful pList =
let rec hasAllUseful right = match right with GEpsilon -> true
| T(_,r) -> hasAllUseful r
| NT(s,r) when (NTset.mem s useful) -> hasAllUseful r | NT(_,_) -> false in
match pList with
(left,right)::tail when (NTset.mem left useful) && hasAllUseful right -> Pset.add (left,right) (purgeUnuseful tail) | (left,right)::tail -> purgeUnuseful tail
| [] -> Pset.empty in
let prod = purgeUnuseful (Pset.elements prod) in let g = (NTset.add s table#getV,t,prod,s) in if (verbose>1)
then (print_string "Resulting grammar:\n"; print_grammar g;);
if (verbose>0)
then print_string "done!\n\n"; g;;
type labelledPolicy = policy * nfa;;
let check (his:heffect) (policies:labelledPolicy list) (local:bool) (verbose:int) =
let rec convert polList = match polList with (label,pol)::tail ->
let result = (label,negateDFA (nfa2dfa framed verbose) verbose) in
result::(convert tail) |[] -> [] in
let policies = convert policies in
let linearized = linearization his verbose in let getSelection h = match h with
PSel(p) -> p
|_ -> raise NotWellLinearized in let p = getSelection linearized in
let rec viablePlans plans = match plans with (pl,hisInPlan)::tailPlan ->(*[pl]*)
let locations =
if local
then separateLocations hisInPlan verbose else [(0,purgeLocations hisInPlan verbose)] in let rec checkHistories locs = match locs with
(loc,currHis)::tailLocs ->
let policiesInHis = getPolicies currHis in if (Rhoset.is_empty policiesInHis)
then (checkHistories tailLocs)
else
(let regolarized = regolarize currHis verbose in
let renamed = renameVars regolarized verbose in
let bpa = his2bpa renamed verbose in let cfg = bpa2cfg bpa verbose in let cleared = clear cfg verbose in let cnf = chomsky cleared verbose in
let gnf = greibach cnf verbose in
let clearedPostGnf = clear gnf verbose in let pda = cfg2pda clearedPostGnf verbose in
let pdaByFinal = acceptanceByFinal pda verbose in
let rec checkPol polList = match polList with
(polLabel,currPol)::tailPol when Rhoset.mem polLabel policiesInHis ->
let con = conjunct currPol pdaByFinal verbose in
let finalCFG = pda2cfg con verbose in
let finalCleared = clear finalCFG verbose in
if(cfg_is_empty finalCleared verbose)
then checkPol tailPol
else
(if (verbose>0) then (print_string ("\nPlan ("^(plan_to_string pl)^") doesn't respect "^polLabel^" at location ");print_int loc;print_string (".A possible violation is: "^rightToString (getString finalCleared)^"\n\n\n"););
viablePlans tailPlan) |(polLabel,currPol)::tailPol -> checkPol tailPol
| [] -> if (verbose>0)
then (print_string "\nAll Policies Respected in Location ";print_int loc;print_string "\n";);
checkHistories tailLocs in checkPol policies)
|[] -> if (verbose>0)
then (print_string ("\nAll Policies Respected in All Location By Plan "^(plan_to_string pl)^"\n\n\n"););
pl::(viablePlans tailPlan) in checkHistories locations
| [] -> [] in
let viable = viablePlans p in viable
;;
(*
let rho:nfa =
let trans = (1,"alpha",1)::(1,"beta",2)::(2,"alpha",3)::(2,"beta",2):: (3,"alpha",3)::(3,"beta",3)::[] in
(Qset.add 1 (Qset.add 2 (Qset.singleton 3)),Sset.add "alpha" (Sset.add "beta" Sset.empty),trans,1,Qset.add 2 (Qset.singleton 1));;
let phi =
let trans = (1,"alpha",1)::(1,"beta",2)::(1,"gamma",1)::(2,"beta",2):: (2,"alpha",1)::(2,"gamma",3)::(3,"alpha",3)::(3,"beta",3)::
(3,"gamma",3)::[] in
(Qset.add 1 (Qset.add 3 (Qset.singleton 2)),Sset.add "alpha" (Sset.add "beta" (Sset.singleton "gamma" )), trans, 1, Qset.add 1 (Qset.singleton 2));;
let hisFail = Mu("h",Choice(Choice(HEvent("alpha"),Seq(Seq(HEvent ("beta"),HVar("h")),HVar("h"))),HFrame("rho",HVar("h"))));;
let hisWork = HFrame("phi",Seq(Mu("h",Choice(Choice(HEvent("alpha"),Seq (Seq(HEvent("beta"),HVar("h")),HVar("h"))),HVar("h"))),HEvent
("gamma")));;
let his = PSel([(SChoice("Fail",0,Empty),hisFail);(SChoice ("Work",1,Empty),hisWork)]) in
print_string ("Initial :"^(heffect_to_string his)^"\n"); let final = (check his [("rho",rho);("phi",phi)] true 2 ) in skip;;(* in
print_string ("Final :"^(planlist_to_string (final)^"\n");*) *)
(*automata.mli*)
(** Definizioni e funzioni su automi.*)
(** Gestisce le operazioni effettuabili su DFA, NFA e PDA. *) open MiscFun
open Memories type q = Qset.t
type alphabet = Sset.t
(** Una entry della relazione di transizione di DFA e NFA: Stato iniziale, simbolo in input, stato finale*)
type automataTrans = (Qset.elt * Sset.elt * Qset.elt)
(** Una entry della relazione di transizione di un PDA:
Stato iniziale, simbolo in input, simbolo sul top della pila, stato finale, stringa da rimpiazzare al top*)
type pdaTrans = Qset.elt * Sset.elt * Sset.elt * Qset.elt * Sset.elt list
(** Definizione di PDA: Iniseme degli stati, Alfabeto di input, Alfabeto dello stack, Relazione di transizione, stato iniziale, stack iniziale, stati finali*)
type pda = q * alphabet * alphabet * pdaTrans list * int * Sset.elt * q (** Definizione di DFA: Insieme degli stati, Alfabeto di input, Funzione di transizione, Stato iniziale, Stati finali*)
type dfa = q * alphabet * automataTrans list * Qset.elt * q (** Definizione di NFA: Insieme degli stati, Alfabeto di input, Relazione di transizione, Stato iniziale, Stati finali*)
type nfa = q * alphabet * automataTrans list * Qset.elt * q
(** Stato di fallimento: utilizzato per segnalare una transizione non presente nell'automa.*)
val failstatus : int
(** Fornendo una relazione di transizione, lo stato iniziale ed il simbolo, fornisce lo stato finale*)
val findDFA : automataTrans list -> Qset.elt -> Sset.elt -> Qset.elt (** Fornendo una relazione di transizione, lo stato iniziale ed il simbolo, fornisce l'insieme degli stati finali*)
val findNFA : ('a * 'b * Qset.elt) list -> 'a -> 'b -> q
(** Fornendo una relazione di transizione, lo stato iniziale, il simbolo di input ed il simbolo al top dello stack
rende l'insieme delle coppie (stato finale, stringa da sostituire)*) val findPDA :
pdaTrans list ->
Qset.elt -> Sset.elt -> Sset.elt -> (Qset.elt * Sset.elt list) list (** Stampa a video una entry della relazione di transizione (PDA)*) val print_PDAtrans : pdaTrans -> unit
(** Stampa a video una entry della relazione di transizione (DFA&NFA)*) val print_trans : automataTrans -> unit
(** Stampa a video un PDA*) val print_pda : pda -> unit
(** Stampa a video un DFA*) val print_dfa : dfa -> unit (** Stampa a video un NFA*) val print_nfa : nfa -> unit
(** Trasforma un PDA che accetta con condizione di pila vuota in un PDA che accetta con condizione di stato finale*)
val acceptanceByFinal : pda -> int -> pda
(** Trasforma un PDA che accetta con condizione di stato finale in unPDA che acceta con condizione di pila vuota*)
val acceptanceByEmpty : pda -> int -> pda (** Trasforma un NFA in un DFA*)
val nfa2dfa : nfa -> int -> dfa
(** Rende un DFA che accetta le sequenze di caratteri che quello fornito come parametro rifiuta, e viceversa.*)
val negateDFA : dfa -> int -> dfa
(** Rende un PDA che accetta una sequenza di caratteri accettata sia dal PDA che dal DFA forniti*)
val conjunct : dfa -> pda -> int -> pda
(** Data una politica di sicurezza, la trasforma nella versione framed corrispondente.*)
(*automata.ml*)
open MiscFun open Memories type q = Qset.t
type alphabet = Sset.t
type automataTrans = (Qset.elt * Sset.elt * Qset.elt)
type pdaTrans = Qset.elt * Sset.elt * Sset.elt * Qset.elt * Sset.elt list
type pda = q * alphabet * alphabet * pdaTrans list * int * Sset.elt * q type dfa = q * alphabet * automataTrans list * Qset.elt * q
type nfa = q * alphabet * automataTrans list * Qset.elt * q
let failstatus = -1 (*Automata definitions*)
(* fornisco funzione di trasnsizione, stato e simbolo e rende stato finale*)
let rec findDFA (trans:automataTrans list) status symbol = match trans with
(s1,sy,s2)::tail -> if ((s1 = status) & (sy = symbol)) then s2
else findDFA tail status symbol | [] -> failstatus
(* fornisco funzione di trasnsizione, stato e simbolo e rende un insieme di stati finali*)
let rec findNFA trans status symbol :q = match trans with
(s1,sy,s2)::tail -> if ((s1 = status) & (sy = symbol)) then Qset.add s2 (findNFA tail status symbol)
else findNFA tail status symbol | [] -> Qset.empty
(*PDA*)
(*PDATrans: stato iniziale,top stack,simbolo letto, stato finale, stringa da sostituire al top*)
(* fornisco funzione di transizione, stato, stack e simbolo e rende una coppia (stato*stack) *)
let rec findPDA (trans:pdaTrans list) status stack symbol = match trans with
(s1,sy,st,s2,stackstring)::tail -> if ((status = s1) & (symbol = sy) & (stack = st))
then (s2,stackstring)::(findPDA tail status stack symbol) else findPDA tail status stack symbol
| [] -> []
(q,sy,st,p,ststr) -> print_string "d("; print_int q; print_string (", "^sy^", "^st^") -> ("); print_int p; print_string ", "; print_stringlist ststr; print_string ")\n"
let print_trans (deltaEntry:automataTrans) = match deltaEntry with (q,sy,p) -> print_string "d("; print_int q; print_string (", "^sy^") -> ("); print_int p; print_string ")\n" let print_pda (pda:pda) = match pda with
(q,sigma, stack,delta,initialQ,initialStack,final) ->
print_string "Q: "; print_intlist (Qset.elements q);print_string ("\n"); print_string "Sigma: "; print_stringlist (Sset.elements
sigma);print_string ("\n");
print_string "Stack: "; print_stringlist (Sset.elements stack);print_string ("\n");
print_string "Delta: \n";
for i=0 to (List.length delta)-1 do print_PDAtrans (List.nth delta i); done;
print_string "Q0: "; print_int initialQ;print_string ("\n"); print_string ("Z0: "^initialStack);print_string ("\n");
print_string "Final set status: "; print_intlist (Qset.elements final); print_string ("\n")
let print_nfa (automata) = match automata with (q,sigma,delta,initialQ,final) ->
print_string "Q: "; print_intlist (Qset.elements q);print_string ("\n"); print_string "Sigma: "; print_stringlist (Sset.elements
sigma);print_string ("\n"); print_string "Delta (NFA): \n"; for i=0 to (List.length delta)-1 do print_trans (List.nth delta i); done;
print_string "Q0: "; print_int initialQ;print_string ("\n");
print_string "Final set status: "; print_intlist (Qset.elements final); print_string ("\n")
let print_dfa (automata) = match automata with (q,sigma,delta,initialQ,final) ->
print_string "Q: "; print_intlist (Qset.elements q);print_string ("\n"); print_string "Sigma: "; print_stringlist (Sset.elements
sigma);print_string ("\n"); print_string "Delta (DFA): \n"; for i=0 to (List.length delta)-1 do print_trans (List.nth delta i); done;
print_string "Q0: "; print_int initialQ;print_string ("\n");
print_string "Final set status: "; print_intlist (Qset.elements final); print_string ("\n")
(*Trasforma un PDA che accetta per pila vuota e lo rende per stato finale*)
let acceptanceByFinal (pda:pda) (verbose:int):pda = if verbose>0
then print_string "Converting PDA (acceptance by Empty Stack) in PDA (acceptance by Final Status)...";
if verbose>1
then (print_string "\nInitial PDA: ";print_pda pda;); match pda with
(q,symb,st,delta,init,initSt,final) -> let q01 = freshint q in
let qf = freshint (Qset.add q01 q) in let x0 = "!inital!" in
let deltaEntry1 = (q01,"",x0,init,[initSt;x0]) in let rec genDeltaEntry3 qList = match qList with
n::tail -> (n,"",x0,qf,[])::(genDeltaEntry3 tail) | [] -> [] in
let newDelta = deltaEntry1::(List.append delta (genDeltaEntry3 (Qset.elements q))) in
let finalPDA = (Qset.add qf (Qset.add q01 q), (Sset.add "" symb),Sset.add x0 st, newDelta, q01,x0,Qset.singleton qf) in if verbose>1
then (print_string "\nResulting PDA: ";print_pda finalPDA;); if verbose >0
then print_string "done!\n\n"; finalPDA
let acceptanceByEmpty (pda:pda) (verbose:int):pda = if verbose>0
then print_string "Converting PDA (acceptance by Final Status) in PDA (acceptance by Empty Stack)...";
if verbose>1
then (print_string "\nInitial PDA: ";print_pda pda;);
match pda with
(q,symb,st,delta,init,initSt,final) -> let q01 = freshint q in
let qe = freshint (Qset.add q01 q) in let x0 = "#inital#" in
let finalStack = Sset.add x0 st in
let stackList = Sset.elements finalStack in
let deltaEntry1 = (q01,"",x0,init,[initSt;x0]) in let rec genDeltaEntry3 qList = match qList with n::tail ->
let rec scanForStack sList = match sList with s::tail -> (n,"",s,qe,[])::scanForStack tail | [] -> [] in
List.append (scanForStack stackList) (genDeltaEntry3 tail) | [] -> [] in
let rec genDeltaEntry4 sList = match sList with
s::tail -> (qe,"",s,qe,[])::(genDeltaEntry4 tail) | [] -> [] in
let deltaEntry3 = genDeltaEntry3 (Qset.elements final) in let deltaEntry4 = genDeltaEntry4 (stackList) in
let newDelta = deltaEntry1::(List.append delta (List.append deltaEntry3 deltaEntry4)) in
let finalPDA = (Qset.add qe (Qset.add q01 q),(Sset.add "" symb),finalStack,newDelta,q01,x0,Qset.empty) in
if verbose>1
then (print_string "\nResulting PDA: ";print_pda finalPDA;); if verbose >0
then print_string "done!\n\n"; finalPDA
(*Aggiunge un insieme di caratteri al DFA fornito, in modo che questi vengano sempre accettati*)
let expandDFA (automata:dfa) (alpha:alphabet):dfa = match automata with (q,s,t,q0,f) ->
let extension = Sset.diff alpha s in let extList = Sset.elements extension in let statList = Qset.elements q in
let rec applyExtension e = match e with
symb::tail ->
let rec applyOnSingleStatus statList = match statList with
p::tail -> (p,symb,p):: (applyOnSingleStatus tail)
| [] -> [] in
List.append (applyOnSingleStatus statList) (applyExtension tail)
| [] -> [] in
let extended = List.append t (applyExtension extList) in (q,(Sset.union s extension), extended, q0,f);;
let nfa2dfa (autom:nfa) (verbose:int):dfa = if (verbose>0)
then print_string "Converting NFA in DFA..."; if (verbose>2)
then (print_string "\nInitial NFA: \n"; print_nfa autom;); match autom with (q,s,d,q0,f) ->
let sigma = Sset.elements s in let t = new associativa in
let rec foo (daEsaminare:QSset.t) (esaminati:QSset.t) = if(QSset.is_empty daEsaminare)
then [] else
let stato = QSset.choose daEsaminare in let index = t#get stato in
let statList = Qset.elements stato in let newtrans =
let rec scanStat sym qList = match qList with
q::tail -> Qset.union (findNFA d q sym) (scanStat sym tail) | [] -> Qset.empty in
let rec scanSym symList = match symList with s::tail -> let p = scanStat s statList in if (Qset.is_empty p)
then scanSym tail
else (index,s,t#get p)::(scanSym tail) | [] -> [] in
scanSym sigma in
let rec getGenStatus l = match l with
(_,_,p)::tail -> QSset.add (t#reverse p) (getGenStatus tail) | [] -> QSset.empty in
let generated = getGenStatus newtrans in
let newEsaminati = QSset.add stato esaminati in
List.append newtrans (foo (QSset.diff (QSset.union daEsaminare generated) newEsaminati) newEsaminati) in
let d1 = foo (QSset.singleton (Qset.singleton q0)) (QSset.empty) in
