]> matita.cs.unibo.it Git - helm.git/blob - helm/ocaml/cic_omdoc/eta_fixing.ml
adding library support (not ready yet)
[helm.git] / helm / ocaml / cic_omdoc / eta_fixing.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 exception ReferenceToNonVariable;;
27
28 let prerr_endline _ = ();;
29
30 (* 
31 let rec fix_lambdas_wrt_type ty te =
32  let module C = Cic in
33  let module S = CicSubstitution in
34 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
35    match ty with
36      C.Prod (_,_,ty') ->
37        (match CicReduction.whd [] te with
38           C.Lambda (n,s,te') ->
39             C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
40         | t ->
41             let rec get_sources =
42               function 
43                 C.Prod (_,s,ty) -> s::(get_sources ty)
44               | _ -> [] in
45             let sources = get_sources ty in
46             let no_sources = List.length sources in
47             let rec mk_rels n shift =
48               if n = 0 then []
49             else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
50             let t' = S.lift no_sources t in
51             let t2 = 
52               match t' with
53                 C.Appl l -> 
54                   C.LetIn 
55                      (C.Name "w",t',C.Appl ((C.Rel 1)::(mk_rels no_sources 1)))
56               | _ -> 
57                   C.Appl (t'::(mk_rels no_sources 0)) in
58                    List.fold_right
59                      (fun source t -> C.Lambda (C.Name "y",source,t)) 
60                       sources t2)
61    | _ -> te
62 ;; *)
63
64 let rec fix_lambdas_wrt_type ty te =
65  let module C = Cic in
66  let module S = CicSubstitution in
67 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
68    match ty,te with
69      C.Prod (_,_,ty'), C.Lambda (n,s,te') ->
70        C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
71    | C.Prod (_,s,ty'), t -> 
72       let rec get_sources =
73         function 
74             C.Prod (_,s,ty) -> s::(get_sources ty)
75           | _ -> [] in
76       let sources = get_sources ty in
77       let no_sources = List.length sources in
78       let rec mk_rels n shift =
79         if n = 0 then []
80         else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
81       let t' = S.lift no_sources t in
82       let t2 = 
83          match t' with
84            C.Appl l -> 
85              C.LetIn (C.Name "w",t',C.Appl ((C.Rel 1)::(mk_rels no_sources 1)))
86          | _ -> C.Appl (t'::(mk_rels no_sources 0)) in
87       List.fold_right
88         (fun source t -> C.Lambda (C.Name "y",CicReduction.whd [] source,t)) sources t2
89    | _, _ -> te
90 ;;
91
92 (*
93 let rec fix_lambdas_wrt_type ty te =
94  let module C = Cic in
95  let module S = CicSubstitution in
96 (*  prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
97    match ty,te with
98      C.Prod (_,_,ty'), C.Lambda (n,s,te') ->
99        C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
100    | C.Prod (_,s,ty'), ((C.Appl (C.Const _ ::_)) as t) -> 
101       (* const have a fixed arity *)
102       (* prerr_endline ("******** fl - eta expansion 0: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
103        let t' = S.lift 1 t in
104        C.Lambda (C.Name "x",s,
105          C.LetIn 
106           (C.Name "H", fix_lambdas_wrt_type ty' t', 
107             C.Appl [C.Rel 1;C.Rel 2])) 
108    | C.Prod (_,s,ty'), C.Appl l ->
109        (* prerr_endline ("******** fl - eta expansion 1: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
110        let l' = List.map (S.lift 1) l in
111         C.Lambda (C.Name "x",s,
112          fix_lambdas_wrt_type ty' (C.Appl (l'@[C.Rel 1])))
113    | C.Prod (_,s,ty'), _ ->
114        (* prerr_endline ("******** fl - eta expansion 2: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
115        flush stderr ;
116        let te' = S.lift 1 te in
117         C.Lambda (C.Name "x",s,
118           fix_lambdas_wrt_type ty' (C.Appl [te';C.Rel 1]))
119    | _, _ -> te
120 ;;*) 
121
122 let fix_according_to_type ty hd tl =
123  let module C = Cic in
124  let module S = CicSubstitution in
125    let rec count_prods =
126      function
127        C.Prod (_,_,t) -> 1 + (count_prods t)
128        | _ -> 0 in
129   let expected_arity = count_prods ty in
130   let rec aux n ty tl res =
131     if n = 0 then
132       (match tl with 
133          [] ->
134           (match res with
135               [] -> assert false
136             | [res] -> res
137             | _ -> C.Appl res)
138        | _ -> 
139           match res with
140             [] -> assert false
141           | [a] -> C.Appl (a::tl)
142           | _ ->
143               (* prerr_endline ("******* too many args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
144               C.LetIn 
145                 (C.Name "H", 
146                   C.Appl res, C.Appl (C.Rel 1::(List.map (S.lift 1) tl))))
147     else 
148       let name,source,target =
149         (match ty with
150            C.Prod (C.Name _ as n,s,t) -> n,s,t
151          | C.Prod (C.Anonymous, s,t) -> C.Name "z",s,t
152          | _ -> (* prods number may only increase for substitution *) 
153            assert false) in
154       match tl with 
155          [] ->
156            (* prerr_endline ("******* too few args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
157            let res' = List.map (S.lift 1) res in 
158            C.Lambda 
159             (name, source, aux (n-1) target [] (res'@[C.Rel 1]))
160         | hd::tl' -> 
161            let hd' = fix_lambdas_wrt_type source hd in
162             (*  (prerr_endline ("++++++prima :" ^(CicPp.ppterm hd)); 
163               prerr_endline ("++++++dopo :" ^(CicPp.ppterm hd'))); *)
164            aux (n-1) (S.subst hd' target) tl' (res@[hd']) in
165   aux expected_arity ty tl [hd]
166 ;;
167
168 let eta_fix metasenv context t =
169  let rec eta_fix' context t = 
170   (* prerr_endline ("entering aux with: term=" ^ CicPp.ppterm t); 
171   flush stderr ; *)
172   let module C = Cic in
173   let module S = CicSubstitution in
174   match t with
175      C.Rel n -> C.Rel n 
176    | C.Var (uri,exp_named_subst) ->
177       let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
178        C.Var (uri,exp_named_subst')
179    | C.Meta (n,l) ->
180       let (_,canonical_context,_) = CicUtil.lookup_meta n metasenv in
181       let l' =
182         List.map2
183          (fun ct t ->
184           match (ct, t) with
185             None, _ -> None
186           | _, Some t -> Some (eta_fix' context t)
187           | Some _, None -> assert false (* due to typing rules *))
188         canonical_context l
189        in
190        C.Meta (n,l')
191    | C.Sort s -> C.Sort s
192    | C.Implicit _ as t -> t
193    | C.Cast (v,t) -> C.Cast (eta_fix' context v, eta_fix' context t)
194    | C.Prod (n,s,t) -> 
195        C.Prod 
196         (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
197    | C.Lambda (n,s,t) -> 
198        C.Lambda 
199         (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
200    | C.LetIn (n,s,t) -> 
201        C.LetIn 
202         (n,eta_fix' context s,eta_fix' ((Some (n,(C.Def (s,None))))::context) t)
203    | C.Appl l as appl -> 
204        let l' =  List.map (eta_fix' context) l 
205        in 
206        (match l' with
207            [] -> assert false
208          | he::tl ->
209             let ty,_ = 
210               CicTypeChecker.type_of_aux' metasenv context he 
211                 CicUniv.empty_ugraph 
212             in
213               fix_according_to_type ty he tl
214 (*
215          C.Const(uri,exp_named_subst)::l'' ->
216            let constant_type =
217              (match CicEnvironment.get_obj uri with
218                C.Constant (_,_,ty,_) -> ty
219              | C.Variable _ -> raise ReferenceToVariable
220              | C.CurrentProof (_,_,_,_,params) -> raise ReferenceToCurrentProof
221              | C.InductiveDefinition _ -> raise ReferenceToInductiveDefinition
222              ) in 
223            fix_according_to_type 
224              constant_type (C.Const(uri,exp_named_subst)) l''
225         | _ -> C.Appl l' *))
226    | C.Const (uri,exp_named_subst) ->
227        let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
228         C.Const (uri,exp_named_subst')
229    | C.MutInd (uri,tyno,exp_named_subst) ->
230        let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
231         C.MutInd (uri, tyno, exp_named_subst')
232    | C.MutConstruct (uri,tyno,consno,exp_named_subst) ->
233        let exp_named_subst' = fix_exp_named_subst context exp_named_subst in
234         C.MutConstruct (uri, tyno, consno, exp_named_subst')
235    | C.MutCase (uri, tyno, outty, term, patterns) as prima ->
236        let outty' =  eta_fix' context outty in
237        let term' = eta_fix' context term in
238        let patterns' = List.map (eta_fix' context) patterns in
239        let inductive_types,noparams =
240          let o,_ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
241            (match o with
242                Cic.Constant _ -> assert false
243              | Cic.Variable _ -> assert false
244              | Cic.CurrentProof _ -> assert false
245              | Cic.InductiveDefinition (l,_,n,_) -> l,n 
246            ) in
247        let (_,_,_,constructors) = List.nth inductive_types tyno in
248        let constructor_types = 
249          let rec clean_up t =
250            function 
251                [] -> t
252              | a::tl -> 
253                  (match t with
254                    Cic.Prod (_,_,t') -> clean_up (S.subst a t') tl
255                   | _ -> assert false) in
256           if noparams = 0 then 
257             List.map (fun (_,t) -> t) constructors 
258           else 
259             let term_type,_ = 
260               CicTypeChecker.type_of_aux' metasenv context term
261                 CicUniv.empty_ugraph 
262             in
263             (match term_type with
264                C.Appl (hd::params) -> 
265                  let rec first_n n l =
266                    if n = 0 then []
267                    else 
268                      (match l with
269                         a::tl -> a::(first_n (n-1) tl)
270                       | _ -> assert false) in 
271                  List.map 
272                   (fun (_,t) -> 
273                      clean_up t (first_n noparams params)) constructors
274              | _ -> prerr_endline ("QUA"); assert false) in 
275        let patterns2 = 
276          List.map2 fix_lambdas_wrt_type
277            constructor_types patterns in 
278          C.MutCase (uri, tyno, outty',term',patterns2)
279    | C.Fix (funno, funs) ->
280        let fun_types = 
281          List.map (fun (n,_,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
282        C.Fix (funno,
283         List.map
284          (fun (name, no, ty, bo) ->
285            (name, no, eta_fix' context ty, eta_fix' (fun_types@context) bo)) 
286         funs)
287    | C.CoFix (funno, funs) ->
288        let fun_types = 
289          List.map (fun (n,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
290        C.CoFix (funno,
291         List.map
292          (fun (name, ty, bo) ->
293            (name, eta_fix' context ty, eta_fix' (fun_types@context) bo)) funs)
294   and fix_exp_named_subst context exp_named_subst =
295    List.rev
296     (List.fold_left
297       (fun newsubst (uri,t) ->
298         let t' = eta_fix' context t in
299         let ty =
300           let o,_ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
301             match o with
302                 Cic.Variable (_,_,ty,_,_) -> 
303                   CicSubstitution.subst_vars newsubst ty
304               | _ ->  raise ReferenceToNonVariable 
305         in
306         let t'' = fix_according_to_type ty t' [] in
307          (uri,t'')::newsubst
308       ) [] exp_named_subst)
309   in
310    eta_fix' context t
311 ;;