package dolmen
Source file view.ml
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251(* This file is free software, part of dolmen. See file "LICENSE" for more information *) (** {2 First-order View} *) module Sexpr = struct (** This explicits a view of untyped terms as first-order terms/formulas *) type _ view = | Symbol : 'id -> < id : 'id; .. > view | App : 'term list -> < term : 'term; .. > view module type S = sig type t type id exception Not_an_sexpr of t val view : t -> < id : id; term : t; > view end end (** {2 First-order View} *) module TFF = struct (** This explicits a view of terms as polymorphic first-order types and terms. In strict first-order, the distinction between types and terms is clear and useful enough that the view distinguishes the two. *) module Sig = struct type _ view = | Signature : 'ty_var list * 'ty list * 'ty -> < ty_var : 'ty_var; ty : 'ty; .. > view (** Function signature *) (** View of type signatures. *) end module Ty = struct type _ view = | Var : 'ty_var -> < ty_var : 'ty_var; .. > view (**) | App : 'ty_cst * 'ty list -> < ty_cst : 'ty_cst; builtin : 'blt; ty : 'ty; .. > view (**) (** View of types in first-order. In first-order, types, which include basically variables and application of type constructors to types, are differentiated from type signatures, which include function types. *) end module TypeDef = struct type _ algebraic_case = | Case : { constructor : 'term_cst; params : ('ty * 'term_cst) list; } -> < ty : 'ty; term_cst : 'term_cst > algebraic_case type _ view = | Abstract : _ view | Algebraic : { vars : 'ty_var list; cases : < term_cst : 'term_cst; ty : 'ty; > algebraic_case list; } -> < ty : 'ty; ty_var : 'ty_var; term_cst : 'term_cst; > view end module Term = struct type _ binder = | Exists : { type_vars : 'ty_var list; term_vars : 'term_var list; triggers : 'term list; } -> < ty_var : 'ty_var; term_var : 'term_var; term : 'term; .. > binder (** Existancial quantification *) | Forall : { type_vars : 'ty_var list; term_vars : 'term_var list; triggers : 'term list; } -> < ty_var : 'ty_var; term_var : 'term_var; term : 'term; .. > binder (** Universal quantification *) | Letin : ('term_var * 'term) list -> < term_var : 'term_var; term : 'term; .. > binder (** Sequential Let bindings *) | Letand : ('term_var * 'term) list -> < term_var : 'term_var; term : 'term; .. > binder (** Parallel Let bindings *) | Map : 'term_var list -> < term_var : 'term_var; .. > binder (** Maps: encoding of higher-order functions in first-order. *) (** First-order binders that can occur in terms. *) type _ pattern = | Var : 'term_var -> < term_var : 'term_var; .. > pattern | Constructor : 'term_cst * 'term_var list -> < term_var : 'term_var; term_cst : 'term_cst; .. > pattern (**) (** First-order patterns. *) type _ view = | Var : 'term_var -> < term_var : 'term_var; .. > view (** Term Variables*) | App : 'term_cst * 'ty list * 'term list -> < ty : 'ty; term : 'term; term_cst : 'term_cst; builtin : 'blt; .. > view (** Polymorphic application of a function symbol, with explicit type arguments *) | Match : 'term * ('t pattern * 'term) list -> (< term_var : 'term_var; term_cst : 'term_cst; term : 'term; .. > as 't) view (** Pattern matching. *) | Binder : < ty_var : 'ty_var; term_var : 'term_var; term : 'term; .. > binder * 'term -> < ty_var : 'ty_var; term_var : 'term_var; term : 'term; .. > view (** Binders over a body term. *) (** View of terms in first-order. *) end (* Aliases to avoid shadowing in the module type S below *) module Vty = Ty module VT = Term (** The signature for a module that provides a first-order view of terms and types. *) module type S = sig type ty type ty_var type ty_cst type ty_def type term type term_var type term_cst type builtin = < ty : ty; ty_var : ty_var; ty_cst : ty_cst; term : term; term_var : term_var; term_cst : term_cst; > Builtin.t (** builtin symbols *) module Ty : sig type t = ty module Var : sig type t = ty_var val equal : t -> t -> bool end module Cst : sig type t = ty_cst val arity : t -> int val builtin : t -> builtin end module Def : sig type t = ty_def val view : expand:bool -> t -> < ty : ty; ty_var : ty_var; term_cst : term_cst > TypeDef.view end exception Not_first_order of t (** exceptions raised by view functions on types that cannot be represented as first-order. *) val view : expand:bool -> t -> < ty_var : Var.t; ty_cst : Cst.t; builtin : builtin; ty : t; .. > Ty.view (** View function for types. @raise Not_first_order_ty if the type cannot be viewed as first-order. *) end module Sig : sig type t val view : expand:bool -> t -> < ty_var : Ty.Var.t; ty : Ty.t; .. > Sig.view end module Term : sig type t = term val equal : t -> t -> bool module Var : sig type t = term_var val ty : t -> Ty.t val equal : t -> t -> bool end module Cst : sig type t = term_cst val ty : t -> Sig.t val builtin : t -> builtin val hash : t -> int val equal : t -> t -> bool end exception Not_first_order of t (** exceptions raised by view functions on terms that cannot be represented as first-order. *) val ty : t -> Ty.t (** Return the type of a term. *) val view : t -> < ty_var: Ty.Var.t; term_var: Var.t; term_cst : Cst.t; builtin : builtin; ty : Ty.t; term : t; .. > Term.view (** View function for terms. @raise Not_first_order_term if the term cannot be viewed as first-order. *) end end end