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