-(* 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 lift_from ?(no_implicit=true) 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 _ as t -> (* was the identity *)
+ if no_implicit then assert false
+ else t
+ | t -> NCicUtils.map (fun _ k -> k + 1) k liftaux t
in
liftaux k
;;
-let lift ?(from=1) n t =
- if n = 0 then t
- else lift_from from n t
+let lift ?(from=1) ?(no_implicit=true) n t =
+ if n = 0 then t else lift_from ~no_implicit 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) ?(no_implicit=true) map_arg args =
let nargs = List.length args in
let rec substaux k = function
- | 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.Sort _ as t -> t
- | 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.Const _ as t -> t
- | 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 ~no_implicit (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 ~no_implicit m x)) lctx)))
+ | C.Implicit _ as t ->
+ if no_implicit then assert false (* was identity *)
+ else t
+ | 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 ~no_implicit
+ 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 ?no_implicit arg =
+ psubst ?avoid_beta_redexes ?no_implicit(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
;;
projects / helm.git / blobdiff