1 (* Copyright (C) 2000, HELM Team.
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.
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.
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.
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,
22 * For details, see the HELM World-Wide-Web page,
23 * http://cs.unibo.it/helm/.
26 exception ReferenceToVariable;;
27 exception RferenceToCurrentProof;;
28 exception ReferenceToInductiveDefinition;;
31 let rec fix_lambdas_wrt_type ty te =
33 let module S = CicSubstitution in
34 (* prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
37 (match CicReduction.whd [] te with
39 C.Lambda (n,s,fix_lambdas_wrt_type ty' te')
43 C.Prod (_,s,ty) -> s::(get_sources ty)
45 let sources = get_sources ty in
46 let no_sources = List.length sources in
47 let rec mk_rels n shift =
49 else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
50 let t' = S.lift no_sources t in
55 (C.Name "w",t',C.Appl ((C.Rel 1)::(mk_rels no_sources 1)))
57 C.Appl (t'::(mk_rels no_sources 0)) in
59 (fun source t -> C.Lambda (C.Name "y",source,t))
64 let rec fix_lambdas_wrt_type ty te =
66 let module S = CicSubstitution in
67 (* prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
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 ->
74 C.Prod (_,s,ty) -> s::(get_sources ty)
76 let sources = get_sources ty in
77 let no_sources = List.length sources in
78 let rec mk_rels n shift =
80 else (C.Rel (n + shift))::(mk_rels (n - 1) shift) in
81 let t' = S.lift no_sources t in
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
88 (fun source t -> C.Lambda (C.Name "y",CicReduction.whd [] source,t)) sources t2
93 let rec fix_lambdas_wrt_type ty te =
95 let module S = CicSubstitution in
96 (* prerr_endline ("entering fix_lambdas: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm te); *)
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,
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); *)
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]))
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 =
127 C.Prod (_,_,t) -> 1 + (count_prods t)
129 let expected_arity = count_prods ty in
130 let rec aux n ty tl res =
137 | [a] -> C.Appl (a::tl)
139 (* prerr_endline ("******* too many args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
142 C.Appl res, C.Appl (C.Rel 1::(List.map (S.lift 1) tl))))
144 let name,source,target =
146 C.Prod (C.Name _ as n,s,t) -> n,s,t
147 | C.Prod (C.Anonymous, s,t) -> C.Name "z",s,t
148 | _ -> (* prods number may only increase for substitution *)
152 (* prerr_endline ("******* too few args: type=" ^ CicPp.ppterm ty ^ "term=" ^ CicPp.ppterm (C.Appl res)); *)
153 let res' = List.map (S.lift 1) res in
155 (name, source, aux (n-1) target [] (res'@[C.Rel 1]))
157 let hd' = fix_lambdas_wrt_type source hd in
158 (* (prerr_endline ("++++++prima :" ^(CicPp.ppterm hd));
159 prerr_endline ("++++++dopo :" ^(CicPp.ppterm hd'))); *)
160 aux (n-1) (S.subst hd' target) tl' (res@[hd']) in
161 aux expected_arity ty tl [hd]
164 let eta_fix metasenv t =
165 let rec eta_fix' context t =
166 prerr_endline ("entering aux with: term=" ^ CicPp.ppterm t);
168 let module C = Cic in
169 let module S = CicSubstitution in
172 | C.Var (uri,exp_named_subst) ->
173 let exp_named_subst' =
175 (function i,t -> i, (eta_fix' context t)) exp_named_subst
177 C.Var (uri,exp_named_subst')
179 let (_,canonical_context,_) =
180 List.find (function (m,_,_) -> n = m) metasenv
187 | _, Some t -> Some (eta_fix' context t)
188 | Some _, None -> assert false (* due to typing rules *))
192 | C.Sort s -> C.Sort s
193 | C.Implicit -> C.Implicit
194 | C.Cast (v,t) -> C.Cast (eta_fix' context v, eta_fix' context t)
197 (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
198 | C.Lambda (n,s,t) ->
200 (n, eta_fix' context s, eta_fix' ((Some (n,(C.Decl s)))::context) t)
203 (n, eta_fix' context s, eta_fix' ((Some (n,(C.Def s)))::context) t)
204 | C.Appl l as appl ->
205 let l' = List.map (eta_fix' context) l
208 C.Const(uri,exp_named_subst)::l'' ->
210 (match CicEnvironment.get_obj uri with
211 C.Constant (_,_,ty,_) -> ty
212 | C.Variable _ -> raise ReferenceToVariable
213 | C.CurrentProof (_,_,_,_,params) -> raise RferenceToCurrentProof
214 | C.InductiveDefinition _ -> raise ReferenceToInductiveDefinition
217 let result = fix_according_to_type constant_type (C.Const(uri,exp_named_subst)) l'' in
218 if not (CicReduction.are_convertible [] appl result) then
219 (prerr_endline ("prima :" ^(CicPp.ppterm appl));
220 prerr_endline ("dopo :" ^(CicPp.ppterm result)));
223 | C.Const (uri,exp_named_subst) ->
224 let exp_named_subst' =
226 (function i,t -> i, (eta_fix' context t)) exp_named_subst
228 C.Const (uri,exp_named_subst')
229 | C.MutInd (uri,tyno,exp_named_subst) ->
230 let exp_named_subst' =
232 (function i,t -> i, (eta_fix' context t)) exp_named_subst
234 C.MutInd (uri, tyno, exp_named_subst')
235 | C.MutConstruct (uri,tyno,consno,exp_named_subst) ->
236 let exp_named_subst' =
238 (function i,t -> i, (eta_fix' context t)) exp_named_subst
240 C.MutConstruct (uri, tyno, consno, exp_named_subst')
241 | C.MutCase (uri, tyno, outty, term, patterns) as prima ->
242 let outty' = eta_fix' context outty in
243 let term' = eta_fix' context term in
244 let patterns' = List.map (eta_fix' context) patterns in
245 let inductive_types,noparams =
246 (match CicEnvironment.get_obj uri with
247 Cic.Constant _ -> assert false
248 | Cic.Variable _ -> assert false
249 | Cic.CurrentProof _ -> assert false
250 | Cic.InductiveDefinition (l,_,n) -> l,n
252 let (_,_,_,constructors) = List.nth inductive_types tyno in
253 prerr_endline ("QUI");
254 let constructor_types =
260 Cic.Prod (_,_,t') -> clean_up (S.subst a t') tl
261 | _ -> assert false) in
263 List.map (fun (_,t) -> t) constructors
266 CicTypeChecker.type_of_aux' metasenv context term in
267 (match term_type with
268 C.Appl (hd::params) ->
269 List.map (fun (_,t) -> clean_up t params) constructors
270 | _ -> prerr_endline ("QUA"); assert false) in
272 List.map2 fix_lambdas_wrt_type
273 constructor_types patterns in
275 C.MutCase (uri, tyno, outty',term',patterns2) in
276 if not (CicReduction.are_convertible [] prima dopo) then
277 (prerr_endline ("prima :" ^(CicPp.ppterm prima));
278 prerr_endline ("dopo :" ^(CicPp.ppterm dopo)));
280 | C.Fix (funno, funs) ->
282 List.map (fun (n,_,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
285 (fun (name, no, ty, bo) ->
286 (name, no, eta_fix' context ty, eta_fix' (fun_types@context) bo))
288 | C.CoFix (funno, funs) ->
290 List.map (fun (n,ty,_) -> Some (C.Name n,(Cic.Decl ty))) funs in
293 (fun (name, ty, bo) ->
294 (name, eta_fix' context ty, eta_fix' (fun_types@context) bo)) funs)