helm/software/components/ng_tactics/nCicElim.ml

   1 (*
   2     ||M||  This file is part of HELM, an Hypertextual, Electronic
   3     ||A||  Library of Mathematics, developed at the Computer Science
   4     ||T||  Department, University of Bologna, Italy.
   5     ||I||
   6     ||T||  HELM is free software; you can redistribute it and/or
   7     ||A||  modify it under the terms of the GNU General Public License
   8     \   /  version 2 or (at your option) any later version.
   9      \ /   This software is distributed as is, NO WARRANTY.
  10       V_______________________________________________________________ *)
  11
  12 (* $Id: nCic.ml 9058 2008-10-13 17:42:30Z tassi $ *)
  13
  14 let fresh_name =
  15  let i = ref 0 in
  16  function () ->
  17   incr i;
  18   "x_" ^ string_of_int !i
  19 ;;
  20
  21 let mk_id id =
  22  let id = if id = "_" then fresh_name () else id in
  23   CicNotationPt.Ident (id,None)
  24 ;;
  25
  26 (*CSC: cut&paste from nCicReduction.split_prods, but does not check that
  27   the return type is a sort *)
  28 let rec my_split_prods ~subst context n te =
  29   match (n, NCicReduction.whd ~subst context te) with
  30    | (0, _) -> context,te
  31    | (n, NCic.Prod (name,so,ta)) ->
  32        my_split_prods ~subst ((name,(NCic.Decl so))::context) (n - 1) ta
  33    | (n, _) when n <= 0 -> context,te
  34    | (_, _) -> raise (Failure "my_split_prods")
  35 ;;
  36
  37 let mk_appl =
  38  function
  39     [] -> assert false
  40   | [x] -> x
  41   | CicNotationPt.Appl l1 :: l2 -> CicNotationPt.Appl (l1 @ l2)
  42   | l -> CicNotationPt.Appl l
  43 ;;
  44
  45 let mk_elim uri leftno it (outsort,suffix) =
  46  let _,ind_name,ty,cl = it in
  47  let srec_name = ind_name ^ "_" ^ suffix in
  48  let rec_name = mk_id srec_name in
  49  let name_of_k id = mk_id ("H_" ^ id) in
  50  let p_name = mk_id "Q_" in
  51  let params,ty = NCicReduction.split_prods ~subst:[] [] leftno ty in
  52  let params = List.rev_map (function name,_ -> mk_id name) params in
  53  let args,sort = NCicReduction.split_prods ~subst:[] [] (-1) ty in
  54  let args = List.rev_map (function name,_ -> mk_id name) args in
  55  let rec_arg = mk_id (fresh_name ()) in
  56  let p_ty =
  57   List.fold_right
  58    (fun name res -> CicNotationPt.Binder (`Forall,(name,None),res)) args
  59    (CicNotationPt.Binder
  60     (`Forall,
  61      (rec_arg,Some (mk_appl (mk_id ind_name :: params @ args))),
  62      CicNotationPt.Sort outsort)) in
  63  let args = args @ [rec_arg] in
  64  let k_names = List.map (function _,name,_ -> name_of_k name) cl in
  65  let final_params =
  66   List.map (function name -> name, None) params @
  67   [p_name,Some p_ty] @
  68   List.map (function name -> name, None) k_names @
  69   List.map (function name -> name, None) args in
  70  let cty = mk_appl (p_name :: args) in
  71  let ty = Some cty in
  72  let branches =
  73   List.map
  74    (function (_,name,ty) ->
  75      let _,ty = NCicReduction.split_prods ~subst:[] [] leftno ty in
  76      let cargs,ty= my_split_prods ~subst:[] [] (-1) ty in
  77      let cargs_and_recursive_args =
  78       List.rev_map
  79        (function
  80            _,NCic.Def _ -> assert false
  81          | name,NCic.Decl ty ->
  82             let context,ty = my_split_prods ~subst:[] [] (-1) ty in
  83              match ty with
  84               | NCic.Const nref
  85               | NCic.Appl (NCic.Const nref::_)
  86                  when
  87                   let NReference.Ref (uri',_) = nref in
  88                    NUri.eq uri uri'
  89                  ->
  90                   let abs = List.rev_map (fun id,_ -> mk_id id) context in
  91                   let name = mk_id name in
  92                    name, Some (
  93                    List.fold_right
  94                     (fun id res ->
  95                       CicNotationPt.Binder (`Lambda,(id,None),res))
  96                     abs
  97                     (CicNotationPt.Appl
  98                      (rec_name ::
  99                       params @
 100                       [p_name] @
 101                       k_names @
 102                       List.map (fun _ -> CicNotationPt.Implicit `JustOne)
 103                        (List.tl args) @
 104                       [mk_appl (name::abs)])))
 105               | _ -> mk_id name,None
 106        ) cargs in
 107      let cargs,recursive_args = List.split cargs_and_recursive_args in
 108      let recursive_args = HExtlib.filter_map (fun x -> x) recursive_args in
 109       CicNotationPt.Pattern (name,None,List.map (fun x -> x,None) cargs),
 110        mk_appl (name_of_k name :: cargs @ recursive_args)
 111    ) cl
 112  in
 113  let bo = CicNotationPt.Case (rec_arg,Some (ind_name,None),None,branches) in
 114  let recno = List.length final_params in
 115  let where = recno - 1 in
 116  let res =
 117   CicNotationPt.LetRec (`Inductive,
 118    [final_params, (rec_name,ty), bo, where], rec_name)
 119  in
 120 (*
 121   prerr_endline
 122    (BoxPp.render_to_string
 123      ~map_unicode_to_tex:false
 124      (function x::_ -> x | _ -> assert false)
 125      80 (CicNotationPres.render (fun _ -> None)
 126      (TermContentPres.pp_ast res)));
 127   prerr_endline "#####";
 128   let cobj = ("xxx", [], None, `Joint {
 129       Content.joint_id = "yyy";
 130       joint_kind = `Recursive [recno];
 131       joint_defs =
 132        [ `Definition {
 133             Content.def_name = Some srec_name;
 134             def_id = "zzz";
 135             def_aref = "www";
 136             def_term = bo;
 137             def_type =
 138               List.fold_right
 139                 (fun x t -> CicNotationPt.Binder(`Forall,x,t))
 140                 final_params cty
 141           }
 142        ];
 143     })
 144   in
 145   let ids_to_nrefs = Hashtbl.create 1 in
 146   let boxml = Content2pres.ncontent2pres ~ids_to_nrefs cobj in
 147   prerr_endline (
 148    (BoxPp.render_to_string ~map_unicode_to_tex:false
 149      (function x::_ -> x | _ -> assert false) 80
 150      (CicNotationPres.mpres_of_box boxml)));
 151 *)
 152   CicNotationPt.Theorem
 153    (`Definition,srec_name,CicNotationPt.Implicit `JustOne,Some res)
 154 ;;
 155
 156 let ast_of_sort s =
 157   match s with
 158      NCic.Prop -> `Prop,"ind"
 159    | NCic.Type u ->
 160       let u = NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] (NCic.Sort s) in
 161       (try
 162         if String.sub u 0 4 = "Type" then
 163          `NType (String.sub u 4 (String.length u - 4)), "rect_" ^ u
 164         else if String.sub u 0 5 = "CProp" then
 165          `NCProp (String.sub u 5 (String.length u - 5)), "rect_" ^ u
 166         else
 167          (prerr_endline u;
 168          assert false)
 169        with Failure _ -> assert false)
 170 ;;
 171
 172 let mk_elims (uri,_,_,_,obj) =
 173   match obj with
 174     NCic.Inductive (true,leftno,[itl],_) ->
 175       List.map (fun s -> mk_elim uri leftno itl (ast_of_sort s))
 176        (NCic.Prop::
 177          List.map (fun s -> NCic.Type s) (NCicEnvironment.get_universes ()))
 178    | _ -> []
 179 ;;
 180
 181 (********************* Projections **********************)
 182
 183 let mk_lambda =
 184  function
 185     [] -> assert false
 186   | [t] -> t
 187   | l -> CicNotationPt.Appl l
 188 ;;
 189
 190 let rec count_prods = function NCic.Prod (_,_,t) -> 1 + count_prods t | _ -> 0;;
 191
 192 let rec nth_prod projs n ty =
 193  match ty with
 194     NCic.Prod (_,s,_) when n=0 -> projs, s
 195   | NCic.Prod (name,_,t) -> nth_prod (name::projs) (n-1) t
 196   | _ -> assert false
 197 ;;
 198
 199 (* this code should be unified with NTermCicContent.nast_of_cic0,
 200    but the two contexts have different types *)
 201 let rec pp rels =
 202  function
 203     NCic.Rel i -> List.nth rels (i - 1)
 204   | NCic.Const _ as t ->
 205      CicNotationPt.Ident
 206       (NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] t,None)
 207   | NCic.Sort s -> CicNotationPt.Sort (fst (ast_of_sort s))
 208   | NCic.Meta _
 209   | NCic.Implicit _ -> assert false
 210   | NCic.Appl l -> CicNotationPt.Appl (List.map (pp rels) l)
 211   | NCic.Prod (n,s,t) ->
 212      let n = mk_id n in
 213       CicNotationPt.Binder (`Pi, (n,Some (pp rels s)), pp (n::rels) t)
 214   | NCic.Lambda (n,s,t) ->
 215      let n = mk_id n in
 216       CicNotationPt.Binder (`Lambda, (n,Some (pp rels s)), pp (n::rels) t)
 217   | NCic.LetIn (n,s,ty,t) ->
 218      let n = mk_id n in
 219       CicNotationPt.LetIn ((n, Some (pp rels ty)), pp rels s, pp (n::rels) t)
 220   | NCic.Match (NReference.Ref (uri,_) as r,outty,te,patterns) ->
 221     let name = NUri.name_of_uri uri in
 222     let case_indty = Some (name, None) in
 223     let constructors, leftno =
 224      let _,leftno,tys,_,n = NCicEnvironment.get_checked_indtys r in
 225      let _,_,_,cl  = List.nth tys n in
 226       cl,leftno
 227     in
 228     let rec eat_branch n rels ty pat =
 229       match (ty, pat) with
 230       | NCic.Prod (name, s, t), _ when n > 0 ->
 231          eat_branch (pred n) rels t pat
 232       | NCic.Prod (_, _, t), NCic.Lambda (name, s, t') ->
 233           let cv, rhs = eat_branch 0 ((mk_id name)::rels) t t' in
 234            (mk_id name, Some (pp rels s)) :: cv, rhs
 235       | _, _ -> [], pp rels pat
 236     in
 237     let patterns =
 238       try
 239         List.map2
 240           (fun (_, name, ty) pat ->
 241             let capture_variables,rhs = eat_branch leftno rels ty pat in
 242              CicNotationPt.Pattern (name, None, capture_variables), rhs
 243           ) constructors patterns
 244       with Invalid_argument _ -> assert false
 245     in
 246      CicNotationPt.Case (pp rels te, case_indty, Some (pp rels outty), patterns)
 247 ;;
 248
 249 let mk_projection leftno tyname consname consty (projname,_,_) i =
 250  let argsno = count_prods consty - leftno in
 251  let rec aux names ty leftno =
 252   match leftno,ty with
 253    | 0,_ ->
 254      let arg = mk_id "xxx" in
 255      let arg_ty = mk_appl (mk_id tyname :: List.rev names) in
 256      let bvar = mk_id "yyy" in
 257      let underscore = CicNotationPt.Ident ("_",None),None in
 258      let bvars =
 259       HExtlib.mk_list underscore i @ [bvar,None] @
 260        HExtlib.mk_list underscore (argsno - i -1) in
 261      let branch = CicNotationPt.Pattern (consname,None,bvars), bvar in
 262      let projs,outtype = nth_prod [] i ty in
 263      let rels =
 264       List.map
 265        (fun name -> mk_appl (mk_id name :: List.rev names @ [arg])) projs
 266       @ names in
 267      let outtype = pp rels outtype in
 268      let outtype= CicNotationPt.Binder (`Lambda, (arg, Some arg_ty), outtype) in
 269       [arg, Some arg_ty], CicNotationPt.Case (arg,None,Some outtype,[branch])
 270    | _,NCic.Prod (name,_,t) ->
 271       let name = mk_id name in
 272       let params,body = aux (name::names) t (leftno - 1) in
 273        (name,None)::params, body
 274    | _,_ -> assert false
 275  in
 276  let params,bo = aux [] consty leftno in
 277  let pprojname = mk_id projname in
 278  let res =
 279   CicNotationPt.LetRec (`Inductive,
 280    [params, (pprojname,None), bo, leftno], pprojname) in
 281 (* prerr_endline
 282    (BoxPp.render_to_string
 283      ~map_unicode_to_tex:false
 284      (function x::_ -> x | _ -> assert false)
 285      80 (CicNotationPres.render (fun _ -> None)
 286      (TermContentPres.pp_ast res)));*)
 287   CicNotationPt.Theorem
 288    (`Definition,projname,CicNotationPt.Implicit `JustOne,Some res)
 289 ;;
 290
 291 let mk_projections (_,_,_,_,obj) =
 292  match obj with
 293     NCic.Inductive
 294      (true,leftno,[_,tyname,_,[_,consname,consty]],(_,`Record fields))
 295     ->
 296      HExtlib.list_mapi (mk_projection leftno tyname consname consty) fields
 297   | _ -> []
 298 ;;