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