X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Fsoftware%2Fcomponents%2Facic_procedural%2FproceduralPreprocess.ml;h=2b8e1ea3d2307bcdf01b22adfab04a9b457a63b9;hb=c465c17581bf606e0330cbd89b238279c184ad35;hp=dcd4cb58b20588734b9a40c5ee5ca27d2db0a1ba;hpb=a8e38e556152d99a0f9b7e643e7ac164d6220d06;p=helm.git

diff --git a/helm/software/components/acic_procedural/proceduralPreprocess.ml b/helm/software/components/acic_procedural/proceduralPreprocess.ml
index dcd4cb58b..2b8e1ea3d 100644
--- a/helm/software/components/acic_procedural/proceduralPreprocess.ml
+++ b/helm/software/components/acic_procedural/proceduralPreprocess.ml
@@ -23,76 +23,32 @@
  * http://cs.unibo.it/helm/.
  *)
 
-module UM   = UriManager
 module C    = Cic
 module Pp   = CicPp
-module Un   = CicUniv
 module I    = CicInspect
-module E    = CicEnvironment
 module S    = CicSubstitution
-module Rd   = CicReduction
-module TC   = CicTypeChecker 
-module Rf   = CicRefine
 module DTI  = DoubleTypeInference
 module HEL  = HExtlib
+module PEH  = ProofEngineHelpers
 
-(* helper functions *********************************************************)
+module H    = ProceduralHelpers
+module Cl   = ProceduralClassify
 
-let identity x = x
+(* term preprocessing: optomization 1 ***************************************)
 
-let comp f g x = f (g x)
-   
-let split c t =
-   let add s v c = Some (s, C.Decl v) :: c in
-   let rec aux whd a n c = function
-      | C.Prod (s, v, t)  -> aux false (v :: a) (succ n) (add s v c) t
-      | v when whd        -> v :: a, n
-      | v                 -> aux true a n c (Rd.whd ~delta:true c v)
-    in
-    aux false [] 0 c t
-
-let get_type c t =
-   try let ty, _ = TC.type_of_aux' [] c t Un.empty_ugraph in ty
-   with e -> 
-      Printf.eprintf "TC: context: %s\n" (Pp.ppcontext c);
-      Printf.eprintf "TC: term   : %s\n" (Pp.ppterm t);
-      raise e
-
-let refine c t =
-   try let t, _, _, _ = Rf.type_of_aux' [] c t Un.empty_ugraph in t
-   with e -> 
-      Printf.eprintf "REFINE EROR: %s\n" (Printexc.to_string e);
-      Printf.eprintf "Ref: context: %s\n" (Pp.ppcontext c);
-      Printf.eprintf "Ref: term   : %s\n" (Pp.ppterm t);
-      raise e
-
-let get_tail c t =
-   match split c t with
-      | hd :: _, _ -> hd
-      | _          -> assert false
-
-let is_proof c t =
-   match get_tail c (get_type c (get_type c t)) with
-      | C.Sort C.Prop -> true
-      | C.Sort _      -> false
-      | _             -> assert false 
+let defined_premise = "DEFINED"
 
-let is_not_atomic = function
-   | C.Sort _
-   | C.Rel _
-   | C.Const _
-   | C.Var _
-   | C.MutInd _ 
-   | C.MutConstruct _ -> false
-   | _                -> true
+let define v =
+   let name = C.Name defined_premise in
+   C.LetIn (name, v, C.Rel 1)
 
 let clear_absts m =
    let rec aux k n = function
-      | C.Lambda (s, v, t) when k > 0    -> 
+      | C.Lambda (s, v, t) when k > 0 -> 
          C.Lambda (s, v, aux (pred k) n t)
-      | C.Lambda (_, _, t) when n > 0    -> 
+      | C.Lambda (_, _, t) when n > 0 -> 
          aux 0 (pred n) (S.lift (-1) t)
-      | t                     when n > 0 ->
+      | t                  when n > 0 ->
          Printf.eprintf "CicPPP clear_absts: %u %s\n" n (Pp.ppterm t);
 	 assert false 
       | t                                 -> t
@@ -104,54 +60,144 @@ let rec add_abst k = function
    | t when k > 0 -> assert false
    | t -> C.Lambda (C.Anonymous, C.Implicit None, S.lift 1 t)
 
