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 -> if m < k then t else NCic.Rel (m + n)
  19     | NCic.Meta (i,(m,l)) as t when k <= m ->
  20        if n = 0 then t else NCic.Meta (i,(m+n,l))
  21     | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t
  22     | NCic.Meta (i,(m,l)) ->
  23        let lctx = NCicUtils.expand_local_context l in
  24        NCic.Meta (i, (m, NCic.Ctx (NCicUtils.sharing_map (liftaux (k-m)) lctx)))
  25     | NCic.Implicit _ -> (* was the identity *) assert false
  26     | t -> NCicUtils.map (fun _ k -> k + 1) k liftaux t
  27  in
  28  liftaux k
  29 ;;
  30
  31 let lift ?(from=1) n t =
  32   if n = 0 then t
  33   else lift_from from n t
  34 ;;
  35
  36 (* subst t1 t2                                                          *)
  37 (*  substitutes [t1] for [Rel 1] in [t2]                                *)
  38 (*  if avoid_beta_redexes is true (default: false) no new beta redexes  *)
  39 (*  are generated. WARNING: the substitution can diverge when t2 is not *)
  40 (*  well typed and avoid_beta_redexes is true.                          *)
  41 (*  map_arg is ReductionStrategy.from_env_for_unwind when psubst is     *)
  42 (*  used to implement nCicReduction.unwind'                             *)
  43 let rec psubst ?(avoid_beta_redexes=false) delift lift_args map_arg args =
  44  let nargs = List.length args in
  45  let rec substaux k = function
  46    | NCic.Rel n as t ->
  47       (match n with
  48       | n when n >= (k+nargs) ->
  49          if delift && nargs <> 0 then NCic.Rel (n - nargs) else t
  50       | n when n < k -> t
  51       | n (* k <= n < k+nargs *) ->
  52        (try lift (k-1+lift_args) (map_arg (List.nth args (n-k)))
  53         with Failure _ -> assert false))
  54    | NCic.Meta (i,(m,l)) as t when m >= k + nargs - 1 ->
  55        if delift && nargs <> 0 then NCic.Meta (i,(m-nargs,l)) else t
  56    | NCic.Meta (i,(m,(NCic.Irl l as irl))) as t when k > l + m ->
  57        if delift && nargs <> 0 then NCic.Meta (i,(m-nargs,irl)) else t
  58    | NCic.Meta (i,(m,l)) ->
  59       let lctx = NCicUtils.expand_local_context l in
  60       (* 1-nargs < k-m, when <= 0 is still reasonable because we will
  61        * substitute args[ k-m ... k-m+nargs-1 > 0 ] *)
  62       NCic.Meta (i,(m, NCic.Ctx (NCicUtils.sharing_map (substaux (k-m)) lctx)))
  63    | NCic.Implicit _ -> assert false (* was identity *)
  64    | NCic.Appl (he::tl) as t ->
  65       (* Invariant: no Appl applied to another Appl *)
  66       let rec avoid he' = function
  67         | [] -> he'
  68         | arg::tl' as args->
  69             (match he' with
  70             | NCic.Appl l -> NCic.Appl (l@args)
  71             | NCic.Lambda (_,_,bo) when avoid_beta_redexes ->
  72                 (* map_arg is here \x.x, Obj magic is needed because
  73                  * we don't have polymorphic recursion w/o records *)
  74                 avoid (psubst
  75                   ~avoid_beta_redexes true 0 Obj.magic [Obj.magic arg] bo) tl'
  76             | _ -> if he == he' && args == tl then t else NCic.Appl (he'::args))
  77       in
  78       let tl = NCicUtils.sharing_map (substaux k) tl in
  79       avoid (substaux k he) tl
  80    | t -> NCicUtils.map (fun _ k -> k + 1) k substaux t
  81  in
  82   substaux 1
  83 ;;
  84
  85 let subst ?avoid_beta_redexes arg =
  86   psubst ?avoid_beta_redexes true 0 (fun x -> x)[arg];;
  87
  88 (* subst_meta (n, Some [t_1 ; ... ; t_n]) t                                  *)
  89 (*  returns the term [t] where [Rel i] is substituted with [t_i] lifted by n *)
  90 (*  [t_i] is lifted as usual when it crosses an abstraction                  *)
  91 (* subst_meta (n, Non) t -> lift n t                                        *)
  92 let subst_meta = function
  93   | m, NCic.Irl _
  94   | m, NCic.Ctx [] -> lift m
  95   | m, NCic.Ctx l  -> psubst false m (fun x -> x) l
  96 ;;