helm/software/components/ng_kernel/nCicSubstitution.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$ *)
  13
  14 let debug_print = fun _ -> ();;
  15
  16 let lift_from k n =
  17  let rec liftaux k = function
  18     | NCic.Rel m as t ->
  19        if m < k then t
  20        else NCic.Rel (m + n)
  21     | NCic.Meta (i,(m,l)) when k <= m -> NCic.Meta (i,(m+n,l))
  22     | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t
  23     | NCic.Meta (i,(m,l)) ->
  24        let lctx = NCicUtils.expand_local_context l in
  25        NCic.Meta (i, (m, NCic.Ctx (List.map (liftaux (k-m)) lctx)))
  26     | NCic.Implicit _ -> (* was the identity *) assert false
  27     | t -> NCicUtils.map liftaux ((+) 1) k t
  28    (*
  29     | NCic.Const _
  30     | NCic.Sort _ as t -> t
  31     | NCic.Rel m ->
  32        if m < k then NCic.Rel m
  33        else NCic.Rel (m + n)
  34     | NCic.Meta (i,(m,l)) when k <= m -> NCic.Meta (i,(m+n,l))
  35     | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t
  36     | NCic.Meta (i,(m,l)) ->
  37        let lctx = NCicUtils.expand_local_context l in
  38        NCic.Meta (i, (m, NCic.Ctx (List.map (liftaux (k-m)) lctx)))
  39     | NCic.Implicit _ -> (* was the identity *) assert false
  40     | NCic.Prod (n,s,t) -> NCic.Prod (n, liftaux k s, liftaux (k+1) t)
  41     | NCic.Lambda (n,s,t) -> NCic.Lambda (n, liftaux k s, liftaux (k+1) t)
  42     | NCic.LetIn (n,ty,te,t) ->
  43        NCic.LetIn (n, liftaux k ty, liftaux k te, liftaux (k+1) t)
  44     | NCic.Appl l -> NCic.Appl (List.map (liftaux k) l)
  45     | NCic.Match (r,outty,t,pl) ->
  46        NCic.Match (r,liftaux k outty,liftaux k t, List.map (liftaux k) pl)
  47    *)
  48  in
  49  liftaux k
  50 ;;
  51
  52 let lift ?(from=1) n t =
  53   if n = 0 then t
  54   else lift_from from n t
  55 ;;
  56
  57 (* subst t1 t2                                                          *)
  58 (*  substitutes [t1] for [Rel 1] in [t2]                                *)
  59 (*  if avoid_beta_redexes is true (default: false) no new beta redexes  *)
  60 (*  are generated. WARNING: the substitution can diverge when t2 is not *)
  61 (*  well typed and avoid_beta_redexes is true.                          *)
  62 (*  map_arg is ReductionStrategy.from_env_for_unwind when psubst is     *)
  63 (*  used to implement nCicReduction.unwind'                             *)
  64 let rec psubst ?(avoid_beta_redexes=false) delift lift_args map_arg args =
  65  let nargs = List.length args in
  66  let rec substaux k = function
  67     | NCic.Rel n as t ->
  68        (match n with
  69        | n when n >= (k+nargs) -> if delift then NCic.Rel (n - nargs) else t
  70        | n when n < k -> t
  71        | n (* k <= n < k+nargs *) ->
  72         (try lift (k+lift_args) (map_arg (List.nth args (n-k)))
  73          with Failure _ -> assert false))
  74     | NCic.Meta (i,(m,l)) as t when m >= k + nargs - 1 ->
  75         if delift then NCic.Meta (i,(m-nargs,l)) else t
  76     | NCic.Meta (i,(m,(NCic.Irl l as irl))) as t when k > l + m ->
  77         if delift then NCic.Meta (i,(m-nargs,irl)) else t
  78     | NCic.Meta (i,(m,l)) ->
  79        let lctx = NCicUtils.expand_local_context l in
  80        (* 1-nargs < k-m, when <= 0 is still reasonable because we will
  81         * substitute args[ k-m ... k-m+nargs-1 > 0 ] *)
  82        NCic.Meta (i,(m, NCic.Ctx (List.map (substaux (k-m)) lctx)))
  83     | NCic.Implicit _ -> assert false (* was identity *)
  84     | NCic.Appl (he::tl) ->
  85        (* Invariant: no Appl applied to another Appl *)
  86        let rec avoid he = function
  87          | [] -> he
  88          | arg::tl as args->
  89              (match he with
  90              | NCic.Appl l -> NCic.Appl (l@args)
  91              | NCic.Lambda (_,_,bo) when avoid_beta_redexes ->
  92                  (* map_arg is here \x.x, Obj magic is needed because
  93                   * we don't have polymorphic recursion w/o records *)
  94                  avoid (psubst
  95                    ~avoid_beta_redexes true 0 Obj.magic [Obj.magic arg] bo) tl
  96              | _ as he -> NCic.Appl (he::args))
  97        in
  98        let tl = List.map (substaux k) tl in
  99        avoid (substaux k he) tl
 100     | NCic.Appl _ -> assert false
 101     | t -> NCicUtils.map substaux ((+) 1) k t
 102    (*
 103     | NCic.Sort _
 104     | NCic.Const _ as t -> t
 105     | NCic.Rel n as t ->
 106        (match n with
 107        | n when n >= (k+nargs) -> if delift then NCic.Rel (n - nargs) else t
 108        | n when n < k -> t
 109        | n (* k <= n < k+nargs *) ->
 110         (try lift (k+lift_args) (map_arg (List.nth args (n-k)))
 111          with Failure _ -> assert false))
 112     | NCic.Meta (i,(m,l)) as t when m >= k + nargs - 1 ->
 113         if delift then NCic.Meta (i,(m-nargs,l)) else t
 114     | NCic.Meta (i,(m,(NCic.Irl l as irl))) as t when k > l + m ->
 115         if delift then NCic.Meta (i,(m-nargs,irl)) else t
 116     | NCic.Meta (i,(m,l)) ->
 117        let lctx = NCicUtils.expand_local_context l in
 118        (* 1-nargs < k-m, when <= 0 is still reasonable because we will
 119         * substitute args[ k-m ... k-m+nargs-1 > 0 ] *)
 120        NCic.Meta (i,(m, NCic.Ctx (List.map (substaux (k-m)) lctx)))
 121     | NCic.Implicit _ -> assert false (* was identity *)
 122     | NCic.Prod (n,s,t) -> NCic.Prod (n, substaux k s, substaux (k + 1) t)
 123     | NCic.Lambda (n,s,t) -> NCic.Lambda (n, substaux k s, substaux (k + 1) t)
 124     | NCic.LetIn (n,ty,te,t) ->
 125        NCic.LetIn (n, substaux k ty, substaux k te, substaux (k + 1) t)
 126     | NCic.Appl (he::tl) ->
 127        (* Invariant: no Appl applied to another Appl *)
 128        let rec avoid he = function
 129          | [] -> he
 130          | arg::tl as args->
 131              (match he with
 132              | NCic.Appl l -> NCic.Appl (l@args)
 133              | NCic.Lambda (_,_,bo) when avoid_beta_redexes ->
 134                  (* map_arg is here \x.x, Obj magic is needed because
 135                   * we don't have polymorphic recursion w/o records *)
 136                  avoid (psubst
 137                    ~avoid_beta_redexes true 0 Obj.magic [Obj.magic arg] bo) tl
 138              | _ as he -> NCic.Appl (he::args))
 139        in
 140        let tl = List.map (substaux k) tl in
 141        avoid (substaux k he) tl
 142     | NCic.Appl _ -> assert false
 143     | NCic.Match (r,outt,t,pl) ->
 144        NCic.Match (r,substaux k outt, substaux k t, List.map (substaux k) pl)
 145    *)
 146  in
 147   substaux 1
 148 ;;
 149
 150 let subst ?avoid_beta_redexes arg =
 151   psubst ?avoid_beta_redexes true 0 (fun x -> x)[arg];;
 152
 153 (* subst_meta (n, Some [t_1 ; ... ; t_n]) t                                  *)
 154 (*  returns the term [t] where [Rel i] is substituted with [t_i] lifted by n *)
 155 (*  [t_i] is lifted as usual when it crosses an abstraction                  *)
 156 (* subst_meta (n, Non) t -> lift n t                                        *)
 157 let subst_meta = function
 158   | m, NCic.Irl _
 159   | m, NCic.Ctx [] -> lift m
 160   | m, NCic.Ctx l  -> psubst false m (fun x -> x) l
 161 ;;