-let get_ind_type uri tyno =
-   match E.get_obj Un.empty_ugraph uri with
-      | C.InductiveDefinition (tys, _, lpsno, _), _ -> lpsno, List.nth tys tyno
-      | _                                           -> assert false
-
-let get_ind_parameters c t =
-   let ty = get_type c t in
-   let ps = match get_tail c ty with
-      | C.MutInd _                  -> []
-      | C.Appl (C.MutInd _ :: args) -> args
-      | _                           -> assert false
+let rec opt1_letin g es c name v t =
+   let name = H.mk_fresh_name c name in
+   let entry = Some (name, C.Def (v, None)) in
+   let g t =
+      if DTI.does_not_occur 1 t then begin	    
+         let x = S.lift (-1) t in
+	 HLog.warn "Optimizer: remove 1"; opt1_proof g true c x 
+      end else 
+      let g = function
+         | C.LetIn (nname, vv, tt) when H.is_proof c v ->
+	    let x = C.LetIn (nname, vv, C.LetIn (name, tt, S.lift_from 2 1 t)) in
+	    HLog.warn "Optimizer: swap 1"; opt1_proof g true c x 
+         | v                               -> 
+	    g (C.LetIn (name, v, t))
+      in
+      if es then opt1_term g es c v else g v
    in
-   let disp = match get_tail c (get_type c ty) with
-      | C.Sort C.Prop -> 0
-      | C.Sort _      -> 1
-      | _             -> assert false
+   if es then opt1_proof g es (entry :: c) t else g t
+
+and opt1_lambda g es c name w t =
+   let name = H.mk_fresh_name c name in
+   let entry = Some (name, C.Decl w) in
+   let g t = 
+      let name = if DTI.does_not_occur 1 t then C.Anonymous else name in
+      g (C.Lambda (name, w, t))
    in
-   ps, disp
+   if es then opt1_proof g es (entry :: c) t else g t
+
+and opt1_appl g es c t vs =
+   let g vs = 
+      let g = function      
+         | C.LetIn (mame, vv, tt) ->
+            let vs = List.map (S.lift 1) vs in
+	    let x = C.LetIn (mame, vv, C.Appl (tt :: vs)) in
+	    HLog.warn "Optimizer: swap 2"; opt1_proof g true c x
+         | C.Lambda (name, ww, tt) ->
+	    let v, vs = List.hd vs, List.tl vs in
+	    let x = C.Appl (C.LetIn (name, v, tt) :: vs) in
+	    HLog.warn "Optimizer: remove 2"; opt1_proof g true c x
+	 | C.Appl vvs              ->
+            let x = C.Appl (vvs @ vs) in
+	    HLog.warn "Optimizer: nested application"; opt1_proof g true c x
+	 | t                       ->
+	    let rec aux d rvs = function
+	       | [], _                   -> 
+	          let x = C.Appl (t :: List.rev rvs) in
+		  if d then opt1_proof g true c x else g x
+	       | v :: vs, (cc, bb) :: cs ->
+	          if H.is_not_atomic v && I.S.mem 0 cc && bb then begin 
+		     HLog.warn "Optimizer: anticipate 1"; 
+                     aux true (define v :: rvs) (vs, cs)
+		  end else 
+		     aux d (v :: rvs) (vs, cs)
+	       | _, []                   -> assert false
+	    in
+	    let h () =
+	       let classes, conclusion = Cl.classify c (H.get_type c t) in
+	       let csno, vsno = List.length classes, List.length vs in
+	       if csno < vsno then
+	          let vvs, vs = HEL.split_nth csno vs in
+		  let x = C.Appl (define (C.Appl (t :: vvs)) :: vs) in
+	          HLog.warn "Optimizer: anticipate 2"; opt1_proof g true c x
+	       else match conclusion, List.rev vs with
+	          | Some _, rv :: rvs when csno = vsno && H.is_not_atomic rv ->
+		     let x = C.Appl (t :: List.rev rvs @ [define rv]) in
+		     HLog.warn "Optimizer: anticipate 3"; opt1_proof g true c x
+	          | Some _, _                                              ->
+		     g (C.Appl (t :: vs))
+		  | None, _                                                ->
+	             aux false [] (vs, classes)
+	    in
+	    let rec aux h prev = function
+	       | C.LetIn (name, vv, tt) :: vs ->
+	          let t = S.lift 1 t in
+                  let prev = List.map (S.lift 1) prev in
+                  let vs = List.map (S.lift 1) vs in
+		  let y = C.Appl (t :: List.rev prev @ tt :: vs) in
+		  let x = C.LetIn (name, vv, y) in  
+		  HLog.warn "Optimizer: swap 3"; opt1_proof g true c x
+	       | v :: vs                      -> aux h (v :: prev) vs
+	       | []                           -> h ()
+	    in 
+	    aux h [] vs
+      in
+      if es then opt1_proof g es c t else g t
+   in
+   if es then H.list_map_cps g (fun h -> opt1_term h es c) vs else g vs
 
