encoding_explicit.ml 6.26 KB
Newer Older
1 2
(**************************************************************************)
(*                                                                        *)
3
(*  Copyright (C) 2010-2011                                               *)
MARCHE Claude's avatar
MARCHE Claude committed
4 5 6
(*    François Bobot                                                     *)
(*    Jean-Christophe Filliâtre                                          *)
(*    Claude Marché                                                      *)
7 8 9 10 11 12 13 14 15 16 17 18 19
(*    Andrei Paskevich                                                    *)
(*                                                                        *)
(*  This software is free software; you can redistribute it and/or        *)
(*  modify it under the terms of the GNU Library General Public           *)
(*  License version 2.1, with the special exception on linking            *)
(*  described in file LICENSE.                                            *)
(*                                                                        *)
(*  This software is distributed in the hope that it will be useful,      *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
(*                                                                        *)
(**************************************************************************)

Francois Bobot's avatar
Francois Bobot committed
20
(** transformation from polymorphic logic to untyped logic. The polymorphic
21 22 23
logic must not have finite support types. *)


24 25 26 27 28 29
open Util
open Ident
open Ty
open Term
open Decl
open Task
30
open Libencoding
31

32 33 34 35 36
(** module with printing functions *)
module Debug = struct
  let print_mtv vprinter fmter m =
    Mtv.iter (fun key value -> Format.fprintf fmter "@[%a@] -> @[%a@]@."
      Pretty.print_tv key vprinter value) m
Simon Cruanes's avatar
Simon Cruanes committed
37

38 39 40
  (** utility to print a list of items *)
  let rec print_list printer fmter = function
    | [] -> Format.fprintf fmter ""
41 42 43 44 45
    | e::es ->
      if es = [] then
        Format.fprintf fmter "@[%a@] %a" printer e (print_list printer) es
      else
        Format.fprintf fmter "@[%a@], %a" printer e (print_list printer) es
46 47 48

  let debug x = Format.eprintf "%s@." x
end
49

Simon Cruanes's avatar
Simon Cruanes committed
50 51
(** {2 module to separate utilities from important functions} *)

52 53
module Transform = struct

54 55
  (** creates a new logic symbol, with a different type if the
  given symbol was polymorphic *)
56
  let findL = Wls.memoize 63 (fun lsymbol ->
57
    if ls_equal lsymbol ps_equ then lsymbol else
58
    let new_ty = ls_ty_freevars lsymbol in
59
    (* as many t as type vars *)
60
    if Stv.is_empty new_ty then lsymbol (* same type *) else
61
      let add _ acc = ty_type :: acc in
62
      let args = Stv.fold add new_ty lsymbol.ls_args in
63
      (* creates a new lsymbol with the same name but a different type *)
64
      Term.create_lsymbol (id_clone lsymbol.ls_name) args lsymbol.ls_value)
65

66 67 68
  (** {1 transformations} *)

  (** translation of terms *)
69
  let rec term_transform varM t = match t.t_node with
70 71
      (* first case : predicate (not =), we must translate it and its args *)
    | Tapp(f, terms) when not (ls_equal f ps_equ) ->
72
      let terms = args_transform varM f terms t.t_ty in
73
      t_app (findL f) terms t.t_ty
74
    | _ -> (* default case : traverse *)
75
      t_map (term_transform varM) t
76

77
  and args_transform varM ls args ty =
78 79 80
    (* Debug.print_list Pretty.print_ty Format.std_formatter type_vars; *)
    let tv_to_ty = ls_app_inst ls args ty in
    (* Debug.print_mtv Pretty.print_ty Format.err_formatter tv_to_ty; *)
81
    let args = List.map (term_transform varM) args in
82
    (* fresh args to be added at the beginning of the list of arguments *)
83
    let add _ ty acc = term_of_ty varM ty :: acc in
84 85
    Mtv.fold add tv_to_ty args

86
  (** transforms a list of logic declarations into another.
87 88
  Declares new lsymbols with explicit polymorphic signatures. *)
  let logic_transform decls =
89
    (* if there is a definition, we must take it into account *)
90
    let helper = function
91
    | (lsymbol, Some ldef) ->
92
      let new_lsymbol = findL lsymbol in (* new lsymbol *)
93
      let vars,expr,close = open_ls_defn_cb ldef in
94
      let add v (vl,vm) =
95
        let vs = Term.create_vsymbol (id_fresh "t") ty_type in
96
        vs :: vl, Mtv.add v (t_var vs) vm
97 98
      in
      let vars,varM = Stv.fold add (ls_ty_freevars lsymbol) (vars,Mtv.empty) in
99 100
      let t = term_transform varM expr in
      close new_lsymbol vars t
101
    | (lsymbol, None) ->
102 103 104
      (findL lsymbol, None)
    in
    [Decl.create_logic_decl (List.map helper decls)]
105

106 107
  (** transform an inductive declaration *)
  let ind_transform idl =
108
    let iconv (pr,f) = pr, Libencoding.t_type_close term_transform f in
109 110 111 112
    let conv (ls,il) = findL ls, List.map iconv il in
    [Decl.create_ind_decl (List.map conv idl)]

  (** transforms a proposition into another (mostly a substitution) *)
113
  let prop_transform (prop_kind, prop_name, f) =
114
    let quantified_fmla = Libencoding.t_type_close term_transform f in
115
    [Decl.create_prop_decl prop_kind prop_name quantified_fmla]
116

117
end
118

Simon Cruanes's avatar
Simon Cruanes committed
119 120
(** {2 main part} *)

121 122 123 124 125 126 127 128
let decl d = match d.d_node with
  | Dtype tdl -> d :: Libencoding.lsdecl_of_tydecl tdl
  | Dlogic ldl -> Transform.logic_transform ldl
  | Dind idl -> Transform.ind_transform idl
  | Dprop prop -> Transform.prop_transform prop

let explicit = Trans.decl decl (Task.add_decl None d_ts_type)

129 130 131 132 133
let meta_enum = Eliminate_algebraic.meta_enum

let explicit =
  Trans.on_tagged_ts meta_enum (fun enum ->
    if Sts.is_empty enum then explicit
134
    else
135 136 137
      let ts = Sts.choose enum in
      let ty = ty_app ts (List.map ty_var ts.ts_args) in
      Printer.unsupportedType ty
138 139 140
      "explicit is unsound in presence of type")


141 142
(** {2 monomorphise task } *)

143
open Libencoding
144

145 146
let lsmap kept = Wls.memoize 63 (fun ls ->
  let tymap ty = if Sty.mem ty kept then ty else ty_base in
147 148 149 150 151 152
  let ty_res = Util.option_map tymap ls.ls_value in
  let ty_arg = List.map tymap ls.ls_args in
  if Util.option_eq ty_equal ty_res ls.ls_value &&
     List.for_all2 ty_equal ty_arg ls.ls_args then ls
  else create_lsymbol (id_clone ls.ls_name) ty_arg ty_res)

153 154
let d_ts_base = create_ty_decl [ts_base, Tabstract]

155
let monomorph = Trans.on_tagged_ty Encoding.meta_kept (fun kept ->
François Bobot's avatar
François Bobot committed
156
  let kept = Sty.add ty_type kept in
157
  let decl = d_monomorph kept (lsmap kept) in
158 159
  Trans.decl decl (Task.add_decl None d_ts_base))

160
let () = Hashtbl.replace Encoding.ft_enco_poly "explicit"
161
    (fun _ -> Trans.compose explicit monomorph)
162