1 (* Copyright (C) 2003-2005, 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 module UM = UriManager
31 module E = CicEnvironment
32 module S = CicSubstitution
33 module Rd = CicReduction
34 module TC = CicTypeChecker
36 module DTI = DoubleTypeInference
39 (* helper functions *********************************************************)
43 let comp f g x = f (g x)
46 let add s v c = Some (s, C.Decl v) :: c in
47 let rec aux whd a n c = function
48 | C.Prod (s, v, t) -> aux false (v :: a) (succ n) (add s v c) t
49 | v when whd -> v :: a, n
50 | v -> aux true a n c (Rd.whd ~delta:true c v)
55 try let ty, _ = TC.type_of_aux' [] c t Un.empty_ugraph in ty
57 Printf.eprintf "TC: context: %s\n" (Pp.ppcontext c);
58 Printf.eprintf "TC: term : %s\n" (Pp.ppterm t);
62 try let t, _, _, _ = Rf.type_of_aux' [] c t Un.empty_ugraph in t
64 Printf.eprintf "REFINE EROR: %s\n" (Printexc.to_string e);
65 Printf.eprintf "Ref: context: %s\n" (Pp.ppcontext c);
66 Printf.eprintf "Ref: term : %s\n" (Pp.ppterm t);
75 match get_tail c (get_type c (get_type c t)) with
76 | C.Sort C.Prop -> true
80 let is_not_atomic = function
86 | C.MutConstruct _ -> false
90 let rec aux k n = function
91 | C.Lambda (s, v, t) when k > 0 ->
92 C.Lambda (s, v, aux (pred k) n t)
93 | C.Lambda (_, _, t) when n > 0 ->
94 aux 0 (pred n) (S.lift (-1) t)
96 Printf.eprintf "CicPPP clear_absts: %u %s\n" n (Pp.ppterm t);
102 let rec add_abst k = function
103 | C.Lambda (s, v, t) when k > 0 -> C.Lambda (s, v, add_abst (pred k) t)
104 | t when k > 0 -> assert false
105 | t -> C.Lambda (C.Anonymous, C.Implicit None, S.lift 1 t)
107 let get_ind_type uri tyno =
108 match E.get_obj Un.empty_ugraph uri with
109 | C.InductiveDefinition (tys, _, lpsno, _), _ -> lpsno, List.nth tys tyno
112 let get_ind_parameters c t =
113 let ty = get_type c t in
114 let ps = match get_tail c ty with
116 | C.Appl (C.MutInd _ :: args) -> args
119 let disp = match get_tail c (get_type c ty) with
126 let get_default_eliminator context uri tyno ty =
127 let _, (name, _, _, _) = get_ind_type uri tyno in
128 let ext = match get_tail context (get_type context ty) with
129 | C.Sort C.Prop -> "_ind"
130 | C.Sort C.Set -> "_rec"
131 | C.Sort C.CProp -> "_rec"
132 | C.Sort (C.Type _) -> "_rect"
134 Printf.eprintf "CicPPP get_default_eliminator: %s\n" (Pp.ppterm t);
137 let buri = UM.buri_of_uri uri in
138 let uri = UM.uri_of_string (buri ^ "/" ^ name ^ ext ^ ".con") in
141 let add g htbl t proof decurry =
142 if proof then C.CicHash.add htbl t decurry;
147 let decurry = C.CicHash.find htbl t in g t true decurry
148 with Not_found -> g t false 0
150 (* term preprocessing *******************************************************)
152 let expanded_premise = "EXPANDED"
154 let defined_premise = "DEFINED"
156 let eta_expand g tys t =
158 let name i = Printf.sprintf "%s%u" expanded_premise i in
159 let lambda i ty t = C.Lambda (C.Name (name i), ty, t) in
160 let arg i = C.Rel (succ i) in
161 let rec aux i f a = function
163 | ty :: tl -> aux (succ i) (comp f (lambda i ty)) (arg i :: a) tl
165 let n = List.length tys in
166 let absts, args = aux 0 identity [] tys in
167 let t = match S.lift n t with
168 | C.Appl ts -> C.Appl (ts @ args)
169 | t -> C.Appl (t :: args)
173 let get_tys c decurry =
174 let rec aux n = function
175 (* | C.Appl (hd :: tl) -> aux (n + List.length tl) hd *)
177 let tys, _ = split c (get_type c t) in
178 let _, tys = HEL.split_nth n (List.rev tys) in
179 let tys, _ = HEL.split_nth decurry tys in
184 let eta_fix c t proof decurry =
185 let rec aux g c = function
186 | C.LetIn (name, v, t) ->
187 let g t = g (C.LetIn (name, v, t)) in
188 let entry = Some (name, C.Def (v, None)) in
190 | t -> eta_expand g (get_tys c decurry t) t
192 if proof && decurry > 0 then aux identity c t else t
194 let rec pp_cast g ht es c t v =
195 if true then pp_proof g ht es c t else find g ht t
197 and pp_lambda g ht es c name v t =
198 let name = if DTI.does_not_occur 1 t then C.Anonymous else name in
199 let entry = Some (name, C.Decl v) in
201 let t = eta_fix (entry :: c) t true decurry in
202 g (C.Lambda (name, v, t)) true 0 in
203 if true then pp_proof g ht es (entry :: c) t else find g ht t
205 and pp_letin g ht es c name v t =
206 let entry = Some (name, C.Def (v, None)) in
208 if DTI.does_not_occur 1 t then g (S.lift (-1) t) true decurry else
209 let g v proof d = match v with
210 | C.LetIn (mame, w, u) when proof ->
211 let x = C.LetIn (mame, w, C.LetIn (name, u, S.lift_from 2 1 t)) in
212 pp_proof g ht false c x
214 let v = eta_fix c v proof d in
215 g (C.LetIn (name, v, t)) true decurry
217 if true then pp_term g ht es c v else find g ht v
219 if true then pp_proof g ht es (entry :: c) t else find g ht t
221 and pp_appl_one g ht es c t v =
225 | t, C.LetIn (mame, w, u) when proof ->
226 let x = C.LetIn (mame, w, C.Appl [S.lift 1 t; u]) in
227 pp_proof g ht false c x
228 | C.LetIn (mame, w, u), v ->
229 let x = C.LetIn (mame, w, C.Appl [u; S.lift 1 v]) in
230 pp_proof g ht false c x
231 | C.Appl ts, v when decurry > 0 ->
232 let v = eta_fix c v proof d in
233 g (C.Appl (List.append ts [v])) true (pred decurry)
234 | t, v when is_not_atomic t ->
235 let mame = C.Name defined_premise in
236 let x = C.LetIn (mame, t, C.Appl [C.Rel 1; S.lift 1 v]) in
237 pp_proof g ht false c x
239 let v = eta_fix c v proof d in
240 g (C.Appl [t; v]) true (pred decurry)
242 if true then pp_term g ht es c v else find g ht v
244 if true then pp_proof g ht es c t else find g ht t
246 and pp_appl g ht es c t = function
247 | [] -> pp_proof g ht es c t
248 | [v] -> pp_appl_one g ht es c t v
250 let x = C.Appl (C.Appl [t; v1] :: v2 :: vs) in
253 and pp_atomic g ht es c t =
254 let _, premsno = split c (get_type c t) in
257 and pp_mutcase g ht es c uri tyno outty arg cases =
258 let eliminator = get_default_eliminator c uri tyno outty in
259 let lpsno, (_, _, _, constructors) = get_ind_type uri tyno in
260 let ps, sort_disp = get_ind_parameters c arg in
261 let lps, rps = HEL.split_nth lpsno ps in
262 let rpsno = List.length rps in
263 let predicate = clear_absts rpsno (1 - sort_disp) outty in
265 I.S.mem tyno (I.get_mutinds_of_uri uri t)
267 let map2 case (_, cty) =
268 let map (h, case, k) premise =
269 if h > 0 then pred h, case, k else
270 if is_recursive premise then
271 0, add_abst k case, k + 2
275 let premises, _ = split c cty in
276 let _, lifted_case, _ =
277 List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
281 let lifted_cases = List.map2 map2 cases constructors in
282 let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
283 let x = refine c (C.Appl args) in
286 and pp_proof g ht es c t =
287 (* Printf.eprintf "IN: |- %s\n" (*CicPp.ppcontext c*) (CicPp.ppterm t);
288 let g t proof decurry =
289 Printf.eprintf "OUT: %b %u |- %s\n" proof decurry (CicPp.ppterm t);
292 (* let g t proof decurry = add g ht t proof decurry in *)
294 | C.Cast (t, v) -> pp_cast g ht es c t v
295 | C.Lambda (name, v, t) -> pp_lambda g ht es c name v t
296 | C.LetIn (name, v, t) -> pp_letin g ht es c name v t
297 | C.Appl (t :: vs) -> pp_appl g ht es c t vs
298 | C.MutCase (u, n, t, v, ws) -> pp_mutcase g ht es c u n t v ws
299 | t -> pp_atomic g ht es c t
301 and pp_term g ht es c t =
302 if is_proof c t then pp_proof g ht es c t else g t false 0
304 (* object preprocessing *****************************************************)
306 let pp_obj = function
307 | C.Constant (name, Some bo, ty, pars, attrs) ->
308 let g bo proof decurry =
309 let bo = eta_fix [] bo proof decurry in
310 C.Constant (name, Some bo, ty, pars, attrs)
312 let ht = C.CicHash.create 1 in
313 Printf.eprintf "BEGIN: %s\n" name;
314 begin try pp_term g ht true [] bo
315 with e -> failwith ("PPP: " ^ Printexc.to_string e) end