1 (* Copyright (C) 2000, HELM Team.
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.
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.
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.
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,
22 * For details, see the HELM World-Wide-Web page,
23 * http://cs.unibo.it/helm/.
28 let debug_print = fun _ -> ();;
31 let rec liftaux k = function
33 | NCic.Sort _ as t -> t
35 if m < k then NCic.Rel m
37 | NCic.Meta (i,(m,l)) when k <= m -> NCic.Meta (i,(m+n,l))
38 | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t
39 | NCic.Meta (i,(m,l)) ->
40 let lctx = NCicUtils.expand_local_context l in
41 NCic.Meta (i, (m, NCic.Ctx (List.map (liftaux (k-m)) lctx)))
42 | NCic.Implicit _ -> (* was the identity *) assert false
43 | NCic.Prod (n,s,t) -> NCic.Prod (n, liftaux k s, liftaux (k+1) t)
44 | NCic.Lambda (n,s,t) -> NCic.Lambda (n, liftaux k s, liftaux (k+1) t)
45 | NCic.LetIn (n,ty,te,t) ->
46 NCic.LetIn (n, liftaux k ty, liftaux k te, liftaux (k+1) t)
47 | NCic.Appl l -> NCic.Appl (List.map (liftaux k) l)
48 | NCic.Match (r,outty,t,pl) ->
49 NCic.Match (r,liftaux k outty,liftaux k t, List.map (liftaux k) pl)
54 let lift ?(from=1) n t =
56 else lift_from from n t
60 (* substitutes [t1] for [Rel 1] in [t2] *)
61 (* if avoid_beta_redexes is true (default: false) no new beta redexes *)
62 (* are generated. WARNING: the substitution can diverge when t2 is not *)
63 (* well typed and avoid_beta_redexes is true. *)
64 let rec psubst ?(avoid_beta_redexes=false) delift lift_args args =
65 let nargs = List.length args in
66 let rec substaux k = function
68 | NCic.Const _ as t -> t
71 | n when n >= (k+nargs) -> if delift then NCic.Rel (n - nargs) else t
73 | n (* k <= n < k+nargs *) ->
74 (try lift (k+lift_args) (List.nth args (n-k))
75 with Failure _ -> assert false))
76 | NCic.Meta (_,(m,_)) as t when m >= k + nargs - 1 -> t
77 | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> 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.Prod (n,s,t) -> NCic.Prod (n, substaux k s, substaux (k + 1) t)
85 | NCic.Lambda (n,s,t) -> NCic.Lambda (n, substaux k s, substaux (k + 1) t)
86 | NCic.LetIn (n,ty,te,t) ->
87 NCic.LetIn (n, substaux k ty, substaux k te, substaux (k + 1) t)
88 | NCic.Appl (he::tl) ->
89 (* Invariant: no Appl applied to another Appl *)
90 let rec avoid he = function
94 | NCic.Appl l -> NCic.Appl (l@args)
95 | NCic.Lambda (_,_,bo) when avoid_beta_redexes ->
96 avoid (psubst ~avoid_beta_redexes true 0 [arg] bo) tl
97 | _ as he -> NCic.Appl (he::args))
99 let tl = List.map (substaux k) tl in
100 avoid (substaux k he) tl
101 | NCic.Appl _ -> assert false
102 | NCic.Match (r,outt,t,pl) ->
103 NCic.Match (r,substaux k outt, substaux k t, List.map (substaux k) pl)
108 let subst ?avoid_beta_redexes arg = psubst ?avoid_beta_redexes true 0 [arg];;
110 (* subst_meta (n, Some [t_1 ; ... ; t_n]) t *)
111 (* returns the term [t] where [Rel i] is substituted with [t_i] lifted by n *)
112 (* [t_i] is lifted as usual when it crosses an abstraction *)
113 (* subst_meta (n, Non) t -> lift n t *)
114 let subst_meta = function
116 | m, NCic.Ctx [] -> lift m
117 | m, NCic.Ctx l -> psubst false m l