aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authornotin2006-12-12 15:57:07 +0000
committernotin2006-12-12 15:57:07 +0000
commit0e416b95c593bf315885f83e17575fcd26470c0f (patch)
treef350bcaf53eee7b4b96f478c55f634fcb0ccfde9
parent9e4f820147f786535f4ad8880efbcf9aa00897ee (diff)
Correction du bug #1273 (problème avec les paramètres non récursivement uniformes dans le cas de types mutuellement inductifs)
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@9445 85f007b7-540e-0410-9357-904b9bb8a0f7
-rw-r--r--kernel/indtypes.ml258
-rw-r--r--pretyping/indrec.ml147
2 files changed, 203 insertions, 202 deletions
diff --git a/kernel/indtypes.ml b/kernel/indtypes.ml
index 4187b8bd66..11264a9e38 100644
--- a/kernel/indtypes.ml
+++ b/kernel/indtypes.ml
@@ -411,34 +411,34 @@ let check_positivity_one (env, _,ntypes,_ as ienv) hyps i indlc =
(* check the inductive types occur positively in [c] *)
let rec check_pos (env, n, ntypes, ra_env as ienv) nmr c =
let x,largs = decompose_app (whd_betadeltaiota env c) in
- match kind_of_term x with
- | Prod (na,b,d) ->
- assert (largs = []);
- (match weaker_noccur_between env n ntypes b with
- None -> failwith_non_pos_list n ntypes [b]
- | Some b ->
- check_pos (ienv_push_var ienv (na, b, mk_norec)) nmr d)
- | Rel k ->
- (try let (ra,rarg) = List.nth ra_env (k-1) in
- let nmr1 =
- (match ra with
- Mrec _ -> compute_rec_par ienv hyps nmr largs
- | _ -> nmr)
- in
- if not (List.for_all (noccur_between n ntypes) largs)
- then failwith_non_pos_list n ntypes largs
- else (nmr1,rarg)
- with Failure _ | Invalid_argument _ -> (nmr,mk_norec))
- | Ind ind_kn ->
- (* If the inductive type being defined appears in a
- parameter, then we have an imbricated type *)
- if List.for_all (noccur_between n ntypes) largs then (nmr,mk_norec)
- else check_positive_imbr ienv nmr (ind_kn, largs)
- | err ->
- if noccur_between n ntypes x &&
- List.for_all (noccur_between n ntypes) largs
- then (nmr,mk_norec)
- else failwith_non_pos_list n ntypes (x::largs)
+ match kind_of_term x with
+ | Prod (na,b,d) ->
+ assert (largs = []);
+ (match weaker_noccur_between env n ntypes b with
+ None -> failwith_non_pos_list n ntypes [b]
+ | Some b ->
+ check_pos (ienv_push_var ienv (na, b, mk_norec)) nmr d)
+ | Rel k ->
+ (try let (ra,rarg) = List.nth ra_env (k-1) in
+ let nmr1 =
+ (match ra with
+ Mrec _ -> compute_rec_par ienv hyps nmr largs
+ | _ -> nmr)
+ in
+ if not (List.for_all (noccur_between n ntypes) largs)
+ then failwith_non_pos_list n ntypes largs
+ else (nmr1,rarg)
+ with Failure _ | Invalid_argument _ -> (nmr,mk_norec))
+ | Ind ind_kn ->
+ (* If the inductive type being defined appears in a
+ parameter, then we have an imbricated type *)
+ if List.for_all (noccur_between n ntypes) largs then (nmr,mk_norec)
+ else check_positive_imbr ienv nmr (ind_kn, largs)
+ | err ->
+ if noccur_between n ntypes x &&
+ List.for_all (noccur_between n ntypes) largs
+ then (nmr,mk_norec)
+ else failwith_non_pos_list n ntypes (x::largs)
(* accesses to the environment are not factorised, but is it worth? *)
and check_positive_imbr (env,n,ntypes,ra_env as ienv) nmr (mi, largs) =
@@ -447,69 +447,69 @@ let check_positivity_one (env, _,ntypes,_ as ienv) hyps i indlc =
let (lpar,auxlargs) =
try list_chop auxnpar largs
with Failure _ -> raise (IllFormedInd (LocalNonPos n)) in
- (* If the inductive appears in the args (non params) then the
- definition is not positive. *)
- if not (List.for_all (noccur_between n ntypes) auxlargs) then
- raise (IllFormedInd (LocalNonPos n));
- (* We do not deal with imbricated mutual inductive types *)
- let auxntyp = mib.mind_ntypes in
- if auxntyp <> 1 then raise (IllFormedInd (LocalNonPos n));
- (* The nested inductive type with parameters removed *)
- let auxlcvect = abstract_mind_lc env auxntyp auxnpar mip.mind_nf_lc in
- (* Extends the environment with a variable corresponding to
- the inductive def *)
- let (env',_,_,_ as ienv') = ienv_push_inductive ienv (mi,lpar) in
- (* Parameters expressed in env' *)
- let lpar' = List.map (lift auxntyp) lpar in
- let irecargs_nmr =
- (* fails if the inductive type occurs non positively *)
- (* when substituted *)
- Array.map
- (function c ->
- let c' = hnf_prod_applist env' c lpar' in
- check_constructors ienv' false nmr c')
- auxlcvect
- in
- let irecargs = Array.map snd irecargs_nmr
- and nmr' = array_min nmr irecargs_nmr
- in
- (nmr',(Rtree.mk_rec [|mk_paths (Imbr mi) irecargs|]).(0))
-
+ (* If the inductive appears in the args (non params) then the
+ definition is not positive. *)
+ if not (List.for_all (noccur_between n ntypes) auxlargs) then
+ raise (IllFormedInd (LocalNonPos n));
+ (* We do not deal with imbricated mutual inductive types *)
+ let auxntyp = mib.mind_ntypes in
+ if auxntyp <> 1 then raise (IllFormedInd (LocalNonPos n));
+ (* The nested inductive type with parameters removed *)
+ let auxlcvect = abstract_mind_lc env auxntyp auxnpar mip.mind_nf_lc in
+ (* Extends the environment with a variable corresponding to
+ the inductive def *)
+ let (env',_,_,_ as ienv') = ienv_push_inductive ienv (mi,lpar) in
+ (* Parameters expressed in env' *)
+ let lpar' = List.map (lift auxntyp) lpar in
+ let irecargs_nmr =
+ (* fails if the inductive type occurs non positively *)
+ (* when substituted *)
+ Array.map
+ (function c ->
+ let c' = hnf_prod_applist env' c lpar' in
+ check_constructors ienv' false nmr c')
+ auxlcvect
+ in
+ let irecargs = Array.map snd irecargs_nmr
+ and nmr' = array_min nmr irecargs_nmr
+ in
+ (nmr',(Rtree.mk_rec [|mk_paths (Imbr mi) irecargs|]).(0))
+
(* check the inductive types occur positively in the products of C, if
check_head=true, also check the head corresponds to a constructor of
the ith type *)
-
+
and check_constructors ienv check_head nmr c =
let rec check_constr_rec (env,n,ntypes,ra_env as ienv) nmr lrec c =
let x,largs = decompose_app (whd_betadeltaiota env c) in
- match kind_of_term x with
-
- | Prod (na,b,d) ->
- assert (largs = []);
- let nmr',recarg = check_pos ienv nmr b in
- let ienv' = ienv_push_var ienv (na,b,mk_norec) in
- check_constr_rec ienv' nmr' (recarg::lrec) d
-
- | hd ->
- if check_head then
- if hd = Rel (n+ntypes-i-1) then
- check_correct_par ienv hyps (ntypes-i) largs
+ match kind_of_term x with
+
+ | Prod (na,b,d) ->
+ assert (largs = []);
+ let nmr',recarg = check_pos ienv nmr b in
+ let ienv' = ienv_push_var ienv (na,b,mk_norec) in
+ check_constr_rec ienv' nmr' (recarg::lrec) d
+
+ | hd ->
+ if check_head then
+ if hd = Rel (n+ntypes-i-1) then
+ check_correct_par ienv hyps (ntypes-i) largs
+ else
+ raise (IllFormedInd LocalNotConstructor)
else
- raise (IllFormedInd LocalNotConstructor)
- else
- if not (List.for_all (noccur_between n ntypes) largs)
+ if not (List.for_all (noccur_between n ntypes) largs)
then raise (IllFormedInd (LocalNonPos n));
- (nmr,List.rev lrec)
+ (nmr,List.rev lrec)
in check_constr_rec ienv nmr [] c
in
let irecargs_nmr =
- Array.map
+ Array.map
(fun c ->
let _,rawc = mind_extract_params lparams c in
- try
- check_constructors ienv true nmr rawc
- with IllFormedInd err ->
- explain_ind_err (ntypes-i) env lparams c err)
+ try
+ check_constructors ienv true nmr rawc
+ with IllFormedInd err ->
+ explain_ind_err (ntypes-i) env lparams c err)
indlc
in
let irecargs = Array.map snd irecargs_nmr
@@ -526,7 +526,7 @@ let check_positivity env_ar params inds =
let ra_env =
list_tabulate (fun _ -> (Norec,mk_norec)) lparams @ lra_ind in
let ienv = (env_ar, 1+lparams, ntypes, ra_env) in
- check_positivity_one ienv params i lc
+ check_positivity_one ienv params i lc
in
let irecargs_nmr = Array.mapi check_one inds in
let irecargs = Array.map snd irecargs_nmr
@@ -597,61 +597,61 @@ let build_inductive env env_ar params isrecord isfinite inds nmr recargs cst =
let consnrealargs =
Array.map (fun (d,_) -> rel_context_length d - rel_context_length params)
splayed_lc in
- (* Elimination sorts *)
+ (* Elimination sorts *)
let arkind,kelim = match ar_kind with
- | Inr (param_levels,lev) ->
- Polymorphic {
- poly_param_levels = param_levels;
- poly_level = lev;
- }, all_sorts
- | Inl ((issmall,isunit),ar,s) ->
- let isunit = isunit && ntypes = 1 && not (is_recursive recargs.(0)) in
- let kelim = allowed_sorts issmall isunit s in
- Monomorphic {
- mind_user_arity = ar;
- mind_sort = s;
- }, kelim in
+ | Inr (param_levels,lev) ->
+ Polymorphic {
+ poly_param_levels = param_levels;
+ poly_level = lev;
+ }, all_sorts
+ | Inl ((issmall,isunit),ar,s) ->
+ let isunit = isunit && ntypes = 1 && not (is_recursive recargs.(0)) in
+ let kelim = allowed_sorts issmall isunit s in
+ Monomorphic {
+ mind_user_arity = ar;
+ mind_sort = s;
+ }, kelim in
let nconst, nblock = ref 0, ref 0 in
let transf num =
let arity = List.length (dest_subterms recarg).(num) in
- if arity = 0 then
- let p = (!nconst, 0) in
- incr nconst; p
- else
- let p = (!nblock + 1, arity) in
- incr nblock; p
- (* les tag des constructeur constant commence a 0,
- les tag des constructeur non constant a 1 (0 => accumulator) *)
+ if arity = 0 then
+ let p = (!nconst, 0) in
+ incr nconst; p
+ else
+ let p = (!nblock + 1, arity) in
+ incr nblock; p
+ (* les tag des constructeur constant commence a 0,
+ les tag des constructeur non constant a 1 (0 => accumulator) *)
in
let rtbl = Array.init (List.length cnames) transf in
- (* Build the inductive packet *)
- { mind_typename = id;
- mind_arity = arkind;
- mind_arity_ctxt = ar_sign;
- mind_nrealargs = rel_context_nhyps ar_sign - nparamargs;
- mind_kelim = kelim;
- mind_consnames = Array.of_list cnames;
- mind_consnrealdecls = consnrealargs;
- mind_user_lc = lc;
- mind_nf_lc = nf_lc;
- mind_recargs = recarg;
- mind_nb_constant = !nconst;
- mind_nb_args = !nblock;
- mind_reloc_tbl = rtbl;
- } in
+ (* Build the inductive packet *)
+ { mind_typename = id;
+ mind_arity = arkind;
+ mind_arity_ctxt = ar_sign;
+ mind_nrealargs = rel_context_nhyps ar_sign - nparamargs;
+ mind_kelim = kelim;
+ mind_consnames = Array.of_list cnames;
+ mind_consnrealdecls = consnrealargs;
+ mind_user_lc = lc;
+ mind_nf_lc = nf_lc;
+ mind_recargs = recarg;
+ mind_nb_constant = !nconst;
+ mind_nb_args = !nblock;
+ mind_reloc_tbl = rtbl;
+ } in
let packets = array_map2 build_one_packet inds recargs in
- (* Build the mutual inductive *)
- { mind_record = isrecord;
- mind_ntypes = ntypes;
- mind_finite = isfinite;
- mind_hyps = hyps;
- mind_nparams = nparamargs;
- mind_nparams_rec = nmr;
- mind_params_ctxt = params;
- mind_packets = packets;
- mind_constraints = cst;
- mind_equiv = None;
- }
+ (* Build the mutual inductive *)
+ { mind_record = isrecord;
+ mind_ntypes = ntypes;
+ mind_finite = isfinite;
+ mind_hyps = hyps;
+ mind_nparams = nparamargs;
+ mind_nparams_rec = nmr;
+ mind_params_ctxt = params;
+ mind_packets = packets;
+ mind_constraints = cst;
+ mind_equiv = None;
+ }
(************************************************************************)
(************************************************************************)
@@ -662,5 +662,5 @@ let check_inductive env mie =
(* Then check positivity conditions *)
let (nmr,recargs) = check_positivity env_ar params inds in
(* Build the inductive packets *)
- build_inductive env env_ar params mie.mind_entry_record mie.mind_entry_finite
- inds nmr recargs cst
+ build_inductive env env_ar params mie.mind_entry_record mie.mind_entry_finite
+ inds nmr recargs cst
diff --git a/pretyping/indrec.ml b/pretyping/indrec.ml
index f3e3b6d2c5..abd49ee4b7 100644
--- a/pretyping/indrec.ml
+++ b/pretyping/indrec.ml
@@ -275,19 +275,18 @@ let mis_make_indrec env sigma listdepkind mib =
Array.create mib.mind_ntypes (None : (bool * constr) option) in
let _ =
let rec
- assign k = function
- | [] -> ()
- | (indi,mibi,mipi,dep,_)::rest ->
- (Array.set depPvec (snd indi) (Some(dep,mkRel k));
- assign (k-1) rest)
+ assign k = function
+ | [] -> ()
+ | (indi,mibi,mipi,dep,_)::rest ->
+ (Array.set depPvec (snd indi) (Some(dep,mkRel k));
+ assign (k-1) rest)
in
- assign nrec listdepkind in
+ assign nrec listdepkind in
let recargsvec =
Array.map (fun mip -> mip.mind_recargs) mib.mind_packets in
- (* recarg information for non recursive parameters *)
+ (* recarg information for non recursive parameters *)
let rec recargparn l n =
- if n = 0 then l else recargparn (mk_norec::l) (n-1)
- in
+ if n = 0 then l else recargparn (mk_norec::l) (n-1) in
let recargpar = recargparn [] (nparams-nparrec) in
let make_one_rec p =
let makefix nbconstruct =
@@ -296,97 +295,97 @@ let mis_make_indrec env sigma listdepkind mib =
let tyi = snd indi in
let nctyi =
Array.length mipi.mind_consnames in (* nb constructeurs du type*)
-
+
(* arity in the context of the fixpoint, i.e.
- P1..P_nrec f1..f_nbconstruct *)
+ P1..P_nrec f1..f_nbconstruct *)
let args = extended_rel_list (nrec+nbconstruct) lnamesparrec in
let indf = make_ind_family(indi,args) in
-
+
let arsign,_ = get_arity env indf in
let depind = build_dependent_inductive env indf in
let deparsign = (Anonymous,None,depind)::arsign in
-
+
let nonrecpar = rel_context_length lnonparrec in
let larsign = rel_context_length deparsign in
let ndepar = larsign - nonrecpar in
let dect = larsign+nrec+nbconstruct in
-
- (* constructors in context of the Cases expr, i.e.
- P1..P_nrec f1..f_nbconstruct F_1..F_nrec a_1..a_nar x:I *)
+
+ (* constructors in context of the Cases expr, i.e.
+ P1..P_nrec f1..f_nbconstruct F_1..F_nrec a_1..a_nar x:I *)
let args' = extended_rel_list (dect+nrec) lnamesparrec in
let args'' = extended_rel_list ndepar lnonparrec in
let indf' = make_ind_family(indi,args'@args'') in
-
+
let branches =
let constrs = get_constructors env indf' in
let fi = rel_vect (dect-i-nctyi) nctyi in
let vecfi = Array.map
- (fun f -> appvect (f,extended_rel_vect ndepar lnonparrec))
- fi
+ (fun f -> appvect (f,extended_rel_vect ndepar lnonparrec))
+ fi
in
- array_map3
- (make_rec_branch_arg env sigma
- (nparrec,depPvec,larsign))
- vecfi constrs (dest_subterms recargsvec.(tyi))
+ array_map3
+ (make_rec_branch_arg env sigma
+ (nparrec,depPvec,larsign))
+ vecfi constrs (dest_subterms recargsvec.(tyi))
in
-
+
let j = (match depPvec.(tyi) with
- | Some (_,c) when isRel c -> destRel c
- | _ -> assert false)
+ | Some (_,c) when isRel c -> destRel c
+ | _ -> assert false)
in
-
- (* Predicate in the context of the case *)
-
+
+ (* Predicate in the context of the case *)
+
let depind' = build_dependent_inductive env indf' in
let arsign',_ = get_arity env indf' in
let deparsign' = (Anonymous,None,depind')::arsign' in
-
+
let pargs =
let nrpar = extended_rel_list (2*ndepar) lnonparrec
and nrar = if dep then extended_rel_list 0 deparsign'
- else extended_rel_list 1 arsign'
+ else extended_rel_list 1 arsign'
in nrpar@nrar
-
+
in
- (* body of i-th component of the mutual fixpoint *)
+ (* body of i-th component of the mutual fixpoint *)
let deftyi =
let ci = make_default_case_info env RegularStyle indi in
let concl = applist (mkRel (dect+j+ndepar),pargs) in
let pred =
it_mkLambda_or_LetIn_name env
((if dep then mkLambda_name env else mkLambda)
- (Anonymous,depind',concl))
+ (Anonymous,depind',concl))
arsign'
in
- it_mkLambda_or_LetIn_name env
- (mkCase (ci, pred,
- mkRel 1,
- branches))
- (lift_rel_context nrec deparsign)
+ it_mkLambda_or_LetIn_name env
+ (mkCase (ci, pred,
+ mkRel 1,
+ branches))
+ (lift_rel_context nrec deparsign)
in
-
+
(* type of i-th component of the mutual fixpoint *)
-
+
let typtyi =
- let concl =
- let pargs = if dep then extended_rel_vect 0 deparsign
- else extended_rel_vect 1 arsign
- in appvect (mkRel (nbconstruct+ndepar+nonrecpar+j),pargs)
- in it_mkProd_or_LetIn_name env
+ let concl =
+ let pargs = if dep then extended_rel_vect 0 deparsign
+ else extended_rel_vect 1 arsign
+ in appvect (mkRel (nbconstruct+ndepar+nonrecpar+j),pargs)
+ in it_mkProd_or_LetIn_name env
concl
deparsign
in
- mrec (i+nctyi) (rel_context_nhyps arsign ::ln) (typtyi::ltyp)
- (deftyi::ldef) rest
+ mrec (i+nctyi) (rel_context_nhyps arsign ::ln) (typtyi::ltyp)
+ (deftyi::ldef) rest
| [] ->
let fixn = Array.of_list (List.rev ln) in
let fixtyi = Array.of_list (List.rev ltyp) in
let fixdef = Array.of_list (List.rev ldef) in
let names = Array.create nrec (Name(id_of_string "F")) in
- mkFix ((fixn,p),(names,fixtyi,fixdef))
+ mkFix ((fixn,p),(names,fixtyi,fixdef))
in
- mrec 0 [] [] []
+ mrec 0 [] [] []
in
let rec make_branch env i = function
| (indi,mibi,mipi,dep,_)::rest ->
@@ -404,44 +403,46 @@ let mis_make_indrec env sigma listdepkind mib =
type_rec_branch
true dep env sigma (vargs,depPvec,i+j) tyi cs recarg
in
- mkLambda_string "f" p_0
- (onerec (push_rel (Anonymous,None,p_0) env) (j+1))
+ mkLambda_string "f" p_0
+ (onerec (push_rel (Anonymous,None,p_0) env) (j+1))
in onerec env 0
| [] ->
makefix i listdepkind
- in
+ in
let rec put_arity env i = function
| (indi,_,_,dep,kinds)::rest ->
let indf = make_ind_family (indi,extended_rel_list i lnamesparrec) in
let typP = make_arity env dep indf (new_sort_in_family kinds) in
- mkLambda_string "P" typP
- (put_arity (push_rel (Anonymous,None,typP) env) (i+1) rest)
+ mkLambda_string "P" typP
+ (put_arity (push_rel (Anonymous,None,typP) env) (i+1) rest)
| [] ->
make_branch env 0 listdepkind
- in
-
- (* Body on make_one_rec *)
+ in
+
+ (* Body on make_one_rec *)
let (indi,mibi,mipi,dep,kind) = List.nth listdepkind p in
-
- if mis_is_recursive_subset
- (List.map (fun (indi,_,_,_,_) -> snd indi) listdepkind)
- mipi.mind_recargs
- then
- let env' = push_rel_context lnamesparrec env in
- it_mkLambda_or_LetIn_name env (put_arity env' 0 listdepkind)
- lnamesparrec
- else
- mis_make_case_com (Some dep) env sigma indi (mibi,mipi) kind
+
+ if (mis_is_recursive_subset
+ (List.map (fun (indi,_,_,_,_) -> snd indi) listdepkind)
+ mipi.mind_recargs)
+ (* mis_is_recursive_subset do not care about mutually recursive calls so: *)
+ || (nparams-nparrec > 0)
+ then
+ let env' = push_rel_context lnamesparrec env in
+ it_mkLambda_or_LetIn_name env (put_arity env' 0 listdepkind)
+ lnamesparrec
+ else
+ mis_make_case_com (Some dep) env sigma indi (mibi,mipi) kind
in
- (* Body of mis_make_indrec *)
- list_tabulate make_one_rec nrec
+ (* Body of mis_make_indrec *)
+ list_tabulate make_one_rec nrec
(**********************************************************************)
(* This builds elimination predicate for Case tactic *)
let make_case_com depopt env sigma ity kind =
let (mib,mip) = lookup_mind_specif env ity in
- mis_make_case_com depopt env sigma ity (mib,mip) kind
+ mis_make_case_com depopt env sigma ity (mib,mip) kind
let make_case_dep env = make_case_com (Some true) env
let make_case_nodep env = make_case_com (Some false) env
@@ -460,7 +461,7 @@ let change_sort_arity sort =
| Sort _ -> mkSort sort
| _ -> assert false
in
- drec
+ drec
(* [npar] is the number of expected arguments (then excluding letin's) *)
let instantiate_indrec_scheme sort =
@@ -536,7 +537,7 @@ let build_indrec env sigma ind =
let (mib,mip) = lookup_mind_specif env ind in
let kind = inductive_sort_family mip in
let dep = kind <> InProp in
- List.hd (mis_make_indrec env sigma [(ind,mib,mip,dep,kind)] mib)
+ List.hd (mis_make_indrec env sigma [(ind,mib,mip,dep,kind)] mib)
(**********************************************************************)
(* To handle old Case/Match syntax in Pretyping *)