package dolmen

  1. Overview
  2. Docs

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