helm/software/components/acic_content/acic2content.ml

   1 (* Copyright (C) 2000, 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://cs.unibo.it/helm/.
  24  *)
  25
  26 (**************************************************************************)
  27 (*                                                                        *)
  28 (*                           PROJECT HELM                                 *)
  29 (*                                                                        *)
  30 (*                Andrea Asperti <asperti@cs.unibo.it>                    *)
  31 (*                             16/6/2003                                   *)
  32 (*                                                                        *)
  33 (**************************************************************************)
  34
  35 (* $Id$ *)
  36
  37 let object_prefix = "obj:";;
  38 let declaration_prefix = "decl:";;
  39 let definition_prefix = "def:";;
  40 let inductive_prefix = "ind:";;
  41 let joint_prefix = "joint:";;
  42 let proof_prefix = "proof:";;
  43 let conclude_prefix = "concl:";;
  44 let premise_prefix = "prem:";;
  45 let lemma_prefix = "lemma:";;
  46
  47 (* e se mettessi la conversione di BY nell'apply_context ? *)
  48 (* sarebbe carino avere l'invariante che la proof2pres
  49 generasse sempre prove con contesto vuoto *)
  50
  51 let gen_id prefix seed =
  52  let res = prefix ^ string_of_int !seed in
  53   incr seed ;
  54   res
  55 ;;
  56
  57 let name_of = function
  58     Cic.Anonymous -> None
  59   | Cic.Name b -> Some b;;
  60
  61 exception Not_a_proof;;
  62 exception NotImplemented;;
  63 exception NotApplicable;;
  64
  65 (* we do not care for positivity, here, that in any case is enforced by
  66    well typing. Just a brutal search *)
  67
  68 let rec occur uri =
  69   let module C = Cic in
  70   function
  71       C.Rel _ -> false
  72     | C.Var _ -> false
  73     | C.Meta _ -> false
  74     | C.Sort _ -> false
  75     | C.Implicit _ -> assert false
  76     | C.Prod (_,s,t) -> (occur uri s) or (occur uri t)
  77     | C.Cast (te,ty) -> (occur uri te)
  78     | C.Lambda (_,s,t) -> (occur uri s) or (occur uri t) (* or false ?? *)
  79     | C.LetIn (_,s,t) -> (occur uri s) or (occur uri t)
  80     | C.Appl l ->
  81         List.fold_left
  82           (fun b a ->
  83              if b then b
  84              else (occur uri a)) false l
  85     | C.Const (_,_) -> false
  86     | C.MutInd (uri1,_,_) -> if uri = uri1 then true else false
  87     | C.MutConstruct (_,_,_,_) -> false
  88     | C.MutCase _ -> false (* presuming too much?? *)
  89     | C.Fix _ -> false (* presuming too much?? *)
  90     | C.CoFix (_,_) -> false (* presuming too much?? *)
  91 ;;
  92
  93 let get_id =
  94   let module C = Cic in
  95   function
  96       C.ARel (id,_,_,_) -> id
  97     | C.AVar (id,_,_) -> id
  98     | C.AMeta (id,_,_) -> id
  99     | C.ASort (id,_) -> id
 100     | C.AImplicit _ -> raise NotImplemented
 101     | C.AProd (id,_,_,_) -> id
 102     | C.ACast (id,_,_) -> id
 103     | C.ALambda (id,_,_,_) -> id
 104     | C.ALetIn (id,_,_,_) -> id
 105     | C.AAppl (id,_) -> id
 106     | C.AConst (id,_,_) -> id
 107     | C.AMutInd (id,_,_,_) -> id
 108     | C.AMutConstruct (id,_,_,_,_) -> id
 109     | C.AMutCase (id,_,_,_,_,_) -> id
 110     | C.AFix (id,_,_) -> id
 111     | C.ACoFix (id,_,_) -> id
 112 ;;
 113
 114 let test_for_lifting ~ids_to_inner_types ~ids_to_inner_sorts=
 115   let module C = Cic in
 116   let module C2A = Cic2acic in
 117   (* atomic terms are never lifted, according to my policy *)
 118   function
 119       C.ARel (id,_,_,_) -> false
 120     | C.AVar (id,_,_) ->
 121          (try
 122             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 123             true;
 124           with Not_found -> false)
 125     | C.AMeta (id,_,_) ->
 126          (try
 127             Hashtbl.find ids_to_inner_sorts id = `Prop
 128           with Not_found -> assert false)
 129     | C.ASort (id,_) -> false
 130     | C.AImplicit _ -> raise NotImplemented
 131     | C.AProd (id,_,_,_) -> false
 132     | C.ACast (id,_,_) ->
 133          (try
 134             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 135             true;
 136           with Not_found -> false)
 137     | C.ALambda (id,_,_,_) ->
 138          (try
 139             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 140             true;
 141           with Not_found -> false)
 142     | C.ALetIn (id,_,_,_) ->
 143          (try
 144             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 145             true;
 146           with Not_found -> false)
 147     | C.AAppl (id,_) ->
 148          (try
 149             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 150             true;
 151           with Not_found -> false)
 152     | C.AConst (id,_,_) ->
 153          (try
 154             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 155             true;
 156           with Not_found -> false)
 157     | C.AMutInd (id,_,_,_) -> false
 158     | C.AMutConstruct (id,_,_,_,_) ->
 159        (try
 160             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 161             true;
 162           with Not_found -> false)
 163         (* oppure: false *)
 164     | C.AMutCase (id,_,_,_,_,_) ->
 165          (try
 166             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 167             true;
 168           with Not_found -> false)
 169     | C.AFix (id,_,_) ->
 170           (try
 171             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 172             true;
 173           with Not_found -> false)
 174     | C.ACoFix (id,_,_) ->
 175          (try
 176             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 177             true;
 178           with Not_found -> false)
 179 ;;
 180
 181 (* transform a proof p into a proof list, concatenating the last
 182 conclude element to the apply_context list, in case context is
 183 empty. Otherwise, it just returns [p] *)
 184
 185 let flat seed p =
 186  let module K = Content in
 187   if (p.K.proof_context = []) then
 188     if p.K.proof_apply_context = [] then [p]
 189     else
 190       let p1 =
 191         { p with
 192           K.proof_context = [];
 193           K.proof_apply_context = []
 194         } in
 195       p.K.proof_apply_context@[p1]
 196   else
 197     [p]
 198 ;;
 199
 200 let rec serialize seed =
 201   function
 202     [] -> []
 203   | a::l -> (flat seed a)@(serialize seed l)
 204 ;;
 205
 206 (* top_down = true if the term is a LAMBDA or a decl *)
 207 let generate_conversion seed top_down id inner_proof ~ids_to_inner_types =
 208  let module C2A = Cic2acic in
 209  let module K = Content in
 210  let exp = (try ((Hashtbl.find ids_to_inner_types id).C2A.annexpected)
 211             with Not_found -> None)
 212  in
 213  match exp with
 214      None -> inner_proof
 215    | Some expty ->
 216        if inner_proof.K.proof_conclude.K.conclude_method = "Intros+LetTac" then
 217          { K.proof_name = inner_proof.K.proof_name;
 218             K.proof_id   = gen_id proof_prefix seed;
 219             K.proof_context = [] ;
 220             K.proof_apply_context = [];
 221             K.proof_conclude =
 222               { K.conclude_id = gen_id conclude_prefix seed;
 223                 K.conclude_aref = id;
 224                 K.conclude_method = "TD_Conversion";
 225                 K.conclude_args =
 226                   [K.ArgProof {inner_proof with K.proof_name = None}];
 227                 K.conclude_conclusion = Some expty
 228               };
 229           }
 230         else
 231           { K.proof_name =  inner_proof.K.proof_name;
 232             K.proof_id   = gen_id proof_prefix seed;
 233             K.proof_context = [] ;
 234             K.proof_apply_context = [{inner_proof with K.proof_name = None}];
 235             K.proof_conclude =
 236               { K.conclude_id = gen_id conclude_prefix seed;
 237                 K.conclude_aref = id;
 238                 K.conclude_method = "BU_Conversion";
 239                 K.conclude_args =
 240                  [K.Premise
 241                   { K.premise_id = gen_id premise_prefix seed;
 242                     K.premise_xref = inner_proof.K.proof_id;
 243                     K.premise_binder = None;
 244                     K.premise_n = None
 245                   }
 246                  ];
 247                 K.conclude_conclusion = Some expty
 248               };
 249           }
 250 ;;
 251
 252 let generate_exact seed t id name ~ids_to_inner_types =
 253   let module C2A = Cic2acic in
 254   let module K = Content in
 255     { K.proof_name = name;
 256       K.proof_id   = gen_id proof_prefix seed ;
 257       K.proof_context = [] ;
 258       K.proof_apply_context = [];
 259       K.proof_conclude =
 260         { K.conclude_id = gen_id conclude_prefix seed;
 261           K.conclude_aref = id;
 262           K.conclude_method = "Exact";
 263           K.conclude_args = [K.Term t];
 264           K.conclude_conclusion =
 265               try Some (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 266               with Not_found -> None
 267         };
 268     }
 269 ;;
 270
 271 let generate_intros_let_tac seed id n s is_intro inner_proof name ~ids_to_inner_types =
 272   let module C2A = Cic2acic in
 273   let module C = Cic in
 274   let module K = Content in
 275     { K.proof_name = name;
 276       K.proof_id  = gen_id proof_prefix seed ;
 277       K.proof_context = [] ;
 278       K.proof_apply_context = [];
 279       K.proof_conclude =
 280         { K.conclude_id = gen_id conclude_prefix seed;
 281           K.conclude_aref = id;
 282           K.conclude_method = "Intros+LetTac";
 283           K.conclude_args = [K.ArgProof inner_proof];
 284           K.conclude_conclusion =
 285             try Some
 286              (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 287             with Not_found ->
 288               (match inner_proof.K.proof_conclude.K.conclude_conclusion with
 289                  None -> None
 290               | Some t ->
 291                   if is_intro then Some (C.AProd ("gen"^id,n,s,t))
 292                   else Some (C.ALetIn ("gen"^id,n,s,t)))
 293         };
 294     }
 295 ;;
 296
 297 let build_decl_item seed id n s ~ids_to_inner_sorts =
 298  let module K = Content in
 299  let sort =
 300    try
 301     Some (Hashtbl.find ids_to_inner_sorts (Cic2acic.source_id_of_id id))
 302    with Not_found -> None
 303  in
 304  match sort with
 305  | Some `Prop ->
 306     `Hypothesis
 307       { K.dec_name = name_of n;
 308         K.dec_id = gen_id declaration_prefix seed;
 309         K.dec_inductive = false;
 310         K.dec_aref = id;
 311         K.dec_type = s
 312       }
 313  | _ ->
 314     `Declaration
 315       { K.dec_name = name_of n;
 316         K.dec_id = gen_id declaration_prefix seed;
 317         K.dec_inductive = false;
 318         K.dec_aref = id;
 319         K.dec_type = s
 320       }
 321 ;;
 322
 323 let rec build_subproofs_and_args seed l ~ids_to_inner_types ~ids_to_inner_sorts =
 324   let module C = Cic in
 325   let module K = Content in
 326   let rec aux =
 327     function
 328       [] -> [],[]
 329     | t::l1 ->
 330        let subproofs,args = aux l1 in
 331         if (test_for_lifting t ~ids_to_inner_types ~ids_to_inner_sorts) then
 332           let new_subproof =
 333             acic2content
 334               seed ~name:"H" ~ids_to_inner_types ~ids_to_inner_sorts t in
 335           let new_arg =
 336             K.Premise
 337               { K.premise_id = gen_id premise_prefix seed;
 338                 K.premise_xref = new_subproof.K.proof_id;
 339                 K.premise_binder = new_subproof.K.proof_name;
 340                 K.premise_n = None
 341               } in
 342           new_subproof::subproofs,new_arg::args
 343         else
 344           let hd =
 345             (match t with
 346                C.ARel (idr,idref,n,b) ->
 347                  let sort =
 348                    (try
 349                      Hashtbl.find ids_to_inner_sorts idr
 350                     with Not_found -> `Type (CicUniv.fresh())) in
 351                  if sort = `Prop then
 352                     K.Premise
 353                       { K.premise_id = gen_id premise_prefix seed;
 354                         K.premise_xref = idr;
 355                         K.premise_binder = Some b;
 356                         K.premise_n = Some n
 357                       }
 358                  else (K.Term t)
 359              | C.AConst(id,uri,[]) ->
 360                  let sort =
 361                    (try
 362                      Hashtbl.find ids_to_inner_sorts id
 363                     with Not_found -> `Type (CicUniv.fresh())) in
 364                  if sort = `Prop then
 365                     K.Lemma
 366                       { K.lemma_id = gen_id lemma_prefix seed;
 367                         K.lemma_name = UriManager.name_of_uri uri;
 368                         K.lemma_uri = UriManager.string_of_uri uri
 369                       }
 370                  else (K.Term t)
 371              | C.AMutConstruct(id,uri,tyno,consno,[]) ->
 372                  let sort =
 373                    (try
 374                      Hashtbl.find ids_to_inner_sorts id
 375                     with Not_found -> `Type (CicUniv.fresh())) in
 376                  if sort = `Prop then
 377                     let inductive_types =
 378                       (let o,_ =
 379                          CicEnvironment.get_obj CicUniv.empty_ugraph uri
 380                        in
 381                          match o with
 382                            | Cic.InductiveDefinition (l,_,_,_) -> l
 383                            | _ -> assert false
 384                       ) in
 385                     let (_,_,_,constructors) =
 386                       List.nth inductive_types tyno in
 387                     let name,_ = List.nth constructors (consno - 1) in
 388                     K.Lemma
 389                       { K.lemma_id = gen_id lemma_prefix seed;
 390                         K.lemma_name = name;
 391                         K.lemma_uri =
 392                           UriManager.string_of_uri uri ^ "#xpointer(1/" ^
 393                           string_of_int (tyno+1) ^ "/" ^ string_of_int consno ^
 394                           ")"
 395                       }
 396                  else (K.Term t)
 397              | _ -> (K.Term t)) in
 398           subproofs,hd::args
 399   in
 400   match (aux l) with
 401     [p],args ->
 402       [{p with K.proof_name = None}],
 403         List.map
 404           (function
 405               K.Premise prem when prem.K.premise_xref = p.K.proof_id ->
 406                K.Premise {prem with K.premise_binder = None}
 407             | i -> i) args
 408   | p,a as c -> c
 409
 410 and
 411
 412 build_def_item seed id n t ~ids_to_inner_sorts ~ids_to_inner_types =
 413  let module K = Content in
 414   try
 415    let sort = Hashtbl.find ids_to_inner_sorts id in
 416    if sort = `Prop then
 417        (let p =
 418         (acic2content seed ?name:(name_of n) ~ids_to_inner_sorts  ~ids_to_inner_types t)
 419        in
 420         `Proof p;)
 421    else
 422       `Definition
 423         { K.def_name = name_of n;
 424           K.def_id = gen_id definition_prefix seed;
 425           K.def_aref = id;
 426           K.def_term = t
 427         }
 428   with
 429    Not_found -> assert false
 430
 431 (* the following function must be called with an object of sort
 432 Prop. For debugging purposes this is tested again, possibly raising an
 433 Not_a_proof exception *)
 434
 435 and acic2content seed ?name ~ids_to_inner_sorts ~ids_to_inner_types t =
 436   let rec aux ?name t =
 437   let module C = Cic in
 438   let module K = Content in
 439   let module C2A = Cic2acic in
 440   let t1 =
 441     match t with
 442       C.ARel (id,idref,n,b) as t ->
 443         let sort = Hashtbl.find ids_to_inner_sorts id in
 444         if sort = `Prop then
 445           generate_exact seed t id name ~ids_to_inner_types
 446         else raise Not_a_proof
 447     | C.AVar (id,uri,exp_named_subst) as t ->
 448         let sort = Hashtbl.find ids_to_inner_sorts id in
 449         if sort = `Prop then
 450           generate_exact seed t id name ~ids_to_inner_types
 451         else raise Not_a_proof
 452     | C.AMeta (id,n,l) as t ->
 453         let sort = Hashtbl.find ids_to_inner_sorts id in
 454         if sort = `Prop then
 455           generate_exact seed t id name ~ids_to_inner_types
 456         else raise Not_a_proof
 457     | C.ASort (id,s) -> raise Not_a_proof
 458     | C.AImplicit _ -> raise NotImplemented
 459     | C.AProd (_,_,_,_) -> raise Not_a_proof
 460     | C.ACast (id,v,t) -> aux v
 461     | C.ALambda (id,n,s,t) ->
 462         let sort = Hashtbl.find ids_to_inner_sorts id in
 463         if sort = `Prop then
 464           let proof = aux t in
 465           let proof' =
 466             if proof.K.proof_conclude.K.conclude_method = "Intros+LetTac" then
 467                match proof.K.proof_conclude.K.conclude_args with
 468                  [K.ArgProof p] -> p
 469                | _ -> assert false
 470             else proof in
 471           let proof'' =
 472             { proof' with
 473               K.proof_name = None;
 474               K.proof_context =
 475                 (build_decl_item seed id n s ids_to_inner_sorts)::
 476                   proof'.K.proof_context
 477             }
 478           in
 479           generate_intros_let_tac seed id n s true proof'' name ~ids_to_inner_types
 480         else raise Not_a_proof
 481     | C.ALetIn (id,n,s,t) ->
 482         let sort = Hashtbl.find ids_to_inner_sorts id in
 483         if sort = `Prop then
 484           let proof = aux t in
 485           let proof' =
 486             if proof.K.proof_conclude.K.conclude_method = "Intros+LetTac" then
 487                match proof.K.proof_conclude.K.conclude_args with
 488                  [K.ArgProof p] -> p
 489                | _ -> assert false
 490             else proof in
 491           let proof'' =
 492             { proof' with
 493                K.proof_name = None;
 494                K.proof_context =
 495                  ((build_def_item seed id n s ids_to_inner_sorts
 496                    ids_to_inner_types):> Cic.annterm K.in_proof_context_element)
 497                  ::proof'.K.proof_context;
 498             }
 499           in
 500           generate_intros_let_tac seed id n s false proof'' name ~ids_to_inner_types
 501         else raise Not_a_proof
 502     | C.AAppl (id,li) ->
 503         (try rewrite
 504            seed name id li ~ids_to_inner_types ~ids_to_inner_sorts
 505          with NotApplicable ->
 506          try inductive
 507           seed name id li ~ids_to_inner_types ~ids_to_inner_sorts
 508          with NotApplicable ->
 509          try transitivity
 510            seed name id li ~ids_to_inner_types ~ids_to_inner_sorts
 511          with NotApplicable ->
 512           let subproofs, args =
 513             build_subproofs_and_args
 514               seed li ~ids_to_inner_types ~ids_to_inner_sorts in
 515 (*
 516           let args_to_lift =
 517             List.filter (test_for_lifting ~ids_to_inner_types) li in
 518           let subproofs =
 519             match args_to_lift with
 520                 [_] -> List.map aux args_to_lift
 521             | _ -> List.map (aux ~name:"H") args_to_lift in
 522           let args = build_args seed li subproofs
 523                  ~ids_to_inner_types ~ids_to_inner_sorts in *)
 524             { K.proof_name = name;
 525               K.proof_id   = gen_id proof_prefix seed;
 526               K.proof_context = [];
 527               K.proof_apply_context = serialize seed subproofs;
 528               K.proof_conclude =
 529                 { K.conclude_id = gen_id conclude_prefix seed;
 530                   K.conclude_aref = id;
 531                   K.conclude_method = "Apply";
 532                   K.conclude_args = args;
 533                   K.conclude_conclusion =
 534                      try Some
 535                        (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 536                      with Not_found -> None
 537                  };
 538             })
 539     | C.AConst (id,uri,exp_named_subst) as t ->
 540         let sort = Hashtbl.find ids_to_inner_sorts id in
 541         if sort = `Prop then
 542           generate_exact seed t id name ~ids_to_inner_types
 543         else raise Not_a_proof
 544     | C.AMutInd (id,uri,i,exp_named_subst) -> raise Not_a_proof
 545     | C.AMutConstruct (id,uri,i,j,exp_named_subst) as t ->
 546         let sort = Hashtbl.find ids_to_inner_sorts id in
 547         if sort = `Prop then
 548           generate_exact seed t id name ~ids_to_inner_types
 549         else raise Not_a_proof
 550     | C.AMutCase (id,uri,typeno,ty,te,patterns) ->
 551         let inductive_types,noparams =
 552           (let o, _ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
 553              match o with
 554                  Cic.Constant _ -> assert false
 555                | Cic.Variable _ -> assert false
 556                | Cic.CurrentProof _ -> assert false
 557                | Cic.InductiveDefinition (l,_,n,_) -> l,n
 558           ) in
 559         let (_,_,_,constructors) = List.nth inductive_types typeno in
 560         let name_and_arities =
 561           let rec count_prods =
 562             function
 563                C.Prod (_,_,t) -> 1 + count_prods t
 564              | _ -> 0 in
 565           List.map
 566             (function (n,t) -> Some n,((count_prods t) - noparams)) constructors in
 567         let pp =
 568           let build_proof p (name,arity) =
 569             let rec make_context_and_body c p n =
 570               if n = 0 then c,(aux p)
 571               else
 572                 (match p with
 573                    Cic.ALambda(idl,vname,s1,t1) ->
 574                      let ce =
 575                        build_decl_item seed idl vname s1 ~ids_to_inner_sorts in
 576                      make_context_and_body (ce::c) t1 (n-1)
 577                    | _ -> assert false) in
 578              let context,body = make_context_and_body [] p arity in
 579                K.ArgProof
 580                 {body with K.proof_name = name; K.proof_context=context} in
 581           List.map2 build_proof patterns name_and_arities in
 582         let context,term =
 583           (match
 584              build_subproofs_and_args
 585                seed ~ids_to_inner_types ~ids_to_inner_sorts [te]
 586            with
 587              l,[t] -> l,t
 588            | _ -> assert false) in
 589         { K.proof_name = name;
 590           K.proof_id   = gen_id proof_prefix seed;
 591           K.proof_context = [];
 592           K.proof_apply_context = serialize seed context;
 593           K.proof_conclude =
 594             { K.conclude_id = gen_id conclude_prefix seed;
 595               K.conclude_aref = id;
 596               K.conclude_method = "Case";
 597               K.conclude_args =
 598                 (K.Aux (UriManager.string_of_uri uri))::
 599                 (K.Aux (string_of_int typeno))::(K.Term ty)::term::pp;
 600               K.conclude_conclusion =
 601                 try Some
 602                   (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 603                 with Not_found -> None
 604              }
 605         }
 606     | C.AFix (id, no, funs) ->
 607         let proofs =
 608           List.map
 609             (function (_,name,_,_,bo) -> `Proof (aux ~name bo)) funs in
 610         let fun_name =
 611           List.nth (List.map (fun (_,name,_,_,_) -> name) funs) no
 612         in
 613         let decreasing_args =
 614           List.map (function (_,_,n,_,_) -> n) funs in
 615         let jo =
 616           { K.joint_id = gen_id joint_prefix seed;
 617             K.joint_kind = `Recursive decreasing_args;
 618             K.joint_defs = proofs
 619           }
 620         in
 621           { K.proof_name = name;
 622             K.proof_id  = gen_id proof_prefix seed;
 623             K.proof_context = [`Joint jo];
 624             K.proof_apply_context = [];
 625             K.proof_conclude =
 626               { K.conclude_id = gen_id conclude_prefix seed;
 627                 K.conclude_aref = id;
 628                 K.conclude_method = "Exact";
 629                 K.conclude_args =
 630                 [ K.Premise
 631                   { K.premise_id = gen_id premise_prefix seed;
 632                     K.premise_xref = jo.K.joint_id;
 633                     K.premise_binder = Some fun_name;
 634                     K.premise_n = Some no;
 635                   }
 636                 ];
 637                 K.conclude_conclusion =
 638                    try Some
 639                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 640                    with Not_found -> None
 641               }
 642         }
 643     | C.ACoFix (id,no,funs) ->
 644         let proofs =
 645           List.map
 646             (function (_,name,_,bo) -> `Proof (aux ~name bo)) funs in
 647         let jo =
 648           { K.joint_id = gen_id joint_prefix seed;
 649             K.joint_kind = `CoRecursive;
 650             K.joint_defs = proofs
 651           }
 652         in
 653           { K.proof_name = name;
 654             K.proof_id   = gen_id proof_prefix seed;
 655             K.proof_context = [`Joint jo];
 656             K.proof_apply_context = [];
 657             K.proof_conclude =
 658               { K.conclude_id = gen_id conclude_prefix seed;
 659                 K.conclude_aref = id;
 660                 K.conclude_method = "Exact";
 661                 K.conclude_args =
 662                 [ K.Premise
 663                   { K.premise_id = gen_id premise_prefix seed;
 664                     K.premise_xref = jo.K.joint_id;
 665                     K.premise_binder = Some "tiralo fuori";
 666                     K.premise_n = Some no;
 667                   }
 668                 ];
 669                 K.conclude_conclusion =
 670                   try Some
 671                     (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 672                   with Not_found -> None
 673               };
 674         }
 675      in
 676      let id = get_id t in
 677      generate_conversion seed false id t1 ~ids_to_inner_types
 678 in aux ?name t
 679
 680 and inductive seed name id li ~ids_to_inner_types ~ids_to_inner_sorts =
 681   let aux ?name = acic2content seed  ~ids_to_inner_types ~ids_to_inner_sorts in
 682   let module C2A = Cic2acic in
 683   let module K = Content in
 684   let module C = Cic in
 685   match li with
 686     C.AConst (idc,uri,exp_named_subst)::args ->
 687       let uri_str = UriManager.string_of_uri uri in
 688       let suffix = Str.regexp_string "_ind.con" in
 689       let len = String.length uri_str in
 690       let n = (try (Str.search_backward suffix uri_str len)
 691                with Not_found -> -1) in
 692       if n<0 then raise NotApplicable
 693       else
 694         let method_name =
 695           if UriManager.eq uri HelmLibraryObjects.Logic.ex_ind_URI then "Exists"
 696           else if UriManager.eq uri HelmLibraryObjects.Logic.and_ind_URI then "AndInd"
 697           else if UriManager.eq uri HelmLibraryObjects.Logic.false_ind_URI then "FalseInd"
 698           else "ByInduction" in
 699         let prefix = String.sub uri_str 0 n in
 700         let ind_str = (prefix ^ ".ind") in
 701         let ind_uri = UriManager.uri_of_string ind_str in
 702         let inductive_types,noparams =
 703           (let o,_ = CicEnvironment.get_obj CicUniv.empty_ugraph ind_uri in
 704              match o with
 705                | Cic.InductiveDefinition (l,_,n,_) -> (l,n)
 706                | _ -> assert false
 707           ) in
 708         let rec split n l =
 709           if n = 0 then ([],l) else
 710           let p,a = split (n-1) (List.tl l) in
 711           ((List.hd l::p),a) in
 712         let params_and_IP,tail_args = split (noparams+1) args in
 713         let constructors =
 714             (match inductive_types with
 715               [(_,_,_,l)] -> l
 716             | _ -> raise NotApplicable) (* don't care for mutual ind *) in
 717         let constructors1 =
 718           let rec clean_up n t =
 719              if n = 0 then t else
 720              (match t with
 721                 (label,Cic.Prod (_,_,t)) -> clean_up (n-1) (label,t)
 722               | _ -> assert false) in
 723           List.map (clean_up noparams) constructors in
 724         let no_constructors= List.length constructors in
 725         let args_for_cases, other_args =
 726           split no_constructors tail_args in
 727         let subproofs,other_method_args =
 728           build_subproofs_and_args seed other_args
 729              ~ids_to_inner_types ~ids_to_inner_sorts in
 730         let method_args=
 731           let rec build_method_args =
 732             function
 733                 [],_-> [] (* extra args are ignored ???? *)
 734               | (name,ty)::tlc,arg::tla ->
 735                   let idarg = get_id arg in
 736                   let sortarg =
 737                     (try (Hashtbl.find ids_to_inner_sorts idarg)
 738                      with Not_found -> `Type (CicUniv.fresh())) in
 739                   let hdarg =
 740                     if sortarg = `Prop then
 741                       let (co,bo) =
 742                         let rec bc =
 743                           function
 744                             Cic.Prod (_,s,t),Cic.ALambda(idl,n,s1,t1) ->
 745                               let ce =
 746                                 build_decl_item
 747                                   seed idl n s1 ~ids_to_inner_sorts in
 748                               if (occur ind_uri s) then
 749                                 ( match t1 with
 750                                    Cic.ALambda(id2,n2,s2,t2) ->
 751                                      let inductive_hyp =
 752                                        `Hypothesis
 753                                          { K.dec_name = name_of n2;
 754                                            K.dec_id =
 755                                             gen_id declaration_prefix seed;
 756                                            K.dec_inductive = true;
 757                                            K.dec_aref = id2;
 758                                            K.dec_type = s2
 759                                          } in
 760                                      let (context,body) = bc (t,t2) in
 761                                      (ce::inductive_hyp::context,body)
 762                                  | _ -> assert false)
 763                               else
 764                                 (
 765                                 let (context,body) = bc (t,t1) in
 766                                 (ce::context,body))
 767                             | _ , t -> ([],aux t) in
 768                         bc (ty,arg) in
 769                       K.ArgProof
 770                        { bo with
 771                          K.proof_name = Some name;
 772                          K.proof_context = co;
 773                        };
 774                     else (K.Term arg) in
 775                   hdarg::(build_method_args (tlc,tla))
 776               | _ -> assert false in
 777           build_method_args (constructors1,args_for_cases) in
 778           { K.proof_name = name;
 779             K.proof_id   = gen_id proof_prefix seed;
 780             K.proof_context = [];
 781             K.proof_apply_context = serialize seed subproofs;
 782             K.proof_conclude =
 783               { K.conclude_id = gen_id conclude_prefix seed;
 784                 K.conclude_aref = id;
 785                 K.conclude_method = method_name;
 786                 K.conclude_args =
 787                   K.Aux (string_of_int no_constructors)
 788                   ::K.Term (C.AAppl(id,((C.AConst(idc,uri,exp_named_subst))::params_and_IP)))
 789                   ::method_args@other_method_args;
 790                 K.conclude_conclusion =
 791                    try Some
 792                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 793                    with Not_found -> None
 794               }
 795           }
 796   | _ -> raise NotApplicable
 797
 798 and rewrite seed name id li ~ids_to_inner_types ~ids_to_inner_sorts =
 799   let aux ?name = acic2content seed ~ids_to_inner_types ~ids_to_inner_sorts in
 800   let module C2A = Cic2acic in
 801   let module K = Content in
 802   let module C = Cic in
 803   match li with
 804     C.AConst (sid,uri,exp_named_subst)::args ->
 805       if UriManager.eq uri HelmLibraryObjects.Logic.eq_ind_URI or
 806          UriManager.eq uri HelmLibraryObjects.Logic.eq_ind_r_URI or
 807          LibraryObjects.is_eq_ind_URI uri or
 808          LibraryObjects.is_eq_ind_r_URI uri then
 809         let subproofs,arg =
 810           (match
 811              build_subproofs_and_args
 812                seed ~ids_to_inner_types ~ids_to_inner_sorts [List.nth args 3]
 813            with
 814              l,[p] -> l,p
 815            | _,_ -> assert false) in
 816         let method_args =
 817           let rec ma_aux n = function
 818               [] -> []
 819             | a::tl ->
 820                 let hd =
 821                   if n = 0 then arg
 822                   else
 823                     let aid = get_id a in
 824                     let asort = (try (Hashtbl.find ids_to_inner_sorts aid)
 825                       with Not_found -> `Type (CicUniv.fresh())) in
 826                     if asort = `Prop then
 827                       K.ArgProof (aux a)
 828                     else K.Term a in
 829                 hd::(ma_aux (n-1) tl) in
 830           (ma_aux 3 args) in
 831           { K.proof_name = name;
 832             K.proof_id  = gen_id proof_prefix seed;
 833             K.proof_context = [];
 834             K.proof_apply_context = serialize seed subproofs;
 835             K.proof_conclude =
 836               { K.conclude_id = gen_id conclude_prefix seed;
 837                 K.conclude_aref = id;
 838                 K.conclude_method = "Rewrite";
 839                 K.conclude_args =
 840                   K.Term (C.AConst (sid,uri,exp_named_subst))::method_args;
 841                 K.conclude_conclusion =
 842                    try Some
 843                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 844                    with Not_found -> None
 845               }
 846           }
 847       else raise NotApplicable
 848   | _ -> raise NotApplicable
 849
 850 and transitivity seed name id li ~ids_to_inner_types ~ids_to_inner_sorts =
 851   let module C2A = Cic2acic in
 852   let module K = Content in
 853   let module C = Cic in
 854   match li with
 855     | C.AConst (sid,uri,exp_named_subst)::args
 856         when LibraryObjects.is_trans_eq_URI uri ->
 857         let exp_args = List.map snd exp_named_subst in
 858         let t1,t2,t3,p1,p2 =
 859           match exp_args@args with
 860             | [_;t1;t2;t3;p1;p2] -> t1,t2,t3,p1,p2
 861             | _ -> raise NotApplicable
 862         in
 863           { K.proof_name = name;
 864             K.proof_id  = gen_id proof_prefix seed;
 865             K.proof_context = [];
 866             K.proof_apply_context = [];
 867             K.proof_conclude =
 868               { K.conclude_id = gen_id conclude_prefix seed;
 869                 K.conclude_aref = id;
 870                 K.conclude_method = "Eq_chain";
 871                 K.conclude_args =
 872                    K.Term t1::
 873                      (transitivity_aux
 874                         seed ~ids_to_inner_types ~ids_to_inner_sorts p1)@
 875                      [K.Term t2]@
 876                      (transitivity_aux
 877                         seed ~ids_to_inner_types ~ids_to_inner_sorts p2)@
 878                      [K.Term t3];
 879                 K.conclude_conclusion =
 880                    try Some
 881                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 882                    with Not_found -> None
 883               }
 884           }
 885     | _ -> raise NotApplicable
 886
 887 and transitivity_aux seed ~ids_to_inner_types ~ids_to_inner_sorts t =
 888   let module C2A = Cic2acic in
 889   let module K = Content in
 890   let module C = Cic in
 891   match t with
 892     | C.AAppl (_,C.AConst (sid,uri,exp_named_subst)::args)
 893         when LibraryObjects.is_trans_eq_URI uri ->
 894         let exp_args = List.map snd exp_named_subst in
 895         let t1,t2,t3,p1,p2 =
 896           match exp_args@args with
 897             | [_;t1;t2;t3;p1;p2] -> t1,t2,t3,p1,p2
 898             | _ -> raise NotApplicable
 899         in
 900           (transitivity_aux seed ~ids_to_inner_types ~ids_to_inner_sorts p1)
 901           @[K.Term t2]
 902           @(transitivity_aux seed ~ids_to_inner_types ~ids_to_inner_sorts p2)
 903     | _ -> [K.ArgProof
 904         (acic2content seed ~ids_to_inner_sorts ~ids_to_inner_types t)]
 905
 906 ;;
 907
 908
 909 let map_conjectures
 910  seed ~ids_to_inner_sorts ~ids_to_inner_types (id,n,context,ty)
 911 =
 912  let module K = Content in
 913  let context' =
 914   List.map
 915    (function
 916        (id,None) -> None
 917      | (id,Some (name,Cic.ADecl t)) ->
 918          Some
 919           (* We should call build_decl_item, but we have not computed *)
 920           (* the inner-types ==> we always produce a declaration      *)
 921           (`Declaration
 922             { K.dec_name = name_of name;
 923               K.dec_id = gen_id declaration_prefix seed;
 924               K.dec_inductive = false;
 925               K.dec_aref = get_id t;
 926               K.dec_type = t
 927             })
 928      | (id,Some (name,Cic.ADef t)) ->
 929          Some
 930           (* We should call build_def_item, but we have not computed *)
 931           (* the inner-types ==> we always produce a declaration     *)
 932           (`Definition
 933              { K.def_name = name_of name;
 934                K.def_id = gen_id definition_prefix seed;
 935                K.def_aref = get_id t;
 936                K.def_term = t
 937              })
 938    ) context
 939  in
 940   (id,n,context',ty)
 941 ;;
 942
 943 (* map_sequent is similar to map_conjectures, but the for the hid
 944 of the hypothesis, which are preserved instead of generating
 945 fresh ones. We shall have to adopt a uniform policy, soon or later *)
 946
 947 let map_sequent ((id,n,context,ty):Cic.annconjecture) =
 948  let module K = Content in
 949  let context' =
 950   List.map
 951    (function
 952        (id,None) -> None
 953      | (id,Some (name,Cic.ADecl t)) ->
 954          Some
 955           (* We should call build_decl_item, but we have not computed *)
 956           (* the inner-types ==> we always produce a declaration      *)
 957           (`Declaration
 958             { K.dec_name = name_of name;
 959               K.dec_id = id;
 960               K.dec_inductive = false;
 961               K.dec_aref = get_id t;
 962               K.dec_type = t
 963             })
 964      | (id,Some (name,Cic.ADef t)) ->
 965          Some
 966           (* We should call build_def_item, but we have not computed *)
 967           (* the inner-types ==> we always produce a declaration     *)
 968           (`Definition
 969              { K.def_name = name_of name;
 970                K.def_id = id;
 971                K.def_aref = get_id t;
 972                K.def_term = t
 973              })
 974    ) context
 975  in
 976   (id,n,context',ty)
 977 ;;
 978
 979 let rec annobj2content ~ids_to_inner_sorts ~ids_to_inner_types =
 980   let module C = Cic in
 981   let module K = Content in
 982   let module C2A = Cic2acic in
 983   let seed = ref 0 in
 984   function
 985       C.ACurrentProof (_,_,n,conjectures,bo,ty,params,_) ->
 986         (gen_id object_prefix seed, params,
 987           Some
 988            (List.map
 989              (map_conjectures seed ~ids_to_inner_sorts ~ids_to_inner_types)
 990              conjectures),
 991           `Def (K.Const,ty,
 992             build_def_item seed (get_id bo) (C.Name n) bo
 993              ~ids_to_inner_sorts ~ids_to_inner_types))
 994     | C.AConstant (_,_,n,Some bo,ty,params,_) ->
 995          (gen_id object_prefix seed, params, None,
 996            `Def (K.Const,ty,
 997              build_def_item seed (get_id bo) (C.Name n) bo
 998                ~ids_to_inner_sorts ~ids_to_inner_types))
 999     | C.AConstant (id,_,n,None,ty,params,_) ->
1000          (gen_id object_prefix seed, params, None,
1001            `Decl (K.Const,
1002              build_decl_item seed id (C.Name n) ty
1003                ~ids_to_inner_sorts))
1004     | C.AVariable (_,n,Some bo,ty,params,_) ->
1005          (gen_id object_prefix seed, params, None,
1006            `Def (K.Var,ty,
1007              build_def_item seed (get_id bo) (C.Name n) bo
1008                ~ids_to_inner_sorts ~ids_to_inner_types))
1009     | C.AVariable (id,n,None,ty,params,_) ->
1010          (gen_id object_prefix seed, params, None,
1011            `Decl (K.Var,
1012              build_decl_item seed id (C.Name n) ty
1013               ~ids_to_inner_sorts))
1014     | C.AInductiveDefinition (id,l,params,nparams,_) ->
1015          (gen_id object_prefix seed, params, None,
1016             `Joint
1017               { K.joint_id = gen_id joint_prefix seed;
1018                 K.joint_kind = `Inductive nparams;
1019                 K.joint_defs = List.map (build_inductive seed) l
1020               })
1021
1022 and
1023     build_inductive seed =
1024      let module K = Content in
1025       fun (_,n,b,ty,l) ->
1026         `Inductive
1027           { K.inductive_id = gen_id inductive_prefix seed;
1028             K.inductive_name = n;
1029             K.inductive_kind = b;
1030             K.inductive_type = ty;
1031             K.inductive_constructors = build_constructors seed l
1032            }
1033
1034 and
1035     build_constructors seed l =
1036      let module K = Content in
1037       List.map
1038        (fun (n,t) ->
1039            { K.dec_name = Some n;
1040              K.dec_id = gen_id declaration_prefix seed;
1041              K.dec_inductive = false;
1042              K.dec_aref = "";
1043              K.dec_type = t
1044            }) l
1045 ;;
1046
1047 (*
1048 and 'term cinductiveType =
1049  id * string * bool * 'term *                (* typename, inductive, arity *)
1050    'term cconstructor list                   (*  constructors        *)
1051
1052 and 'term cconstructor =
1053  string * 'term
1054 *)
1055
1056