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