-let get_default_eliminator context uri tyno ty =
-   let _, (name, _, _, _) = get_ind_type uri tyno in
-   let ext = match get_tail context (get_type context ty) with
-      | C.Sort C.Prop     -> "_ind"
-      | C.Sort C.Set      -> "_rec"
-      | C.Sort C.CProp    -> "_rec"
-      | C.Sort (C.Type _) -> "_rect"
-      | t                 -> 
-         Printf.eprintf "CicPPP get_default_eliminator: %s\n" (Pp.ppterm t);
-         assert false
+and opt1_mutcase g es c uri tyno outty arg cases =
+   let eliminator = H.get_default_eliminator c uri tyno outty in
+   let lpsno, (_, _, _, constructors) = H.get_ind_type uri tyno in
+   let ps, sort_disp = H.get_ind_parameters c arg in
+   let lps, rps = HEL.split_nth lpsno ps in
+   let rpsno = List.length rps in
+   let predicate = clear_absts rpsno (1 - sort_disp) outty in   
+   let is_recursive t =
+      I.S.mem tyno (I.get_mutinds_of_uri uri t) 
    in
-   let buri = UM.buri_of_uri uri in
-   let uri = UM.uri_of_string (buri ^ "/" ^ name ^ ext ^ ".con") in
-   C.Const (uri, [])
+   let map2 case (_, cty) = 
+      let map (h, case, k) (_, premise) = 
+         if h > 0 then pred h, case, k else
+	 if is_recursive premise then 
+	    0, add_abst k case, k + 2 
+	 else
+	    0, case, succ k
+      in
+      let premises, _ = PEH.split_with_whd (c, cty) in
+      let _, lifted_case, _ =
+         List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
+      in
+      lifted_case
+   in
+   let lifted_cases = List.map2 map2 cases constructors in
+   let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
+   let x = H.refine c (C.Appl args) in
+   HLog.warn "Optimizer: remove 3"; opt1_proof g es c x
 
-let add g htbl t proof decurry =
-   if proof then C.CicHash.add htbl t decurry; 
-   g t proof decurry
+and opt1_cast g es c t w =
+   let g t = HLog.warn "Optimizer: remove 4"; g t in
+   if es then  opt1_proof g es c t else g t
 
-let find g htbl t = 
-   try 
-      let decurry = C.CicHash.find htbl t in g t true decurry
-   with Not_found -> g t false 0
+and opt1_other g es c t = g t 
 
-(* term preprocessing *******************************************************)
+and opt1_proof g es c = function 
+   | C.LetIn (name, v, t)       -> opt1_letin g es c name v t
+   | C.Lambda (name, w, t)      -> opt1_lambda g es c name w t
+   | C.Appl (t :: v :: vs)      -> opt1_appl g es c t (v :: vs)
+   | C.Appl [t]                 -> opt1_proof g es c t
+   | C.MutCase (u, n, t, v, ws) -> opt1_mutcase g es c u n t v ws
+   | C.Cast (t, w)              -> opt1_cast g es c t w
+   | t                          -> opt1_other g es c t
 
-let expanded_premise = "EXPANDED"
+and opt1_term g es c t = 
+   if H.is_proof c t then opt1_proof g es c t else g t
 
-let defined_premise = "DEFINED"
+(* term preprocessing: optomization 2 ***************************************)
+
+let expanded_premise = "EXPANDED"
 
 let eta_expand g tys t =
    assert (tys <> []);
@@ -159,158 +205,70 @@ let eta_expand g tys t =
    let lambda i ty t = C.Lambda (C.Name (name i), ty, t) in
    let arg i = C.Rel (succ i) in
    let rec aux i f a = function
-      | []       -> f, a 
-      | ty :: tl -> aux (succ i) (comp f (lambda i ty)) (arg i :: a) tl
+      | []            -> f, a 
+      | (_, ty) :: tl -> aux (succ i) (H.compose f (lambda i ty)) (arg i :: a) tl
    in
    let n = List.length tys in
