components/library/cicCoercion.ml

   1 (* Copyright (C) 2005, HELM Team.
   2  *
   3  * This file is part of HELM, an Hypertextual, Electronic
   4  * Library of Mathematics, developed at the Computer Science
   5  * Department, University of Bologna, Italy.
   6  *
   7  * HELM is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation; either version 2
  10  * of the License, or (at your option) any later version.
  11  *
  12  * HELM is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with HELM; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20  * MA  02111-1307, USA.
  21  *
  22  * For details, see the HELM World-Wide-Web page,
  23  * http://helm.cs.unibo.it/
  24  *)
  25
  26 (* $Id$ *)
  27
  28 let debug = false
  29 let debug_print s = if debug then prerr_endline (Lazy.force s) else ()
  30
  31 (* given the new coercion uri from src to tgt returns the list
  32  * of new coercions to create. hte list elements are
  33  * (source, list of coercions to follow, target)
  34  *)
  35 let get_closure_coercions src tgt uri coercions =
  36   let eq_carr s t =
  37     try
  38       CoercDb.eq_carr s t
  39     with
  40     | CoercDb.EqCarrNotImplemented _ | CoercDb.EqCarrOnNonMetaClosed -> false
  41   in
  42   match src,tgt with
  43   | CoercDb.Uri _, CoercDb.Uri _ ->
  44       let c_from_tgt =
  45         List.filter
  46           (fun (f,t,_) -> eq_carr f tgt && not (eq_carr t src))
  47           coercions
  48       in
  49       let c_to_src =
  50         List.filter
  51           (fun (f,t,_) -> eq_carr t src && not (eq_carr f tgt))
  52           coercions
  53       in
  54         (HExtlib.flatten_map
  55           (fun (_,t,ul) -> List.map (fun u -> src,[uri; u],t) ul) c_from_tgt) @
  56         (HExtlib.flatten_map
  57           (fun (s,_,ul) -> List.map (fun u -> s,[u; uri],tgt) ul) c_to_src) @
  58         (HExtlib.flatten_map
  59           (fun (s,_,u1l) ->
  60             HExtlib.flatten_map
  61               (fun (_,t,u2l) ->
  62                 HExtlib.flatten_map
  63                   (fun u1 ->
  64                     List.map
  65                       (fun u2 -> (s,[u1;uri;u2],t))
  66                       u2l)
  67                   u1l)
  68               c_from_tgt)
  69           c_to_src)
  70   | _ -> [] (* do not close in case source or target is not an indty ?? *)
  71 ;;
  72
  73 let obj_attrs = [`Class `Coercion; `Generated]
  74
  75 exception UnableToCompose
  76
  77 (* generate_composite_closure (c2 (c1 s)) in the universe graph univ *)
  78 let generate_composite_closure rt c1 c2 univ =
  79   let module RT = RefinementTool in
  80   let c1_ty,univ = CicTypeChecker.type_of_aux' [] [] c1 univ in
  81   let c2_ty,univ = CicTypeChecker.type_of_aux' [] [] c2 univ in
  82   let rec mk_implicits n =
  83     match n with
  84     | 0 -> []
  85     | _ -> (Cic.Implicit None) :: mk_implicits (n-1)
  86   in
  87   let rec mk_lambda_spline c = function
  88     | 0 -> c
  89     | n ->
  90         Cic.Lambda
  91           (Cic.Name ("A" ^ string_of_int (n-1)),
  92            (Cic.Implicit None),
  93            mk_lambda_spline c (n-1))
  94   in
  95   let rec count_saturations_needed n = function
  96     | Cic.Prod (_,src, ((Cic.Prod _) as t)) -> count_saturations_needed (n+1) t
  97     | _ -> n
  98   in
  99   let compose c1 nc1 c2 nc2 =
 100     Cic.Lambda
 101       (Cic.Name "x",
 102       (Cic.Implicit None),
 103       Cic.Appl ( c2 :: mk_implicits nc2 @
 104         [ Cic.Appl ( c1 :: mk_implicits nc1 @ [Cic.Rel 1]) ]))
 105   in
 106   let order_metasenv metasenv =
 107     List.sort
 108       (fun (_,ctx1,_) (_,ctx2,_) -> List.length ctx1 - List.length ctx2)
 109       metasenv
 110   in
 111   let rec create_subst_from_metas_to_rels n = function
 112     | [] -> []
 113     | (metano, ctx, ty)::tl ->
 114         (metano,(ctx,Cic.Rel (n+1),ty)) ::
 115           create_subst_from_metas_to_rels (n-1) tl
 116   in
 117   let split_metasenv metasenv n =
 118     List.partition (fun (_,ctx,_) -> List.length ctx > n) metasenv
 119   in
 120   let purge_unused_lambdas metasenv t =
 121     let rec aux = function
 122         | Cic.Lambda (_, Cic.Meta (i,_), t) when
 123           List.exists (fun (j,_,_) -> j = i) metasenv ->
 124             aux (CicSubstitution.subst (Cic.Rel ~-100) t)
 125         | Cic.Lambda (name, s, t) ->
 126             Cic.Lambda (name, s, aux t)
 127         | t -> t
 128     in
 129     aux t
 130   in
 131   debug_print (lazy ("\nCOMPOSING"));
 132   debug_print (lazy (" c1= "^CicPp.ppterm c1 ^"  :  "^ CicPp.ppterm c1_ty));
 133   debug_print (lazy (" c2= "^CicPp.ppterm c2 ^"  :  "^ CicPp.ppterm c2_ty));
 134   let saturations_for_c1 = count_saturations_needed 0 c1_ty in
 135   let saturations_for_c2 = count_saturations_needed 0 c2_ty in
 136   let c = compose c1 saturations_for_c1 c2 saturations_for_c2 in
 137   let spline_len = saturations_for_c1 + saturations_for_c2 in
 138   let c = mk_lambda_spline c spline_len in
 139   (* debug_print (lazy ("COMPOSTA: " ^ CicPp.ppterm c)); *)
 140   let c, univ =
 141     match rt.RT.type_of_aux' [] [] c univ with
 142     | RT.Success (term, ty, metasenv, ugraph) ->
 143         debug_print(lazy("COMPOSED REFINED: "^CicPp.ppterm term));
 144         let metasenv = order_metasenv metasenv in
 145         debug_print(lazy("ORDERED MENV: "^rt.RT.ppmetasenv [] metasenv));
 146         let body_metasenv, lambdas_metasenv =
 147           split_metasenv metasenv spline_len
 148         in
 149         debug_print(lazy("B_MENV: "^rt.RT.ppmetasenv [] body_metasenv));
 150         debug_print(lazy("L_MENV: "^rt.RT.ppmetasenv [] lambdas_metasenv));
 151         let subst = create_subst_from_metas_to_rels spline_len body_metasenv in
 152         debug_print (lazy("SUBST: "^rt.RT.ppsubst subst));
 153         let term = rt.RT.apply_subst subst term in
 154         debug_print (lazy ("COMPOSED SUBSTITUTED: " ^ CicPp.ppterm term));
 155         (match rt.RT.type_of_aux' metasenv [] term ugraph with
 156         | RT.Success (term, ty, metasenv, ugraph) ->
 157             let body_metasenv, lambdas_metasenv =
 158               split_metasenv metasenv spline_len
 159             in
 160             let term = purge_unused_lambdas lambdas_metasenv term in
 161             debug_print (lazy ("COMPOSED: " ^ CicPp.ppterm term));
 162             term, ugraph
 163         | RT.Exception s -> debug_print s; raise UnableToCompose)
 164     | RT.Exception s -> debug_print s; raise UnableToCompose
 165   in
 166   let c_ty,univ =
 167     try
 168       CicTypeChecker.type_of_aux' [] [] c univ
 169     with CicTypeChecker.TypeCheckerFailure s ->
 170       debug_print (lazy (Printf.sprintf "Generated composite coercion:\n%s\n%s"
 171         (CicPp.ppterm c) (Lazy.force s)));
 172       raise UnableToCompose
 173   in
 174   let cleaned_ty =
 175     FreshNamesGenerator.clean_dummy_dependent_types c_ty
 176   in
 177   let obj = Cic.Constant ("xxxx",Some c,cleaned_ty,[],obj_attrs) in
 178     obj,univ
 179 ;;
 180
 181 (* removes from l the coercions that are in !coercions *)
 182 let filter_duplicates l coercions =
 183   List.filter (
 184       fun (src,l1,tgt) ->
 185         not (List.exists (fun (s,t,l2) ->
 186           CoercDb.eq_carr s src &&
 187           CoercDb.eq_carr t tgt &&
 188           try
 189             List.for_all2 (fun u1 u2 -> UriManager.eq u1 u2) l1 l2
 190           with
 191           | Invalid_argument "List.for_all2" -> false)
 192         coercions))
 193   l
 194
 195 let mangle s t l =
 196   (*List.fold_left
 197     (fun s x -> s ^ "_" ^ x)
 198     (s ^ "_OF_" ^ t ^ "_BY" ^ string_of_int (List.length l)) l*)
 199   s ^ "_OF_" ^ t
 200 ;;
 201
 202 exception ManglingFailed of string
 203
 204 let number_if_already_defined buri name =
 205   let rec aux n =
 206     let suffix = if n > 0 then string_of_int n else "" in
 207     let uri = buri ^ "/" ^ name ^ suffix ^ ".con" in
 208     try
 209       let _  = Http_getter.resolve ~writable:true uri in
 210       if Http_getter.exists uri then
 211         begin
 212           HLog.warn ("Uri " ^ uri ^ " already exists.");
 213           if n < 10 then aux (n+1) else
 214             raise
 215               (ManglingFailed
 216                 ("Unable to give an altenative name to " ^
 217                   buri ^ "/" ^ name ^ ".con"))
 218         end
 219       else
 220         UriManager.uri_of_string uri
 221     with
 222     | Http_getter_types.Key_not_found _ -> UriManager.uri_of_string uri
 223     | Http_getter_types.Unresolvable_URI _ -> assert false
 224   in
 225   aux 0
 226 ;;
 227
 228 (* given a new coercion uri from src to tgt returns
 229  * a list of (new coercion uri, coercion obj, universe graph)
 230  *)
 231 let close_coercion_graph rt src tgt uri =
 232   (* check if the coercion already exists *)
 233   let coercions = CoercDb.to_list () in
 234   let todo_list = get_closure_coercions src tgt uri coercions in
 235   let todo_list = filter_duplicates todo_list coercions in
 236   try
 237     let new_coercions =
 238       HExtlib.filter_map (
 239         fun (src, l , tgt) ->
 240           try
 241             (match l with
 242             | [] -> assert false
 243             | he :: tl ->
 244                 let first_step =
 245                   Cic.Constant ("",
 246                     Some (CoercDb.term_of_carr (CoercDb.Uri he)),
 247                     Cic.Sort Cic.Prop, [], obj_attrs)
 248                 in
 249                 let o,_ =
 250                   List.fold_left (fun (o,univ) coer ->
 251                     match o with
 252                     | Cic.Constant (_,Some c,_,[],_) ->
 253                           generate_composite_closure rt c
 254                             (CoercDb.term_of_carr (CoercDb.Uri coer)) univ
 255                     | _ -> assert false
 256                   ) (first_step, CicUniv.empty_ugraph) tl
 257                 in
 258                 let name_src = CoercDb.name_of_carr src in
 259                 let name_tgt = CoercDb.name_of_carr tgt in
 260                 let by = List.map UriManager.name_of_uri l in
 261                 let name = mangle name_tgt name_src by in
 262                 let buri = UriManager.buri_of_uri uri in
 263                 let c_uri = number_if_already_defined buri name in
 264                 let named_obj =
 265                   match o with
 266                   | Cic.Constant (_,bo,ty,vl,attrs) ->
 267                       Cic.Constant (name,bo,ty,vl,attrs)
 268                   | _ -> assert false
 269                 in
 270                   Some ((src,tgt,c_uri,named_obj)))
 271           with UnableToCompose -> None
 272       ) todo_list
 273     in
 274     new_coercions
 275   with ManglingFailed s -> HLog.error s; []
 276 ;;
 277