X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;ds=sidebyside;f=helm%2Fsoftware%2Fcomponents%2Fng_refiner%2FnCicRefiner.ml;h=68a1b2cbe983f0746a33e2fc9fe54b02de009ea7;hb=2b837ca9e298eb44eee95d9ca0e331c577785dcb;hp=6779667d9ca8f4bd4bf83cb6ea2bc9edcc31a688;hpb=46b91f34b693dabbd351ba813f5190051b09a117;p=helm.git diff --git a/helm/software/components/ng_refiner/nCicRefiner.ml b/helm/software/components/ng_refiner/nCicRefiner.ml index 6779667d9..68a1b2cbe 100644 --- a/helm/software/components/ng_refiner/nCicRefiner.ml +++ b/helm/software/components/ng_refiner/nCicRefiner.ml @@ -23,12 +23,9 @@ let inside c = indent := !indent ^ String.make 1 c;; let outside () = indent := String.sub !indent 0 (String.length !indent -1);; -(* let pp s = prerr_endline (Printf.sprintf "%-20s" !indent ^ " " ^ Lazy.force s) ;; -*) - let pp _ = ();; @@ -63,7 +60,7 @@ let check_allowed_sort_elimination hdb localise r orig = NCicPp.ppmetasenv ~subst metasenv)); match arity1 with | C.Prod (name,so1,de1) (* , t ==?== C.Prod _ *) -> - let metasenv, meta, _ = + let metasenv, _, meta, _ = NCicMetaSubst.mk_meta metasenv ((name,C.Decl so1)::context) `Type in let metasenv, subst = @@ -77,7 +74,7 @@ let check_allowed_sort_elimination hdb localise r orig = aux metasenv subst ((name, C.Decl so1)::context) (mkapp (NCicSubstitution.lift 1 ind) (C.Rel 1)) de1 meta | C.Sort _ (* , t ==?== C.Prod _ *) -> - let metasenv, meta, _ = NCicMetaSubst.mk_meta metasenv [] `Type in + let metasenv, _, meta, _ = NCicMetaSubst.mk_meta metasenv [] `Type in let metasenv, subst = try NCicUnification.unify hdb metasenv subst context arity2 (C.Prod ("_", ind, meta)) @@ -111,7 +108,7 @@ let rec typeof hdb | _ -> pp (lazy ( (NCicPp.ppterm ~metasenv ~subst ~context infty) ^ " === " ^ - (NCicPp.ppterm ~metasenv ~subst ~context expty))); + (NCicPp.ppterm ~metasenv ~subst:[] ~context expty))); try let metasenv, subst = NCicUnification.unify hdb metasenv subst context infty expty @@ -127,7 +124,9 @@ let rec typeof hdb fun t as orig -> (*D*)inside 'R'; try let rc = pp (lazy (NCicPp.ppterm ~metasenv ~subst ~context t)); - pp (lazy (NCicPp.ppmetasenv ~subst metasenv)); + pp (lazy (if expty = None then "NONE" else "SOME")); + if (List.exists (fun (i,_) -> i=29) subst) then + pp (lazy (NCicPp.ppsubst ~metasenv subst)); let metasenv, subst, t, infty = match t with | C.Rel n -> @@ -146,7 +145,7 @@ let rec typeof hdb NCicPp.ppterm ~subst ~metasenv ~context t))) | C.Sort _ -> metasenv,subst,t,(C.Sort (C.Type NCicEnvironment.type0)) | C.Implicit infos -> - let metasenv,t,ty = exp_implicit metasenv context expty infos in + let metasenv,_,t,ty = exp_implicit metasenv context expty infos in metasenv, subst, t, ty | C.Meta (n,l) as t -> let ty = @@ -154,7 +153,11 @@ let rec typeof hdb let _,_,_,ty = NCicUtils.lookup_subst n subst in ty with NCicUtils.Subst_not_found _ -> try let _,_,ty = NCicUtils.lookup_meta n metasenv in - match ty with C.Implicit _ -> assert false | _ -> ty + match ty with C.Implicit _ -> + prerr_endline (string_of_int n); + prerr_endline (NCicPp.ppmetasenv ~subst metasenv); + prerr_endline (NCicPp.ppsubst ~metasenv subst); + assert false | _ -> ty with NCicUtils.Meta_not_found _ -> raise (AssertFailure (lazy (Printf.sprintf "%s not found" (NCicPp.ppterm ~subst ~metasenv ~context t)))) @@ -225,10 +228,17 @@ let rec typeof hdb let bo_ty = NCicSubstitution.subst ~avoid_beta_redexes:true t bo_ty in metasenv, subst, C.LetIn (n, ty, t, bo), bo_ty | C.Appl ((he as orig_he)::(_::_ as args)) -> + let upto = + match orig_he with C.Meta _ -> List.length args | _ -> 0 + in let metasenv, subst, he, ty_he = typeof_aux metasenv subst context None he in - eat_prods hdb ~localise ~look_for_coercion - metasenv subst context orig_he he ty_he args + let metasenv, subst, t, ty = + eat_prods hdb ~localise ~look_for_coercion + metasenv subst context orig_he he ty_he args + in + let t = if upto > 0 then NCicReduction.head_beta_reduce ~upto t else t in + metasenv, subst, t, ty | C.Appl _ -> raise (AssertFailure (lazy "Appl of length < 2")) | C.Match (Ref.Ref (_,Ref.Ind (_,tyno,_)) as r, outtype,(term as orig_term),pl) as orig -> @@ -240,9 +250,35 @@ let rec typeof hdb let ind = if args = [] then C.Const r else C.Appl (C.Const r::args) in let metasenv, subst, term, _ = typeof_aux metasenv subst context (Some ind) term in + let parameters, arguments = HExtlib.split_nth "NR 1" leftno args in + let outtype = + match outtype with + | C.Implicit _ as ot -> + let rec aux = function + | [] -> NCic.Lambda ("_",NCic.Implicit `Type,ot) + | _::tl -> NCic.Lambda ("_",NCic.Implicit `Type,aux tl) + in + aux arguments + | _ -> outtype + in let metasenv, subst, outtype, outsort = typeof_aux metasenv subst context None outtype in - let parameters, arguments = HExtlib.split_nth leftno args in + + (* next lines are to do a subst-expansion of the outtype, so + that when it becomes a beta-abstraction, the beta-redex is + fired during substitution *) + (*CSC: this is instantiate! should we move it from tactics to the + refiner? I think so! *) + let metasenv,metanoouttype,newouttype,metaoutsort = + NCicMetaSubst.mk_meta metasenv context `Term in + let metasenv,subst = + NCicUnification.unify hdb metasenv subst context outsort metaoutsort in + let metasenv = + List.filter (function (j,_) -> j <> metanoouttype) metasenv in + let subst = + (metanoouttype,(Some "outtype",context,outtype,metaoutsort))::subst in + let outtype = newouttype in + (* let's control if the sort elimination is allowed: [(I q1 ... qr)|B] *) let ind = if parameters = [] then C.Const r @@ -257,6 +293,14 @@ let rec typeof hdb if List.length pl <> constructorsno then raise (RefineFailure (lazy (localise orig, "Wrong number of cases in a match"))); +(* + let metasenv, subst = + match expty with + | None -> metasenv, subst + | Some expty -> + NCicUnification.unify hdb metasenv subst context resty expty + in +*) let _, metasenv, subst, pl_rev = List.fold_left (fun (j, metasenv, subst, branches) p -> @@ -278,12 +322,10 @@ let rec typeof hdb j+1, metasenv, subst, p :: branches) (1, metasenv, subst, []) pl in - metasenv, subst, - C.Match (r, outtype, term, List.rev pl_rev), - NCicReduction.head_beta_reduce (C.Appl (outtype::arguments@[term])) - | C.Match _ as orig -> - prerr_endline (NCicPp.ppterm ~metasenv ~subst ~context orig); - assert false + let resty = C.Appl (outtype::arguments@[term]) in + let resty = NCicReduction.head_beta_reduce ~subst resty in + metasenv, subst, C.Match (r, outtype, term, List.rev pl_rev),resty + | C.Match _ -> assert false in pp (lazy (NCicPp.ppterm ~metasenv ~subst ~context t ^ " :: "^ NCicPp.ppterm ~metasenv ~subst ~context infty )); @@ -342,8 +384,8 @@ and force_to_sort hdb match NCicReduction.whd ~subst context ty with | C.Meta (_,(0,(C.Irl 0 | C.Ctx []))) as ty -> metasenv, subst, t, ty - | C.Meta (i,(_,(C.Irl 0 | C.Ctx []))) -> - metasenv, subst, t, C.Meta(i,(0,C.Irl 0)) + | C.Meta (i,(_,(C.Irl 0 | C.Ctx []))) -> assert false (*CSC: ??? + metasenv, subst, t, C.Meta(i,(0,C.Irl 0)) *) | C.Meta (i,(_,lc)) -> let len = match lc with C.Irl len->len | C.Ctx l->List.length l in let metasenv, subst, newmeta = @@ -401,7 +443,7 @@ and eat_prods hdb let metasenv, subst, arg, ty_arg = typeof hdb ~look_for_coercion ~localise metasenv subst context arg None in - let metasenv, meta, _ = + let metasenv, _, meta, _ = NCicMetaSubst.mk_meta metasenv (("_",C.Decl ty_arg) :: context) `Type in @@ -482,33 +524,34 @@ let relocalise old_localise dt t add = let undebruijnate inductive ref t rev_fl = NCicSubstitution.psubst (fun x -> x) - (HExtlib.list_mapi + (List.rev (HExtlib.list_mapi (fun (_,_,rno,_,_,_) i -> NCic.Const (if inductive then NReference.mk_fix i rno ref else NReference.mk_cofix i ref)) - rev_fl) + rev_fl)) t ;; let typeof_obj hdb ?(localise=fun _ -> Stdpp.dummy_loc) - ~look_for_coercion (uri,height,metasenv,subst, obj) + ~look_for_coercion (uri,height,metasenv,subst,obj) = - let check_type metasenv subst (ty as orig_ty) = (* XXX fattorizza *) +prerr_endline ("===============\n" ^ NCicPp.ppobj (uri,height,metasenv,subst,obj)); + let check_type metasenv subst context (ty as orig_ty) = (* XXX fattorizza *) let metasenv, subst, ty, sort = - typeof hdb ~localise ~look_for_coercion metasenv subst [] ty None + typeof hdb ~localise ~look_for_coercion metasenv subst context ty None in - let metasenv, subst, ty, _ = + let metasenv, subst, ty, sort = force_to_sort hdb ~look_for_coercion - metasenv subst [] ty orig_ty localise sort + metasenv subst context ty orig_ty localise sort in - metasenv, subst, ty + metasenv, subst, ty, sort in match obj with | C.Constant (relevance, name, bo, ty , attr) -> - let metasenv, subst, ty = check_type metasenv subst ty in + let metasenv, subst, ty, _ = check_type metasenv subst [] ty in let metasenv, subst, bo, ty, height = match bo with | Some bo -> @@ -527,7 +570,7 @@ let typeof_obj hdb let types, metasenv, subst, rev_fl = List.fold_left (fun (types, metasenv, subst, fl) (relevance,name,k,ty,bo) -> - let metasenv, subst, ty = check_type metasenv subst ty in + let metasenv, subst, ty, _ = check_type metasenv subst [] ty in let dbo = NCicTypeChecker.debruijn uri len [] bo in let localise = relocalise localise dbo bo in (name,C.Decl ty)::types, @@ -559,85 +602,131 @@ let typeof_obj hdb in uri, height, metasenv, subst, C.Fixpoint (inductive, fl, attr) - - | C.Inductive (ind, leftno, itl, attr) -> assert false -(* - (* let's check if the arity of the inductive types are well formed *) - List.iter (fun (_,_,x,_) -> ignore (typeof ~subst ~metasenv [] x)) tyl; - (* let's check if the types of the inductive constructors are well formed. *) - let len = List.length tyl in - let tys = List.rev_map (fun (_,n,ty,_) -> (n,(C.Decl ty))) tyl in - ignore - (List.fold_right - (fun (it_relev,_,ty,cl) i -> - let context,ty_sort = split_prods ~subst [] ~-1 ty in - let sx_context_ty_rev,_ = HExtlib.split_nth leftno (List.rev context) in - List.iter - (fun (k_relev,_,te) -> - let _,k_relev = HExtlib.split_nth leftno k_relev in - let te = debruijn uri len [] te in - let context,te = split_prods ~subst tys leftno te in - let _,chopped_context_rev = - HExtlib.split_nth (List.length tys) (List.rev context) in - let sx_context_te_rev,_ = - HExtlib.split_nth leftno chopped_context_rev in - (try - ignore (List.fold_left2 - (fun context item1 item2 -> - let convertible = - match item1,item2 with - (n1,C.Decl ty1),(n2,C.Decl ty2) -> - n1 = n2 && - R.are_convertible ~metasenv ~subst context ty1 ty2 - | (n1,C.Def (bo1,ty1)),(n2,C.Def (bo2,ty2)) -> - n1 = n2 - && R.are_convertible ~metasenv ~subst context ty1 ty2 - && R.are_convertible ~metasenv ~subst context bo1 bo2 - | _,_ -> false - in - if not convertible then - raise (TypeCheckerFailure (lazy - ("Mismatch between the left parameters of the constructor " ^ - "and those of its inductive type"))) - else - item1::context - ) [] sx_context_ty_rev sx_context_te_rev) - with Invalid_argument "List.fold_left2" -> assert false); - let con_sort = typeof ~subst ~metasenv context te in - (match R.whd ~subst context con_sort, R.whd ~subst [] ty_sort with - (C.Sort (C.Type u1) as s1), (C.Sort (C.Type u2) as s2) -> - if not (E.universe_leq u1 u2) then - raise - (TypeCheckerFailure - (lazy ("The type " ^ PP.ppterm ~metasenv ~subst ~context s1^ - " of the constructor is not included in the inductive" ^ - " type sort " ^ PP.ppterm ~metasenv ~subst ~context s2))) - | C.Sort _, C.Sort C.Prop - | C.Sort _, C.Sort C.Type _ -> () - | _, _ -> + | C.Inductive (ind, leftno, itl, attr) -> + let len = List.length itl in + let metasenv,subst,rev_itl,tys = + List.fold_left + (fun (metasenv,subst,res,ctx) (relevance,n,ty,cl) -> + let metasenv, subst, ty, _ = check_type metasenv subst [] ty in + metasenv,subst,(relevance,n,ty,cl)::res,(n,NCic.Decl ty)::ctx + ) (metasenv,subst,[],[]) itl in + let metasenv,subst,itl,_ = + List.fold_left + (fun (metasenv,subst,res,i) (it_relev,n,ty,cl) -> + let context,ty_sort = NCicReduction.split_prods ~subst [] ~-1 ty in + let sx_context_ty_rev,_= HExtlib.split_nth "NR 2" leftno (List.rev context) in + let metasenv,subst,cl = + List.fold_right + (fun (k_relev,n,te) (metasenv,subst,res) -> + let k_relev = + try snd (HExtlib.split_nth "NR 3" leftno k_relev) + with Failure _ -> k_relev in + let te = NCicTypeChecker.debruijn uri len [] te in + let metasenv, subst, te, _ = check_type metasenv subst tys te in + let context,te = NCicReduction.split_prods ~subst tys leftno te in + let _,chopped_context_rev = + HExtlib.split_nth "NR 4" (List.length tys) (List.rev context) in + let sx_context_te_rev,_ = + HExtlib.split_nth "NR 5" leftno chopped_context_rev in + let metasenv,subst,_ = + try + List.fold_left2 + (fun (metasenv,subst,context) item1 item2 -> + let (metasenv,subst),convertible = + try + match item1,item2 with + (n1,C.Decl ty1),(n2,C.Decl ty2) -> + if n1 = n2 then + NCicUnification.unify hdb ~test_eq_only:true metasenv + subst context ty1 ty2,true + else + (metasenv,subst),false + | (n1,C.Def (bo1,ty1)),(n2,C.Def (bo2,ty2)) -> + if n1 = n2 then + let metasenv,subst = + NCicUnification.unify hdb ~test_eq_only:true metasenv + subst context ty1 ty2 + in + NCicUnification.unify hdb ~test_eq_only:true metasenv + subst context bo1 bo2,true + else + (metasenv,subst),false + | _,_ -> (metasenv,subst),false + with + | NCicUnification.Uncertain _ + | NCicUnification.UnificationFailure _ -> + (metasenv,subst),false + in + let term2 = + match item2 with + _,C.Decl t -> t + | _,C.Def (b,_) -> b in + if not convertible then + raise (RefineFailure (lazy (localise term2, + ("Mismatch between the left parameters of the constructor " ^ + "and those of its inductive type")))) + else + metasenv,subst,item1::context + ) (metasenv,subst,[]) sx_context_ty_rev sx_context_te_rev + with Invalid_argument "List.fold_left2" -> assert false in + let con_sort= NCicTypeChecker.typeof ~subst ~metasenv context te in + (match + NCicReduction.whd ~subst context con_sort, + NCicReduction.whd ~subst [] ty_sort + with + (C.Sort (C.Type u1) as s1), (C.Sort (C.Type u2) as s2) -> + if not (NCicEnvironment.universe_leq u1 u2) then + raise + (RefineFailure + (lazy(localise te, "The type " ^ + NCicPp.ppterm ~metasenv ~subst ~context s1 ^ + " of the constructor is not included in the inductive"^ + " type sort " ^ + NCicPp.ppterm ~metasenv ~subst ~context s2))) + | C.Sort _, C.Sort C.Prop + | C.Sort _, C.Sort C.Type _ -> () + | _, _ -> + raise + (RefineFailure + (lazy (localise te, + "Wrong constructor or inductive arity shape")))); + (* let's check also the positivity conditions *) + if + not + (NCicTypeChecker.are_all_occurrences_positive + ~subst context uri leftno (i+leftno) leftno (len+leftno) te) + then raise - (TypeCheckerFailure - (lazy ("Wrong constructor or inductive arity shape")))); - (* let's check also the positivity conditions *) - if - not - (are_all_occurrences_positive ~subst context uri leftno - (i+leftno) leftno (len+leftno) te) - then - raise - (TypeCheckerFailure - (lazy ("Non positive occurence in "^NUri.string_of_uri - uri))) - else check_relevance ~subst ~metasenv context k_relev te) - cl; - check_relevance ~subst ~metasenv [] it_relev ty; - i+1) - tyl 1) -*) - - + (RefineFailure + (lazy (localise te, + "Non positive occurence in " ^ NUri.string_of_uri uri))) + else + let relsno = List.length itl + leftno in + let te = + NCicSubstitution.psubst + (fun i -> + if i <= leftno then + NCic.Rel i + else + NCic.Const (NReference.reference_of_spec uri + (NReference.Ind (ind,relsno - i,leftno)))) + (HExtlib.list_seq 1 (relsno+1)) + te in + let te = + List.fold_right + (fun (name,decl) te -> + match decl with + NCic.Decl ty -> NCic.Prod (name,ty,te) + | NCic.Def (bo,ty) -> NCic.LetIn (name,ty,bo,te) + ) sx_context_te_rev te + in + metasenv,subst,(k_relev,n,te)::res + ) cl (metasenv,subst,[]) + in + metasenv,subst,(it_relev,n,ty,cl)::res,i+1 + ) (metasenv,subst,[],1) rev_itl + in + uri, height, metasenv, subst, C.Inductive (ind, leftno, itl, attr) ;; - - (* vim:set foldmethod=marker: *)