X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Fsoftware%2Fcomponents%2Fng_kernel%2FnCicSubstitution.ml;h=43a2f8174a74a1cad4696523908e8a4575f6933e;hb=889815067d64e081eb90ea1a792890c2ad4e511c;hp=4f5e25ecce91be0764fc841ee5bf423bdea7a317;hpb=3594cdffdc6941ed86fef264a681e5db417c5d8a;p=helm.git diff --git a/helm/software/components/ng_kernel/nCicSubstitution.ml b/helm/software/components/ng_kernel/nCicSubstitution.ml index 4f5e25ecc..43a2f8174 100644 --- a/helm/software/components/ng_kernel/nCicSubstitution.ml +++ b/helm/software/components/ng_kernel/nCicSubstitution.ml @@ -1,52 +1,38 @@ -(* Copyright (C) 2000, HELM Team. - * - * This file is part of HELM, an Hypertextual, Electronic - * Library of Mathematics, developed at the Computer Science - * Department, University of Bologna, Italy. - * - * HELM is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - * - * HELM is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with HELM; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, - * MA 02111-1307, USA. - * - * For details, see the HELM World-Wide-Web page, - * http://cs.unibo.it/helm/. - *) +(* + ||M|| This file is part of HELM, an Hypertextual, Electronic + ||A|| Library of Mathematics, developed at the Computer Science + ||T|| Department, University of Bologna, Italy. + ||I|| + ||T|| HELM is free software; you can redistribute it and/or + ||A|| modify it under the terms of the GNU General Public License + \ / version 2 or (at your option) any later version. + \ / This software is distributed as is, NO WARRANTY. + V_______________________________________________________________ *) (* $Id$ *) +let ppterm = + ref (fun ~context:_ ~subst:_ ~metasenv:_ ?inside_fix _ -> + let _ = inside_fix in assert false) +;; +let set_ppterm f = ppterm := f;; + +module C = NCic +module Ref = NReference + let debug_print = fun _ -> ();; let lift_from k n = let rec liftaux k = function - | NCic.Const _ - | NCic.Sort _ as t -> t - | NCic.Rel m -> - if m < k then NCic.Rel m - else NCic.Rel (m + n) - | NCic.Meta (i,(m,l)) when k <= m -> NCic.Meta (i,(m+n,l)) - | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t - | NCic.Meta (i,(m,l)) -> + | C.Rel m as t -> if m < k then t else C.Rel (m + n) + | C.Meta (i,(m,(C.Irl 0 as l))) when k <= m+1 -> C.Meta (i,(m,l)) + | C.Meta (i,(m,l)) when k <= m+1 -> C.Meta (i,(m+n,l)) + | C.Meta (_,(m,C.Irl l)) as t when k > l + m -> t + | C.Meta (i,(m,l)) -> let lctx = NCicUtils.expand_local_context l in - NCic.Meta (i, (m, NCic.Ctx (List.map (liftaux (k-m)) lctx))) - | NCic.Implicit _ -> (* was the identity *) assert false - | NCic.Prod (n,s,t) -> NCic.Prod (n, liftaux k s, liftaux (k+1) t) - | NCic.Lambda (n,s,t) -> NCic.Lambda (n, liftaux k s, liftaux (k+1) t) - | NCic.LetIn (n,ty,te,t) -> - NCic.LetIn (n, liftaux k ty, liftaux k te, liftaux (k+1) t) - | NCic.Appl l -> NCic.Appl (List.map (liftaux k) l) - | NCic.Match (r,outty,t,pl) -> - NCic.Match (r,liftaux k outty,liftaux k t, List.map (liftaux k) pl) + C.Meta (i, (m, C.Ctx (HExtlib.sharing_map (liftaux (k-m)) lctx))) + | C.Implicit _ -> (* was the identity *) assert false + | t -> NCicUtils.map (fun _ k -> k + 1) k liftaux t in liftaux k ;; @@ -56,63 +42,63 @@ let lift ?(from=1) n t = else lift_from from n t ;; + (* subst t1 t2 *) (* substitutes [t1] for [Rel 1] in [t2] *) (* if avoid_beta_redexes is true (default: false) no new beta redexes *) (* are generated. WARNING: the substitution can diverge when t2 is not *) (* well typed and avoid_beta_redexes is true. *) -let rec psubst ?(avoid_beta_redexes=false) delift lift_args args = +(* map_arg is ReductionStrategy.from_env_for_unwind when psubst is *) +(* used to implement nCicReduction.unwind' *) +let rec psubst ?(avoid_beta_redexes=false) map_arg args = let nargs = List.length args in let rec substaux k = function - | NCic.Sort _ - | NCic.Const _ as t -> t - | NCic.Rel n as t -> - (match n with - | n when n >= (k+nargs) -> if delift then NCic.Rel (n - nargs) else t - | n when n < k -> t - | n (* k <= n < k+nargs *) -> - (try lift (k+lift_args) (List.nth args (n-k)) - with Failure _ -> assert false)) - | NCic.Meta (_,(m,_)) as t when m >= k + nargs - 1 -> t - | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t - | NCic.Meta (i,(m,l)) -> - let lctx = NCicUtils.expand_local_context l in - (* 1-nargs < k-m, when <= 0 is still reasonable because we will - * substitute args[ k-m ... k-m+nargs-1 > 0 ] *) - NCic.Meta (i,(m, NCic.Ctx (List.map (substaux (k-m)) lctx))) - | NCic.Implicit _ -> assert false (* was identity *) - | NCic.Prod (n,s,t) -> NCic.Prod (n, substaux k s, substaux (k + 1) t) - | NCic.Lambda (n,s,t) -> NCic.Lambda (n, substaux k s, substaux (k + 1) t) - | NCic.LetIn (n,ty,te,t) -> - NCic.LetIn (n, substaux k ty, substaux k te, substaux (k + 1) t) - | NCic.Appl (he::tl) -> - (* Invariant: no Appl applied to another Appl *) - let rec avoid he = function - | [] -> he - | arg::tl as args-> - (match he with - | NCic.Appl l -> NCic.Appl (l@args) - | NCic.Lambda (_,_,bo) when avoid_beta_redexes -> - avoid (psubst ~avoid_beta_redexes true 0 [arg] bo) tl - | _ as he -> NCic.Appl (he::args)) - in - let tl = List.map (substaux k) tl in - avoid (substaux k he) tl - | NCic.Appl _ -> assert false - | NCic.Match (r,outt,t,pl) -> - NCic.Match (r,substaux k outt, substaux k t, List.map (substaux k) pl) + | C.Rel n as t -> + (match n with + | n when n >= (k+nargs) -> + if nargs <> 0 then C.Rel (n - nargs) else t + | n when n < k -> t + | n (* k <= n < k+nargs *) -> + (try lift (k-1) (map_arg (List.nth args (n-k))) + with Failure _ | Invalid_argument _ -> assert false)) + | C.Meta (i,(m,l)) as t when m >= k + nargs - 1 -> + if nargs <> 0 then C.Meta (i,(m-nargs,l)) else t + | C.Meta (_,(m,(C.Irl l))) as t when k > l + m -> t + | C.Meta (i,(m,l)) -> + let lctx = NCicUtils.expand_local_context l in + C.Meta (i,(0, + C.Ctx (HExtlib.sharing_map (fun x -> substaux k (lift m x)) lctx))) + | C.Implicit _ -> assert false (* was identity *) + | C.Appl (he::tl) as t -> + (* Invariant: no Appl applied to another Appl *) + let rec avoid he' = function + | [] -> he' + | arg::tl' as args-> + (match he' with + | C.Appl l -> C.Appl (l@args) + | C.Lambda (_,_,bo) when avoid_beta_redexes -> + (* map_arg is here \x.x, Obj magic is needed because + * we don't have polymorphic recursion w/o records *) + avoid (psubst + ~avoid_beta_redexes Obj.magic [Obj.magic arg] bo) tl' + | _ -> if he == he' && args == tl then t else C.Appl (he'::args)) + in + let tl = HExtlib.sharing_map (substaux k) tl in + avoid (substaux k he) tl + | t -> NCicUtils.map (fun _ k -> k + 1) k substaux t in substaux 1 ;; -let subst ?avoid_beta_redexes arg = psubst ?avoid_beta_redexes true 0 [arg];; +let subst ?avoid_beta_redexes arg = + psubst ?avoid_beta_redexes (fun x -> x)[arg];; -(* subst_meta (n, Some [t_1 ; ... ; t_n]) t *) +(* subst_meta (n, C.Ctx [t_1 ; ... ; t_n]) t *) (* returns the term [t] where [Rel i] is substituted with [t_i] lifted by n *) (* [t_i] is lifted as usual when it crosses an abstraction *) -(* subst_meta (n, Non) t -> lift n t *) +(* subst_meta (n, (C.Irl _ | C.Ctx [])) t | -> lift n t *) let subst_meta = function - | m, NCic.Irl _ - | m, NCic.Ctx [] -> lift m - | m, NCic.Ctx l -> psubst false m l + | m, C.Irl _ + | m, C.Ctx [] -> lift m + | m, C.Ctx l -> psubst (lift m) l ;;