]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/acic_content/acic2content.ml
Equality chains.
[helm.git] / 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