matita/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   NotationPt.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 status ~subst context n te =
  29   match (n, NCicReduction.whd status ~subst context te) with
  30    | (0, _) -> context,te
  31    | (n, NCic.Prod (name,so,ta)) ->
  32        my_split_prods status ~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   | NotationPt.Appl l1 :: l2 -> NotationPt.Appl (l1 @ l2)
  42   | l -> NotationPt.Appl l
  43 ;;
  44
  45 let mk_elim status uri leftno it (outsort,suffix) pragma =
  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 status ~subst:[] [] leftno ty in
  52  let params = List.rev_map (function name,_ -> mk_id name) params in
  53  let args,sort = NCicReduction.split_prods status ~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 mk_prods =
  57   List.fold_right
  58    (fun name res -> NotationPt.Binder (`Forall,(name,None),res)) in
  59  let p_ty = mk_prods args
  60    (NotationPt.Binder
  61     (`Forall,
  62      (rec_arg,Some (mk_appl (mk_id ind_name :: params @ args))),
  63      NotationPt.Sort outsort)) in
  64  let mk_arrs n = mk_prods (HExtlib.mk_list (mk_id "_") n) in
  65  let args = args @ [rec_arg] in
  66  let k_names = List.map (function _,name,_ -> name_of_k name) cl in
  67  (*
  68  let final_params =
  69   List.map (function name -> name, None) params @
  70   [p_name,Some p_ty] @
  71   List.map (function name -> name, None) k_names @
  72   List.map (function name -> name, None) args in
  73  *)
  74  let cty = mk_appl (p_name :: args) in
  75  let ty = Some cty in
  76  let branches_with_args =
  77   List.map
  78    (function (_,name,ty) ->
  79      let _,ty = NCicReduction.split_prods status ~subst:[] [] leftno ty in
  80      let cargs,ty= my_split_prods status ~subst:[] [] (-1) ty in
  81      let cargs_recargs_nih =
  82       List.fold_left
  83        (fun (acc,nih) -> function
  84            _,NCic.Def _ -> assert false
  85          | name,NCic.Decl ty ->
  86             let context,ty = my_split_prods status ~subst:[] [] (-1) ty in
  87              match ty with
  88               | NCic.Const nref
  89               | NCic.Appl (NCic.Const nref::_)
  90                  when
  91                   let NReference.Ref (uri',_) = nref in
  92                    NUri.eq uri uri'
  93                  ->
  94                   let abs = List.rev_map (fun id,_ -> mk_id id) context in
  95                   let name = mk_id name in
  96                    (name, Some (
  97                    List.fold_right
  98                     (fun id res ->
  99                       NotationPt.Binder (`Lambda,(id,None),res))
 100                     abs
 101                     (NotationPt.Appl
 102                      (rec_name ::
 103                       params @
 104                       [p_name] @
 105                       k_names @
 106                       List.map (fun _ -> NotationPt.Implicit `JustOne)
 107                        (List.tl args) @
 108                       [mk_appl (name::abs)]))))::acc, nih + 1
 109               | _ -> (mk_id name,None)::acc,nih
 110        ) ([],0) cargs in
 111      let cargs_and_recursive_args, nih = cargs_recargs_nih in
 112      let cargs,recursive_args = List.split cargs_and_recursive_args in
 113      let recursive_args = HExtlib.filter_map (fun x -> x) recursive_args in
 114       (NotationPt.Pattern (name,None,List.map (fun x -> x,None) cargs),
 115        mk_appl (name_of_k name :: cargs @ recursive_args)), (name,cargs, nih)
 116    ) cl
 117  in
 118  let branches, branch_args = List.split branches_with_args in
 119  let bo = NotationPt.Case (rec_arg,Some (ind_name,None),Some p_name,branches) in
 120  let final_params =
 121   List.map (function name -> name, None) params @
 122   [p_name,Some p_ty] @
 123   List.map (function name, cargs, nih ->
 124             name_of_k name,
 125             Some (mk_prods cargs (mk_arrs nih
 126              (mk_appl
 127               (p_name::HExtlib.mk_list (NotationPt.Implicit `JustOne)
 128                (List.length args - 1) @
 129                [mk_appl (mk_id name :: params @ cargs)]))))) branch_args @
 130                List.map (function name -> name, None) args in
 131  let recno = List.length final_params in
 132  let where = recno - 1 in
 133  let attrs = `Generated, `Definition, pragma in
 134  let res =
 135   NotationPt.LetRec (`Inductive,
 136    [final_params, (rec_name,ty), bo, where], attrs)
 137  in
 138 (*
 139   prerr_endline
 140    (BoxPp.render_to_string
 141      ~map_unicode_to_tex:false
 142      (function x::_ -> x | _ -> assert false)
 143      80 (NotationPres.render (fun _ -> None)
 144      (TermContentPres.pp_ast res)));
 145   prerr_endline "#####";
 146   let cobj = ("xxx", [], None, `Joint {
 147       Content.joint_id = "yyy";
 148       joint_kind = `Recursive [recno];
 149       joint_defs =
 150        [ `Definition {
 151             Content.def_name = Some srec_name;
 152             def_id = "zzz";
 153             def_aref = "www";
 154             def_term = bo;
 155             def_type =
 156               List.fold_right
 157                 (fun x t -> NotationPt.Binder(`Forall,x,t))
 158                 final_params cty
 159           }
 160        ];
 161     })
 162   in
 163   let ids_to_nrefs = Hashtbl.create 1 in
 164   let boxml = Content2pres.ncontent2pres ~ids_to_nrefs cobj in
 165   prerr_endline (
 166    (BoxPp.render_to_string ~map_unicode_to_tex:false
 167      (function x::_ -> x | _ -> assert false) 80
 168      (NotationPres.mpres_of_box boxml)));
 169 *)
 170   res
 171 ;;
 172
 173 let ast_of_sort s =
 174   let headrm prefix s =
 175     try
 176       let len_prefix = String.length prefix in
 177       assert (String.sub s 0 len_prefix = prefix);
 178       String.sub s len_prefix (String.length s - len_prefix)
 179     with Invalid_argument _ -> assert false
 180   in
 181   match s with
 182    | NCic.Prop -> `Prop,"ind"
 183    | NCic.Type []  -> `NType "", "rect_Type"
 184    | NCic.Type ((`Type,u) :: _) ->
 185        let name = NUri.name_of_uri u in
 186        `NType (headrm "Type" name), "rect_" ^ name
 187    | NCic.Type ((`CProp,u) :: _) ->
 188        let name = NUri.name_of_uri u in
 189        `NCProp (headrm "Type" name),
 190        "rect_" ^ Str.replace_first (Str.regexp "Type") "CProp" name
 191    | _ -> assert false
 192 ;;
 193
 194 let mk_elims status (uri,_,_,_,obj) =
 195   match obj with
 196     NCic.Inductive (true,leftno,[itl],_) ->
 197       List.map (fun s-> mk_elim status uri leftno itl (ast_of_sort s) (`Elim s))
 198        (NCic.Prop::
 199          List.map (fun s -> NCic.Type s) (NCicEnvironment.get_universes ()))
 200    | _ -> []
 201 ;;
 202
 203 (********************* Projections **********************)
 204
 205 let mk_lambda =
 206  function
 207     [] -> assert false
 208   | [t] -> t
 209   | l -> NotationPt.Appl l
 210 ;;
 211
 212 let rec count_prods = function NCic.Prod (_,_,t) -> 1 + count_prods t | _ -> 0;;
 213
 214 let rec nth_prod projs n ty =
 215  match ty with
 216     NCic.Prod (_,s,_) when n=0 -> projs, s
 217   | NCic.Prod (name,_,t) -> nth_prod (name::projs) (n-1) t
 218   | _ -> assert false
 219 ;;
 220
 221 (* this code should be unified with NTermCicContent.nast_of_cic0,
 222    but the two contexts have different types *)
 223 let pp (status: #NCic.status) =
 224  let rec pp rels =
 225   function
 226     NCic.Rel i -> List.nth rels (i - 1)
 227   | NCic.Const _ as t -> NotationPt.NCic t
 228   | NCic.Sort s -> NotationPt.Sort (fst (ast_of_sort s))
 229   | NCic.Meta _
 230   | NCic.Implicit _ -> assert false
 231   | NCic.Appl l -> NotationPt.Appl (List.map (pp rels) l)
 232   | NCic.Prod (n,s,t) ->
 233      let n = mk_id n in
 234       NotationPt.Binder (`Pi, (n,Some (pp rels s)), pp (n::rels) t)
 235   | NCic.Lambda (n,s,t) ->
 236      let n = mk_id n in
 237       NotationPt.Binder (`Lambda, (n,Some (pp rels s)), pp (n::rels) t)
 238   | NCic.LetIn (n,ty,s,t) ->
 239      let n = mk_id n in
 240       NotationPt.LetIn ((n, Some (pp rels ty)), pp rels s, pp (n::rels) t)
 241   | NCic.Match (NReference.Ref (uri,_) as r,outty,te,patterns) ->
 242     let name = NUri.name_of_uri uri in
 243     let case_indty = Some (name, None) in
 244     let constructors, leftno =
 245      let _,leftno,tys,_,n = NCicEnvironment.get_checked_indtys status r in
 246      let _,_,_,cl  = List.nth tys n in
 247       cl,leftno
 248     in
 249     let rec eat_branch n rels ty pat =
 250       match (ty, pat) with
 251       | NCic.Prod (name, s, t), _ when n > 0 ->
 252          eat_branch (pred n) rels t pat
 253       | NCic.Prod (_, _, t), NCic.Lambda (name, s, t') ->
 254           let cv, rhs = eat_branch 0 ((mk_id name)::rels) t t' in
 255            (mk_id name, Some (pp rels s)) :: cv, rhs
 256       | _, _ -> [], pp rels pat
 257     in
 258     let patterns =
 259       try
 260         List.map2
 261           (fun (_, name, ty) pat ->
 262             let capture_variables,rhs = eat_branch leftno rels ty pat in
 263              NotationPt.Pattern (name, None, capture_variables), rhs
 264           ) constructors patterns
 265       with Invalid_argument _ -> assert false
 266     in
 267      NotationPt.Case (pp rels te, case_indty, Some (pp rels outty), patterns)
 268  in
 269   pp
 270 ;;
 271
 272 let mk_projection status leftno tyname consname consty (projname,_,_) i =
 273  let argsno = count_prods consty - leftno in
 274  let rec aux names ty leftno =
 275   match leftno,ty with
 276    | 0,_ ->
 277      let arg = mk_id "xxx" in
 278      let arg_ty = mk_appl (mk_id tyname :: List.rev names) in
 279      let bvar = mk_id "yyy" in
 280      let underscore = NotationPt.Ident ("_",None),None in
 281      let bvars =
 282       HExtlib.mk_list underscore i @ [bvar,None] @
 283        HExtlib.mk_list underscore (argsno - i -1) in
 284      let branch = NotationPt.Pattern (consname,None,bvars), bvar in
 285      let projs,outtype = nth_prod [] i ty in
 286      let rels =
 287       List.map
 288        (fun name -> mk_appl (mk_id name :: List.rev names @ [arg])) projs
 289       @ names in
 290      let outtype = pp status rels outtype in
 291      let outtype= NotationPt.Binder (`Lambda, (arg, Some arg_ty), outtype) in
 292       [arg, Some arg_ty], NotationPt.Case (arg,None,Some outtype,[branch])
 293    | _,NCic.Prod (name,_,t) ->
 294       let name = mk_id name in
 295       let params,body = aux (name::names) t (leftno - 1) in
 296        (name,None)::params, body
 297    | _,_ -> assert false
 298  in
 299  let params,bo = aux [] consty leftno in
 300  let pprojname = mk_id projname in
 301  let attrs = `Generated, `Definition, `Projection in
 302  let res =
 303   NotationPt.LetRec (`Inductive,
 304    [params, (pprojname,None), bo, leftno], attrs) in
 305 (* prerr_endline
 306    (BoxPp.render_to_string
 307      ~map_unicode_to_tex:false
 308      (function x::_ -> x | _ -> assert false)
 309      80 (NotationPres.render (fun _ -> None)
 310      (TermContentPres.pp_ast res)));*)
 311    res
 312 ;;
 313
 314 let mk_projections status (_,_,_,_,obj) =
 315  match obj with
 316     NCic.Inductive
 317      (true,leftno,[_,tyname,_,[_,consname,consty]],(_,`Record fields))
 318     ->
 319      HExtlib.list_mapi (mk_projection status leftno tyname consname consty) fields
 320   | _ -> []
 321 ;;