src/formula.mli

   1 (***********************************************************************)
   2 (*                                                                     *)
   3 (*                               TAToo                                 *)
   4 (*                                                                     *)
   5 (*                     Kim Nguyen, LRI UMR8623                         *)
   6 (*                   Université Paris-Sud & CNRS                       *)
   7 (*                                                                     *)
   8 (*  Copyright 2010-2012 Université Paris-Sud and Centre National de la *)
   9 (*  Recherche Scientifique. All rights reserved.  This file is         *)
  10 (*  distributed under the terms of the GNU Lesser General Public       *)
  11 (*  License, with the special exception on linking described in file   *)
  12 (*  ../LICENSE.                                                        *)
  13 (*                                                                     *)
  14 (***********************************************************************)
  15
  16 (** Implementation of hashconsed Boolean formulae *)
  17
  18 type move = [ `Left |`Right | `Self ]
  19 (** Direction for automata predicates *)
  20
  21 type 'hcons expr =
  22     False
  23     | True
  24     | Or of 'hcons * 'hcons
  25     | And of 'hcons * 'hcons
  26     | Atom of (move * bool * State.t)
  27
  28 (** Partial internal representation of a formula,
  29     used for pattern matching *)
  30
  31 type t
  32 (** Abstract type representing hashconsed formulae *)
  33
  34 val hash : t -> int
  35 (** Hash function for formulae *)
  36
  37 val uid : t -> Uid.t
  38 (** Returns a unique ID for formulae *)
  39
  40 val equal : t -> t -> bool
  41 (** Equality over formulae *)
  42
  43 val expr : t -> t expr
  44 (** Equality over formulae *)
  45
  46 val st : t -> StateSet.t * StateSet.t * StateSet.t
  47 (** States occuring self, left and right, positively or negatively *)
  48
  49 val compare : t -> t -> int
  50 (** Comparison of formulae *)
  51
  52 val size : t -> int
  53 (** Syntactic size of the formula *)
  54
  55
  56 module HcEval : sig
  57   include Sigs.HashedType
  58 end
  59 module HcInfer : sig
  60   include Sigs.HashedType
  61 end
  62 module HashEval : Hashtbl.S
  63 module HashInfer : Hashtbl.S
  64 type hcEval = bool HashEval.t
  65 type hcInfer = bool HashInfer.t
  66 (** Optimization: hconsigned eval and infer *)
  67
  68 val eval_form : (StateSet.t * StateSet.t * StateSet.t) -> t -> hcEval -> bool
  69 (** [eval_form (s,sf,sn) F] evaluates the formula [F] on [(s,sf,sn)] *)
  70
  71 val infer_form : (StateSet.t * StateSet.t) -> (StateSet.t * StateSet.t) ->
  72   (StateSet.t * StateSet.t) -> t -> hcInfer -> bool
  73 (** [eval_form S Sf Sn F] infers S; (S1,S2) |- F *)
  74
  75 val print : Format.formatter -> t -> unit
  76 (** Pretty printer *)
  77
  78 val is_true : t -> bool
  79 (** [is_true f] tests whether the formula is the atom True *)
  80
  81 val is_false : t -> bool
  82 (** [is_false f] tests whether the formula is the atom False *)
  83
  84 val true_ : t
  85 (** Atom True *)
  86
  87 val false_ : t
  88 (** Atom False *)
  89
  90 val atom_ : move -> bool -> StateSet.elt -> t
  91 (** [atom_ dir b q] creates a down_left or down_right atom for state
  92     [q]. The atom is positive if [b == true].
  93 *)
  94
  95 val not_ : t -> t
  96 val or_ : t -> t -> t
  97 val and_ : t -> t -> t
  98 (** Boolean connective *)
  99
 100 val of_bool : bool -> t
 101 (** Convert an ocaml Boolean value to a formula *)
 102
 103 module Infix : sig
 104   val ( +| ) : t -> t -> t
 105   val ( *& ) : t -> t -> t
 106   val ( *+ ) : move -> StateSet.elt -> t
 107   val ( *- ) : move -> StateSet.elt -> t
 108 end
 109 (** Module to facilitate infix notations of formulae.
 110     Just [open Formla.Infix] and write:
 111     [let f = `Left *+ q1 +| `Right *+ q2 in ...]
 112 *)