helm/software/components/ng_kernel/nCicSubstitution.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$ *)
  27
  28 let debug_print = fun _ -> ();;
  29
  30 (* to be moved in cic util *)
  31 let expand_local_context = function
  32   | NCic.Irl len ->
  33       let rec aux acc = function
  34         | 0 -> acc
  35         | n -> aux (NCic.Rel n::acc) (n-1)
  36       in
  37        aux [] len
  38   | NCic.Ctx lctx -> lctx
  39 ;;
  40
  41 let lift_from k n =
  42  let rec liftaux k = function
  43     | NCic.Const _
  44     | NCic.Sort _ as t -> t
  45     | NCic.Rel m ->
  46        if m < k then NCic.Rel m
  47        else NCic.Rel (m + n)
  48     | NCic.Meta (i,(m,l)) when k <= m -> NCic.Meta (i,(m+n,l))
  49     | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t
  50     | NCic.Meta (i,(m,l)) ->
  51        let lctx = expand_local_context l in
  52        NCic.Meta (i, (m, NCic.Ctx (List.map (liftaux (k-m)) lctx)))
  53     | NCic.Implicit _ -> (* was the identity *) assert false
  54     | NCic.Prod (n,s,t) -> NCic.Prod (n, liftaux k s, liftaux (k+1) t)
  55     | NCic.Lambda (n,s,t) -> NCic.Lambda (n, liftaux k s, liftaux (k+1) t)
  56     | NCic.LetIn (n,ty,te,t) ->
  57        NCic.LetIn (n, liftaux k ty, liftaux k te, liftaux (k+1) t)
  58     | NCic.Appl l -> NCic.Appl (List.map (liftaux k) l)
  59     | NCic.Match (r,outty,t,pl) ->
  60        NCic.Match (r,liftaux k outty,liftaux k t, List.map (liftaux k) pl)
  61  in
  62  liftaux k
  63 ;;
  64
  65 let lift ?(from=1) n t =
  66   if n = 0 then t
  67   else lift_from from n t
  68 ;;
  69
  70 (* subst t1 t2                                                          *)
  71 (*  substitutes [t1] for [Rel 1] in [t2]                                *)
  72 (*  if avoid_beta_redexes is true (default: false) no new beta redexes  *)
  73 (*  are generated. WARNING: the substitution can diverge when t2 is not *)
  74 (*  well typed and avoid_beta_redexes is true.                          *)
  75 let rec psubst ?(avoid_beta_redexes=false) delift lift_args args =
  76  let nargs = List.length args in
  77  let rec substaux k = function
  78     | NCic.Rel n as t ->
  79        (match n with
  80        | n when n >= (k+nargs) -> if delift then NCic.Rel (n - nargs) else t
  81        | n when n < k -> t
  82        | n (* k <= n < k+nargs *) ->
  83         (try lift (k+lift_args) (List.nth args (n-k))
  84          with Failure _ -> assert false))
  85     | NCic.Meta (_,(m,_)) as t when m >= k + nargs - 1 -> t
  86     | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t
  87     | NCic.Meta (i,(m,l)) ->
  88        let lctx = expand_local_context l in
  89        (* 1-nargs < k-m, when <= 0 is still reasonable because we will
  90         * substitute args[ k-m ... k-m+nargs-1 > 0 ] *)
  91        NCic.Meta (i,(m, NCic.Ctx (List.map (substaux (k-m)) lctx)))
  92     | NCic.Sort _ as t -> t
  93     | NCic.Implicit _ -> assert false (* was identity *)
  94     | NCic.Prod (n,s,t) -> NCic.Prod (n, substaux k s, substaux (k + 1) t)
  95     | NCic.Lambda (n,s,t) -> NCic.Lambda (n, substaux k s, substaux (k + 1) t)
  96     | NCic.LetIn (n,ty,te,t) ->
  97        NCic.LetIn (n, substaux k ty, substaux k te, substaux (k + 1) t)
  98     | NCic.Appl (he::tl) ->
  99        (* Invariant: no Appl applied to another Appl *)
 100        let rec avoid he = function
 101          | [] -> he
 102          | arg::tl as args->
 103              (match he with
 104              | NCic.Appl l -> NCic.Appl (l@args)
 105              | NCic.Lambda (_,_,bo) when avoid_beta_redexes ->
 106                  avoid (psubst ~avoid_beta_redexes true 0 [arg] bo) tl
 107              | _ as he -> NCic.Appl (he::args))
 108        in
 109        let tl = List.map (substaux k) tl in
 110        avoid (substaux k he) tl
 111     | NCic.Appl _ -> assert false
 112     | NCic.Const _ as t -> t
 113     | NCic.Match (r,outt,t,pl) ->
 114        NCic.Match (r,substaux k outt, substaux k t, List.map (substaux k) pl)
 115  in
 116   substaux 1
 117 ;;
 118
 119 let subst ?avoid_beta_redexes arg = psubst ?avoid_beta_redexes true 0 [arg];;
 120
 121 (* subst_meta (n, Some [t_1 ; ... ; t_n]) t                                  *)
 122 (*  returns the term [t] where [Rel i] is substituted with [t_i] lifted by n *)
 123 (*  [t_i] is lifted as usual when it crosses an abstraction                  *)
 124 (* subst_meta (n, Non) t -> lift n t                                        *)
 125 let subst_meta = function
 126   | m, NCic.Irl _
 127   | m, NCic.Ctx [] -> lift m
 128   | m, NCic.Ctx l  -> psubst false m l
 129 ;;