helm/matita/matitaInterpreter.ml

   1 (* Copyright (C) 2004, 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://helm.cs.unibo.it/
  24  *)
  25
  26 (** Interpreter for textual phrases coming from matita's console (textual entry
  27 * window at the bottom of the main window).
  28 *
  29 * Interpreter is either in Command state or in Proof state (see state type
  30 * below). In Command state commands for starting proofs are accepted, but
  31 * tactic and tactical applications are not. In Proof state both
  32 * tactic/tacticals and commands are accepted.
  33 *)
  34
  35 open Printf
  36
  37 open MatitaTypes
  38
  39 type state = Command | Proof
  40 type outcome = New_state of state | Quiet | Echo of string
  41
  42 exception Command_error of string
  43
  44 (*
  45 let uri name =
  46   UriManager.uri_of_string (sprintf "%s/%s" BuildTimeConf.base_uri name)
  47 *)
  48
  49 let baseuri = lazy (ref ("cic:/matita/" ^ Helm_registry.get "matita.owner"))
  50 let qualify name =
  51   let baseuri = !(Lazy.force baseuri) in
  52   if baseuri.[String.length baseuri - 1] = '/' then
  53     baseuri ^ name
  54   else
  55     String.concat "/" [baseuri; name]
  56 let split_obj = function
  57   | Cic.Constant (name, body, ty, _, attrs)
  58   | Cic.Variable (name, body, ty, _, attrs) -> (name, body, ty, attrs)
  59   | _ -> assert false
  60
  61 let canonical_context metano metasenv =
  62   try
  63     let (_, context, _) = List.find (fun (m, _, _) -> m = metano) metasenv in
  64     context
  65   with Not_found ->
  66     failwith (sprintf "Can't find canonical context for %d" metano)
  67
  68 let get_context_and_metasenv (currentProof:MatitaTypes.currentProof) =
  69   if currentProof#onGoing () then
  70     let proof = currentProof#proof in
  71     let metasenv = proof#metasenv in
  72     let goal = proof#goal in
  73     (canonical_context goal metasenv, metasenv)
  74   else
  75     ([], [])
  76
  77   (** term AST -> Cic.term. Uses disambiguator and change imperatively the
  78   * metasenv as needed *)
  79 let disambiguate ~(disambiguator:MatitaTypes.disambiguator) ~currentProof ast =
  80   if currentProof#onGoing () then begin
  81     let proof = currentProof#proof in
  82     let metasenv = proof#metasenv in
  83     let goal = proof#goal in
  84     let context = canonical_context goal metasenv in
  85     let (_, metasenv, term,ugraph) as retval =
  86       disambiguator#disambiguateTermAst ~context ~metasenv ast
  87     in
  88     proof#set_metasenv metasenv;
  89     retval
  90   end else
  91     disambiguator#disambiguateTermAst ast
  92
  93 class virtual interpreterState =
  94     (* static values, shared by all states inheriting this class *)
  95   let loc = ref None in
  96   let history = ref [] in
  97   fun ~(console: MatitaTypes.console) ->
  98   object (self)
  99
 100       (** eval a toplevel phrase in the current state and return the new state
 101       *)
 102     method parsePhrase s =
 103       match CicTextualParser2.parse_tactical s with
 104       | (TacticAst.LocatedTactical (loc', tac)) as tactical ->
 105           loc := Some loc';
 106           (match tac with (* update interpreter history *)
 107           | TacticAst.Command (TacticAst.Qed None) ->
 108               history := `Qed :: !history
 109           | TacticAst.Command (TacticAst.Theorem (_, Some name, _, None)) ->
 110               history := `Theorem name :: !history
 111           | TacticAst.Command (TacticAst.Qed _)
 112           | TacticAst.Command (TacticAst.Theorem _) -> assert false
 113           | _ -> history := `Tactic :: !history);
 114           tactical
 115       | _ -> assert false
 116
 117     method virtual evalTactical:
 118       (CicAst.term, string) TacticAst.tactical -> outcome
 119
 120     method evalPhrase s =
 121       debug_print (sprintf "evaluating '%s'" s);
 122       self#evalTactical (self#parsePhrase (Stream.of_string s))
 123
 124     method evalAst ast = self#evalTactical ast
 125
 126     method endOffset =
 127       match !loc with
 128       | Some (start_pos, end_pos) -> end_pos.Lexing.pos_cnum
 129       | None -> failwith "MatitaInterpreter: no offset recorded"
 130
 131   end
 132
 133   (** Implements phrases that should be accepted in all states *)
 134 class sharedState
 135   ~(disambiguator: MatitaTypes.disambiguator)
 136   ~(currentProof: MatitaTypes.currentProof)
 137   ~(console: MatitaTypes.console)
 138   ?(mathViewer: MatitaTypes.mathViewer option)
 139   ~(dbd: Mysql.dbd)
 140   ()
 141 =
 142   object (self)
 143     inherit interpreterState ~console
 144     method evalTactical = function
 145       | TacticAst.Command TacticAst.Quit ->
 146           currentProof#quit ();
 147           assert false  (* dummy answer, useless *)
 148       | TacticAst.Command TacticAst.Proof ->
 149             (* do nothing, just for compatibility with coq syntax *)
 150           New_state Command
 151       | TacticAst.Command (TacticAst.Baseuri (Some uri)) ->
 152           Lazy.force baseuri := uri;
 153           console#echo_message (sprintf "base uri set to \"%s\"" uri);
 154           Quiet
 155       | TacticAst.Command (TacticAst.Baseuri None) ->
 156           console#echo_message (sprintf "base uri is \"%s\""
 157             !(Lazy.force baseuri));
 158           Quiet
 159       | TacticAst.Command (TacticAst.Check term) ->
 160           let (_, _, term,ugraph) =
 161             disambiguate ~disambiguator ~currentProof term
 162           in
 163           let (context, metasenv) = get_context_and_metasenv currentProof in
 164           let dummyno = CicMkImplicit.new_meta metasenv [] in
 165           let ty,ugraph1 =
 166             CicTypeChecker.type_of_aux' metasenv context term ugraph
 167           in
 168             (* TASSI: here ugraph1 is unused.... FIXME *)
 169           let expr = Cic.Cast (term, ty) in
 170           let sequent = (dummyno, context, expr) in
 171           (match mathViewer with
 172           | None -> ()
 173           | Some v -> v#checkTerm sequent metasenv);
 174           Quiet
 175       | TacticAst.Command (TacticAst.Search_pat (search_kind, pat)) ->
 176           let uris =
 177             match search_kind with
 178             | `Locate -> MetadataQuery.locate ~dbd pat
 179             | `Elim -> MetadataQuery.elim ~dbd pat
 180             | _ -> assert false
 181           in
 182           (* TODO ZACK: show URIs to the user *)
 183           Quiet
 184       | tactical ->
 185           raise (Command_error (TacticAstPp.pp_tactical tactical))
 186   end
 187
 188 open Printf
 189
 190 let pp_indtypes indTypes =
 191   List.iter
 192     (fun (name, _, typ, constructors) ->
 193       printf "%s: %s\n" name (CicPp.ppterm typ);
 194       List.iter
 195         (fun (name, term) -> printf "\t%s: %s\n" name (CicPp.ppterm term))
 196         constructors)
 197     indTypes;
 198   flush stdout
 199
 200 let inddef_of_ast params indTypes (disambiguator:MatitaTypes.disambiguator) =
 201   let add_pi binders t =
 202     List.fold_right
 203       (fun (name, ast) acc ->
 204         CicAst.Binder (`Forall, (Cic.Name name, Some ast), acc))
 205       binders t
 206   in
 207   let ind_binders =
 208     List.map (fun (name, _, typ, _) -> (name, add_pi params typ)) indTypes
 209   in
 210   let binders = ind_binders @ params in
 211   let asts = ref [] in
 212   let add_ast ast = asts := ast :: !asts in
 213   let paramsno = List.length params in
 214   let indbindersno = List.length ind_binders in
 215   List.iter
 216     (fun (name, _, typ, constructors) ->
 217       add_ast (add_pi params typ);
 218       List.iter (fun (_, ast) -> add_ast (add_pi binders ast)) constructors)
 219     indTypes;
 220   let (_, metasenv, terms, ugraph) =
 221     disambiguator#disambiguateTermAsts ~metasenv:[] !asts
 222   in
 223   let terms = ref (List.rev terms) in
 224   let get_term () =
 225     match !terms with [] -> assert false | hd :: tl -> terms := tl; hd
 226   in
 227   let uri =
 228     match indTypes with
 229     | (name, _, _, _) :: _ -> qualify name ^ ".ind"
 230     | _ -> assert false
 231   in
 232   let mutinds =
 233     let counter = ref 0 in
 234     List.map
 235       (fun _ ->
 236         incr counter;
 237         CicUtil.term_of_uri (sprintf "%s#xpointer(1/%d)" uri !counter))
 238       indTypes
 239   in
 240   let subst_mutinds = List.fold_right CicSubstitution.subst mutinds in
 241   let cicIndTypes =
 242     List.fold_left
 243       (fun acc (name, inductive, typ, constructors) ->
 244         let cicTyp = get_term () in
 245         let cicConstructors =
 246           List.fold_left
 247             (fun acc (name, _) ->
 248               let typ =
 249                 subst_mutinds (CicUtil.strip_prods indbindersno (get_term ()))
 250               in
 251               (name, typ) :: acc)
 252             [] constructors
 253         in
 254         (name, inductive, cicTyp, List.rev cicConstructors) :: acc)
 255       [] indTypes
 256   in
 257   let cicIndTypes = List.rev cicIndTypes in
 258   (UriManager.uri_of_string uri, (cicIndTypes, [], paramsno))
 259
 260   (* TODO Zack a lot more to be done here:
 261     * - save object to disk in xml format
 262     * - register uri to the getter
 263     * - save universe file *)
 264 let add_constant_to_world ~(console:MatitaTypes.console)
 265   ~dbd ~uri ?body ~ty ?(params = []) ?(attrs = []) ~ugraph ()
 266 =
 267   let suri = UriManager.string_of_uri uri in
 268   if CicEnvironment.in_library uri then
 269     error (sprintf "%s constant already defined" suri)
 270   else begin
 271     let name = UriManager.name_of_uri uri in
 272     let obj = Cic.Constant (name, body, ty, params, attrs) in
 273     let ugraph = CicUnivUtils.clean_and_fill uri obj ugraph in
 274     CicEnvironment.add_type_checked_term uri (obj, ugraph);
 275     MetadataDb.index_constant ~dbd
 276       ~owner:(Helm_registry.get "matita.owner") ~uri ~body ~ty;
 277     console#echo_message (sprintf "%s constant defined" suri)
 278   end
 279
 280 let add_inductive_def_to_world ~(console:MatitaTypes.console)
 281   ~dbd ~uri ~indTypes ?(params = []) ?(leftno = 0) ?(attrs = []) ~ugraph ()
 282 =
 283   let suri = UriManager.string_of_uri uri in
 284   if CicEnvironment.in_library uri then
 285     error (sprintf "%s inductive type already defined" suri)
 286   else begin
 287     let name = UriManager.name_of_uri uri in
 288     let obj = Cic.InductiveDefinition (indTypes, params, leftno, attrs) in
 289     let ugraph = CicUnivUtils.clean_and_fill uri obj ugraph in
 290     CicEnvironment.put_inductive_definition uri (obj, ugraph);
 291     MetadataDb.index_inductive_def ~dbd
 292       ~owner:(Helm_registry.get "matita.owner") ~uri ~types:indTypes;
 293     console#echo_message (sprintf "%s inductive type defined" suri);
 294     let elim sort =
 295       try
 296         let obj = CicElim.elim_of ~sort uri 0 in
 297         let (name, body, ty, attrs) = split_obj obj in
 298         let suri = qualify name ^ ".con" in
 299         let uri = UriManager.uri_of_string suri in
 300           (* TODO Zack: make CicElim returns a universe *)
 301         let ugraph = CicUniv.empty_ugraph in
 302         add_constant_to_world ~console ~dbd ~uri ?body ~ty ~attrs ~ugraph ();
 303 (*
 304         console#echo_message
 305           (sprintf "%s eliminator (automatically) defined" suri)
 306 *)
 307       with CicElim.Can_t_eliminate -> ()
 308     in
 309     List.iter elim [ Cic.Prop; Cic.Set; (Cic.Type (CicUniv.fresh ())) ];
 310   end
 311
 312   (** Implements phrases that should be accepted only in Command state *)
 313 class commandState
 314   ~(disambiguator: MatitaTypes.disambiguator)
 315   ~(currentProof: MatitaTypes.currentProof)
 316   ~(console: MatitaTypes.console)
 317   ?mathViewer
 318   ~(dbd: Mysql.dbd)
 319   ()
 320 =
 321   let shared =
 322     new sharedState ~disambiguator ~currentProof ~console ?mathViewer ~dbd ()
 323   in
 324   object (self)
 325     inherit interpreterState ~console
 326
 327     method evalTactical = function
 328       | TacticAst.LocatedTactical (_, tactical) -> self#evalTactical tactical
 329       | TacticAst.Command (TacticAst.Theorem (_, Some name, ast, None)) ->
 330           let (_, metasenv, expr,ugraph) =
 331             disambiguator#disambiguateTermAst ast
 332           in
 333           let uri = UriManager.uri_of_string (qualify name ^ ".con") in
 334           let proof = MatitaProof.proof ~typ:expr ~uri ~metasenv () in
 335           currentProof#start proof;
 336           New_state Proof
 337       | TacticAst.Command
 338         (TacticAst.Theorem (_, Some name, type_ast, Some body_ast)) ->
 339           let (_, metasenv, type_cic, ugraph) =
 340             disambiguator#disambiguateTermAst type_ast
 341           in
 342           let (_, metasenv, body_cic, ugraph) =
 343             disambiguator#disambiguateTermAst ~metasenv body_ast
 344           in
 345           let (body_type, ugraph) =
 346             CicTypeChecker.type_of_aux' metasenv [] body_cic ugraph
 347           in
 348           let uri = UriManager.uri_of_string (qualify name ^ ".con") in
 349           let (subst, metasenv, ugraph) =
 350             CicUnification.fo_unif metasenv [] body_type type_cic ugraph
 351           in
 352           let body = CicMetaSubst.apply_subst subst body_cic in
 353           let ty = CicMetaSubst.apply_subst subst type_cic in
 354           add_constant_to_world ~console ~dbd ~uri ~body ~ty ~ugraph ();
 355           Quiet
 356       | TacticAst.Command (TacticAst.Inductive (params, indTypes)) ->
 357
 358           let (uri, (indTypes, params, leftno)) =
 359             inddef_of_ast params indTypes disambiguator
 360           in
 361           let obj = Cic.InductiveDefinition (indTypes, params, leftno, []) in
 362           let ugraph =
 363             CicTypeChecker.typecheck_mutual_inductive_defs uri
 364               (indTypes, params, leftno) CicUniv.empty_ugraph
 365           in
 366           add_inductive_def_to_world ~console
 367             ~dbd ~uri ~indTypes ~params ~leftno ~ugraph ();
 368           Quiet
 369       | TacticAst.Command TacticAst.Quit ->
 370           currentProof#quit ();
 371           New_state Command (* dummy answer, useless *)
 372       | TacticAst.Command TacticAst.Proof ->
 373             (* do nothing, just for compatibility with coq syntax *)
 374           New_state Command
 375       | tactical -> shared#evalTactical tactical
 376   end
 377
 378   (** create a ProofEngineTypes.mk_fresh_name_type function which uses given
 379   * names as long as they are available, then it fallbacks to name generation
 380   * using FreshNamesGenerator module *)
 381 let namer_of names =
 382   let len = List.length names in
 383   let count = ref 0 in
 384   fun metasenv context name ~typ ->
 385     if !count < len then begin
 386       let name = Cic.Name (List.nth names !count) in
 387       incr count;
 388       name
 389     end else
 390       FreshNamesGenerator.mk_fresh_name ~subst:[] metasenv context name ~typ
 391
 392   (** Implements phrases that should be accepted only in Proof state, basically
 393   * tacticals *)
 394 class proofState
 395   ~(disambiguator: MatitaTypes.disambiguator)
 396   ~(currentProof: MatitaTypes.currentProof)
 397   ~(console: MatitaTypes.console)
 398   ?mathViewer
 399   ~(dbd: Mysql.dbd)
 400   ()
 401 =
 402   let disambiguate ast =
 403     let (_, _, term, _) = disambiguate ~disambiguator ~currentProof ast in
 404     term
 405   in
 406     (** tactic AST -> ProofEngineTypes.tactic *)
 407   let rec lookup_tactic = function
 408     | TacticAst.LocatedTactic (_, tactic) -> lookup_tactic tactic
 409     | TacticAst.Intros (_, names) ->  (* TODO Zack implement intros length *)
 410         PrimitiveTactics.intros_tac ~mk_fresh_name_callback:(namer_of names) ()
 411     | TacticAst.Reflexivity -> Tactics.reflexivity
 412     | TacticAst.Assumption -> Tactics.assumption
 413     | TacticAst.Contradiction -> Tactics.contradiction
 414     | TacticAst.Exists -> Tactics.exists
 415     | TacticAst.Fourier -> Tactics.fourier
 416     | TacticAst.Left -> Tactics.left
 417     | TacticAst.Right -> Tactics.right
 418     | TacticAst.Ring -> Tactics.ring
 419     | TacticAst.Split -> Tactics.split
 420     | TacticAst.Symmetry -> Tactics.symmetry
 421     | TacticAst.Transitivity term -> Tactics.transitivity (disambiguate term)
 422     | TacticAst.Apply term -> Tactics.apply (disambiguate term)
 423     | TacticAst.Absurd term -> Tactics.absurd (disambiguate term)
 424     | TacticAst.Exact term -> Tactics.exact (disambiguate term)
 425     | TacticAst.Cut term -> Tactics.cut (disambiguate term)
 426     | TacticAst.Elim (term, _) -> (* TODO Zack implement "using" argument *)
 427         Tactics.elim_intros_simpl (disambiguate term)
 428     | TacticAst.ElimType term -> Tactics.elim_type (disambiguate term)
 429     | TacticAst.Replace (what, with_what) ->
 430         Tactics.replace ~what:(disambiguate what)
 431           ~with_what:(disambiguate with_what)
 432     | TacticAst.Auto -> Tactics.auto_new ~dbd
 433   (*
 434     (* TODO Zack a lot more of tactics to be implemented here ... *)
 435     | TacticAst.Change of 'term * 'term * 'ident option
 436     | TacticAst.Change_pattern of 'term pattern * 'term * 'ident option
 437     | TacticAst.Decompose of 'ident * 'ident list
 438     | TacticAst.Discriminate of 'ident
 439     | TacticAst.Fold of reduction_kind * 'term
 440     | TacticAst.Injection of 'ident
 441     | TacticAst.LetIn of 'term * 'ident
 442     | TacticAst.Reduce of reduction_kind * 'term pattern * 'ident option
 443     | TacticAst.Replace_pattern of 'term pattern * 'term
 444     | TacticAst.Rewrite of direction * 'term * 'ident option
 445   *)
 446     | _ ->
 447         MatitaTypes.not_implemented "some tactic"
 448   in
 449   let shared =
 450     new sharedState ~disambiguator ~currentProof ~console ?mathViewer ~dbd ()
 451   in
 452   object (self)
 453     inherit interpreterState ~console
 454
 455     method evalTactical = function
 456       | TacticAst.LocatedTactical (_, tactical) -> self#evalTactical tactical
 457       | TacticAst.Command TacticAst.Abort ->
 458           currentProof#abort ();
 459           New_state Command
 460       | TacticAst.Command (TacticAst.Undo steps) ->
 461           currentProof#proof#undo ?steps ();
 462           New_state Proof
 463       | TacticAst.Command (TacticAst.Redo steps) ->
 464           currentProof#proof#redo ?steps ();
 465           New_state Proof
 466       | TacticAst.Command (TacticAst.Qed None) ->
 467           if not (currentProof#onGoing ()) then assert false;
 468           let proof = currentProof#proof in
 469           let (uri, metasenv, bo, ty) = proof#proof in
 470           let uri = MatitaTypes.unopt_uri uri in
 471           let suri = UriManager.string_of_uri uri in
 472             (* TODO Zack this function probably should not simply fail with
 473             * Failure, but rather raise some more meaningful exception *)
 474           if metasenv <> [] then failwith "Proof not completed";
 475           let proved_ty,ugraph =
 476             CicTypeChecker.type_of_aux' [] [] bo CicUniv.empty_ugraph
 477           in
 478           let b,ugraph =
 479             CicReduction.are_convertible [] proved_ty ty ugraph
 480           in
 481           if not b then failwith "Wrong proof";
 482           add_constant_to_world ~console ~dbd ~uri ~body:bo ~ty ~ugraph ();
 483           currentProof#abort ();
 484           (match mathViewer with None -> () | Some v -> v#unload ());
 485           console#echo_message (sprintf "%s defined" suri);
 486           New_state Command
 487       | TacticAst.Seq tacticals ->
 488           (* TODO Zack check for proof completed at each step? *)
 489           List.iter (fun t -> ignore (self#evalTactical t)) tacticals;
 490           New_state Proof
 491       | TacticAst.Tactic tactic_phrase ->
 492           let tactic = lookup_tactic tactic_phrase in
 493           currentProof#proof#apply_tactic tactic;
 494           New_state Proof
 495       | tactical -> shared#evalTactical tactical
 496   end
 497
 498 class interpreter
 499   ~(disambiguator: MatitaTypes.disambiguator)
 500   ~(currentProof: MatitaTypes.currentProof)
 501   ~(console: MatitaTypes.console)
 502   ?mathViewer
 503   ~(dbd: Mysql.dbd)
 504   ()
 505 =
 506   let commandState =
 507     new commandState ~disambiguator ~currentProof ~console ?mathViewer ~dbd ()
 508   in
 509   let proofState =
 510     new proofState ~disambiguator ~currentProof ~console ?mathViewer ~dbd ()
 511   in
 512   object (self)
 513     val mutable state = commandState
 514
 515     method reset = state <- commandState
 516
 517     method endOffset = state#endOffset
 518
 519     method private updateState = function
 520       | New_state Command -> (state <- commandState)
 521       | New_state Proof -> (state <- proofState)
 522       | _ -> ()
 523
 524     method private eval f =
 525       let ok () = (* console#clear (); *) (true, true) in
 526       match console#wrap_exn f with
 527       | Some (New_state Command) -> (state <- commandState); ok ()
 528       | Some (New_state Proof) -> (state <- proofState); ok ()
 529       | Some (Echo msg) -> console#echo_message msg; (true, false)
 530       | Some Quiet -> ok ()
 531       | None -> (false, false)
 532
 533     method evalPhrase s = self#eval (fun () -> state#evalPhrase s)
 534     method evalAst ast = self#eval (fun () -> state#evalAst ast)
 535   end
 536