encoding_explicit.ml 6.8 KB
Newer Older
1 2
(**************************************************************************)
(*                                                                        *)
3
(*  Copyright (C) 2010-2011                                               *)
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 87
  let param_transform ls = [Decl.create_param_decl (findL ls)]

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

105 106
  (** transform an inductive declaration *)
  let ind_transform idl =
107
    let iconv (pr,f) = pr, Libencoding.t_type_close term_transform f in
108 109 110 111
    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) *)
112
  let prop_transform (prop_kind, prop_name, f) =
113
    let quantified_fmla = Libencoding.t_type_close term_transform f in
114
    [Decl.create_prop_decl prop_kind prop_name quantified_fmla]
115

116
end
117

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

120
let decl d = match d.d_node with
121 122 123 124 125 126
  | Dtype { ts_def = Some _ } -> []
  | Dtype ts -> [d; Libencoding.lsdecl_of_ts ts]
  | Ddata _ -> Printer.unsupportedDecl d
      "Algebraic and recursively-defined types are \
            not supported, run eliminate_algebraic"
  | Dparam ls -> Transform.param_transform ls
127 128 129 130 131 132
  | 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)

133
let explicit =
134 135
  Trans.on_tagged_ty Libencoding.meta_kept (fun kept ->
  Trans.on_tagged_ts Eliminate_algebraic.meta_enum (fun enum ->
Andrei Paskevich's avatar
Andrei Paskevich committed
136
    let check ts = not (ts.ts_args = [] && Sty.mem (ty_app ts []) kept) in
137
    let enum = Sts.filter check enum in
138
    if Sts.is_empty enum then explicit
139
    else
140 141 142
      let ts = Sts.choose enum in
      let ty = ty_app ts (List.map ty_var ts.ts_args) in
      Printer.unsupportedType ty
Andrei Paskevich's avatar
Andrei Paskevich committed
143
      "Encoding_explicit is unsound in presence of unprotected finite types"))
144 145


146 147
(** {2 monomorphise task } *)

148
open Libencoding
149

150
let lsmap kept = Wls.memoize 63 (fun ls ->
151 152 153 154 155 156
  let prot_arg = is_protecting_id ls.ls_name in
  let prot_val = is_protected_id ls.ls_name in
  let neg ty = if prot_arg && Sty.mem ty kept then ty else ty_base in
  let pos ty = if prot_val && Sty.mem ty kept then ty else ty_base in
  let ty_arg = List.map neg ls.ls_args in
  let ty_res = Util.option_map pos ls.ls_value in
157 158 159 160
  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)

161
let d_ts_base = create_ty_decl ts_base
162

163
let monomorph = Trans.on_tagged_ty Libencoding.meta_kept (fun kept ->
François Bobot's avatar
François Bobot committed
164
  let kept = Sty.add ty_type kept in
165
  let decl = d_monomorph kept (lsmap kept) in
166 167
  Trans.decl decl (Task.add_decl None d_ts_base))

168
let () = Hashtbl.replace Encoding.ft_enco_poly "explicit"
169
    (fun _ -> Trans.compose explicit monomorph)