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/.
29 module S = CicSubstitution
30 module DTI = DoubleTypeInference
32 module PEH = ProofEngineHelpers
34 module H = ProceduralHelpers
35 module Cl = ProceduralClassify
37 (* term preprocessing: optomization 1 ***************************************)
39 let defined_premise = "DEFINED"
42 let name = C.Name defined_premise in
43 (*CSC: here we need the type of v *)
44 C.LetIn (name, v, assert false, C.Rel 1)
47 let rec aux k n = function
48 | C.Lambda (s, v, t) when k > 0 ->
49 C.Lambda (s, v, aux (pred k) n t)
50 | C.Lambda (_, _, t) when n > 0 ->
51 aux 0 (pred n) (S.lift (-1) t)
53 Printf.eprintf "CicPPP clear_absts: %u %s\n" n (Pp.ppterm t);
59 let rec add_abst k = function
60 | C.Lambda (s, v, t) when k > 0 -> C.Lambda (s, v, add_abst (pred k) t)
61 | t when k > 0 -> assert false
62 | t -> C.Lambda (C.Anonymous, C.Implicit None, S.lift 1 t)
64 let rec opt1_letin g es c name v t =
65 let name = H.mk_fresh_name c name in
66 (*CSC: here we need the type of v *)
67 let entry = Some (name, C.Def (v, assert false)) in
69 if DTI.does_not_occur 1 t then begin
70 let x = S.lift (-1) t in
71 HLog.warn "Optimizer: remove 1"; opt1_proof g true c x
74 | C.LetIn (nname, vv, tyty, tt) when H.is_proof c v ->
75 (*CSC: here we need the type of v *)
76 let x = C.LetIn (nname, vv, tyty,
77 C.LetIn (name, tt, assert false, S.lift_from 2 1 t)) in
78 HLog.warn "Optimizer: swap 1"; opt1_proof g true c x
79 | v when H.is_proof c v && H.is_atomic v ->
80 let x = S.subst v t in
81 HLog.warn "Optimizer: remove 5"; opt1_proof g true c x
83 (*CSC: here we need the type of v *)
84 g (C.LetIn (name, v, assert false, t))
86 if es then opt1_term g es c v else g v
88 if es then opt1_proof g es (entry :: c) t else g t
90 and opt1_lambda g es c name w t =
91 let name = H.mk_fresh_name c name in
92 let entry = Some (name, C.Decl w) in
93 let g t = g (C.Lambda (name, w, t)) in
94 if es then opt1_proof g es (entry :: c) t else g t
96 and opt1_appl g es c t vs =
99 | C.LetIn (mame, vv, tyty, tt) ->
100 let vs = List.map (S.lift 1) vs in
101 let x = C.LetIn (mame, vv, tyty, C.Appl (tt :: vs)) in
102 HLog.warn "Optimizer: swap 2"; opt1_proof g true c x
103 | C.Lambda (name, ww, tt) ->
104 let v, vs = List.hd vs, List.tl vs in
105 (*CSC: here we need the type of v *)
106 let x = C.Appl (C.LetIn (name, v, assert false, tt) :: vs) in
107 HLog.warn "Optimizer: remove 2"; opt1_proof g true c x
109 let x = C.Appl (vvs @ vs) in
110 HLog.warn "Optimizer: nested application"; opt1_proof g true c x
112 let rec aux d rvs = function
114 let x = C.Appl (t :: List.rev rvs) in
115 if d then opt1_proof g true c x else g x
116 | v :: vs, (cc, bb) :: cs ->
117 if H.is_not_atomic v && I.S.mem 0 cc && bb then begin
118 HLog.warn "Optimizer: anticipate 1";
119 aux true (define v :: rvs) (vs, cs)
121 aux d (v :: rvs) (vs, cs)
122 | _, [] -> assert false
125 let classes, conclusion = Cl.classify c (H.get_type c t) in
126 let csno, vsno = List.length classes, List.length vs in
128 let vvs, vs = HEL.split_nth csno vs in
129 let x = C.Appl (define (C.Appl (t :: vvs)) :: vs) in
130 HLog.warn "Optimizer: anticipate 2"; opt1_proof g true c x
131 else match conclusion, List.rev vs with
132 | Some _, rv :: rvs when csno = vsno && H.is_not_atomic rv ->
133 let x = C.Appl (t :: List.rev rvs @ [define rv]) in
134 HLog.warn "Optimizer: anticipate 3"; opt1_proof g true c x
135 | _ (* Some _, _ *) ->
138 aux false [] (vs, classes)
140 let rec aux h prev = function
141 | C.LetIn (name, vv, tyty, tt) :: vs ->
142 let t = S.lift 1 t in
143 let prev = List.map (S.lift 1) prev in
144 let vs = List.map (S.lift 1) vs in
145 let y = C.Appl (t :: List.rev prev @ tt :: vs) in
146 (*CSC: here we need the type of vv *)
147 let x = C.LetIn (name, vv, assert false, y) in
148 HLog.warn "Optimizer: swap 3"; opt1_proof g true c x
149 | v :: vs -> aux h (v :: prev) vs
154 if es then opt1_proof g es c t else g t
156 if es then H.list_map_cps g (fun h -> opt1_term h es c) vs else g vs
158 and opt1_mutcase g es c uri tyno outty arg cases =
159 let eliminator = H.get_default_eliminator c uri tyno outty in
160 let lpsno, (_, _, _, constructors) = H.get_ind_type uri tyno in
161 let ps, sort_disp = H.get_ind_parameters c arg in
162 let lps, rps = HEL.split_nth lpsno ps in
163 let rpsno = List.length rps in
164 let predicate = clear_absts rpsno (1 - sort_disp) outty in
166 I.S.mem tyno (I.get_mutinds_of_uri uri t)
168 let map2 case (_, cty) =
169 let map (h, case, k) (_, premise) =
170 if h > 0 then pred h, case, k else
171 if is_recursive premise then
172 0, add_abst k case, k + 2
176 let premises, _ = PEH.split_with_whd (c, cty) in
177 let _, lifted_case, _ =
178 List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
182 let lifted_cases = List.map2 map2 cases constructors in
183 let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
184 let x = H.refine c (C.Appl args) in
185 HLog.warn "Optimizer: remove 3"; opt1_proof g es c x
187 and opt1_cast g es c t w =
188 let g t = HLog.warn "Optimizer: remove 4"; g t in
189 if es then opt1_proof g es c t else g t
191 and opt1_other g es c t = g t
193 and opt1_proof g es c = function
194 (*CSC: what to do now that we have also ty? *)
195 | C.LetIn (name, v, ty, t) -> assert false (*opt1_letin g es c name v t*)
196 | C.Lambda (name, w, t) -> opt1_lambda g es c name w t
197 | C.Appl (t :: v :: vs) -> opt1_appl g es c t (v :: vs)
198 | C.Appl [t] -> opt1_proof g es c t
199 | C.MutCase (u, n, t, v, ws) -> opt1_mutcase g es c u n t v ws
200 | C.Cast (t, w) -> opt1_cast g es c t w
201 | t -> opt1_other g es c t
203 and opt1_term g es c t =
204 if H.is_proof c t then opt1_proof g es c t else g t
206 (* term preprocessing: optomization 2 ***************************************)
208 let expanded_premise = "EXPANDED"
210 let eta_expand g tys t =
212 let name i = Printf.sprintf "%s%u" expanded_premise i in
213 let lambda i ty t = C.Lambda (C.Name (name i), ty, t) in
214 let arg i = C.Rel (succ i) in
215 let rec aux i f a = function
217 | (_, ty) :: tl -> aux (succ i) (H.compose f (lambda i ty)) (arg i :: a) tl
219 let n = List.length tys in
220 let absts, args = aux 0 H.identity [] tys in
221 let t = match S.lift n t with
222 | C.Appl ts -> C.Appl (ts @ args)
223 | t -> C.Appl (t :: args)
227 let rec opt2_letin g c name v t =
228 (*CSC: here we need the type of v *)
229 let entry = Some (name, C.Def (v, assert false)) in
231 (*CSC: here we need the type of v *)
232 let g v = g (C.LetIn (name, v, assert false, t)) in
235 opt2_proof g (entry :: c) t
237 and opt2_lambda g c name w t =
238 let entry = Some (name, C.Decl w) in
239 let g t = g (C.Lambda (name, w, t)) in
240 opt2_proof g (entry :: c) t
242 and opt2_appl g c t vs =
244 let x = C.Appl (t :: vs) in
245 let vsno = List.length vs in
246 let _, csno = PEH.split_with_whd (c, H.get_type c t) in
248 let tys, _ = PEH.split_with_whd (c, H.get_type c x) in
249 let tys = List.rev (List.tl tys) in
250 let tys, _ = HEL.split_nth (csno - vsno) tys in
251 HLog.warn "Optimizer: eta 1"; eta_expand g tys x
254 H.list_map_cps g (fun h -> opt2_term h c) vs
256 and opt2_other g c t =
257 let tys, csno = PEH.split_with_whd (c, H.get_type c t) in
258 if csno > 0 then begin
259 let tys = List.rev (List.tl tys) in
260 HLog.warn "Optimizer: eta 2"; eta_expand g tys t
263 and opt2_proof g c = function
264 (*CSC: what to do now that we have also ty? *)
265 | C.LetIn (name, v, ty, t) -> assert false (*opt2_letin g c name v t*)
266 | C.Lambda (name, w, t) -> opt2_lambda g c name w t
267 | C.Appl (t :: vs) -> opt2_appl g c t vs
268 | t -> opt2_other g c t
270 and opt2_term g c t =
271 if H.is_proof c t then opt2_proof g c t else g t
273 (* object preprocessing *****************************************************)
275 let optimize_obj = function
276 | C.Constant (name, Some bo, ty, pars, attrs) ->
277 let bo, ty = H.cic_bc [] bo, H.cic_bc [] ty in
279 Printf.eprintf "Optimized : %s\nPost Nodes: %u\n"
280 (Pp.ppterm bo) (I.count_nodes 0 bo);
281 let _ = H.get_type [] (C.Cast (bo, ty)) in
282 C.Constant (name, Some bo, ty, pars, attrs)
284 Printf.eprintf "BEGIN: %s\nPre Nodes : %u\n"
285 name (I.count_nodes 0 bo);
286 begin try opt1_term g (* (opt2_term g []) *) true [] bo
287 with e -> failwith ("PPP: " ^ Printexc.to_string e) end