components/acic_procedural/proceduralPreprocess.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 Un   = CicUniv
  30 module I    = CicInspect
  31 module E    = CicEnvironment
  32 module S    = CicSubstitution
  33 module TC   = CicTypeChecker
  34 module Rf   = CicRefine
  35 module DTI  = DoubleTypeInference
  36 module HEL  = HExtlib
  37 module PEH  = ProofEngineHelpers
  38
  39 module Cl   = ProceduralClassify
  40
  41 (* helper functions *********************************************************)
  42
  43 let rec list_map_cps g map = function
  44    | []       -> g []
  45    | hd :: tl ->
  46       let h hd =
  47          let g tl = g (hd :: tl) in
  48          list_map_cps g map tl
  49       in
  50       map h hd
  51
  52 let identity x = x
  53
  54 let comp f g x = f (g x)
  55
  56 let refine c t =
  57    try let t, _, _, _ = Rf.type_of_aux' [] c t Un.empty_ugraph in t
  58    with e ->
  59       Printf.eprintf "REFINE EROR: %s\n" (Printexc.to_string e);
  60       Printf.eprintf "Ref: context: %s\n" (Pp.ppcontext c);
  61       Printf.eprintf "Ref: term   : %s\n" (Pp.ppterm t);
  62       raise e
  63
  64 let get_type c t =
  65    try let ty, _ = TC.type_of_aux' [] c t Un.empty_ugraph in ty
  66    with e ->
  67       Printf.eprintf "TC: context: %s\n" (Pp.ppcontext c);
  68       Printf.eprintf "TC: term   : %s\n" (Pp.ppterm t);
  69       raise e
  70
  71 let get_tail c t =
  72    match PEH.split_with_whd (c, t) with
  73       | (_, hd) :: _, _ -> hd
  74       | _               -> assert false
  75
  76 let is_proof c t =
  77    match get_tail c (get_type c (get_type c t)) with
  78       | C.Sort C.Prop -> true
  79       | C.Sort _      -> false
  80       | _             -> assert false
  81
  82 let is_not_atomic = function
  83    | C.Sort _
  84    | C.Rel _
  85    | C.Const _
  86    | C.Var _
  87    | C.MutInd _
  88    | C.MutConstruct _ -> false
  89    | _                -> true
  90
  91 let get_ind_type uri tyno =
  92    match E.get_obj Un.empty_ugraph uri with
  93       | C.InductiveDefinition (tys, _, lpsno, _), _ -> lpsno, List.nth tys tyno
  94       | _                                           -> assert false
  95
  96 let get_default_eliminator context uri tyno ty =
  97    let _, (name, _, _, _) = get_ind_type uri tyno in
  98    let ext = match get_tail context (get_type context ty) with
  99       | C.Sort C.Prop     -> "_ind"
 100       | C.Sort C.Set      -> "_rec"
 101       | C.Sort C.CProp    -> "_rec"
 102       | C.Sort (C.Type _) -> "_rect"
 103       | t                 ->
 104          Printf.eprintf "CicPPP get_default_eliminator: %s\n" (Pp.ppterm t);
 105          assert false
 106    in
 107    let buri = UM.buri_of_uri uri in
 108    let uri = UM.uri_of_string (buri ^ "/" ^ name ^ ext ^ ".con") in
 109    C.Const (uri, [])
 110
 111 let get_ind_parameters c t =
 112    let ty = get_type c t in
 113    let ps = match get_tail c ty with
 114       | C.MutInd _                  -> []
 115       | C.Appl (C.MutInd _ :: args) -> args
 116       | _                           -> assert false
 117    in
 118    let disp = match get_tail c (get_type c ty) with
 119       | C.Sort C.Prop -> 0
 120       | C.Sort _      -> 1
 121       | _             -> assert false
 122    in
 123    ps, disp
 124
 125 (* term preprocessing: optomization 1 ***************************************)
 126
 127 let defined_premise = "DEFINED"
 128
 129 let define c v =
 130    let name = C.Name defined_premise in
 131    C.LetIn (name, v, C.Rel 1)
 132
 133 let clear_absts m =
 134    let rec aux k n = function
 135       | C.Lambda (s, v, t) when k > 0    ->
 136          C.Lambda (s, v, aux (pred k) n t)
 137       | C.Lambda (_, _, t) when n > 0    ->
 138          aux 0 (pred n) (S.lift (-1) t)
 139       | t                     when n > 0 ->
 140          Printf.eprintf "CicPPP clear_absts: %u %s\n" n (Pp.ppterm t);
 141          assert false
 142       | t                                 -> t
 143    in
 144    aux m
 145
 146 let rec add_abst k = function
 147    | C.Lambda (s, v, t) when k > 0 -> C.Lambda (s, v, add_abst (pred k) t)
 148    | t when k > 0 -> assert false
 149    | t -> C.Lambda (C.Anonymous, C.Implicit None, S.lift 1 t)
 150
 151 let rec opt1_letin g es c name v t =
 152    let entry = Some (name, C.Def (v, None)) in
 153    let g t =
 154       if DTI.does_not_occur 1 t then begin
 155          HLog.warn "Optimizer: remove 1"; g (S.lift (-1) t)
 156       end else
 157       let g = function
 158          | C.LetIn (nname, vv, tt) when is_proof c v ->
 159             let x = C.LetIn (nname, vv, C.LetIn (name, tt, S.lift_from 2 1 t)) in
 160             HLog.warn "Optimizer: swap 1"; opt1_proof g false c x
 161          | v                               ->
 162             g (C.LetIn (name, v, t))
 163       in
 164       if es then opt1_term g es c v else g v
 165    in
 166    if es then opt1_proof g es (entry :: c) t else g t
 167
 168 and opt1_lambda g es c name w t =
 169    let entry = Some (name, C.Decl w) in
 170    let g t =
 171       let name = if DTI.does_not_occur 1 t then C.Anonymous else name in
 172       g (C.Lambda (name, w, t))
 173    in
 174    if es then opt1_proof g es (entry :: c) t else g t
 175
 176 and opt1_appl g es c t vs =
 177    let g vs =
 178       let g = function
 179          | C.LetIn (mame, vv, tt) ->
 180             let vs = List.map (S.lift 1) vs in
 181             let x = C.LetIn (mame, vv, C.Appl (tt :: vs)) in
 182             HLog.warn "Optimizer: swap 2"; opt1_proof g false c x
 183          | C.Lambda (name, ww, tt) ->
 184             let v, vs = List.hd vs, List.tl vs in
 185             let x = C.Appl (C.LetIn (name, v, tt) :: vs) in
 186             HLog.warn "Optimizer: remove 2"; opt1_proof g false c x
 187          | C.Appl vvs              ->
 188             let x = C.Appl (vvs @ vs) in
 189             HLog.warn "Optimizer: nested application"; opt1_proof g false c x
 190          | t                       ->
 191             let rec aux d rvs = function
 192                | [], _                 ->
 193                   let x = C.Appl (t :: List.rev rvs) in
 194                   if d then opt1_proof g false c x else g x
 195                | v :: vs, (c, b) :: cs ->
 196                   if is_not_atomic v && I.S.mem 0 c && b then begin
 197                      HLog.warn "Optimizer: anticipate 1";
 198                      aux true (define c v :: rvs) (vs, cs)
 199                   end else
 200                      aux d (v :: rvs) (vs, cs)
 201                | _, []                 -> assert false
 202             in
 203             let h () =
 204                let classes, conclusion = Cl.classify c (get_type c t) in
 205                let csno, vsno = List.length classes, List.length vs in
 206                if csno < vsno && csno > 0 then
 207                   let vvs, vs = HEL.split_nth csno vs in
 208                   let x = C.Appl (define c (C.Appl (t :: vvs)) :: vs) in
 209                   HLog.warn "Optimizer: anticipate 2"; opt1_proof g false c x
 210                else match conclusion, List.rev vs with
 211                   | Some _, rv :: rvs when csno = vsno && is_not_atomic rv ->
 212                      let x = C.Appl (t :: List.rev rvs @ [define c rv]) in
 213                      HLog.warn "Optimizer: anticipate 3"; opt1_proof g false c x
 214                   | Some _, _                                              ->
 215                      g (C.Appl (t :: vs))
 216                   | None, _                                                ->
 217                      if csno > 0 then aux false [] (vs, classes)
 218                      else g (C.Appl (t :: vs))
 219             in
 220             let rec aux h prev = function
 221                | C.LetIn (name, vv, tt) :: vs ->
 222                   let t = S.lift 1 t in
 223                   let prev = List.map (S.lift 1) prev in
 224                   let vs = List.map (S.lift 1) vs in
 225                   let y = C.Appl (t :: List.rev prev @ tt :: vs) in
 226                   let x = C.LetIn (name, vv, y) in
 227                   HLog.warn "Optimizer: swap 3"; opt1_proof g false c x
 228                | v :: vs                      -> aux h (v :: prev) vs
 229                | []                           -> h ()
 230             in
 231             aux h [] vs
 232       in
 233       if es then opt1_proof g es c t else g t
 234    in
 235    if es then list_map_cps g (fun h -> opt1_term h es c) vs else g vs
 236
 237 and opt1_mutcase g es c uri tyno outty arg cases =
 238    let eliminator = get_default_eliminator c uri tyno outty in
 239    let lpsno, (_, _, _, constructors) = get_ind_type uri tyno in
 240    let ps, sort_disp = get_ind_parameters c arg in
 241    let lps, rps = HEL.split_nth lpsno ps in
 242    let rpsno = List.length rps in
 243    let predicate = clear_absts rpsno (1 - sort_disp) outty in
 244    let is_recursive t =
 245       I.S.mem tyno (I.get_mutinds_of_uri uri t)
 246    in
 247    let map2 case (_, cty) =
 248       let map (h, case, k) (_, premise) =
 249          if h > 0 then pred h, case, k else
 250          if is_recursive premise then
 251             0, add_abst k case, k + 2
 252          else
 253             0, case, succ k
 254       in
 255       let premises, _ = PEH.split_with_whd (c, cty) in
 256       let _, lifted_case, _ =
 257          List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
 258       in
 259       lifted_case
 260    in
 261    let lifted_cases = List.map2 map2 cases constructors in
 262    let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
 263    let x = refine c (C.Appl args) in
 264    HLog.warn "Optimizer: remove 3"; opt1_proof g es c x
 265
 266 and opt1_cast g es c t w =
 267    let g t = HLog.warn "Optimizer: remove 4"; g t in
 268    if es then  opt1_proof g es c t else g t
 269
 270 and opt1_other g es c t = g t
 271
 272 and opt1_proof g es c = function
 273    | C.LetIn (name, v, t)       -> opt1_letin g es c name v t
 274    | C.Lambda (name, w, t)      -> opt1_lambda g es c name w t
 275    | C.Appl (t :: v :: vs)      -> opt1_appl g es c t (v :: vs)
 276    | C.Appl [t]                 -> opt1_proof g es c t
 277    | C.MutCase (u, n, t, v, ws) -> opt1_mutcase g es c u n t v ws
 278    | C.Cast (t, w)              -> opt1_cast g es c t w
 279    | t                          -> opt1_other g es c t
 280
 281 and opt1_term g es c t =
 282    if is_proof c t then opt1_proof g es c t else g t
 283
 284 (* term preprocessing: optomization 2 ***************************************)
 285
 286 let expanded_premise = "EXPANDED"
 287
 288 let eta_expand g tys t =
 289    assert (tys <> []);
 290    let name i = Printf.sprintf "%s%u" expanded_premise i in
 291    let lambda i ty t = C.Lambda (C.Name (name i), ty, t) in
 292    let arg i = C.Rel (succ i) in
 293    let rec aux i f a = function
 294       | []            -> f, a
 295       | (_, ty) :: tl -> aux (succ i) (comp f (lambda i ty)) (arg i :: a) tl
 296    in
 297    let n = List.length tys in
 298    let absts, args = aux 0 identity [] tys in
 299    let t = match S.lift n t with
 300       | C.Appl ts -> C.Appl (ts @ args)
 301       | t         -> C.Appl (t :: args)
 302    in
 303    g (absts t)
 304
 305 let rec opt2_letin g c name v t =
 306    let entry = Some (name, C.Def (v, None)) in
 307    let g t =
 308       let g v = g (C.LetIn (name, v, t)) in
 309       opt2_term g c v
 310    in
 311    opt2_proof g (entry :: c) t
 312
 313 and opt2_lambda g c name w t =
 314    let entry = Some (name, C.Decl w) in
 315    let g t = g (C.Lambda (name, w, t)) in
 316    opt2_proof g (entry :: c) t
 317
 318 and opt2_appl g c t vs =
 319    let g vs =
 320       let x = C.Appl (t :: vs) in
 321       let vsno = List.length vs in
 322       let _, csno = PEH.split_with_whd (c, get_type c t) in
 323       if vsno < csno then
 324          let tys, _ = PEH.split_with_whd (c, get_type c x) in
 325          let tys = List.rev (List.tl tys) in
 326          let tys, _ = HEL.split_nth (csno - vsno) tys in
 327          HLog.warn "Optimizer: eta 1"; eta_expand g tys x
 328       else g x
 329    in
 330    list_map_cps g (fun h -> opt2_term h c) vs
 331
 332 and opt2_other g c t =
 333    let tys, csno = PEH.split_with_whd (c, get_type c t) in
 334    if csno > 0 then begin
 335       let tys = List.rev (List.tl tys) in
 336       HLog.warn "Optimizer: eta 2"; eta_expand g tys t
 337    end else g t
 338
 339 and opt2_proof g c = function
 340    | C.LetIn (name, v, t)  -> opt2_letin g c name v t
 341    | C.Lambda (name, w, t) -> opt2_lambda g c name w t
 342    | C.Appl (t :: vs)      -> opt2_appl g c t vs
 343    | t                     -> opt2_other g c t
 344
 345 and opt2_term g c t =
 346    if is_proof c t then opt2_proof g c t else g t
 347
 348 (* object preprocessing *****************************************************)
 349
 350 let pp_obj = function
 351    | C.Constant (name, Some bo, ty, pars, attrs) ->
 352       let g bo = C.Constant (name, Some bo, ty, pars, attrs) in
 353       Printf.eprintf "BEGIN: %s\n" name;
 354       begin try opt1_term (opt2_term g []) true [] bo
 355       with e -> failwith ("PPP: " ^ Printexc.to_string e) end
 356    | obj                                         -> obj