-   let absts, args = aux 0 identity [] tys in
+   let absts, args = aux 0 H.identity [] tys in
    let t = match S.lift n t with
       | C.Appl ts -> C.Appl (ts @ args)
       | t         -> C.Appl (t :: args)
    in
    g (absts t)
 
-let get_tys c decurry =
-   let rec aux n = function
-(*      | C.Appl (hd :: tl) -> aux (n + List.length tl) hd *)
-      | t                 ->
-         let tys, _ = split c (get_type c t) in
-         let _, tys = HEL.split_nth n (List.rev tys) in
-	 let tys, _ = HEL.split_nth decurry tys in
-         tys
-   in
-   aux 0
-
-let eta_fix c t proof decurry =
-   let rec aux g c = function
-      | C.LetIn (name, v, t) ->
-         let g t = g (C.LetIn (name, v, t)) in
-	 let entry = Some (name, C.Def (v, None)) in
-         aux g (entry :: c) t
-      | t                    -> eta_expand g (get_tys c decurry t) t 
-   in 
-   if proof && decurry > 0 then aux identity c t else t
-
-let rec pp_cast g ht es c t v =
-   if true then pp_proof g ht es c t else find g ht t
-
-and pp_lambda g ht es c name v t =
-   let name = if DTI.does_not_occur 1 t then C.Anonymous else name in
-   let entry = Some (name, C.Decl v) in
-   let g t _ decurry = 
-      let t = eta_fix (entry :: c) t true decurry in
-      g (C.Lambda (name, v, t)) true 0 in
-   if true then pp_proof g ht es (entry :: c) t else find g ht t
-
-and pp_letin g ht es c name v t =
+let rec opt2_letin g c name v t =
    let entry = Some (name, C.Def (v, None)) in
-   let g t _ decurry =
-      if DTI.does_not_occur 1 t then g (S.lift (-1) t) true decurry else 
-      let g v proof d = match v with
-         | C.LetIn (mame, w, u) when proof ->
-            let x = C.LetIn (mame, w, C.LetIn (name, u, S.lift_from 2 1 t)) in
-	    pp_proof g ht false c x 
-         | v                               -> 
-            let v = eta_fix c v proof d in
-	    g (C.LetIn (name, v, t)) true decurry
-      in
-      if true then pp_term g ht es c v else find g ht v
+   let g t = 
+      let g v = g (C.LetIn (name, v, t)) in
+      opt2_term g c v
    in
-   if true then pp_proof g ht es (entry :: c) t else find g ht t
-
-and pp_appl_one g ht es c t v =
-   let g t _ decurry =
-      let g v proof d =
-         match t, v with
-	    | t, C.LetIn (mame, w, u) when proof ->
-               let x = C.LetIn (mame, w, C.Appl [S.lift 1 t; u]) in
-	       pp_proof g ht false c x 
-            | C.LetIn (mame, w, u), v            ->
-               let x = C.LetIn (mame, w, C.Appl [u; S.lift 1 v]) in
-	       pp_proof g ht false c x
-	    | C.Appl ts, v when decurry > 0      ->
-	       let v = eta_fix c v proof d in
-	       g (C.Appl (List.append ts [v])) true (pred decurry)
-	    | t, v  when is_not_atomic t         ->
-	       let mame = C.Name defined_premise in
-	       let x = C.LetIn (mame, t, C.Appl [C.Rel 1; S.lift 1 v]) in
-	       pp_proof g ht false c x
-	    | t, v                               ->
-	       let v = eta_fix c v proof d in
-               g (C.Appl [t; v]) true (pred decurry)
-      in
-      if true then pp_term g ht es c v else find g ht v
+   opt2_proof g (entry :: c) t
+
+and opt2_lambda g c name w t =
+   let entry = Some (name, C.Decl w) in
+   let g t = g (C.Lambda (name, w, t)) in
+   opt2_proof g (entry :: c) t
+
+and opt2_appl g c t vs =
+   let g vs =
+      let x = C.Appl (t :: vs) in
+      let vsno = List.length vs in
+      let _, csno = PEH.split_with_whd (c, H.get_type c t) in
+      if vsno < csno then 
+         let tys, _ = PEH.split_with_whd (c, H.get_type c x) in
+	 let tys = List.rev (List.tl tys) in
+	 let tys, _ = HEL.split_nth (csno - vsno) tys in
+         HLog.warn "Optimizer: eta 1"; eta_expand g tys x
+      else g x 
    in
