branch for universe

[helm.git] / components / ng_kernel / nCicSubstitution.ml

diff --git a/components/ng_kernel/nCicSubstitution.ml b/components/ng_kernel/nCicSubstitution.ml
new file mode 100644 (file)
index 0000000..67eb10a
--- /dev/null
+++ b/components/ng_kernel/nCicSubstitution.ml
@@ -0,0 +1,96 @@
+(*
+    ||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 debug_print = fun _ -> ();;
+
+let lift_from k n =
+ let rec liftaux k = function
+    | NCic.Rel m as t -> if m < k then t else NCic.Rel (m + n)
+    | NCic.Meta (i,(m,l)) as t when k <= m ->
+       if n = 0 then t else NCic.Meta (i,(m+n,l))
+    | 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
+       NCic.Meta (i, (m, NCic.Ctx (NCicUtils.sharing_map (liftaux (k-m)) lctx)))
+    | NCic.Implicit _ -> (* was the identity *) assert false
+    | 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
+;;
+
+(* 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.                          *)
+(*  map_arg is ReductionStrategy.from_env_for_unwind when psubst is     *)
+(*  used to implement nCicReduction.unwind'                             *)
+let rec psubst ?(avoid_beta_redexes=false) delift lift_args 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 && nargs <> 0 then NCic.Rel (n - nargs) else t
+      | n when n < k -> t
+      | n (* k <= n < k+nargs *) ->
+       (try lift (k-1+lift_args) (map_arg (List.nth args (n-k)))
+        with Failure _ -> assert false))
+   | NCic.Meta (i,(m,l)) as t when m >= k + nargs - 1 -> 
+       if delift && nargs <> 0 then NCic.Meta (i,(m-nargs,l)) else t
+   | NCic.Meta (i,(m,(NCic.Irl l as irl))) as t when k > l + m -> 
+       if delift && nargs <> 0 then NCic.Meta (i,(m-nargs,irl)) else 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 (NCicUtils.sharing_map (substaux (k-m)) lctx)))
+   | NCic.Implicit _ -> assert false (* was identity *)
+   | NCic.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
+            | NCic.Appl l -> NCic.Appl (l@args)
+            | NCic.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 true 0 Obj.magic [Obj.magic arg] bo) tl'
+            | _ -> if he == he' && args == tl then t else NCic.Appl (he'::args))
+      in
+      let tl = NCicUtils.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 (fun x -> x)[arg];;
+
+(* subst_meta (n, Some [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                                        *)
+let subst_meta = function 
+  | m, NCic.Irl _ 
+  | m, NCic.Ctx [] -> lift m 
+  | m, NCic.Ctx l  -> psubst false m (fun x -> x) l 
+;;