components/cic_exportation/cicExportation.ml

   1 (* Copyright (C) 2000, 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 (* $Id: cicPp.ml 7413 2007-05-29 15:30:53Z tassi $ *)
  27
  28 exception CicExportationInternalError;;
  29 exception NotEnoughElements;;
  30
  31 (* Utility functions *)
  32
  33 let analyze_term context t =
  34  match fst(CicTypeChecker.type_of_aux' [] context t CicUniv.oblivion_ugraph)with
  35     Cic.Sort _ -> `Type
  36   | ty ->
  37      match
  38       fst (CicTypeChecker.type_of_aux' [] context ty CicUniv.oblivion_ugraph)
  39      with
  40         Cic.Sort Cic.Prop -> `Proof
  41      | _ -> `Term
  42 ;;
  43
  44 let analyze_type context t =
  45  let rec aux =
  46   function
  47      Cic.Sort s -> `Sort s
  48    | Cic.Prod (_,_,t) -> aux t
  49    | _ -> `SomethingElse
  50  in
  51  match aux t with
  52     `Sort _ as res -> res
  53   | `SomethingElse ->
  54       match
  55        fst(CicTypeChecker.type_of_aux' [] context t CicUniv.oblivion_ugraph)
  56       with
  57           Cic.Sort Cic.Prop -> `Statement
  58        | _ -> `Type
  59 ;;
  60
  61 let ppid =
  62  let reserved =
  63   [ "to";
  64     "mod";
  65     "val";
  66     "in";
  67     "function"
  68   ]
  69  in
  70   function n ->
  71    let n = String.uncapitalize n in
  72     if List.mem n reserved then n ^ "_" else n
  73 ;;
  74
  75 let ppname =
  76  function
  77     Cic.Name s     -> ppid s
  78   | Cic.Anonymous  -> "_"
  79 ;;
  80
  81 (* get_nth l n   returns the nth element of the list l if it exists or *)
  82 (* raises NotEnoughElements if l has less than n elements             *)
  83 let rec get_nth l n =
  84  match (n,l) with
  85     (1, he::_) -> he
  86   | (n, he::tail) when n > 1 -> get_nth tail (n-1)
  87   | (_,_) -> raise NotEnoughElements
  88 ;;
  89
  90 let qualified_name_of_uri current_module_uri ?(capitalize=false) uri =
  91  let name =
  92   if capitalize then
  93    String.capitalize (UriManager.name_of_uri uri)
  94   else
  95    ppid (UriManager.name_of_uri uri) in
  96   let filename =
  97    let suri = UriManager.buri_of_uri uri in
  98    let s = String.sub suri 5 (String.length suri - 5) in
  99    let s = Pcre.replace ~pat:"/" ~templ:"_" s in
 100     String.uncapitalize s in
 101   if current_module_uri = UriManager.buri_of_uri uri then
 102    name
 103   else
 104    String.capitalize filename ^ "." ^ name
 105 ;;
 106
 107 let pp current_module_uri ?metasenv ~in_type =
 108 let rec pp ~in_type t context =
 109  let module C = Cic in
 110    match t with
 111       C.Rel n ->
 112        begin
 113         try
 114          (match get_nth context n with
 115              Some (C.Name s,_) -> ppid s
 116            | Some (C.Anonymous,_) -> "__" ^ string_of_int n
 117            | None -> "_hidden_" ^ string_of_int n
 118          )
 119         with
 120          NotEnoughElements -> string_of_int (List.length context - n)
 121        end
 122     | C.Var (uri,exp_named_subst) ->
 123         qualified_name_of_uri current_module_uri uri ^
 124          pp_exp_named_subst exp_named_subst context
 125     | C.Meta (n,l1) ->
 126        (match metasenv with
 127            None ->
 128             "?" ^ (string_of_int n) ^ "[" ^
 129              String.concat " ; "
 130               (List.rev_map
 131                 (function
 132                     None -> "_"
 133                   | Some t -> pp ~in_type:false t context) l1) ^
 134              "]"
 135          | Some metasenv ->
 136             try
 137              let _,context,_ = CicUtil.lookup_meta n metasenv in
 138               "?" ^ (string_of_int n) ^ "[" ^
 139                String.concat " ; "
 140                 (List.rev
 141                   (List.map2
 142                     (fun x y ->
 143                       match x,y with
 144                          _, None
 145                        | None, _ -> "_"
 146                        | Some _, Some t -> pp ~in_type:false t context
 147                     ) context l1)) ^
 148                "]"
 149             with
 150               CicUtil.Meta_not_found _
 151             | Invalid_argument _ ->
 152               "???" ^ (string_of_int n) ^ "[" ^
 153                String.concat " ; "
 154                 (List.rev_map (function None -> "_" | Some t ->
 155                   pp ~in_type:false t context) l1) ^
 156                "]"
 157        )
 158     | C.Sort s ->
 159        (match s with
 160            C.Prop  -> "Prop"
 161          | C.Set   -> "Set"
 162          | C.Type _ -> "Type"
 163          (*| C.Type u -> ("Type" ^ CicUniv.string_of_universe u)*)
 164          | C.CProp -> "CProp"
 165        )
 166     | C.Implicit (Some `Hole) -> "%"
 167     | C.Implicit _ -> "?"
 168     | C.Prod (b,s,t) ->
 169        (match b with
 170           C.Name n ->
 171            let n = "'" ^ String.uncapitalize n in
 172             "(" ^ pp ~in_type:true s context ^ " -> " ^
 173             pp ~in_type:true t ((Some (Cic.Name n,Cic.Decl s))::context) ^ ")"
 174         | C.Anonymous ->
 175            "(" ^ pp ~in_type:true s context ^ " -> " ^
 176            pp ~in_type:true t ((Some (b,Cic.Decl s))::context) ^ ")")
 177     | C.Cast (v,t) -> pp ~in_type v context
 178     | C.Lambda (b,s,t) ->
 179        (match analyze_type context s with
 180            `Sort _
 181          | `Statement -> pp ~in_type t ((Some (b,Cic.Decl s))::context)
 182          | `Type ->
 183             "(function " ^ ppname b ^ " -> " ^
 184              pp ~in_type t ((Some (b,Cic.Decl s))::context) ^ ")")
 185     | C.LetIn (b,s,t) ->
 186        let ty,_ = CicTypeChecker.type_of_aux' [] context s CicUniv.oblivion_ugraph in
 187        "(let " ^ ppname b ^ " = " ^ pp ~in_type:false s context ^ " in " ^
 188         pp ~in_type t ((Some (b,Cic.Def (s,Some ty)))::context) ^ ")"
 189     | C.Appl (he::tl) when in_type ->
 190        let hes = pp ~in_type he context in
 191        let stl = String.concat "," (clean_args_for_ty context tl) in
 192         (if stl = "" then "" else "(" ^ stl ^ ") ") ^ hes
 193     | C.Appl (C.MutInd _ as he::tl) ->
 194        let hes = pp ~in_type he context in
 195        let stl = String.concat "," (clean_args_for_ty context tl) in
 196         (if stl = "" then "" else "(" ^ stl ^ ") ") ^ hes
 197     | C.Appl (C.MutConstruct (uri,n,_,_) as he::tl) ->
 198        let nparams =
 199         match fst(CicEnvironment.get_obj CicUniv.empty_ugraph uri) with
 200            C.InductiveDefinition (_,_,nparams,_) -> nparams
 201          | _ -> assert false in
 202        let hes = pp ~in_type he context in
 203        let stl = String.concat "," (clean_args nparams context tl) in
 204         "(" ^ hes ^ (if stl = "" then "" else "(" ^ stl ^ ")") ^ ")"
 205     | C.Appl li ->
 206        "(" ^ String.concat " " (clean_args 0 context li) ^ ")"
 207     | C.Const (uri,exp_named_subst) ->
 208        qualified_name_of_uri current_module_uri uri ^
 209         pp_exp_named_subst exp_named_subst context
 210     | C.MutInd (uri,n,exp_named_subst) ->
 211        (try
 212          match fst(CicEnvironment.get_obj CicUniv.empty_ugraph uri) with
 213             C.InductiveDefinition (dl,_,_,_) ->
 214              let (name,_,_,_) = get_nth dl (n+1) in
 215               qualified_name_of_uri current_module_uri
 216                (UriManager.uri_of_string
 217                  (UriManager.buri_of_uri uri ^ "/" ^ name ^ ".con")) ^
 218               pp_exp_named_subst exp_named_subst context
 219           | _ -> raise CicExportationInternalError
 220         with
 221            Sys.Break as exn -> raise exn
 222          | _ -> UriManager.string_of_uri uri ^ "#1/" ^ string_of_int (n + 1)
 223        )
 224     | C.MutConstruct (uri,n1,n2,exp_named_subst) ->
 225        (try
 226          match fst(CicEnvironment.get_obj CicUniv.empty_ugraph uri) with
 227             C.InductiveDefinition (dl,_,_,_) ->
 228              let _,_,_,cons = get_nth dl (n1+1) in
 229               let id,_ = get_nth cons n2 in
 230                qualified_name_of_uri current_module_uri ~capitalize:true
 231                 (UriManager.uri_of_string
 232                   (UriManager.buri_of_uri uri ^ "/" ^ id ^ ".con")) ^
 233                pp_exp_named_subst exp_named_subst context
 234           | _ -> raise CicExportationInternalError
 235         with
 236            Sys.Break as exn -> raise exn
 237          | _ ->
 238           UriManager.string_of_uri uri ^ "#1/" ^ string_of_int (n1 + 1) ^ "/" ^
 239            string_of_int n2
 240        )
 241     | C.MutCase (uri,n1,ty,te,patterns) ->
 242        if in_type then
 243         "unit (* TOO POLYMORPHIC TYPE *)"
 244        else (
 245        let needs_obj_magic =
 246         (* BUG HERE: we should consider also the right parameters *)
 247         match CicReduction.whd context ty with
 248            Cic.Lambda (_,_,t) -> not (DoubleTypeInference.does_not_occur 1 t)
 249          | _ -> false (* it can be a Rel, e.g. in *_rec *)
 250        in
 251        (match analyze_term context te with
 252            `Type -> assert false
 253          | `Proof ->
 254              (match patterns with
 255                  [] -> "assert false"   (* empty type elimination *)
 256                | [he] ->
 257                   pp ~in_type:false he context  (* singleton elimination *)
 258                | _ -> assert false)
 259          | `Term ->
 260             if patterns = [] then "assert false"
 261             else
 262              (let connames_and_argsno =
 263                (match fst(CicEnvironment.get_obj CicUniv.empty_ugraph uri) with
 264                    C.InductiveDefinition (dl,_,paramsno,_) ->
 265                     let (_,_,_,cons) = get_nth dl (n1+1) in
 266                      List.map
 267                       (fun (id,ty) ->
 268                         (* this is just an approximation since we do not have
 269                            reduction yet! *)
 270                         let rec count_prods toskip =
 271                          function
 272                             C.Prod (_,_,bo) when toskip > 0 ->
 273                              count_prods (toskip - 1) bo
 274                           | C.Prod (_,_,bo) -> 1 + count_prods 0 bo
 275                           | _ -> 0
 276                         in
 277                          qualified_name_of_uri current_module_uri
 278                           ~capitalize:true
 279                           (UriManager.uri_of_string
 280                             (UriManager.buri_of_uri uri ^ "/" ^ id ^ ".con")),
 281                          count_prods paramsno ty
 282                       ) cons
 283                  | _ -> raise CicExportationInternalError
 284                )
 285               in
 286                let connames_and_argsno_and_patterns =
 287                 let rec combine =
 288                    function
 289                       [],[] -> []
 290                     | (x,no)::tlx,y::tly -> (x,no,y)::(combine (tlx,tly))
 291                     | _,_ -> assert false
 292                 in
 293                  combine (connames_and_argsno,patterns)
 294                in
 295                 "\n(match " ^ pp ~in_type:false te context ^ " with \n   " ^
 296                  (String.concat "\n | "
 297                   (List.map
 298                    (fun (x,argsno,y) ->
 299                      let rec aux argsno context =
 300                       function
 301                          Cic.Lambda (name,ty,bo) when argsno > 0 ->
 302                           let name =
 303                            match name with
 304                               Cic.Anonymous -> Cic.Anonymous
 305                             | Cic.Name n -> Cic.Name (ppid n) in
 306                           let args,res =
 307                            aux (argsno - 1) (Some (name,Cic.Decl ty)::context)
 308                             bo
 309                           in
 310                            (match analyze_type context ty with
 311                                `Statement
 312                              | `Sort _ -> args,res
 313                              | `Type ->
 314                                  (match name with
 315                                      C.Anonymous -> "_"
 316                                    | C.Name s -> s)::args,res)
 317                        | t when argsno = 0 -> [],pp ~in_type:false t context
 318                        | t ->
 319                           ["{" ^ string_of_int argsno ^ " args missing}"],
 320                            pp ~in_type:false t context
 321                      in
 322                       let pattern,body =
 323                        if argsno = 0 then x,pp ~in_type:false y context
 324                        else
 325                         let args,body = aux argsno context y in
 326                         let sargs = String.concat "," args in
 327                          x ^ (if sargs = "" then "" else "(" ^ sargs^ ")"),
 328                           body
 329                       in
 330                        pattern ^ " -> " ^
 331                         if needs_obj_magic then
 332                          "Obj.magic (" ^ body ^ ")"
 333                         else
 334                          body
 335                    ) connames_and_argsno_and_patterns)) ^
 336                  ")\n")))
 337     | C.Fix (no, funs) ->
 338        let names =
 339         List.rev
 340          (List.map
 341            (function (name,_,ty,_) ->
 342              Some (C.Name name,Cic.Decl ty)) funs)
 343        in
 344          "let rec " ^
 345          List.fold_right
 346           (fun (name,ind,ty,bo) i -> name ^ " = \n" ^
 347             pp ~in_type:false bo (names@context) ^ i)
 348           funs "" ^
 349          " in " ^
 350          (match get_nth names (no + 1) with
 351              Some (Cic.Name n,_) -> n
 352            | _ -> assert false)
 353     | C.CoFix (no,funs) ->
 354        let names =
 355         List.rev
 356          (List.map
 357            (function (name,ty,_) ->
 358              Some (C.Name name,Cic.Decl ty)) funs)
 359        in
 360          "\nCoFix " ^ " {" ^
 361          List.fold_right
 362           (fun (name,ty,bo) i -> "\n" ^ name ^
 363             " : " ^ pp ~in_type:true ty context ^ " := \n" ^
 364             pp ~in_type:false bo (names@context) ^ i)
 365           funs "" ^
 366          "}\n"
 367 and pp_exp_named_subst exp_named_subst context =
 368  if exp_named_subst = [] then "" else
 369   "\\subst[" ^
 370    String.concat " ; " (
 371     List.map
 372      (function (uri,t) -> UriManager.name_of_uri uri ^ " \\Assign " ^ pp ~in_type:false t context)
 373      exp_named_subst
 374    ) ^ "]"
 375 and clean_args nparams context =
 376  let nparams = ref nparams in
 377  HExtlib.filter_map
 378   (function t ->
 379     decr nparams;
 380     match analyze_term context t with
 381        `Term when !nparams < 0 -> Some (pp ~in_type:false t context)
 382      | `Term
 383      | `Type
 384      | `Proof -> None)
 385 and clean_args_for_ty context =
 386  HExtlib.filter_map
 387   (function t ->
 388     match analyze_term context t with
 389        `Type -> Some (pp ~in_type:true t context)
 390      | `Proof -> None
 391      | `Term -> None)
 392 in
 393  pp ~in_type
 394 ;;
 395
 396 let ppty current_module_uri =
 397  (* nparams is the number of left arguments
 398     left arguments should either become parameters or be skipped altogether *)
 399  let rec args nparams context =
 400   function
 401      Cic.Prod (n,s,t) ->
 402       let n =
 403        match n with
 404           Cic.Anonymous -> Cic.Anonymous
 405         | Cic.Name n -> Cic.Name (String.uncapitalize n)
 406       in
 407        (match analyze_type context s with
 408            `Statement
 409          | `Sort Cic.Prop ->
 410              args (nparams - 1) ((Some (n,Cic.Decl s))::context) t
 411          | `Type when nparams > 0 ->
 412              args (nparams - 1) ((Some (n,Cic.Decl s))::context) t
 413          | `Type ->
 414              let abstr,args =
 415               args (nparams - 1) ((Some (n,Cic.Decl s))::context) t in
 416                abstr,pp ~in_type:true current_module_uri s context::args
 417          | `Sort _ when nparams <= 0 ->
 418              let n = Cic.Name "unit (* EXISTENTIAL TYPE *)" in
 419               args (nparams - 1) ((Some (n,Cic.Decl s))::context) t
 420          | `Sort _ ->
 421              let n =
 422               match n with
 423                  Cic.Anonymous -> Cic.Anonymous
 424                | Cic.Name name -> Cic.Name ("'" ^ name) in
 425              let abstr,args =
 426               args (nparams - 1) ((Some (n,Cic.Decl s))::context) t
 427              in
 428               (match n with
 429                   Cic.Anonymous -> abstr
 430                 | Cic.Name name -> name::abstr),
 431               args)
 432    | _ -> [],[]
 433  in
 434   args
 435 ;;
 436
 437 exception DoNotExtract;;
 438
 439 let pp_abstracted_ty current_module_uri =
 440  let rec args context =
 441   function
 442      Cic.Lambda (n,s,t) ->
 443       let n =
 444        match n with
 445           Cic.Anonymous -> Cic.Anonymous
 446         | Cic.Name n -> Cic.Name (String.uncapitalize n)
 447       in
 448        (match analyze_type context s with
 449            `Statement
 450          | `Type
 451          | `Sort Cic.Prop ->
 452              args ((Some (n,Cic.Decl s))::context) t
 453          | `Sort _ ->
 454              let n =
 455               match n with
 456                  Cic.Anonymous -> Cic.Anonymous
 457                | Cic.Name name -> Cic.Name ("'" ^ name) in
 458              let abstr,res =
 459               args ((Some (n,Cic.Decl s))::context) t
 460              in
 461               (match n with
 462                   Cic.Anonymous -> abstr
 463                 | Cic.Name name -> name::abstr),
 464               res)
 465    | ty ->
 466      match analyze_type context ty with
 467       `  Sort _
 468       | `Statement -> raise DoNotExtract
 469       | `Type ->
 470           (* BUG HERE: this can be a real System F type *)
 471           let head = pp ~in_type:true current_module_uri ty context in
 472           [],head
 473  in
 474   args
 475 ;;
 476
 477
 478 (* ppinductiveType (typename, inductive, arity, cons)                       *)
 479 (* pretty-prints a single inductive definition                              *)
 480 (* (typename, inductive, arity, cons)                                       *)
 481 let ppinductiveType current_module_uri nparams (typename, inductive, arity, cons)
 482 =
 483  match analyze_type [] arity with
 484     `Sort Cic.Prop -> ""
 485   | `Statement
 486   | `Type -> assert false
 487   | `Sort _ ->
 488     if cons = [] then
 489      "type " ^ String.uncapitalize typename ^ " = unit (* empty type *)\n"
 490     else (
 491      let abstr,scons =
 492       List.fold_right
 493        (fun (id,ty) (_abstr,i) -> (* we should verify _abstr = abstr' *)
 494           let abstr',sargs = ppty current_module_uri nparams [] ty in
 495           let sargs = String.concat " * " sargs in
 496            abstr',
 497            String.capitalize id ^
 498             (if sargs = "" then "" else " of " ^ sargs) ^
 499             (if i = "" then "" else "\n | ") ^ i)
 500        cons ([],"")
 501       in
 502        let abstr =
 503         let s = String.concat "," abstr in
 504         if s = "" then "" else "(" ^ s ^ ") "
 505        in
 506        "type " ^ abstr ^ String.uncapitalize typename ^ " =\n" ^ scons ^ "\n")
 507 ;;
 508
 509 let ppobj current_module_uri obj =
 510  let module C = Cic in
 511  let module U = UriManager in
 512   let pp ~in_type = pp ~in_type current_module_uri in
 513   match obj with
 514     C.Constant (name, Some t1, t2, params, _) ->
 515       (match analyze_type [] t2 with
 516           `Sort Cic.Prop
 517         | `Statement -> ""
 518         | `Type -> "let " ^ ppid name ^ " =\n" ^ pp ~in_type:false t1 [] ^ "\n"
 519         | `Sort _ ->
 520             match analyze_type [] t1 with
 521                `Sort Cic.Prop -> ""
 522              | _ ->
 523                (try
 524                  let abstr,res = pp_abstracted_ty current_module_uri [] t1 in
 525                  let abstr =
 526                   let s = String.concat "," abstr in
 527                   if s = "" then "" else "(" ^ s ^ ") "
 528                  in
 529                   "type " ^ abstr ^ ppid name ^ " = " ^ res ^ "\n"
 530                 with
 531                  DoNotExtract -> ""))
 532    | C.Constant (name, None, ty, params, _) ->
 533       (match analyze_type [] ty with
 534           `Sort Cic.Prop
 535         | `Statement -> ""
 536         | `Sort _ -> "type " ^ ppid name ^ "\n"
 537         | `Type -> "let " ^ ppid name ^ " = assert false\n")
 538    | C.Variable (name, bo, ty, params, _) ->
 539       "Variable " ^ name ^
 540        "(" ^ String.concat ";" (List.map UriManager.string_of_uri params) ^
 541        ")" ^ ":\n" ^
 542        pp ~in_type:true ty [] ^ "\n" ^
 543        (match bo with None -> "" | Some bo -> ":= " ^ pp ~in_type:false bo [])
 544    | C.CurrentProof (name, conjectures, value, ty, params, _) ->
 545       "Current Proof of " ^ name ^
 546        "(" ^ String.concat ";" (List.map UriManager.string_of_uri params) ^
 547        ")" ^ ":\n" ^
 548       let separate s = if s = "" then "" else s ^ " ; " in
 549        List.fold_right
 550         (fun (n, context, t) i ->
 551           let conjectures',name_context =
 552                  List.fold_right
 553                   (fun context_entry (i,name_context) ->
 554                     (match context_entry with
 555                         Some (n,C.Decl at) ->
 556                          (separate i) ^
 557                            ppname n ^ ":" ^
 558                             pp ~in_type:true ~metasenv:conjectures
 559                             at name_context ^ " ",
 560                             context_entry::name_context
 561                       | Some (n,C.Def (at,None)) ->
 562                          (separate i) ^
 563                            ppname n ^ ":= " ^ pp ~in_type:false
 564                             ~metasenv:conjectures at name_context ^ " ",
 565                             context_entry::name_context
 566                       | None ->
 567                          (separate i) ^ "_ :? _ ", context_entry::name_context
 568                       | _ -> assert false)
 569             ) context ("",[])
 570           in
 571            conjectures' ^ " |- " ^ "?" ^ (string_of_int n) ^ ": " ^
 572             pp ~in_type:true ~metasenv:conjectures t name_context ^ "\n" ^ i
 573         ) conjectures "" ^
 574         "\n" ^ pp ~in_type:false ~metasenv:conjectures value [] ^ " : " ^
 575           pp ~in_type:true ~metasenv:conjectures ty []
 576    | C.InductiveDefinition (l, params, nparams, _) ->
 577       List.fold_right
 578        (fun x i -> ppinductiveType current_module_uri nparams x ^ i) l ""
 579 ;;
 580
 581 let ppobj current_module_uri obj =
 582  let res = ppobj current_module_uri obj in
 583   if res = "" then "" else res ^ ";;\n\n"
 584 ;;