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