-   if true then pp_proof g ht es c t else find g ht t
-
-and pp_appl g ht es c t = function
-   | []             -> pp_proof g ht es c t
-   | [v]            -> pp_appl_one g ht es c t v
-   | v1 :: v2 :: vs ->
-      let x = C.Appl (C.Appl [t; v1] :: v2 :: vs) in 
-      pp_proof g ht es c x
-
-and pp_atomic g ht es c t =
-   let _, premsno = split c (get_type c t) in
-   g t true premsno
+   H.list_map_cps g (fun h -> opt2_term h c) vs
 
-and pp_mutcase g ht es c uri tyno outty arg cases =
-   let eliminator = get_default_eliminator c uri tyno outty in
-   let lpsno, (_, _, _, constructors) = get_ind_type uri tyno in
-   let ps, sort_disp = get_ind_parameters c arg in
-   let lps, rps = HEL.split_nth lpsno ps in
-   let rpsno = List.length rps in
-   let predicate = clear_absts rpsno (1 - sort_disp) outty in   
-   let is_recursive t =
-      I.S.mem tyno (I.get_mutinds_of_uri uri t) 
-   in
-   let map2 case (_, cty) = 
-      let map (h, case, k) premise = 
-         if h > 0 then pred h, case, k else
-	 if is_recursive premise then 
-	    0, add_abst k case, k + 2 
-	 else
-	    0, case, succ k
-      in
-      let premises, _ = split c cty in
-      let _, lifted_case, _ =
-         List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
-      in
-      lifted_case
-   in
-   let lifted_cases = List.map2 map2 cases constructors in
-   let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
-   let x = refine c (C.Appl args) in
-   pp_proof g ht es c x
+and opt2_other g c t =
+   let tys, csno = PEH.split_with_whd (c, H.get_type c t) in
+   if csno > 0 then begin
+      let tys = List.rev (List.tl tys) in      
+      HLog.warn "Optimizer: eta 2"; eta_expand g tys t 
+   end else g t
 
-and pp_proof g ht es c t = 
-(*  Printf.eprintf "IN: |- %s\n" (*CicPp.ppcontext c*) (CicPp.ppterm t);
-  let g t proof decurry = 
-     Printf.eprintf "OUT: %b %u |- %s\n" proof decurry (CicPp.ppterm t);
-     g t proof decurry
-  in *)
-(*   let g t proof decurry = add g ht t proof decurry in *)
-   match t with
-      | C.Cast (t, v)              -> pp_cast g ht es c t v
-      | C.Lambda (name, v, t)      -> pp_lambda g ht es c name v t
-      | C.LetIn (name, v, t)       -> pp_letin g ht es c name v t
-      | C.Appl (t :: vs)           -> pp_appl g ht es c t vs
-      | C.MutCase (u, n, t, v, ws) -> pp_mutcase g ht es c u n t v ws
-      | t                          -> pp_atomic g ht es c t
+and opt2_proof g c = function 
+   | C.LetIn (name, v, t)  -> opt2_letin g c name v t
+   | C.Lambda (name, w, t) -> opt2_lambda g c name w t
+   | C.Appl (t :: vs)      -> opt2_appl g c t vs
+   | t                     -> opt2_other g c t
 
-and pp_term g ht es c t =
-   if is_proof c t then pp_proof g ht es c t else g t false 0
+and opt2_term g c t = 
+   if H.is_proof c t then opt2_proof g c t else g t
 
 (* object preprocessing *****************************************************)
 
 let pp_obj = function
    | C.Constant (name, Some bo, ty, pars, attrs) ->
-      let g bo proof decurry = 
-         let bo = eta_fix [] bo proof decurry in
-         C.Constant (name, Some bo, ty, pars, attrs)
+      let g bo = 
+         Printf.eprintf "Optimized: %s\n" (Pp.ppterm bo);
+	 let _ = H.get_type [] (C.Cast (bo, ty)) in
+	 C.Constant (name, Some bo, ty, pars, attrs)
       in
-      let ht = C.CicHash.create 1 in
       Printf.eprintf "BEGIN: %s\n" name;
-      begin try pp_term g ht true [] bo
+      begin try opt1_term (opt2_term g []) true [] bo
       with e -> failwith ("PPP: " ^ Printexc.to_string e) end
    | obj                                         -> obj