]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/acic_procedural/proceduralOptimizer.ml
cicDischarge: new module for discharging the explicit variables occurring in a
[helm.git] / helm / software / components / acic_procedural / proceduralOptimizer.ml
1 (* Copyright (C) 2003-2005, 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 module UM   = UriManager
27 module C    = Cic
28 module Pp   = CicPp
29 module I    = CicInspect
30 module E    = CicEnvironment
31 module S    = CicSubstitution
32 module DTI  = DoubleTypeInference
33 module HEL  = HExtlib
34 module PEH  = ProofEngineHelpers
35 module TC   = CicTypeChecker 
36 module Un   = CicUniv
37
38 module H    = ProceduralHelpers
39 module Cl   = ProceduralClassify
40
41 (* term preprocessing: optomization 1 ***************************************)
42
43 let defined_premise = "DEFINED"
44
45 let define c v =
46    let name = C.Name defined_premise in
47    let ty = H.get_type "define" c v in
48    C.LetIn (name, v, ty, C.Rel 1)
49
50 let clear_absts m =
51    let rec aux k n = function
52       | C.Lambda (s, v, t) when k > 0 -> 
53          C.Lambda (s, v, aux (pred k) n t)
54       | C.Lambda (_, _, t) when n > 0 -> 
55          aux 0 (pred n) (S.lift (-1) t)
56       | t                  when n > 0 ->
57          Printf.eprintf "CicPPP clear_absts: %u %s\n" n (Pp.ppterm t);
58          assert false 
59       | t                                 -> t
60    in 
61    aux m
62
63 let rec add_abst k = function 
64    | C.Lambda (s, v, t) when k > 0 -> C.Lambda (s, v, add_abst (pred k) t)
65    | t when k > 0 -> assert false
66    | t -> C.Lambda (C.Anonymous, C.Implicit None, S.lift 1 t)
67
68 let rec opt1_letin g es c name v w t =
69    let name = H.mk_fresh_name c name in
70    let entry = Some (name, C.Def (v, w)) in
71    let g t =
72       if DTI.does_not_occur 1 t then begin          
73          let x = S.lift (-1) t in
74          HLog.warn "Optimizer: remove 1"; opt1_proof g true c x 
75       end else 
76       let g = function
77          | C.LetIn (nname, vv, ww, tt) when H.is_proof c v ->
78             let eentry = Some (nname, C.Def (vv, ww)) in
79             let ttw = H.get_type "opt1_letin 1" (eentry :: c) tt in
80             let x = C.LetIn (nname, vv, ww,
81              C.LetIn (name, tt, ttw, S.lift_from 2 1 t)) in
82             HLog.warn "Optimizer: swap 1"; opt1_proof g true c x 
83          | v when H.is_proof c v && H.is_atomic v     ->
84             let x = S.subst v t in
85             HLog.warn "Optimizer: remove 5"; opt1_proof g true c x 
86          | v                                           ->
87             g (C.LetIn (name, v, w, t))
88       in
89       if es then opt1_term g es c v else g v
90    in
91    if es then opt1_proof g es (entry :: c) t else g t
92
93 and opt1_lambda g es c name w t =
94    let name = H.mk_fresh_name c name in
95    let entry = Some (name, C.Decl w) in
96    let g t = g (C.Lambda (name, w, t)) in
97    if es then opt1_proof g es (entry :: c) t else g t
98
99 and opt1_appl g es c t vs =
100    let g vs = 
101       let g = function      
102          | C.LetIn (mame, vv, tyty, tt) ->
103             let vs = List.map (S.lift 1) vs in
104             let x = C.LetIn (mame, vv, tyty, C.Appl (tt :: vs)) in
105             HLog.warn "Optimizer: swap 2"; opt1_proof g true c x
106          | C.Lambda (name, ww, tt) ->
107             let v, vs = List.hd vs, List.tl vs in
108             let w = H.get_type "opt1_appl 1" c v in
109             let x = C.Appl (C.LetIn (name, v, w, tt) :: vs) in
110             HLog.warn "Optimizer: remove 2"; opt1_proof g true c x
111          | C.Appl vvs              ->
112             let x = C.Appl (vvs @ vs) in
113             HLog.warn "Optimizer: nested application"; opt1_proof g true c x
114          | t                       ->
115             let rec aux d rvs = function
116                | [], _                   -> 
117                   let x = C.Appl (t :: List.rev rvs) in
118                   if d then opt1_proof g true c x else g x
119                | v :: vs, (cc, bb) :: cs ->
120                   if H.is_not_atomic v && I.S.mem 0 cc && bb then begin 
121                      HLog.warn "Optimizer: anticipate 1"; 
122                      aux true (define c v :: rvs) (vs, cs)
123                   end else 
124                      aux d (v :: rvs) (vs, cs)
125                | _, []                   -> assert false
126             in
127             let h () =
128                let classes, conclusion = Cl.classify c (H.get_type "opt1_appl 3" c t) in
129                let csno, vsno = List.length classes, List.length vs in
130                if csno < vsno then
131                   let vvs, vs = HEL.split_nth csno vs in
132                   let x = C.Appl (define c (C.Appl (t :: vvs)) :: vs) in
133                   HLog.warn "Optimizer: anticipate 2"; opt1_proof g true c x
134                else match conclusion, List.rev vs with
135                   | Some _, rv :: rvs when csno = vsno && H.is_not_atomic rv ->
136                      let x = C.Appl (t :: List.rev rvs @ [define c rv]) in
137                      HLog.warn "Optimizer: anticipate 3"; opt1_proof g true c x
138                   | _ (* Some _, _ *)                                             ->
139                      g (C.Appl (t :: vs))
140 (*                | None, _                                                ->
141                      aux false [] (vs, classes)
142 *)          in
143             let rec aux h prev = function
144                | C.LetIn (name, vv, tyty, tt) :: vs ->
145                   let t = S.lift 1 t in
146                   let prev = List.map (S.lift 1) prev in
147                   let vs = List.map (S.lift 1) vs in
148                   let y = C.Appl (t :: List.rev prev @ tt :: vs) in
149                   let ww = H.get_type "opt1_appl 2" c vv in
150                   let x = C.LetIn (name, vv, ww, y) in  
151                   HLog.warn "Optimizer: swap 3"; opt1_proof g true c x
152                | v :: vs                      -> aux h (v :: prev) vs
153                | []                           -> h ()
154             in 
155             aux h [] vs
156       in
157       if es then opt1_proof g es c t else g t
158    in
159    if es then H.list_map_cps g (fun h -> opt1_term h es c) vs else g vs
160
161 and opt1_mutcase g es c uri tyno outty arg cases =
162    let eliminator = H.get_default_eliminator c uri tyno outty in
163    let lpsno, (_, _, _, constructors) = H.get_ind_type uri tyno in
164    let ps, sort_disp = H.get_ind_parameters c arg in
165    let lps, rps = HEL.split_nth lpsno ps in
166    let rpsno = List.length rps in
167    let predicate = clear_absts rpsno (1 - sort_disp) outty in   
168    let is_recursive t =
169       I.S.mem tyno (I.get_mutinds_of_uri uri t) 
170    in
171    let map2 case (_, cty) = 
172       let map (h, case, k) (_, premise) = 
173          if h > 0 then pred h, case, k else
174          if is_recursive premise then 
175             0, add_abst k case, k + 2 
176          else
177             0, case, succ k
178       in
179       let premises, _ = PEH.split_with_whd (c, cty) in
180       let _, lifted_case, _ =
181          List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
182       in
183       lifted_case
184    in
185    let lifted_cases = List.map2 map2 cases constructors in
186    let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
187    let x = H.refine c (C.Appl args) in
188    HLog.warn "Optimizer: remove 3"; opt1_proof g es c x
189
190 and opt1_cast g es c t w =
191    let g t = HLog.warn "Optimizer: remove 4"; g t in
192    if es then  opt1_proof g es c t else g t
193
194 and opt1_other g es c t = g t 
195
196 and opt1_proof g es c = function 
197    | C.LetIn (name, v, ty, t)   -> opt1_letin g es c name v ty t
198    | C.Lambda (name, w, t)      -> opt1_lambda g es c name w t
199    | C.Appl (t :: v :: vs)      -> opt1_appl g es c t (v :: vs)
200    | C.Appl [t]                 -> opt1_proof g es c t
201    | C.MutCase (u, n, t, v, ws) -> opt1_mutcase g es c u n t v ws
202    | C.Cast (t, w)              -> opt1_cast g es c t w
203    | t                          -> opt1_other g es c t
204
205 and opt1_term g es c t = 
206    if H.is_proof c t then opt1_proof g es c t else g t
207
208 (* term preprocessing: optomization 2 ***************************************)
209
210 let expanded_premise = "EXPANDED"
211
212 let eta_expand g tys t =
213    assert (tys <> []);
214    let name i = Printf.sprintf "%s%u" expanded_premise i in 
215    let lambda i ty t = C.Lambda (C.Name (name i), ty, t) in
216    let arg i = C.Rel (succ i) in
217    let rec aux i f a = function
218       | []            -> f, a 
219       | (_, ty) :: tl -> aux (succ i) (H.compose f (lambda i ty)) (arg i :: a) tl
220    in
221    let n = List.length tys in
222    let absts, args = aux 0 H.identity [] tys in
223    let t = match S.lift n t with
224       | C.Appl ts -> C.Appl (ts @ args)
225       | t         -> C.Appl (t :: args)
226    in
227    g (absts t)
228
229 let rec opt2_letin g c name v w t =
230    let entry = Some (name, C.Def (v, w)) in
231    let g t = 
232       let g v = g (C.LetIn (name, v, w, t)) in
233       opt2_term g c v
234    in
235    opt2_proof g (entry :: c) t
236
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
241
242 and opt2_appl g c t vs =
243    let g 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 "opt2_appl 1" c t) in
247       if vsno < csno then 
248          let tys, _ = PEH.split_with_whd (c, H.get_type "opt2_appl 2" 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
252       else g x 
253    in
254    H.list_map_cps g (fun h -> opt2_term h c) vs
255
256 and opt2_other g c t =
257    let tys, csno = PEH.split_with_whd (c, H.get_type "opt2_other" 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 
261    end else g t
262
263 and opt2_proof g c = function 
264    | C.LetIn (name, v, w, t) -> opt2_letin g c name v w t
265    | C.Lambda (name, w, t)   -> opt2_lambda g c name w t
266    | C.Appl (t :: vs)        -> opt2_appl g c t vs
267    | t                       -> opt2_other g c t
268
269 and opt2_term g c t = 
270    if H.is_proof c t then opt2_proof g c t else g t
271
272 (* object preprocessing *****************************************************)
273
274 let optimize_obj = function
275    | C.Constant (name, Some bo, ty, pars, attrs) ->
276       let bo, ty = H.cic_bc [] bo, H.cic_bc [] ty in 
277       let g bo = 
278          Printf.eprintf "Optimized : %s\nPost Nodes: %u\n" 
279             (Pp.ppterm bo) (I.count_nodes 0 bo);
280          prerr_string "H.pp_term : ";
281          H.pp_term prerr_string [] [] bo; prerr_newline ();
282          let _ = H.get_type "opt" [] (C.Cast (bo, ty)) in
283          C.Constant (name, Some bo, ty, pars, attrs)
284       in
285       Printf.eprintf "BEGIN: %s\nPre Nodes : %u\n" 
286          name (I.count_nodes 0 bo);
287       begin try opt1_term g (* (opt2_term g []) *) true [] bo with
288         | E.Object_not_found uri ->
289            let msg = "optimize_obj: object not found: " ^ UM.string_of_uri uri in
290            failwith msg 
291         | e                      -> 
292            let msg = "optimize_obj: " ^ Printexc.to_string e in
293            failwith msg
294       end
295    | obj                                         -> obj