]> matita.cs.unibo.it Git - helm.git/blob - matitaB/components/ng_tactics/nCicElim.ml
missing notation file
[helm.git] / matitaB / components / ng_tactics / nCicElim.ml
1 (*
2     ||M||  This file is part of HELM, an Hypertextual, Electronic        
3     ||A||  Library of Mathematics, developed at the Computer Science     
4     ||T||  Department, University of Bologna, Italy.                     
5     ||I||                                                                
6     ||T||  HELM is free software; you can redistribute it and/or         
7     ||A||  modify it under the terms of the GNU General Public License   
8     \   /  version 2 or (at your option) any later version.      
9      \ /   This software is distributed as is, NO WARRANTY.     
10       V_______________________________________________________________ *)
11
12 (* $Id: nCic.ml 9058 2008-10-13 17:42:30Z tassi $ *)
13
14 let fresh_name =
15  let i = ref 0 in
16  function () ->
17   incr i;
18   "x_" ^ string_of_int !i
19 ;;
20
21 let mk_id id =
22  let id = if id = "_" then fresh_name () else id in
23   NotationPt.Ident (id,`Ambiguous)
24 ;;
25
26 (*CSC: cut&paste from nCicReduction.split_prods, but does not check that
27   the return type is a sort *)
28 let rec my_split_prods status ~subst context n te =
29   match (n, NCicReduction.whd status ~subst context te) with
30    | (0, _) -> context,te
31    | (n, NCic.Prod (name,so,ta)) ->
32        my_split_prods status ~subst ((name,(NCic.Decl so))::context) (n - 1) ta
33    | (n, _) when n <= 0 -> context,te
34    | (_, _) -> raise (Failure "my_split_prods")
35 ;;
36
37 let mk_appl =
38  function
39     [] -> assert false
40   | [x] -> x
41   | NotationPt.Appl l1 :: l2 -> NotationPt.Appl (l1 @ l2)
42   | l -> NotationPt.Appl l
43 ;;
44
45 let mk_elim status uri leftno it (outsort,suffix) pragma =
46  let _,ind_name,ty,cl = it in
47  let srec_name = ind_name ^ "_" ^ suffix in
48  let rec_name = mk_id srec_name in
49  let name_of_k id = mk_id ("H_" ^ id) in
50  let p_name = mk_id "Q_" in
51  let params,ty = NCicReduction.split_prods status ~subst:[] [] leftno ty in
52  let params = List.rev_map (function name,_ -> mk_id name) params in
53  let args,sort = NCicReduction.split_prods status ~subst:[] [] (-1) ty in
54  let args = List.rev_map (function name,_ -> mk_id name) args in
55  let rec_arg = mk_id (fresh_name ()) in
56  let mk_prods = 
57   List.fold_right
58    (fun name res -> NotationPt.Binder (`Forall,(name,None),res)) in
59  let p_ty = mk_prods args
60    (NotationPt.Binder
61     (`Forall,
62      (rec_arg,Some (mk_appl (mk_id ind_name :: params @ args))),
63      NotationPt.Sort outsort)) in
64  let mk_arrs n = mk_prods (HExtlib.mk_list (mk_id "_") n) in
65  let args = args @ [rec_arg] in
66  let k_names = List.map (function _,name,_ -> name_of_k name) cl in
67  (*
68  let final_params =
69   List.map (function name -> name, None) params @
70   [p_name,Some p_ty] @
71   List.map (function name -> name, None) k_names @
72   List.map (function name -> name, None) args in
73  *)
74  let cty = mk_appl (p_name :: args) in
75  let ty = Some cty in
76  let branches_with_args =
77   List.map
78    (function (_,name,ty) ->
79      let _,ty = NCicReduction.split_prods status ~subst:[] [] leftno ty in
80      let cargs,ty= my_split_prods status ~subst:[] [] (-1) ty in
81      let cargs_recargs_nih =
82       List.fold_left
83        (fun (acc,nih) -> function
84            _,NCic.Def _ -> assert false
85          | name,NCic.Decl ty ->
86             let context,ty = my_split_prods status ~subst:[] [] (-1) ty in
87              match ty with
88               | NCic.Const nref
89               | NCic.Appl (NCic.Const nref::_)
90                  when
91                   let NReference.Ref (uri',_) = nref in
92                    NUri.eq uri uri'
93                  ->
94                   let abs = List.rev_map (fun id,_ -> mk_id id) context in
95                   let name = mk_id name in
96                    (name, Some (
97                    List.fold_right
98                     (fun id res ->
99                       NotationPt.Binder (`Lambda,(id,None),res))
100                     abs
101                     (NotationPt.Appl
102                      (rec_name ::
103                       params @
104                       [p_name] @
105                       k_names @
106                       List.map (fun _ -> NotationPt.Implicit `JustOne)
107                        (List.tl args) @
108                       [mk_appl (name::abs)]))))::acc, nih + 1
109               | _ -> (mk_id name,None)::acc,nih
110        ) ([],0) cargs in
111      let cargs_and_recursive_args, nih = cargs_recargs_nih in
112      let cargs,recursive_args = List.split cargs_and_recursive_args in
113      let recursive_args = HExtlib.filter_map (fun x -> x) recursive_args in
114       (NotationPt.Pattern (name,None,List.map (fun x -> x,None) cargs),
115        mk_appl (name_of_k name :: cargs @ recursive_args)), (name,cargs, nih)
116    ) cl
117  in
118  let branches, branch_args = List.split branches_with_args in
119  let bo = NotationPt.Case (rec_arg,Some (ind_name,None),Some p_name,branches) in
120  let final_params =
121   List.map (function name -> name, None) params @
122   [p_name,Some p_ty] @
123   List.map (function name, cargs, nih -> 
124             name_of_k name, 
125             Some (mk_prods cargs (mk_arrs nih 
126              (mk_appl 
127               (p_name::HExtlib.mk_list (NotationPt.Implicit `JustOne)
128                (List.length args - 1) @
129                [mk_appl (mk_id name :: params @ cargs)]))))) branch_args @
130                List.map (function name -> name, None) args in
131  let recno = List.length final_params in
132  let where = recno - 1 in
133  let res =
134   NotationPt.LetRec (`Inductive,
135    [final_params, (rec_name,ty), bo, where], rec_name)
136  in
137 (*
138   prerr_endline
139    (BoxPp.render_to_string
140      ~map_unicode_to_tex:false
141      (function x::_ -> x | _ -> assert false)
142      80 (NotationPres.render (fun _ -> None)
143      (TermContentPres.pp_ast res)));
144   prerr_endline "#####";
145   let cobj = ("xxx", [], None, `Joint {
146       Content.joint_id = "yyy";
147       joint_kind = `Recursive [recno];
148       joint_defs =
149        [ `Definition {
150             Content.def_name = Some srec_name;
151             def_id = "zzz";
152             def_aref = "www";
153             def_term = bo;
154             def_type = 
155               List.fold_right 
156                 (fun x t -> NotationPt.Binder(`Forall,x,t))
157                 final_params cty
158           }
159        ];
160     })
161   in
162   let ids_to_nrefs = Hashtbl.create 1 in
163   let boxml = Content2pres.ncontent2pres ~ids_to_nrefs cobj in
164   prerr_endline (
165    (BoxPp.render_to_string ~map_unicode_to_tex:false
166      (function x::_ -> x | _ -> assert false) 80 
167      (NotationPres.mpres_of_box boxml)));
168 *)
169   NotationPt.Theorem
170    (`Definition,srec_name,
171       NotationPt.Implicit `JustOne,Some res,pragma)
172 ;;
173
174 let ast_of_sort s =
175   let headrm prefix s =
176     try 
177       let len_prefix = String.length prefix in 
178       assert (String.sub s 0 len_prefix = prefix);
179       String.sub s len_prefix (String.length s - len_prefix)
180     with Invalid_argument _ -> assert false
181   in
182   match s with
183    | NCic.Prop -> `Prop,"ind"
184    | NCic.Type []  -> `NType "", "rect_Type"
185    | NCic.Type ((`Type,u) :: _) ->
186        let name = NUri.name_of_uri u in
187        `NType (headrm "Type" name), "rect_" ^ name
188    | NCic.Type ((`CProp,u) :: _) ->
189        let name = NUri.name_of_uri u in
190        `NCProp (headrm "Type" name), 
191        "rect_" ^ Str.replace_first (Str.regexp "Type") "CProp" name
192    | _ -> assert false
193 ;;
194
195 let mk_elims status (uri,_,_,_,obj) =
196   match obj with
197     NCic.Inductive (true,leftno,[itl],_) ->
198       List.map (fun s-> mk_elim status uri leftno itl (ast_of_sort s) (`Elim s))
199        (NCic.Prop::
200          List.map (fun s -> NCic.Type s) (NCicEnvironment.get_universes status))
201    | _ -> []
202 ;;
203
204 (********************* Projections **********************)
205
206 let mk_lambda =
207  function
208     [] -> assert false 
209   | [t] -> t
210   | l -> NotationPt.Appl l
211 ;;
212
213 let rec count_prods = function NCic.Prod (_,_,t) -> 1 + count_prods t | _ -> 0;;
214
215 let rec nth_prod projs n ty =
216  match ty with
217     NCic.Prod (_,s,_) when n=0 -> projs, s
218   | NCic.Prod (name,_,t) -> nth_prod (name::projs) (n-1) t
219   | _ -> assert false
220 ;;
221
222 (* this code should be unified with NTermCicContent.nast_of_cic0,
223    but the two contexts have different types *)
224 let pp (status: #NCic.status) =
225  let rec pp rels =
226   function
227     NCic.Rel i -> List.nth rels (i - 1)
228   | NCic.Const _ as t -> NotationPt.NCic t
229   | NCic.Sort s -> NotationPt.Sort (fst (ast_of_sort s))
230   | NCic.Meta _
231   | NCic.Implicit _ -> assert false
232   | NCic.Appl l -> NotationPt.Appl (List.map (pp rels) l)
233   | NCic.Prod (n,s,t) ->
234      let n = mk_id n in
235       NotationPt.Binder (`Pi, (n,Some (pp rels s)), pp (n::rels) t)
236   | NCic.Lambda (n,s,t) ->
237      let n = mk_id n in
238       NotationPt.Binder (`Lambda, (n,Some (pp rels s)), pp (n::rels) t)
239   | NCic.LetIn (n,s,ty,t) ->
240      let n = mk_id n in
241       NotationPt.LetIn ((n, Some (pp rels ty)), pp rels s, pp (n::rels) t)
242   | NCic.Match (NReference.Ref (uri,_) as r,outty,te,patterns) ->
243     let name = NUri.name_of_uri uri in
244     let case_indty = Some (name, None) in
245     let constructors, leftno =
246      let _,leftno,tys,_,n = NCicEnvironment.get_checked_indtys status r in
247      let _,_,_,cl  = List.nth tys n in
248       cl,leftno
249     in
250     let rec eat_branch n rels ty pat =
251       match (ty, pat) with
252       | NCic.Prod (name, s, t), _ when n > 0 ->
253          eat_branch (pred n) rels t pat
254       | NCic.Prod (_, _, t), NCic.Lambda (name, s, t') ->
255           let cv, rhs = eat_branch 0 ((mk_id name)::rels) t t' in
256            (mk_id name, Some (pp rels s)) :: cv, rhs
257       | _, _ -> [], pp rels pat
258     in
259     let patterns =
260       try
261         List.map2
262           (fun (_, name, ty) pat ->
263             let capture_variables,rhs = eat_branch leftno rels ty pat in
264              NotationPt.Pattern (name, None, capture_variables), rhs
265           ) constructors patterns
266       with Invalid_argument _ -> assert false
267     in
268      NotationPt.Case (pp rels te, case_indty, Some (pp rels outty), patterns)
269  in
270   pp
271 ;;
272
273 let mk_projection status leftno tyname consname consty (projname,_,_) i =
274  let argsno = count_prods consty - leftno in
275  let rec aux names ty leftno =
276   match leftno,ty with
277    | 0,_ ->
278      let arg = mk_id "xxx" in
279      let arg_ty = mk_appl (mk_id tyname :: List.rev names) in
280      let bvar = mk_id "yyy" in
281      let underscore = NotationPt.Ident ("_",`Ambiguous),None in
282      let bvars =
283       HExtlib.mk_list underscore i @ [bvar,None] @
284        HExtlib.mk_list underscore (argsno - i -1) in
285      let branch = NotationPt.Pattern (consname,None,bvars), bvar in
286      let projs,outtype = nth_prod [] i ty in
287      let rels =
288       List.map
289        (fun name -> mk_appl (mk_id name :: List.rev names @ [arg])) projs
290       @ names in
291      let outtype = pp status rels outtype in
292      let outtype= NotationPt.Binder (`Lambda, (arg, Some arg_ty), outtype) in
293       [arg, Some arg_ty], NotationPt.Case (arg,None,Some outtype,[branch])
294    | _,NCic.Prod (name,_,t) ->
295       let name = mk_id name in
296       let params,body = aux (name::names) t (leftno - 1) in
297        (name,None)::params, body
298    | _,_ -> assert false
299  in
300  let params,bo = aux [] consty leftno in
301  let pprojname = mk_id projname in
302  let res =
303   NotationPt.LetRec (`Inductive,
304    [params, (pprojname,None), bo, leftno], pprojname) in
305 (* prerr_endline
306    (BoxPp.render_to_string
307      ~map_unicode_to_tex:false
308      (function x::_ -> x | _ -> assert false)
309      80 (NotationPres.render (fun _ -> None)
310      (TermContentPres.pp_ast res)));*)
311   NotationPt.Theorem
312    (`Definition,projname,NotationPt.Implicit `JustOne,Some res,`Projection)
313 ;;
314
315 let mk_projections status (_,_,_,_,obj) =
316  match obj with
317     NCic.Inductive
318      (true,leftno,[_,tyname,_,[_,consname,consty]],(_,`Record fields))
319     ->
320      HExtlib.list_mapi (mk_projection status leftno tyname consname consty) fields
321   | _ -> []
322 ;;