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