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 _ = ();;
| _ -> assert false
;;
-let force_to_sort metasenv subst context t =
- match NCicReduction.whd ~subst context t with
- | C.Meta (_,(0,(C.Irl 0 | C.Ctx []))) as t ->
- metasenv, subst, t
- | C.Meta (i,(_,(C.Irl 0 | C.Ctx []))) ->
- metasenv, subst, 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 =
- if len > 0 then
- NCicMetaSubst.restrict metasenv subst i (HExtlib.list_seq 1 (len+1))
- else metasenv, subst, i
- in
- metasenv, subst, C.Meta (newmeta,(0,C.Irl 0))
- | C.Sort _ as t -> metasenv, subst, t
- | _ -> assert false
-;;
-let sort_of_prod
- localise metasenv subst context orig_s orig_t (name,s) t (t1, t2)
-=
- let metasenv, subst, t1 = force_to_sort metasenv subst context t1 in
- let metasenv, subst, t2 =
- force_to_sort metasenv subst ((name,C.Decl s)::context) t2 in
- match t1, t2 with
- | C.Sort _, C.Sort C.Prop -> metasenv, subst, t2
- | C.Sort (C.Type u1), C.Sort (C.Type u2) ->
- metasenv, subst, C.Sort (C.Type (u1@u2))
- | C.Sort C.Prop,C.Sort (C.Type _) -> metasenv, subst, t2
- | C.Meta _, C.Sort _
- | C.Meta _, C.Meta (_,(_,_))
- | C.Sort _, C.Meta (_,(_,_)) -> metasenv, subst, t2
- | x, (C.Sort _ | C.Meta _) | _, x ->
- let y, context, orig =
- if x == t1 then s, context, orig_s
- else t, ((name,C.Decl s)::context), orig_t
- in
- raise (RefineFailure (lazy (localise orig,Printf.sprintf
- "%s is expected to be a type, but its type is %s that is not a sort"
- (NCicPp.ppterm ~subst ~metasenv ~context y)
- (NCicPp.ppterm ~subst ~metasenv ~context x))))
-;;
-
-let check_allowed_sort_elimination localise r orig =
+let check_allowed_sort_elimination rdb localise r orig =
let mkapp he arg =
match he with
| C.Appl l -> C.Appl (l @ [arg])
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 =
- try NCicUnification.unify metasenv subst context
+ try NCicUnification.unify rdb metasenv subst context
arity2 (C.Prod (name, so1, meta))
with exc -> raise (wrap_exc (lazy (localise orig, Printf.sprintf
"expected %s, found %s" (* XXX localizzare meglio *)
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 metasenv subst context
+ try NCicUnification.unify rdb metasenv subst context
arity2 (C.Prod ("_", ind, meta))
with exc -> raise (wrap_exc (lazy (localise orig, Printf.sprintf
"expected %s, found %s" (* XXX localizzare meglio *)
aux
;;
-let rec typeof
- ?(localise=fun _ -> Stdpp.dummy_loc) metasenv subst context term expty
+let rec typeof rdb
+ ?(localise=fun _ -> Stdpp.dummy_loc)
+ metasenv subst context term expty
=
- let force_ty metasenv subst context orig t infty expty =
+ let force_ty skip_lambda metasenv subst context orig t infty expty =
(*D*)inside 'F'; try let rc =
match expty with
| Some expty ->
(match t with
- | C.Implicit _
- | C.Lambda _ -> metasenv, subst, t, expty
+ | C.Implicit _ -> assert false
+ | C.Lambda _ when skip_lambda -> metasenv, subst, t, expty
| _ ->
pp (lazy (
(NCicPp.ppterm ~metasenv ~subst ~context infty) ^ " === " ^
- (NCicPp.ppterm ~metasenv ~subst ~context expty)));
- let metasenv, subst =
- try NCicUnification.unify metasenv subst context infty expty
- with exc -> raise (wrap_exc (lazy (localise orig, Printf.sprintf
- "The term %s has type %s but is here used with type %s"
- (NCicPp.ppterm ~metasenv ~subst ~context t)
- (NCicPp.ppterm ~metasenv ~subst ~context infty)
- (NCicPp.ppterm ~metasenv ~subst ~context expty))) exc)
- in
- metasenv, subst, t, expty)
+ (NCicPp.ppterm ~metasenv ~subst:[] ~context expty)));
+ try
+ let metasenv, subst =
+ NCicUnification.unify rdb metasenv subst context infty expty
+ in
+ metasenv, subst, t, expty
+ with exc ->
+ try_coercions rdb ~localise
+ metasenv subst context t orig infty expty true exc)
| None -> metasenv, subst, t, infty
(*D*)in outside(); rc with exc -> outside (); raise exc
in
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 ->
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 =
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))))
metasenv, subst, t, NCicTypeChecker.typeof ~subst ~metasenv context t
| C.Prod (name,(s as orig_s),(t as orig_t)) ->
let metasenv, subst, s, s1 = typeof_aux metasenv subst context None s in
+ let metasenv, subst, s, s1 =
+ force_to_sort rdb
+ metasenv subst context s orig_s localise s1 in
let context1 = (name,(C.Decl s))::context in
let metasenv, subst, t, s2 = typeof_aux metasenv subst context1 None t in
- let metasenv, subst, ty =
+ let metasenv, subst, t, s2 =
+ force_to_sort rdb
+ metasenv subst context1 t orig_t localise s2 in
+ let metasenv, subst, s, t, ty =
sort_of_prod localise metasenv subst
context orig_s orig_t (name,s) t (s1,s2)
in
metasenv, subst, NCic.Prod(name,s,t), ty
- | C.Lambda (n,(s as orig_s),t) ->
- let exp_s, exp_ty_t =
+ | C.Lambda (n,(s as orig_s),t) as orig ->
+ let exp_s, exp_ty_t, force_after =
match expty with
- | None -> None, None
+ | None -> None, None, false
| Some expty ->
match NCicReduction.whd ~subst context expty with
- | C.Prod (_,s,t) -> Some s, Some t
- | _ -> None, None
+ | C.Prod (_,s,t) -> Some s, Some t, false
+ | _ -> None, None, true
in
let metasenv, subst, s, ty_s =
typeof_aux metasenv subst context None s in
- let metasenv, subst, _ = force_to_sort metasenv subst context ty_s in
+ let metasenv, subst, s, _ =
+ force_to_sort rdb
+ metasenv subst context s orig_s localise ty_s in
let (metasenv,subst), exp_ty_t =
match exp_s with
| Some exp_s ->
- (try NCicUnification.unify metasenv subst context s exp_s,exp_ty_t
+ (try NCicUnification.unify rdb metasenv subst context s exp_s,exp_ty_t
with exc -> raise (wrap_exc (lazy (localise orig_s, Printf.sprintf
"Source type %s was expected to be %s" (NCicPp.ppterm ~metasenv
~subst ~context s) (NCicPp.ppterm ~metasenv ~subst ~context
exp_s))) exc))
| None -> (metasenv, subst), None
in
- (* XXX coerce_to_sort s *)
- let context = (n,C.Decl s) :: context in
+ let context_for_t = (n,C.Decl s) :: context in
let metasenv, subst, t, ty_t =
- typeof_aux metasenv subst context exp_ty_t t
+ typeof_aux metasenv subst context_for_t exp_ty_t t
in
- metasenv, subst, C.Lambda(n,s,t), C.Prod (n,s,ty_t)
- | C.LetIn (n,ty,t,bo) ->
+ if force_after then
+ force_ty false metasenv subst context orig
+ (C.Lambda(n,s,t)) (C.Prod (n,s,ty_t)) expty
+ else
+ metasenv, subst, C.Lambda(n,s,t), C.Prod (n,s,ty_t)
+ | C.LetIn (n,(ty as orig_ty),t,bo) ->
let metasenv, subst, ty, ty_ty =
typeof_aux metasenv subst context None ty in
- let metasenv, subst, _ = force_to_sort metasenv subst context ty_ty in
+ let metasenv, subst, ty, _ =
+ force_to_sort rdb
+ metasenv subst context ty orig_ty localise ty_ty in
let metasenv, subst, t, _ =
typeof_aux metasenv subst context (Some ty) t in
let context1 = (n, C.Def (t,ty)) :: context in
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 localise metasenv subst context orig_he he ty_he args
+ let metasenv, subst, t, ty =
+ eat_prods rdb ~localise
+ 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 ->
let _, _, arity, cl = List.nth itl tyno in
let constructorsno = List.length cl in
let _, metasenv, args =
- NCicMetaSubst.saturate metasenv context arity 0 in
+ NCicMetaSubst.saturate metasenv subst context arity 0 in
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 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 rdb 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
let metasenv, subst, ind, ind_ty =
typeof_aux metasenv subst context None ind in
let metasenv, subst =
- check_allowed_sort_elimination localise r orig_term metasenv subst
+ check_allowed_sort_elimination rdb localise r orig_term metasenv subst
context ind ind_ty outsort
in
(* let's check if the type of branches are right *)
if List.length pl <> constructorsno then
raise (RefineFailure (lazy (localise orig,
"Wrong number of cases in a match")));
- let _, metasenv, subst, pl_rev =
- List.fold_left
- (fun (j, metasenv, subst, branches) p ->
+(*
+ let metasenv, subst =
+ match expty with
+ | None -> metasenv, subst
+ | Some expty ->
+ NCicUnification.unify rdb metasenv subst context resty expty
+ in
+*)
+ let _, metasenv, subst, pl =
+ List.fold_right
+ (fun p (j, metasenv, subst, branches) ->
let cons =
let cons = Ref.mk_constructor j r in
if parameters = [] then C.Const cons
NCicPp.ppterm ~metasenv ~subst ~context ty_branch ));
let metasenv, subst, p, _ =
typeof_aux metasenv subst context (Some ty_branch) p in
- j+1, metasenv, subst, p :: branches)
- (1, metasenv, subst, []) pl
+ j-1, metasenv, subst, p :: branches)
+ pl (List.length pl, metasenv, subst, [])
in
- metasenv, subst,
- C.Match (r, outtype, term, List.rev pl_rev),
- NCicReduction.head_beta_reduce (C.Appl (outtype::arguments@[term]))
+ let resty = C.Appl (outtype::arguments@[term]) in
+ let resty = NCicReduction.head_beta_reduce ~subst resty in
+ metasenv, subst, C.Match (r, outtype, term, pl),resty
| C.Match _ -> assert false
in
pp (lazy (NCicPp.ppterm ~metasenv ~subst ~context t ^ " :: "^
NCicPp.ppterm ~metasenv ~subst ~context infty ));
- force_ty metasenv subst context orig t infty expty
+ force_ty true metasenv subst context orig t infty expty
(*D*)in outside(); rc with exc -> outside (); raise exc
in
typeof_aux metasenv subst context expty term
-and eat_prods localise metasenv subst context orig_he he ty_he args =
+and try_coercions rdb
+ ~localise
+ metasenv subst context t orig_t infty expty perform_unification exc
+=
+ (* we try with a coercion *)
+ let rec first exc = function
+ | [] ->
+ raise (wrap_exc (lazy (localise orig_t, Printf.sprintf
+ "The term %s has type %s but is here used with type %s"
+ (NCicPp.ppterm ~metasenv ~subst ~context t)
+ (NCicPp.ppterm ~metasenv ~subst ~context infty)
+ (NCicPp.ppterm ~metasenv ~subst ~context expty))) exc)
+ | (metasenv, newterm, newtype, meta)::tl ->
+ try
+ pp (lazy ( "UNIFICATION in CTX:\n"^
+ NCicPp.ppcontext ~metasenv ~subst context
+ ^ "\nMENV: " ^
+ NCicPp.ppmetasenv metasenv ~subst
+ ^ "\nOF: " ^
+ NCicPp.ppterm ~metasenv ~subst ~context meta ^ " === " ^
+ NCicPp.ppterm ~metasenv ~subst ~context t ^ "\n"));
+ let metasenv, subst =
+ NCicUnification.unify rdb metasenv subst context meta t
+ in
+ pp (lazy ( "UNIFICATION in CTX:\n"^
+ NCicPp.ppcontext ~metasenv ~subst context
+ ^ "\nMENV: " ^
+ NCicPp.ppmetasenv metasenv ~subst
+ ^ "\nOF: " ^
+ NCicPp.ppterm ~metasenv ~subst ~context newtype ^ " === " ^
+ NCicPp.ppterm ~metasenv ~subst ~context expty ^ "\n"));
+ let metasenv, subst =
+ if perform_unification then
+ NCicUnification.unify rdb metasenv subst context newtype expty
+ else metasenv, subst
+ in
+ metasenv, subst, newterm, newtype
+ with
+ | NCicUnification.UnificationFailure _ -> first exc tl
+ | NCicUnification.Uncertain _ as exc -> first exc tl
+ in
+ first exc
+ (NCicCoercion.look_for_coercion rdb metasenv subst context infty expty)
+
+and force_to_sort rdb metasenv subst context t orig_t localise ty =
+ 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 []))) -> 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 =
+ if len > 0 then
+ NCicMetaSubst.restrict metasenv subst i (HExtlib.list_seq 1 (len+1))
+ else metasenv, subst, i
+ in
+ metasenv, subst, t, C.Meta (newmeta,(0,C.Irl 0))
+ | C.Sort _ as ty -> metasenv, subst, t, ty
+ | ty ->
+ try_coercions rdb ~localise metasenv subst context
+ t orig_t ty (NCic.Sort (NCic.Type NCicEnvironment.type0)) false
+ (Uncertain (lazy (localise orig_t,
+ "The type of " ^ NCicPp.ppterm ~metasenv ~subst ~context t
+ ^ " is not a sort: " ^ NCicPp.ppterm ~metasenv ~subst ~context ty)))
+
+and sort_of_prod
+ localise metasenv subst context orig_s orig_t (name,s) t (t1, t2)
+=
+ (* force to sort is done in the Prod case in typeof *)
+ match t1, t2 with
+ | C.Sort _, C.Sort C.Prop -> metasenv, subst, s, t, t2
+ | C.Sort (C.Type u1), C.Sort (C.Type u2) ->
+ metasenv, subst, s, t, C.Sort (C.Type (NCicEnvironment.max u1 u2))
+ | C.Sort C.Prop,C.Sort (C.Type _) -> metasenv, subst, s, t, t2
+ | C.Meta _, C.Sort _
+ | C.Meta _, C.Meta (_,(_,_))
+ | C.Sort _, C.Meta (_,(_,_)) -> metasenv, subst, s, t, t2
+ | x, (C.Sort _ | C.Meta _) | _, x ->
+ let y, context, orig =
+ if x == t1 then s, context, orig_s
+ else t, ((name,C.Decl s)::context), orig_t
+ in
+ raise (RefineFailure (lazy (localise orig,Printf.sprintf
+ "%s is expected to be a type, but its type is %s that is not a sort"
+ (NCicPp.ppterm ~subst ~metasenv ~context y)
+ (NCicPp.ppterm ~subst ~metasenv ~context x))))
+
+and guess_name subst ctx ty =
+ let aux initial = "#" ^ String.make 1 initial in
+ match ty with
+ | C.Const (NReference.Ref (u,_))
+ | C.Appl (C.Const (NReference.Ref (u,_)) :: _) ->
+ aux (String.sub (NUri.name_of_uri u) 0 1).[0]
+ | C.Prod _ -> aux 'f'
+ | C.Meta (n,lc) ->
+ (try
+ let _,_,t,_ = NCicUtils.lookup_subst n subst in
+ guess_name subst ctx (NCicSubstitution.subst_meta lc t)
+ with NCicUtils.Subst_not_found _ -> aux 'M')
+ | _ -> aux 'H'
+
+and eat_prods rdb
+ ~localise metasenv subst context orig_he he ty_he args
+=
(*D*)inside 'E'; try let rc =
- let rec aux metasenv subst args_so_far ty_he = function
- | [] -> metasenv, subst, NCic.Appl (he :: List.rev args_so_far), ty_he
+ let rec aux metasenv subst args_so_far he ty_he = function
+ | []->metasenv, subst, NCicUntrusted.mk_appl he (List.rev args_so_far), ty_he
| arg::tl ->
match NCicReduction.whd ~subst context ty_he with
| C.Prod (_,s,t) ->
let metasenv, subst, arg, _ =
- typeof ~localise metasenv subst context arg (Some s) in
+ typeof rdb ~localise
+ metasenv subst context arg (Some s) in
let t = NCicSubstitution.subst ~avoid_beta_redexes:true arg t in
- aux metasenv subst (arg :: args_so_far) t tl
+ aux metasenv subst (arg :: args_so_far) he t tl
| C.Meta _
| C.Appl (C.Meta _ :: _) as t ->
let metasenv, subst, arg, ty_arg =
- typeof ~localise metasenv subst context arg None in
- let metasenv, meta, _ =
+ typeof rdb ~localise
+ metasenv subst context arg None in
+ let name = guess_name subst context ty_arg in
+ let metasenv, _, meta, _ =
NCicMetaSubst.mk_meta metasenv
- (("_",C.Decl ty_arg) :: context) `Type
+ ((name,C.Decl ty_arg) :: context) `Type
in
- let flex_prod = C.Prod ("_", ty_arg, meta) in
+ let flex_prod = C.Prod (name, ty_arg, meta) in
+ (* next line grants that ty_args is a type *)
+ let metasenv,subst, flex_prod, _ =
+ typeof rdb ~localise metasenv subst
+ context flex_prod None in
pp (lazy ( "UNIFICATION in CTX:\n"^
NCicPp.ppcontext ~metasenv ~subst context
^ "\nOF: " ^
NCicPp.ppterm ~metasenv ~subst ~context t ^ " === " ^
NCicPp.ppterm ~metasenv ~subst ~context flex_prod ^ "\n"));
let metasenv, subst =
- try NCicUnification.unify metasenv subst context t flex_prod
+ try NCicUnification.unify rdb metasenv subst context t flex_prod
with exc -> raise (wrap_exc (lazy (localise orig_he, Printf.sprintf
("The term %s has an inferred type %s, but is applied to the" ^^
" argument %s of type %s")
(* XXX coerce to funclass *)
in
let meta = NCicSubstitution.subst ~avoid_beta_redexes:true arg meta in
- aux metasenv subst (arg :: args_so_far) meta tl
+ aux metasenv subst (arg :: args_so_far) he meta tl
| C.Match (_,_,C.Meta _,_)
| C.Match (_,_,C.Appl (C.Meta _ :: _),_)
| C.Appl (C.Const (NReference.Ref (_, NReference.Fix _)) :: _) ->
("The term %s is here applied to %d arguments but expects " ^^
"only %d arguments") (NCicPp.ppterm ~metasenv ~subst ~context he)
(List.length args) (List.length args_so_far))))
- | _ ->
- raise (RefineFailure (lazy (localise orig_he, Printf.sprintf
- ("The term %s is here applied to %d arguments but expects " ^^
- "only %d arguments") (NCicPp.ppterm ~metasenv ~subst ~context he)
- (List.length args) (List.length args_so_far))))
+ | ty ->
+ let metasenv, subst, newhead, newheadty =
+ try_coercions rdb ~localise metasenv subst context
+ (NCicUntrusted.mk_appl he (List.rev args_so_far)) orig_he ty
+ (NCic.Prod ("_",NCic.Implicit `Term,NCic.Implicit `Term))
+ false
+ (RefineFailure (lazy (localise orig_he, Printf.sprintf
+ ("The term %s is here applied to %d arguments but expects " ^^
+ "only %d arguments") (NCicPp.ppterm ~metasenv ~subst ~context he)
+ (List.length args) (List.length args_so_far))))
+ in
+ aux metasenv subst [] newhead newheadty (arg :: tl)
in
- aux metasenv subst [] ty_he args
+ (* We need to reverse the order of the new created metas since they
+ are pushed on top of the metasenv in the wrong order *)
+ let highest_meta = NCicMetaSubst.maxmeta () in
+ let metasenv, subst, newhead, newheadty =
+ aux metasenv subst [] he ty_he args in
+ let metasenv_old,metasenv_new =
+ List.partition (fun (i,_) -> i <= highest_meta) metasenv
+ in
+ (List.rev metasenv_new) @ metasenv_old, subst, newhead, newheadty
(*D*)in outside(); rc with exc -> outside (); raise exc
;;
+
+let rec first f l1 l2 =
+ match l1,l2 with
+ | x1::tl1, x2::tl2 ->
+ (try f x1 x2 with Not_found -> first f tl1 tl2)
+ | _ -> raise Not_found
+;;
+
+let rec find add dt t =
+ if dt == add then t
+ else
+ let dl, l =
+ match dt, t with
+ | C.Meta (_,(_,C.Ctx dl)), C.Meta (_,(_,C.Ctx l))
+ | C.Appl dl,C.Appl l -> dl,l
+ | C.Lambda (_,ds,dt), C.Lambda (_,s,t)
+ | C.Prod (_,ds,dt), C.Prod (_,s,t) -> [ds;dt],[s;t]
+ | C.LetIn (_,ds,db,dt), C.LetIn (_,s,b,t) -> [ds;db;dt],[s;b;t]
+ | C.Match (_,dot,dt,dl), C.Match (_,ot,t,l) -> (dot::dt::dl),(ot::t::l)
+ | _ -> raise Not_found
+ in
+ first (find add) dl l
+;;
+
+let relocalise old_localise dt t add =
+ old_localise
+ (try find add dt t with Not_found -> assert false)
+;;
+
+let undebruijnate inductive ref t rev_fl =
+ NCicSubstitution.psubst (fun x -> x)
+ (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))
+ t
+;;
+
+
+let typeof_obj
+ rdb ?(localise=fun _ -> Stdpp.dummy_loc) (uri,height,metasenv,subst,obj)
+=
+ let check_type metasenv subst context (ty as orig_ty) = (* XXX fattorizza *)
+ let metasenv, subst, ty, sort =
+ typeof rdb ~localise metasenv subst context ty None
+ in
+ let metasenv, subst, ty, sort =
+ force_to_sort rdb metasenv subst context ty orig_ty localise sort
+ in
+ 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, bo, ty, height =
+ match bo with
+ | Some bo ->
+ let metasenv, subst, bo, ty =
+ typeof rdb ~localise metasenv subst [] bo (Some ty) in
+ let height = (* XXX recalculate *) height in
+ metasenv, subst, Some bo, ty, height
+ | None -> metasenv, subst, None, ty, 0
+ in
+ uri, height, metasenv, subst,
+ C.Constant (relevance, name, bo, ty, attr)
+ | C.Fixpoint (inductive, fl, attr) ->
+ let len = List.length fl in
+ 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 dbo = NCicTypeChecker.debruijn uri len [] ~subst bo in
+ let localise = relocalise localise dbo bo in
+ (name,C.Decl ty)::types,
+ metasenv, subst, (relevance,name,k,ty,dbo,localise)::fl
+ ) ([], metasenv, subst, []) fl (* XXX kl rimosso nel nucleo *)
+ in
+ let metasenv, subst, fl =
+ List.fold_left
+ (fun (metasenv,subst,fl) (relevance,name,k,ty,dbo,localise) ->
+ let metasenv, subst, dbo, ty =
+ typeof rdb ~localise metasenv subst types dbo (Some ty)
+ in
+ metasenv, subst, (relevance,name,k,ty,dbo)::fl)
+ (metasenv, subst, []) rev_fl
+ in
+ let height = (* XXX recalculate *) height in
+ let fl =
+ List.map
+ (fun (relevance,name,k,ty,dbo) ->
+ let bo =
+ undebruijnate inductive
+ (NReference.reference_of_spec uri
+ (if inductive then NReference.Fix (0,k,0)
+ else NReference.CoFix 0)) dbo rev_fl
+ in
+ relevance,name,k,ty,bo)
+ fl
+ in
+ uri, height, metasenv, subst,
+ C.Fixpoint (inductive, fl, attr)
+ | 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 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 leftno k_relev)
+ with Failure _ -> k_relev in
+ let te = NCicTypeChecker.debruijn uri len [] ~subst 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 (List.length tys) (List.rev context) in
+ let sx_context_te_rev,_ =
+ HExtlib.split_nth 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 rdb ~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 rdb ~test_eq_only:true metasenv
+ subst context ty1 ty2
+ in
+ NCicUnification.unify rdb ~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
+ (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: *)
projects / helm.git / blobdiff