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