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.
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_______________________________________________________________ *)
12 (* $Id: terms.mli 9822 2009-06-03 15:37:06Z tassi $ *)
14 module type NCicContext =
16 val metasenv : NCic.metasenv
17 val subst : NCic.substitution
18 val context : NCic.context
21 module NCicBlob(C : NCicContext) : Terms.Blob with type t = NCic.term = struct
25 let eq x y = NCicReduction.alpha_eq C.metasenv C.subst C.context x y;;
29 | NCic.Rel i, NCic.Rel j -> i-j
30 | NCic.Meta (i,_), NCic.Meta (j,_) -> i-j
31 | NCic.Const r1, NCic.Const r2 -> NReference.compare r1 r2
32 | NCic.Appl l1, NCic.Appl l2 -> FoUtils.lexicograph compare l1 l2
33 | NCic.Rel _, ( NCic.Meta _ | NCic.Const _ | NCic.Appl _ ) -> ~-1
34 | ( NCic.Meta _ | NCic.Const _ | NCic.Appl _ ), NCic.Rel _ -> 1
35 | NCic.Const _, ( NCic.Meta _ | NCic.Appl _ ) -> ~-1
36 | ( NCic.Meta _ | NCic.Appl _ ), NCic.Const _ -> 1
37 | NCic.Appl _, NCic.Meta _ -> ~-1
38 | NCic.Meta _, NCic.Appl _ -> 1
43 if NCicReduction.alpha_eq C.metasenv C.subst C.context x y then 0
48 NCicPp.ppterm ~context:C.context ~metasenv:C.metasenv ~subst:C.subst t;;
50 let rec embed = function
51 | NCic.Meta (i,_) -> Terms.Var i, [i]
53 let rec aux acc l = function
55 |hd::tl -> if List.mem hd l then aux acc l tl else aux (hd::acc) l tl
57 let res,vars = List.fold_left
58 (fun (r,v) t -> let r1,v1 = embed t in (r1::r),aux [] v v1) ([],[]) l
59 in (Terms.Node (List.rev res)), vars
60 | t -> Terms.Leaf t, []
63 let embed t = fst (embed t) ;;
67 NCicMetaSubst.saturate ~delta:max_int C.metasenv C.subst C.context
71 if args = [] then Terms.Leaf t
72 else Terms.Node (Terms.Leaf t :: List.map embed args)
74 let sty = embed sty in
80 OCic2NCic.reference_of_oxuri
81 (UriManager.uri_of_string
82 "cic:/matita/logic/equality/eq.ind#xpointer(1/1)")
89 OCic2NCic.reference_of_oxuri
90 (UriManager.uri_of_string
91 "cic:/matita/logic/equality/eq_ind.con")
98 OCic2NCic.reference_of_oxuri
99 (UriManager.uri_of_string
100 "cic:/matita/logic/equality/eq_elim_r.con")
107 OCic2NCic.reference_of_oxuri
108 (UriManager.uri_of_string
109 "cic:/matita/logic/equality/eq.ind#xpointer(1/1/1)")
114 let extract lift vl t =
115 let rec pos i = function
116 | [] -> raise Not_found
117 | j :: tl when j <> i -> 1+ pos i tl
120 let vl_len = List.length vl in
121 let rec extract = function
122 | Terms.Leaf x -> NCicSubstitution.lift (vl_len+lift) x
124 (try NCic.Rel (pos j vl) with Not_found -> NCic.Implicit `Term)
125 | Terms.Node l -> NCic.Appl (List.map extract l)
130 let rec ppfot = function
131 | Terms.Leaf _ -> "."
132 | Terms.Var i -> "?" ^ string_of_int i
133 | Terms.Node l -> "(" ^ String.concat " " (List.map ppfot l) ^ ")"
136 let mk_predicate hole_type amount ft p1 vl =
144 prerr_endline ("term: " ^ ppfot ft);
145 prerr_endline ("path: " ^ String.concat ","
146 (List.map string_of_int p1));
152 if i = n then aux t tl
153 else extract amount (0::vl) t)
158 NCic.Lambda("x", hole_type, aux ft (List.rev p1))
161 let mk_proof (bag : NCic.term Terms.bag) mp steps =
162 let module Subst = FoSubst in
164 let rec aux = function
166 | (j,_) :: tl when i = j -> 1
167 | _ :: tl -> 1 + aux tl
171 let vars_of i l = fst (List.assoc i l) in
172 let ty_of i l = snd (List.assoc i l) in
173 let close_with_lambdas vl t =
176 NCic.Lambda ("x"^string_of_int i, NCic.Implicit `Type, t))
179 let close_with_forall vl t =
182 NCic.Prod ("x"^string_of_int i, NCic.Implicit `Type, t))
186 let _, lit, vl, proof = Terms.M.find id bag in
187 let lit =match lit with
188 | Terms.Predicate t -> assert false
189 | Terms.Equation (l,r,ty,_) ->
190 Terms.Node [ Terms.Leaf eqP; ty; l; r]
194 let rec aux ongoal seen = function
197 let amount = List.length seen in
198 let lit,vl,proof = get_literal id in
199 if not ongoal && id = mp then
200 ((*prerr_endline ("Reached m point, id=" ^ (string_of_int id));*)
201 NCic.LetIn ("clause_" ^ string_of_int id,
202 extract amount [] lit,
203 (NCic.Appl [eq_refl;NCic.Implicit `Type;NCic.Implicit `Term]),
204 aux true ((id,([],lit))::seen) (id::tl)))
207 | Terms.Exact _ when tl=[] ->
208 (* prerr_endline ("Exact (tl=[]) for " ^ (string_of_int id));*)
210 | Terms.Step _ when tl=[] -> assert false
212 (* prerr_endline ("Exact for " ^ (string_of_int id));*)
213 NCic.LetIn ("clause_" ^ string_of_int id,
214 close_with_forall vl (extract amount vl lit),
215 close_with_lambdas vl (extract amount vl ft),
217 ((id,(List.map (fun x -> Terms.Var x) vl,lit))::seen) tl)
218 | Terms.Step (_, id1, id2, dir, pos, subst) ->
219 let id, id1,(lit,vl,proof) =
220 if ongoal then id1,id,get_literal id1
221 else id,id1,(lit,vl,proof)
223 let vl = if ongoal then Subst.filter subst vl else vl in
225 let vars = List.rev (vars_of id seen) in
226 let args = List.map (Subst.apply_subst subst) vars in
227 let args = List.map (extract amount vl) args in
228 let rel_for_id = NCic.Rel (List.length vl + position id seen) in
229 if args = [] then rel_for_id
230 else NCic.Appl (rel_for_id::args)
232 let p_id1 = proof_of_id id1 in
233 let p_id2 = proof_of_id id2 in
234 let pred, hole_type, l, r =
235 let id1_ty = ty_of id1 seen in
237 match ty_of id2 seen with
238 | Terms.Node [ _; t; l; r ] ->
239 extract amount vl (Subst.apply_subst subst t),
240 extract amount vl (Subst.apply_subst subst l),
241 extract amount vl (Subst.apply_subst subst r)
244 (*prerr_endline "mk_predicate :";
245 if ongoal then prerr_endline "ongoal=true"
246 else prerr_endline "ongoal=false";
247 prerr_endline ("id=" ^ string_of_int id);
248 prerr_endline ("id1=" ^ string_of_int id1);
249 prerr_endline ("id2=" ^ string_of_int id2);
250 prerr_endline ("Positions :" ^
252 (List.map string_of_int pos)));*)
254 id2_ty amount (Subst.apply_subst subst id1_ty) pos vl,
259 if (ongoal=true) = (dir=Terms.Left2Right) then
264 NCic.LetIn ("clause_" ^ string_of_int id,
265 close_with_forall vl (extract amount vl lit),
266 (* NCic.Implicit `Type, *)
267 close_with_lambdas vl
268 (NCic.Appl [ eq_ind ; hole_type; l; pred; p_id1; r; p_id2 ]),
270 ((id,(List.map (fun x -> Terms.Var x) vl,lit))::seen) tl)