helm/software/components/cic_unification/termUtil.ml

   1 (* Copyright (C) 2002, 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: proofEngineHelpers.ml 7022 2006-11-15 19:47:41Z fguidi $ *)
  27
  28 (* saturate_term newmeta metasenv context ty goal_arity                       *)
  29 (* Given a type [ty] (a backbone), it returns its suffix of length            *)
  30 (* [goal_arity] head and a new metasenv in which there is new a META for each *)
  31 (* hypothesis, a list of arguments for the new applications and the index of  *)
  32 (* the last new META introduced. The nth argument in the list of arguments is *)
  33 (* just the nth new META.                                                     *)
  34 let saturate_term ?(delta=true) newmeta metasenv context ty goal_arity =
  35  let module C = Cic in
  36  let module S = CicSubstitution in
  37  assert (goal_arity >= 0);
  38   let rec aux newmeta ty =
  39    match ty with
  40       C.Cast (he,_) -> aux newmeta he
  41 (* CSC: patch to generate ?1 : ?2 : Type in place of ?1 : Type to simulate ?1 :< Type
  42       (* If the expected type is a Type, then also Set is OK ==>
  43       *  we accept any term of type Type *)
  44       (*CSC: BUG HERE: in this way it is possible for the term of
  45       * type Type to be different from a Sort!!! *)
  46     | C.Prod (name,(C.Sort (C.Type _) as s),t) ->
  47        (* TASSI: ask CSC if BUG HERE refers to the C.Cast or C.Propd case *)
  48        let irl =
  49          CicMkImplicit.identity_relocation_list_for_metavariable context
  50        in
  51         let newargument = C.Meta (newmeta+1,irl) in
  52          let (res,newmetasenv,arguments,lastmeta) =
  53           aux (newmeta + 2) (S.subst newargument t)
  54          in
  55           res,
  56            (newmeta,[],s)::(newmeta+1,context,C.Meta (newmeta,[]))::newmetasenv,
  57            newargument::arguments,lastmeta
  58 *)
  59     | C.Prod (name,s,t) ->
  60        let irl =
  61          CicMkImplicit.identity_relocation_list_for_metavariable context
  62        in
  63         let newargument = C.Meta (newmeta,irl) in
  64          let res,newmetasenv,arguments,lastmeta,prod_no =
  65           aux (newmeta + 1) (S.subst newargument t)
  66          in
  67           if prod_no + 1 = goal_arity then
  68            let head = CicReduction.normalize ~delta:false context ty in
  69             head,[],[],newmeta,goal_arity + 1
  70           else
  71            (** NORMALIZE RATIONALE
  72             * we normalize the target only NOW since we may be in this case:
  73             * A1 -> A2 -> T where T = (\lambda x.A3 -> P) k
  74             * and we want a mesasenv with ?1:A1 and ?2:A2 and not
  75             * ?1, ?2, ?3 (that is the one we whould get if we start from the
  76             * beta-normalized A1 -> A2 -> A3 -> P **)
  77            let s' = CicReduction.normalize ~delta:false context s in
  78             res,(newmeta,context,s')::newmetasenv,newargument::arguments,
  79              lastmeta,prod_no + 1
  80     | t ->
  81        let head = CicReduction.normalize ~delta:false context t in
  82         match CicReduction.whd context head ~delta with
  83            C.Prod _ as head' -> aux newmeta head'
  84          | _ -> head,[],[],newmeta,0
  85   in
  86    (* WARNING: here we are using the invariant that above the most *)
  87    (* recente new_meta() there are no used metas.                  *)
  88    let res,newmetasenv,arguments,lastmeta,_ = aux newmeta ty in
  89     res,metasenv @ newmetasenv,arguments,lastmeta