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 Rd   = CicReduction
  34 module TC   = CicTypeChecker
  35 module Rf   = CicRefine
  36 module DTI  = DoubleTypeInference
  37 module HEL  = HExtlib
  38
  39 (* helper functions *********************************************************)
  40
  41 let identity x = x
  42
  43 let comp f g x = f (g x)
  44
  45 let split c t =
  46    let add s v c = Some (s, C.Decl v) :: c in
  47    let rec aux whd a n c = function
  48       | C.Prod (s, v, t)  -> aux false (v :: a) (succ n) (add s v c) t
  49       | v when whd        -> v :: a, n
  50       | v                 -> aux true a n c (Rd.whd ~delta:true c v)
  51     in
  52     aux false [] 0 c t
  53
  54 let get_type c t =
  55    try let ty, _ = TC.type_of_aux' [] c t Un.empty_ugraph in ty
  56    with e ->
  57       Printf.eprintf "TC: context: %s\n" (Pp.ppcontext c);
  58       Printf.eprintf "TC: term   : %s\n" (Pp.ppterm t);
  59       raise e
  60
  61 let refine c t =
  62    try let t, _, _, _ = Rf.type_of_aux' [] c t Un.empty_ugraph in t
  63    with e ->
  64       Printf.eprintf "REFINE EROR: %s\n" (Printexc.to_string e);
  65       Printf.eprintf "Ref: context: %s\n" (Pp.ppcontext c);
  66       Printf.eprintf "Ref: term   : %s\n" (Pp.ppterm t);
  67       raise e
  68
  69 let get_tail c t =
  70    match split c t with
  71       | hd :: _, _ -> hd
  72       | _          -> assert false
  73
  74 let is_proof c t =
  75    match get_tail c (get_type c (get_type c t)) with
  76       | C.Sort C.Prop -> true
  77       | C.Sort _      -> false
  78       | _             -> assert false
  79
  80 let is_not_atomic = function
  81    | C.Sort _
  82    | C.Rel _
  83    | C.Const _
  84    | C.Var _
  85    | C.MutInd _
  86    | C.MutConstruct _ -> false
  87    | _                -> true
  88
  89 let clear_absts m =
  90    let rec aux k n = function
  91       | C.Lambda (s, v, t) when k > 0    ->
  92          C.Lambda (s, v, aux (pred k) n t)
  93       | C.Lambda (_, _, t) when n > 0    ->
  94          aux 0 (pred n) (S.lift (-1) t)
  95       | t                     when n > 0 ->
  96          Printf.eprintf "CicPPP clear_absts: %u %s\n" n (Pp.ppterm t);
  97          assert false
  98       | t                                 -> t
  99    in
 100    aux m
 101
 102 let rec add_abst k = function
 103    | C.Lambda (s, v, t) when k > 0 -> C.Lambda (s, v, add_abst (pred k) t)
 104    | t when k > 0 -> assert false
 105    | t -> C.Lambda (C.Anonymous, C.Implicit None, S.lift 1 t)
 106
 107 let get_ind_type uri tyno =
 108    match E.get_obj Un.empty_ugraph uri with
 109       | C.InductiveDefinition (tys, _, lpsno, _), _ -> lpsno, List.nth tys tyno
 110       | _                                           -> assert false
 111
 112 let get_ind_parameters c t =
 113    let ty = get_type c t in
 114    let ps = match get_tail c ty with
 115       | C.MutInd _                  -> []
 116       | C.Appl (C.MutInd _ :: args) -> args
 117       | _                           -> assert false
 118    in
 119    let disp = match get_tail c (get_type c ty) with
 120       | C.Sort C.Prop -> 0
 121       | C.Sort _      -> 1
 122       | _             -> assert false
 123    in
 124    ps, disp
 125
 126 let get_default_eliminator context uri tyno ty =
 127    let _, (name, _, _, _) = get_ind_type uri tyno in
 128    let ext = match get_tail context (get_type context ty) with
 129       | C.Sort C.Prop     -> "_ind"
 130       | C.Sort C.Set      -> "_rec"
 131       | C.Sort C.CProp    -> "_rec"
 132       | C.Sort (C.Type _) -> "_rect"
 133       | t                 ->
 134          Printf.eprintf "CicPPP get_default_eliminator: %s\n" (Pp.ppterm t);
 135          assert false
 136    in
 137    let buri = UM.buri_of_uri uri in
 138    let uri = UM.uri_of_string (buri ^ "/" ^ name ^ ext ^ ".con") in
 139    C.Const (uri, [])
 140
 141 let add g htbl t proof decurry =
 142    if proof then C.CicHash.add htbl t decurry;
 143    g t proof decurry
 144
 145 let find g htbl t =
 146    try
 147       let decurry = C.CicHash.find htbl t in g t true decurry
 148    with Not_found -> g t false 0
 149
 150 (* term preprocessing *******************************************************)
 151
 152 let expanded_premise = "EXPANDED"
 153
 154 let defined_premise = "DEFINED"
 155
 156 let eta_expand g tys t =
 157    assert (tys <> []);
 158    let name i = Printf.sprintf "%s%u" expanded_premise i in
 159    let lambda i ty t = C.Lambda (C.Name (name i), ty, t) in
 160    let arg i = C.Rel (succ i) in
 161    let rec aux i f a = function
 162       | []       -> f, a
 163       | ty :: tl -> aux (succ i) (comp f (lambda i ty)) (arg i :: a) tl
 164    in
 165    let n = List.length tys in
 166    let absts, args = aux 0 identity [] tys in
 167    let t = match S.lift n t with
 168       | C.Appl ts -> C.Appl (ts @ args)
 169       | t         -> C.Appl (t :: args)
 170    in
 171    g (absts t)
 172
 173 let get_tys c decurry =
 174    let rec aux n = function
 175 (*      | C.Appl (hd :: tl) -> aux (n + List.length tl) hd *)
 176       | t                 ->
 177          let tys, _ = split c (get_type c t) in
 178          let _, tys = HEL.split_nth n (List.rev tys) in
 179          let tys, _ = HEL.split_nth decurry tys in
 180          tys
 181    in
 182    aux 0
 183
 184 let eta_fix c t proof decurry =
 185    let rec aux g c = function
 186       | C.LetIn (name, v, t) ->
 187          let g t = g (C.LetIn (name, v, t)) in
 188          let entry = Some (name, C.Def (v, None)) in
 189          aux g (entry :: c) t
 190       | t                    -> eta_expand g (get_tys c decurry t) t
 191    in
 192    if proof && decurry > 0 then aux identity c t else t
 193
 194 let rec pp_cast g ht es c t v =
 195    if true then pp_proof g ht es c t else find g ht t
 196
 197 and pp_lambda g ht es c name v t =
 198    let name = if DTI.does_not_occur 1 t then C.Anonymous else name in
 199    let entry = Some (name, C.Decl v) in
 200    let g t _ decurry =
 201       let t = eta_fix (entry :: c) t true decurry in
 202       g (C.Lambda (name, v, t)) true 0 in
 203    if true then pp_proof g ht es (entry :: c) t else find g ht t
 204
 205 and pp_letin g ht es c name v t =
 206    let entry = Some (name, C.Def (v, None)) in
 207    let g t _ decurry =
 208       if DTI.does_not_occur 1 t then g (S.lift (-1) t) true decurry else
 209       let g v proof d = match v with
 210          | C.LetIn (mame, w, u) when proof ->
 211             let x = C.LetIn (mame, w, C.LetIn (name, u, S.lift_from 2 1 t)) in
 212             pp_proof g ht false c x
 213          | v                               ->
 214             let v = eta_fix c v proof d in
 215             g (C.LetIn (name, v, t)) true decurry
 216       in
 217       if true then pp_term g ht es c v else find g ht v
 218    in
 219    if true then pp_proof g ht es (entry :: c) t else find g ht t
 220
 221 and pp_appl_one g ht es c t v =
 222    let g t _ decurry =
 223       let g v proof d =
 224          match t, v with
 225             | t, C.LetIn (mame, w, u) when proof ->
 226                let x = C.LetIn (mame, w, C.Appl [S.lift 1 t; u]) in
 227                pp_proof g ht false c x
 228             | C.LetIn (mame, w, u), v            ->
 229                let x = C.LetIn (mame, w, C.Appl [u; S.lift 1 v]) in
 230                pp_proof g ht false c x
 231             | C.Appl ts, v when decurry > 0      ->
 232                let v = eta_fix c v proof d in
 233                g (C.Appl (List.append ts [v])) true (pred decurry)
 234             | t, v  when is_not_atomic t         ->
 235                let mame = C.Name defined_premise in
 236                let x = C.LetIn (mame, t, C.Appl [C.Rel 1; S.lift 1 v]) in
 237                pp_proof g ht false c x
 238             | t, v                               ->
 239                let v = eta_fix c v proof d in
 240                g (C.Appl [t; v]) true (pred decurry)
 241       in
 242       if true then pp_term g ht es c v else find g ht v
 243    in
 244    if true then pp_proof g ht es c t else find g ht t
 245
 246 and pp_appl g ht es c t = function
 247    | []             -> pp_proof g ht es c t
 248    | [v]            -> pp_appl_one g ht es c t v
 249    | v1 :: v2 :: vs ->
 250       let x = C.Appl (C.Appl [t; v1] :: v2 :: vs) in
 251       pp_proof g ht es c x
 252
 253 and pp_atomic g ht es c t =
 254    let _, premsno = split c (get_type c t) in
 255    g t true premsno
 256
 257 and pp_mutcase g ht es c uri tyno outty arg cases =
 258    let eliminator = get_default_eliminator c uri tyno outty in
 259    let lpsno, (_, _, _, constructors) = get_ind_type uri tyno in
 260    let ps, sort_disp = get_ind_parameters c arg in
 261    let lps, rps = HEL.split_nth lpsno ps in
 262    let rpsno = List.length rps in
 263    let predicate = clear_absts rpsno (1 - sort_disp) outty in
 264    let is_recursive t =
 265       I.S.mem tyno (I.get_mutinds_of_uri uri t)
 266    in
 267    let map2 case (_, cty) =
 268       let map (h, case, k) premise =
 269          if h > 0 then pred h, case, k else
 270          if is_recursive premise then
 271             0, add_abst k case, k + 2
 272          else
 273             0, case, succ k
 274       in
 275       let premises, _ = split c cty in
 276       let _, lifted_case, _ =
 277          List.fold_left map (lpsno, case, 1) (List.rev (List.tl premises))
 278       in
 279       lifted_case
 280    in
 281    let lifted_cases = List.map2 map2 cases constructors in
 282    let args = eliminator :: lps @ predicate :: lifted_cases @ rps @ [arg] in
 283    let x = refine c (C.Appl args) in
 284    pp_proof g ht es c x
 285
 286 and pp_proof g ht es c t =
 287 (*  Printf.eprintf "IN: |- %s\n" (*CicPp.ppcontext c*) (CicPp.ppterm t);
 288   let g t proof decurry =
 289      Printf.eprintf "OUT: %b %u |- %s\n" proof decurry (CicPp.ppterm t);
 290      g t proof decurry
 291   in *)
 292 (*   let g t proof decurry = add g ht t proof decurry in *)
 293    match t with
 294       | C.Cast (t, v)              -> pp_cast g ht es c t v
 295       | C.Lambda (name, v, t)      -> pp_lambda g ht es c name v t
 296       | C.LetIn (name, v, t)       -> pp_letin g ht es c name v t
 297       | C.Appl (t :: vs)           -> pp_appl g ht es c t vs
 298       | C.MutCase (u, n, t, v, ws) -> pp_mutcase g ht es c u n t v ws
 299       | t                          -> pp_atomic g ht es c t
 300
 301 and pp_term g ht es c t =
 302    if is_proof c t then pp_proof g ht es c t else g t false 0
 303
 304 (* object preprocessing *****************************************************)
 305
 306 let pp_obj = function
 307    | C.Constant (name, Some bo, ty, pars, attrs) ->
 308       let g bo proof decurry =
 309          let bo = eta_fix [] bo proof decurry in
 310          C.Constant (name, Some bo, ty, pars, attrs)
 311       in
 312       let ht = C.CicHash.create 1 in
 313       Printf.eprintf "BEGIN: %s\n" name;
 314       begin try pp_term g ht true [] bo
 315       with e -> failwith ("PPP: " ^ Printexc.to_string e) end
 316    | obj                                         -> obj