substitution et pattern modulo let

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@2466 85f007b7-540e-0410-9357-904b9bb8a0f7

10 files changed, 265 insertions, 238 deletions

diff --git a/.depend b/.depend
index 6363cbebf..11dd9cdd5 100644
--- a/.depend
+++ b/.depend
@@ -25,8 +25,6 @@ kernel/typeops.cmi: kernel/environ.cmi kernel/names.cmi kernel/sign.cmi \
     kernel/term.cmi kernel/univ.cmi 
 kernel/univ.cmi: kernel/names.cmi lib/pp.cmi 
 lib/pp.cmi: lib/pp_control.cmi 
-lib/system.cmi: lib/pp.cmi 
-lib/util.cmi: lib/pp.cmi 
 library/declare.cmi: kernel/cooking.cmi kernel/declarations.cmi \
     kernel/environ.cmi kernel/indtypes.cmi library/libobject.cmi \
     library/library.cmi kernel/names.cmi library/nametab.cmi \
@@ -47,6 +45,8 @@ library/nameops.cmi: kernel/environ.cmi kernel/names.cmi lib/pp.cmi \
 library/nametab.cmi: kernel/environ.cmi kernel/names.cmi lib/pp.cmi \
     lib/util.cmi 
 library/summary.cmi: kernel/names.cmi 
+lib/system.cmi: lib/pp.cmi 
+lib/util.cmi: lib/pp.cmi 
 parsing/ast.cmi: parsing/coqast.cmi lib/dyn.cmi kernel/names.cmi \
     parsing/pcoq.cmi lib/pp.cmi 
 parsing/astterm.cmi: parsing/coqast.cmi kernel/environ.cmi pretyping/evd.cmi \
@@ -225,18 +225,18 @@ toplevel/recordobj.cmi: library/nametab.cmi
 toplevel/searchisos.cmi: library/libobject.cmi kernel/names.cmi \
     kernel/term.cmi 
 toplevel/toplevel.cmi: parsing/pcoq.cmi lib/pp.cmi 
-toplevel/vernac.cmi: parsing/coqast.cmi parsing/pcoq.cmi 
 toplevel/vernacentries.cmi: kernel/environ.cmi pretyping/evd.cmi \
     kernel/names.cmi kernel/term.cmi toplevel/vernacinterp.cmi 
 toplevel/vernacinterp.cmi: parsing/coqast.cmi lib/dyn.cmi kernel/names.cmi \
     library/nametab.cmi proofs/proof_type.cmi 
+toplevel/vernac.cmi: parsing/coqast.cmi parsing/pcoq.cmi 
 contrib/correctness/past.cmi: parsing/coqast.cmi kernel/names.cmi \
     contrib/correctness/ptype.cmi kernel/term.cmi 
-contrib/correctness/pcic.cmi: contrib/correctness/past.cmi \
-    pretyping/rawterm.cmi 
 contrib/correctness/pcicenv.cmi: kernel/names.cmi \
     contrib/correctness/penv.cmi contrib/correctness/prename.cmi \
     kernel/sign.cmi kernel/term.cmi 
+contrib/correctness/pcic.cmi: contrib/correctness/past.cmi \
+    pretyping/rawterm.cmi 
 contrib/correctness/pdb.cmi: kernel/names.cmi contrib/correctness/past.cmi \
     contrib/correctness/ptype.cmi 
 contrib/correctness/peffect.cmi: kernel/names.cmi lib/pp.cmi 
@@ -286,7 +286,8 @@ contrib/extraction/miniml.cmi: kernel/names.cmi library/nametab.cmi \
 contrib/extraction/mlutil.cmi: contrib/extraction/miniml.cmi kernel/names.cmi \
     library/nametab.cmi kernel/term.cmi 
 contrib/extraction/ocaml.cmi: contrib/extraction/miniml.cmi kernel/names.cmi \
-    library/nametab.cmi lib/pp.cmi kernel/term.cmi 
+    library/nametab.cmi lib/pp.cmi contrib/extraction/table.cmi \
+    kernel/term.cmi 
 contrib/extraction/table.cmi: kernel/names.cmi library/nametab.cmi \
     toplevel/vernacinterp.cmi 
 contrib/interface/blast.cmi: contrib/interface/ctast.cmo \
@@ -427,32 +428,24 @@ lib/edit.cmo: lib/bstack.cmi lib/pp.cmi lib/util.cmi lib/edit.cmi
 lib/edit.cmx: lib/bstack.cmx lib/pp.cmx lib/util.cmx lib/edit.cmi 
 lib/explore.cmo: lib/explore.cmi 
 lib/explore.cmx: lib/explore.cmi 
-lib/gmap.cmo: lib/gmap.cmi 
-lib/gmap.cmx: lib/gmap.cmi 
 lib/gmapl.cmo: lib/gmap.cmi lib/util.cmi lib/gmapl.cmi 
 lib/gmapl.cmx: lib/gmap.cmx lib/util.cmx lib/gmapl.cmi 
+lib/gmap.cmo: lib/gmap.cmi 
+lib/gmap.cmx: lib/gmap.cmi 
 lib/gset.cmo: lib/gset.cmi 
 lib/gset.cmx: lib/gset.cmi 
 lib/hashcons.cmo: lib/hashcons.cmi 
 lib/hashcons.cmx: lib/hashcons.cmi 
 lib/options.cmo: lib/util.cmi lib/options.cmi 
 lib/options.cmx: lib/util.cmx lib/options.cmi 
-lib/pp.cmo: lib/pp_control.cmi lib/pp.cmi 
-lib/pp.cmx: lib/pp_control.cmx lib/pp.cmi 
 lib/pp_control.cmo: lib/pp_control.cmi 
 lib/pp_control.cmx: lib/pp_control.cmi 
+lib/pp.cmo: lib/pp_control.cmi lib/pp.cmi 
+lib/pp.cmx: lib/pp_control.cmx lib/pp.cmi 
 lib/predicate.cmo: lib/predicate.cmi 
 lib/predicate.cmx: lib/predicate.cmi 
 lib/profile.cmo: lib/profile.cmi 
 lib/profile.cmx: lib/profile.cmi 
-lib/stamps.cmo: lib/stamps.cmi 
-lib/stamps.cmx: lib/stamps.cmi 
-lib/system.cmo: config/coq_config.cmi lib/pp.cmi lib/util.cmi lib/system.cmi 
-lib/system.cmx: config/coq_config.cmx lib/pp.cmx lib/util.cmx lib/system.cmi 
-lib/tlm.cmo: lib/gmap.cmi lib/gset.cmi lib/tlm.cmi 
-lib/tlm.cmx: lib/gmap.cmx lib/gset.cmx lib/tlm.cmi 
-lib/util.cmo: lib/pp.cmi lib/util.cmi 
-lib/util.cmx: lib/pp.cmx lib/util.cmi 
 library/declare.cmo: kernel/declarations.cmi kernel/environ.cmi \
     library/global.cmi library/impargs.cmi kernel/indtypes.cmi \
     kernel/inductive.cmi library/lib.cmi library/libobject.cmi \
@@ -529,6 +522,14 @@ library/summary.cmo: lib/dyn.cmi kernel/names.cmi lib/pp.cmi lib/util.cmi \
     library/summary.cmi 
 library/summary.cmx: lib/dyn.cmx kernel/names.cmx lib/pp.cmx lib/util.cmx \
     library/summary.cmi 
+lib/stamps.cmo: lib/stamps.cmi 
+lib/stamps.cmx: lib/stamps.cmi 
+lib/system.cmo: config/coq_config.cmi lib/pp.cmi lib/util.cmi lib/system.cmi 
+lib/system.cmx: config/coq_config.cmx lib/pp.cmx lib/util.cmx lib/system.cmi 
+lib/tlm.cmo: lib/gmap.cmi lib/gset.cmi lib/tlm.cmi 
+lib/tlm.cmx: lib/gmap.cmx lib/gset.cmx lib/tlm.cmi 
+lib/util.cmo: lib/pp.cmi lib/util.cmi 
+lib/util.cmx: lib/pp.cmx lib/util.cmi 
 parsing/ast.cmo: parsing/coqast.cmi lib/dyn.cmi kernel/names.cmi \
     parsing/pcoq.cmi lib/pp.cmi lib/util.cmi parsing/ast.cmi 
 parsing/ast.cmx: parsing/coqast.cmx lib/dyn.cmx kernel/names.cmx \
@@ -777,18 +778,18 @@ pretyping/indrec.cmo: kernel/declarations.cmi library/declare.cmi \
     kernel/environ.cmi pretyping/evd.cmi library/global.cmi \
     kernel/indtypes.cmi kernel/inductive.cmi pretyping/inductiveops.cmi \
     pretyping/instantiate.cmi library/nameops.cmi kernel/names.cmi \
-    library/nametab.cmi lib/options.cmi lib/pp.cmi pretyping/reductionops.cmi \
-    kernel/safe_typing.cmi kernel/term.cmi pretyping/termops.cmi \
-    kernel/type_errors.cmi kernel/typeops.cmi lib/util.cmi \
-    pretyping/indrec.cmi 
+    library/nametab.cmi lib/options.cmi lib/pp.cmi kernel/reduction.cmi \
+    pretyping/reductionops.cmi kernel/safe_typing.cmi kernel/term.cmi \
+    pretyping/termops.cmi kernel/type_errors.cmi kernel/typeops.cmi \
+    lib/util.cmi pretyping/indrec.cmi 
 pretyping/indrec.cmx: kernel/declarations.cmx library/declare.cmx \
     kernel/environ.cmx pretyping/evd.cmx library/global.cmx \
     kernel/indtypes.cmx kernel/inductive.cmx pretyping/inductiveops.cmx \
     pretyping/instantiate.cmx library/nameops.cmx kernel/names.cmx \
-    library/nametab.cmx lib/options.cmx lib/pp.cmx pretyping/reductionops.cmx \
-    kernel/safe_typing.cmx kernel/term.cmx pretyping/termops.cmx \
-    kernel/type_errors.cmx kernel/typeops.cmx lib/util.cmx \
-    pretyping/indrec.cmi 
+    library/nametab.cmx lib/options.cmx lib/pp.cmx kernel/reduction.cmx \
+    pretyping/reductionops.cmx kernel/safe_typing.cmx kernel/term.cmx \
+    pretyping/termops.cmx kernel/type_errors.cmx kernel/typeops.cmx \
+    lib/util.cmx pretyping/indrec.cmi 
 pretyping/inductiveops.cmo: kernel/declarations.cmi kernel/environ.cmi \
     pretyping/evd.cmi kernel/inductive.cmi kernel/names.cmi \
     pretyping/reductionops.cmi kernel/sign.cmi kernel/term.cmi \
@@ -901,14 +902,12 @@ pretyping/tacred.cmx: pretyping/cbv.cmx kernel/closure.cmx \
     library/nametab.cmx lib/pp.cmx pretyping/reductionops.cmx \
     library/summary.cmx kernel/term.cmx pretyping/termops.cmx lib/util.cmx \
     pretyping/tacred.cmi 
-pretyping/termops.cmo: kernel/environ.cmi library/global.cmi \
-    library/nameops.cmi kernel/names.cmi library/nametab.cmi lib/pp.cmi \
-    kernel/sign.cmi kernel/term.cmi kernel/univ.cmi lib/util.cmi \
-    pretyping/termops.cmi 
-pretyping/termops.cmx: kernel/environ.cmx library/global.cmx \
-    library/nameops.cmx kernel/names.cmx library/nametab.cmx lib/pp.cmx \
-    kernel/sign.cmx kernel/term.cmx kernel/univ.cmx lib/util.cmx \
-    pretyping/termops.cmi 
+pretyping/termops.cmo: kernel/environ.cmi library/nameops.cmi \
+    kernel/names.cmi library/nametab.cmi lib/pp.cmi kernel/sign.cmi \
+    kernel/term.cmi kernel/univ.cmi lib/util.cmi pretyping/termops.cmi 
+pretyping/termops.cmx: kernel/environ.cmx library/nameops.cmx \
+    kernel/names.cmx library/nametab.cmx lib/pp.cmx kernel/sign.cmx \
+    kernel/term.cmx kernel/univ.cmx lib/util.cmx pretyping/termops.cmi 
 pretyping/typing.cmo: kernel/environ.cmi kernel/inductive.cmi \
     pretyping/instantiate.cmi kernel/names.cmi pretyping/pretype_errors.cmi \
     pretyping/reductionops.cmi kernel/term.cmi kernel/type_errors.cmi \
@@ -1199,24 +1198,22 @@ tactics/hipattern.cmx: proofs/clenv.cmx parsing/coqlib.cmx \
     kernel/names.cmx pretyping/pattern.cmx lib/pp.cmx proofs/proof_trees.cmx \
     pretyping/reductionops.cmx kernel/term.cmx pretyping/termops.cmx \
     lib/util.cmx tactics/hipattern.cmi 
-tactics/inv.cmo: tactics/auto.cmi proofs/clenv.cmi parsing/coqlib.cmi \
-    tactics/elim.cmi kernel/environ.cmi tactics/equality.cmi \
-    proofs/evar_refiner.cmi library/global.cmi pretyping/inductiveops.cmi \
-    library/nameops.cmi kernel/names.cmi pretyping/pattern.cmi lib/pp.cmi \
-    parsing/printer.cmi proofs/proof_type.cmi pretyping/reductionops.cmi \
-    pretyping/retyping.cmi kernel/sign.cmi proofs/tacmach.cmi \
-    tactics/tacticals.cmi tactics/tactics.cmi kernel/term.cmi \
-    pretyping/termops.cmi pretyping/typing.cmi lib/util.cmi \
-    tactics/wcclausenv.cmi tactics/inv.cmi 
-tactics/inv.cmx: tactics/auto.cmx proofs/clenv.cmx parsing/coqlib.cmx \
-    tactics/elim.cmx kernel/environ.cmx tactics/equality.cmx \
-    proofs/evar_refiner.cmx library/global.cmx pretyping/inductiveops.cmx \
-    library/nameops.cmx kernel/names.cmx pretyping/pattern.cmx lib/pp.cmx \
-    parsing/printer.cmx proofs/proof_type.cmx pretyping/reductionops.cmx \
-    pretyping/retyping.cmx kernel/sign.cmx proofs/tacmach.cmx \
-    tactics/tacticals.cmx tactics/tactics.cmx kernel/term.cmx \
-    pretyping/termops.cmx pretyping/typing.cmx lib/util.cmx \
-    tactics/wcclausenv.cmx tactics/inv.cmi 
+tactics/inv.cmo: proofs/clenv.cmi parsing/coqlib.cmi tactics/elim.cmi \
+    kernel/environ.cmi tactics/equality.cmi proofs/evar_refiner.cmi \
+    library/global.cmi pretyping/inductiveops.cmi library/nameops.cmi \
+    kernel/names.cmi pretyping/pattern.cmi lib/pp.cmi parsing/printer.cmi \
+    proofs/proof_type.cmi pretyping/reductionops.cmi pretyping/retyping.cmi \
+    kernel/sign.cmi proofs/tacmach.cmi tactics/tacticals.cmi \
+    tactics/tactics.cmi kernel/term.cmi pretyping/termops.cmi \
+    pretyping/typing.cmi lib/util.cmi tactics/wcclausenv.cmi tactics/inv.cmi 
+tactics/inv.cmx: proofs/clenv.cmx parsing/coqlib.cmx tactics/elim.cmx \
+    kernel/environ.cmx tactics/equality.cmx proofs/evar_refiner.cmx \
+    library/global.cmx pretyping/inductiveops.cmx library/nameops.cmx \
+    kernel/names.cmx pretyping/pattern.cmx lib/pp.cmx parsing/printer.cmx \
+    proofs/proof_type.cmx pretyping/reductionops.cmx pretyping/retyping.cmx \
+    kernel/sign.cmx proofs/tacmach.cmx tactics/tacticals.cmx \
+    tactics/tactics.cmx kernel/term.cmx pretyping/termops.cmx \
+    pretyping/typing.cmx lib/util.cmx tactics/wcclausenv.cmx tactics/inv.cmi 
 tactics/leminv.cmo: parsing/astterm.cmi proofs/clenv.cmi \
     kernel/declarations.cmi library/declare.cmi kernel/environ.cmi \
     proofs/evar_refiner.cmi pretyping/evd.cmi library/global.cmi \
@@ -1349,12 +1346,12 @@ tactics/wcclausenv.cmx: proofs/clenv.cmx kernel/environ.cmx \
     proofs/proof_trees.cmx pretyping/reductionops.cmx kernel/sign.cmx \
     proofs/tacmach.cmx kernel/term.cmx pretyping/termops.cmx lib/util.cmx \
     tactics/wcclausenv.cmi 
-tools/coq_vo2xml.cmo: config/coq_config.cmi toplevel/usage.cmi 
-tools/coq_vo2xml.cmx: config/coq_config.cmx toplevel/usage.cmx 
-tools/coqdep.cmo: config/coq_config.cmi tools/coqdep_lexer.cmo 
-tools/coqdep.cmx: config/coq_config.cmx tools/coqdep_lexer.cmx 
 tools/coqdep_lexer.cmo: config/coq_config.cmi 
 tools/coqdep_lexer.cmx: config/coq_config.cmx 
+tools/coqdep.cmo: config/coq_config.cmi tools/coqdep_lexer.cmo 
+tools/coqdep.cmx: config/coq_config.cmx tools/coqdep_lexer.cmx 
+tools/coq_vo2xml.cmo: config/coq_config.cmi toplevel/usage.cmi 
+tools/coq_vo2xml.cmx: config/coq_config.cmx toplevel/usage.cmx 
 tools/gallina.cmo: tools/gallina_lexer.cmo 
 tools/gallina.cmx: tools/gallina_lexer.cmx 
 toplevel/class.cmo: pretyping/classops.cmi kernel/declarations.cmi \
@@ -1535,16 +1532,6 @@ toplevel/toplevel.cmx: parsing/ast.cmx toplevel/errors.cmx library/lib.cmx \
     toplevel/vernac.cmx toplevel/vernacinterp.cmx toplevel/toplevel.cmi 
 toplevel/usage.cmo: config/coq_config.cmi toplevel/usage.cmi 
 toplevel/usage.cmx: config/coq_config.cmx toplevel/usage.cmi 
-toplevel/vernac.cmo: parsing/ast.cmi parsing/coqast.cmi library/lib.cmi \
-    library/library.cmi library/nameops.cmi kernel/names.cmi lib/options.cmi \
-    parsing/pcoq.cmi lib/pp.cmi library/states.cmi lib/system.cmi \
-    pretyping/termops.cmi lib/util.cmi toplevel/vernacinterp.cmi \
-    toplevel/vernac.cmi 
-toplevel/vernac.cmx: parsing/ast.cmx parsing/coqast.cmx library/lib.cmx \
-    library/library.cmx library/nameops.cmx kernel/names.cmx lib/options.cmx \
-    parsing/pcoq.cmx lib/pp.cmx library/states.cmx lib/system.cmx \
-    pretyping/termops.cmx lib/util.cmx toplevel/vernacinterp.cmx \
-    toplevel/vernac.cmi 
 toplevel/vernacentries.cmo: parsing/ast.cmi parsing/astterm.cmi \
     toplevel/class.cmi pretyping/classops.cmi toplevel/command.cmi \
     parsing/coqast.cmi kernel/declarations.cmi library/declare.cmi \
@@ -1589,18 +1576,16 @@ toplevel/vernacinterp.cmx: parsing/ast.cmx parsing/astterm.cmx \
     kernel/names.cmx library/nametab.cmx lib/options.cmx lib/pp.cmx \
     proofs/proof_type.cmx proofs/tacinterp.cmx lib/util.cmx \
     toplevel/vernacinterp.cmi 
-contrib/correctness/pcic.cmo: parsing/ast.cmi kernel/declarations.cmi \
-    library/declare.cmi pretyping/detyping.cmi kernel/indtypes.cmi \
-    kernel/names.cmi library/nametab.cmi contrib/correctness/past.cmi \
-    contrib/correctness/pmisc.cmi pretyping/rawterm.cmi toplevel/record.cmi \
-    kernel/sign.cmi kernel/term.cmi pretyping/termops.cmi kernel/typeops.cmi \
-    lib/util.cmi contrib/correctness/pcic.cmi 
-contrib/correctness/pcic.cmx: parsing/ast.cmx kernel/declarations.cmx \
-    library/declare.cmx pretyping/detyping.cmx kernel/indtypes.cmx \
-    kernel/names.cmx library/nametab.cmx contrib/correctness/past.cmi \
-    contrib/correctness/pmisc.cmx pretyping/rawterm.cmx toplevel/record.cmx \
-    kernel/sign.cmx kernel/term.cmx pretyping/termops.cmx kernel/typeops.cmx \
-    lib/util.cmx contrib/correctness/pcic.cmi 
+toplevel/vernac.cmo: parsing/ast.cmi parsing/coqast.cmi library/lib.cmi \
+    library/library.cmi library/nameops.cmi kernel/names.cmi lib/options.cmi \
+    parsing/pcoq.cmi lib/pp.cmi library/states.cmi lib/system.cmi \
+    pretyping/termops.cmi lib/util.cmi toplevel/vernacinterp.cmi \
+    toplevel/vernac.cmi 
+toplevel/vernac.cmx: parsing/ast.cmx parsing/coqast.cmx library/lib.cmx \
+    library/library.cmx library/nameops.cmx kernel/names.cmx lib/options.cmx \
+    parsing/pcoq.cmx lib/pp.cmx library/states.cmx lib/system.cmx \
+    pretyping/termops.cmx lib/util.cmx toplevel/vernacinterp.cmx \
+    toplevel/vernac.cmi 
 contrib/correctness/pcicenv.cmo: library/global.cmi kernel/names.cmi \
     contrib/correctness/past.cmi contrib/correctness/penv.cmi \
     contrib/correctness/pmisc.cmi contrib/correctness/pmonad.cmi \
@@ -1613,6 +1598,20 @@ contrib/correctness/pcicenv.cmx: library/global.cmx kernel/names.cmx \
     contrib/correctness/prename.cmx contrib/correctness/ptype.cmi \
     contrib/correctness/putil.cmx kernel/sign.cmx kernel/term.cmx \
     kernel/univ.cmx contrib/correctness/pcicenv.cmi 
+contrib/correctness/pcic.cmo: parsing/ast.cmi kernel/declarations.cmi \
+    library/declare.cmi pretyping/detyping.cmi library/global.cmi \
+    kernel/indtypes.cmi kernel/names.cmi library/nametab.cmi \
+    contrib/correctness/past.cmi contrib/correctness/pmisc.cmi \
+    pretyping/rawterm.cmi toplevel/record.cmi kernel/sign.cmi kernel/term.cmi \
+    pretyping/termops.cmi kernel/typeops.cmi lib/util.cmi \
+    contrib/correctness/pcic.cmi 
+contrib/correctness/pcic.cmx: parsing/ast.cmx kernel/declarations.cmx \
+    library/declare.cmx pretyping/detyping.cmx library/global.cmx \
+    kernel/indtypes.cmx kernel/names.cmx library/nametab.cmx \
+    contrib/correctness/past.cmi contrib/correctness/pmisc.cmx \
+    pretyping/rawterm.cmx toplevel/record.cmx kernel/sign.cmx kernel/term.cmx \
+    pretyping/termops.cmx kernel/typeops.cmx lib/util.cmx \
+    contrib/correctness/pcic.cmi 
 contrib/correctness/pdb.cmo: library/declare.cmi library/global.cmi \
     kernel/names.cmi library/nametab.cmi contrib/correctness/past.cmi \
     contrib/correctness/peffect.cmi contrib/correctness/penv.cmi \
@@ -1893,12 +1892,12 @@ contrib/extraction/mlutil.cmx: kernel/declarations.cmx \
     contrib/extraction/mlutil.cmi 
 contrib/extraction/ocaml.cmo: contrib/extraction/miniml.cmi \
     contrib/extraction/mlutil.cmi library/nameops.cmi kernel/names.cmi \
-    library/nametab.cmi lib/options.cmi lib/pp.cmi parsing/printer.cmi \
+    library/nametab.cmi lib/options.cmi lib/pp.cmi \
     contrib/extraction/table.cmi kernel/term.cmi lib/util.cmi \
     contrib/extraction/ocaml.cmi 
 contrib/extraction/ocaml.cmx: contrib/extraction/miniml.cmi \
     contrib/extraction/mlutil.cmx library/nameops.cmx kernel/names.cmx \
-    library/nametab.cmx lib/options.cmx lib/pp.cmx parsing/printer.cmx \
+    library/nametab.cmx lib/options.cmx lib/pp.cmx \
     contrib/extraction/table.cmx kernel/term.cmx lib/util.cmx \
     contrib/extraction/ocaml.cmi 
 contrib/extraction/table.cmo: kernel/declarations.cmi library/global.cmi \
@@ -2085,6 +2084,14 @@ contrib/interface/pbp.cmx: parsing/astterm.cmx parsing/coqlib.cmx \
     kernel/reduction.cmx proofs/tacinterp.cmx proofs/tacmach.cmx \
     tactics/tacticals.cmx tactics/tactics.cmx kernel/term.cmx \
     pretyping/typing.cmx lib/util.cmx contrib/interface/pbp.cmi 
+contrib/interface/showproof_ct.cmo: contrib/interface/ascent.cmi \
+    parsing/esyntax.cmi library/global.cmi toplevel/metasyntax.cmi lib/pp.cmi \
+    parsing/printer.cmi contrib/interface/translate.cmi \
+    contrib/interface/vtp.cmi contrib/interface/xlate.cmi 
+contrib/interface/showproof_ct.cmx: contrib/interface/ascent.cmi \
+    parsing/esyntax.cmx library/global.cmx toplevel/metasyntax.cmx lib/pp.cmx \
+    parsing/printer.cmx contrib/interface/translate.cmx \
+    contrib/interface/vtp.cmx contrib/interface/xlate.cmx 
 contrib/interface/showproof.cmo: parsing/ast.cmi parsing/astterm.cmi \
     proofs/clenv.cmi parsing/coqast.cmi kernel/declarations.cmi \
     kernel/environ.cmi pretyping/evd.cmi library/global.cmi \
@@ -2105,14 +2112,6 @@ contrib/interface/showproof.cmx: parsing/ast.cmx parsing/astterm.cmx \
     kernel/term.cmx parsing/termast.cmx pretyping/termops.cmx \
     contrib/interface/translate.cmx pretyping/typing.cmx lib/util.cmx \
     toplevel/vernacinterp.cmx contrib/interface/showproof.cmi 
-contrib/interface/showproof_ct.cmo: contrib/interface/ascent.cmi \
-    parsing/esyntax.cmi library/global.cmi toplevel/metasyntax.cmi lib/pp.cmi \
-    parsing/printer.cmi contrib/interface/translate.cmi \
-    contrib/interface/vtp.cmi contrib/interface/xlate.cmi 
-contrib/interface/showproof_ct.cmx: contrib/interface/ascent.cmi \
-    parsing/esyntax.cmx library/global.cmx toplevel/metasyntax.cmx lib/pp.cmx \
-    parsing/printer.cmx contrib/interface/translate.cmx \
-    contrib/interface/vtp.cmx contrib/interface/xlate.cmx 
 contrib/interface/translate.cmo: contrib/interface/ascent.cmi parsing/ast.cmi \
     contrib/interface/ctast.cmo kernel/environ.cmi pretyping/evarutil.cmi \
     pretyping/evd.cmi library/libobject.cmi library/library.cmi \
@@ -2209,8 +2208,6 @@ contrib/romega/refl_omega.cmx: parsing/ast.cmx tactics/auto.cmx \
     parsing/printer.cmx proofs/proof_type.cmx kernel/reduction.cmx \
     kernel/sign.cmx proofs/tacmach.cmx tactics/tacticals.cmx \
     tactics/tactics.cmx kernel/term.cmx lib/util.cmx 
-contrib/xml/xml.cmo: contrib/xml/xml.cmi 
-contrib/xml/xml.cmx: contrib/xml/xml.cmi 
 contrib/xml/xmlcommand.cmo: kernel/declarations.cmi library/declare.cmi \
     kernel/environ.cmi pretyping/evd.cmi library/global.cmi library/lib.cmi \
     library/libobject.cmi library/library.cmi library/nameops.cmi \
@@ -2231,6 +2228,8 @@ contrib/xml/xmlentries.cmo: lib/util.cmi toplevel/vernacinterp.cmi \
     contrib/xml/xmlcommand.cmi 
 contrib/xml/xmlentries.cmx: lib/util.cmx toplevel/vernacinterp.cmx \
     contrib/xml/xmlcommand.cmx 
+contrib/xml/xml.cmo: contrib/xml/xml.cmi 
+contrib/xml/xml.cmx: contrib/xml/xml.cmi 
 tactics/tauto.cmo: parsing/grammar.cma kernel/names.cmo parsing/ast.cmo parsing/g_tactic.cmo parsing/g_ltac.cmo parsing/g_constr.cmo
 contrib/correctness/psyntax.cmo: parsing/grammar.cma
 contrib/field/field.cmo: parsing/grammar.cma kernel/names.cmo parsing/ast.cmo parsing/g_tactic.cmo parsing/g_ltac.cmo parsing/g_constr.cmo
diff --git a/kernel/term.mli b/kernel/term.mli
index b676376d3..00f835e0d 100644
--- a/kernel/term.mli
+++ b/kernel/term.mli
@@ -474,6 +474,12 @@ val map_constr : (constr -> constr) -> constr -> constr
 val map_constr_with_binders :
   ('a -> 'a) -> ('a -> constr -> constr) -> 'a -> constr -> constr
 
+(* [iter_constr f c] iters [f] on the immediate subterms of [c]; it is
+   not recursive and the order with which subterms are processed is
+   not specified *)
+
+val iter_constr : (constr -> unit) -> constr -> unit
+
 (* [iter_constr_with_binders g f n c] iters [f n] on the immediate
    subterms of [c]; it carries an extra data [n] (typically a lift
    index) which is processed by [g] (which typically add 1 to [n]) at
diff --git a/parsing/printer.ml b/parsing/printer.ml
index dcabd954c..af0bcf1b2 100644
--- a/parsing/printer.ml
+++ b/parsing/printer.ml
@@ -91,14 +91,14 @@ let gentermpr_core at_top env t =
 
 let prterm_env_at_top env = gentermpr_core true env
 let prterm_env env = gentermpr_core false env
-let prterm = prterm_env empty_env
+let prterm = prterm_env (Global.env())
 
 let prtype_env env typ = prterm_env env typ
-let prtype = prtype_env empty_env
+let prtype = prtype_env (Global.env())
 
 let prjudge_env env j =
   (prterm_env env j.uj_val, prterm_env env j.uj_type)
-let prjudge = prjudge_env empty_env
+let prjudge = prjudge_env (Global.env())
 
 let fprterm_env a =
   warning "Fw printing not implemented, use CCI printing 1"; prterm_env a
diff --git a/pretyping/detyping.ml b/pretyping/detyping.ml
index 5300f1f9b..6d12257b3 100644
--- a/pretyping/detyping.ml
+++ b/pretyping/detyping.ml
@@ -273,11 +273,11 @@ and detype_fix tenv avoid env fixkind (names,tys,bodies) =
 
 and detype_eqn tenv avoid env constr construct_nargs branch =
   let make_pat x avoid env b ids =
-    if not (force_wildcard ()) or (dependent (mkRel 1) b) then
+    if force_wildcard () & noccurn 1 b then
+      PatVar (dummy_loc,Anonymous),avoid,(add_name Anonymous env),ids
+    else 
       let id = next_name_away_with_default "x" x avoid in
       PatVar (dummy_loc,Name id),id::avoid,(add_name (Name id) env),id::ids
-    else 
-      PatVar (dummy_loc,Anonymous),avoid,(add_name Anonymous env),ids
   in
   let rec buildrec ids patlist avoid env n b =
     if n=0 then
diff --git a/pretyping/evarutil.ml b/pretyping/evarutil.ml
index a53ecf535..4ccf4817c 100644
--- a/pretyping/evarutil.ml
+++ b/pretyping/evarutil.ml
@@ -71,6 +71,7 @@ let whd_castappevar_stack sigma c =
 	  whrec (existential_value sigma (ev,args), l)
       | Cast (c,_) -> whrec (c, l)
       | App (f,args) -> whrec (f, Array.fold_right (fun a l -> a::l) args l)
+      | LetIn (_,v,_,b) -> whrec (subst1 v b, l)
       | _ -> s
   in 
   whrec (c, [])
diff --git a/pretyping/reductionops.mli b/pretyping/reductionops.mli
index a1291284f..c078e1db4 100644
--- a/pretyping/reductionops.mli
+++ b/pretyping/reductionops.mli
@@ -200,4 +200,3 @@ val instance : (int * constr) list -> constr -> constr
 val hnf : env -> 'a evar_map -> constr -> constr * constr list
 i*)
 val apprec :  state_reduction_function
-
diff --git a/pretyping/termops.ml b/pretyping/termops.ml
index 790abaa43..8958d1f58 100644
--- a/pretyping/termops.ml
+++ b/pretyping/termops.ml
@@ -125,6 +125,18 @@ let it_mkNamedLambda_or_LetIn = it_named_context_quantifier mkNamedLambda_or_Let
 
 (* *)
 
+(* strips head casts and flattens head applications *)
+let rec strip_head_cast c = match kind_of_term c with
+  | App (f,cl) -> 
+      let rec collapse_rec f cl2 = match kind_of_term f with
+	| App (g,cl1) -> collapse_rec g (Array.append cl1 cl2)
+	| Cast (c,_) -> collapse_rec c cl2
+	| _ -> if cl2 = [||] then f else mkApp (f,cl2)
+      in 
+      collapse_rec f cl
+  | Cast (c,t) -> strip_head_cast c
+  | _ -> c
+
 (* [map_constr_with_named_binders g f l c] maps [f l] on the immediate
    subterms of [c]; it carries an extra data [l] (typically a name
    list) which is processed by [g na] (which typically cons [na] to
@@ -180,26 +192,41 @@ let array_map_left_pair f a g b =
     r, s
   end
 
+let fold_rec_types g (lna,typarray,_) e =
+  let ctxt =
+    array_map2_i
+      (fun i na t -> (na, None, type_app (lift i) t)) lna typarray in
+  Array.fold_left
+    (fun e assum -> g assum e) e ctxt
+
+
 let map_constr_with_binders_left_to_right g f l c = match kind_of_term c with
   | (Rel _ | Meta _ | Var _   | Sort _ | Const _ | Ind _
     | Construct _) -> c
   | Cast (c,t) -> let c' = f l c in mkCast (c', f l t)
-  | Prod (na,t,c) -> let t' = f l t in mkProd (na, t', f (g l) c)
-  | Lambda (na,t,c) -> let t' = f l t in mkLambda (na, t', f (g l) c)
+  | Prod (na,t,c) ->
+      let t' = f l t in
+      mkProd (na, t', f (g (na,None,t) l) c)
+  | Lambda (na,t,c) ->
+      let t' = f l t in
+      mkLambda (na, t', f (g (na,None,t) l) c)
   | LetIn (na,b,t,c) ->
-      let b' = f l b in let t' = f l t in mkLetIn (na, b', t', f (g l) c)
+      let b' = f l b in
+      let t' = f l t in
+      let c' = f (g (na,Some b,t) l) c in
+      mkLetIn (na, b', t', c')
   | App (c,al) -> 
       let c' = f l c in mkApp (c', array_map_left (f l) al)
   | Evar (e,al) -> mkEvar (e, array_map_left (f l) al)
   | Case (ci,p,c,bl) ->
       let p' = f l p in let c' = f l c in
       mkCase (ci, p', c', array_map_left (f l) bl)
-  | Fix (ln,(lna,tl,bl)) ->
-      let l' = iterate g (Array.length tl) l in
+  | Fix (ln,(lna,tl,bl as fx)) ->
+      let l' = fold_rec_types g fx l in
       let (tl',bl') = array_map_left_pair (f l) tl (f l') bl in
       mkFix (ln,(lna,tl',bl'))
-  | CoFix(ln,(lna,tl,bl)) ->
-      let l' = iterate g (Array.length tl) l in
+  | CoFix(ln,(lna,tl,bl as fx)) ->
+      let l' = fold_rec_types g fx l in
       let (tl',bl') = array_map_left_pair (f l) tl (f l') bl in
       mkCoFix (ln,(lna,tl',bl'))
 
@@ -223,24 +250,15 @@ let map_constr_with_full_binders g f l c = match kind_of_term c with
         array_fold_left2 (fun l na t -> g (na,None,t) l) l lna tl in
       mkCoFix (ln,(lna,Array.map (f l) tl,Array.map (f l') bl))
 
-  
-(* [iter_constr f c] iters [f] on the immediate subterms of [c]; it is
-   not recursive and the order with which subterms are processed is
-   not specified *)
-
-let iter_constr f c = match kind_of_term c with
-  | (Rel _ | Meta _ | Var _   | Sort _ | Const _ | Ind _ | Construct _) -> ()
-  | Cast (c,t) -> f c; f t
-  | Prod (_,t,c) -> f t; f c
-  | Lambda (_,t,c) -> f t; f c
-  | LetIn (_,b,t,c) -> f b; f t; f c
-  | App (c,l) -> f c; Array.iter f l
-  | Evar (_,l) -> Array.iter f l
-  | Case (_,p,c,bl) -> f p; f c; Array.iter f bl
-  | Fix (_,(_,tl,bl)) -> Array.iter f tl; Array.iter f bl
-  | CoFix (_,(_,tl,bl)) -> Array.iter f tl; Array.iter f bl
-
- 
+
+(* Equality modulo let reduction *)
+let rec zeta_eq_constr m n = 
+  (m==n) or
+  match kind_of_term m, kind_of_term n with
+    | LetIn(_,v1,_,b1),_ -> zeta_eq_constr (subst1 v1 b1) n
+    | _,LetIn(_,v2,_,b2) -> zeta_eq_constr m (subst1 v2 b2)
+    | _ -> compare_constr zeta_eq_constr m n
+
 (***************************)
 (* occurs check functions  *)                         
 (***************************)
@@ -291,55 +309,75 @@ let occur_var_in_decl env hyp (_,c,typ) =
         occur_var env hyp (body_of_type typ) ||
         occur_var env hyp body
 
+(* returns the list of free debruijn indices in a term *)
+
+let free_rels m = 
+  let rec frec depth acc c = match kind_of_term c with
+    | Rel n       -> if n >= depth then Intset.add (n-depth+1) acc else acc
+    | _ -> fold_constr_with_binders succ frec depth acc c
+  in 
+  frec 1 Intset.empty m
+
+
 (* (dependent M N) is true iff M is eq_term with a subterm of N 
    M is appropriately lifted through abstractions of N *)
 
 let dependent m t =
   let rec deprec m t =
-    if (eq_constr m t) then
+    if zeta_eq_constr m t then
       raise Occur
     else
       iter_constr_with_binders (lift 1) deprec m t
   in 
   try deprec m t; false with Occur -> true
 
-(* returns the list of free debruijn indices in a term *)
-
-let free_rels m = 
-  let rec frec depth acc c = match kind_of_term c with
-    | Rel n       -> if n >= depth then Intset.add (n-depth+1) acc else acc
-    | _ -> fold_constr_with_binders succ frec depth acc c
-  in 
-  frec 1 Intset.empty m
-
-
 (***************************)
 (*  substitution functions *)                         
 (***************************)
 
+(* Equality modulo let reduction *)
+let rec whd_rel hyps c =
+  match kind_of_term c with
+      Rel i ->
+        (try
+          (match Sign.lookup_rel i hyps with
+              (_,Some v,_) -> whd_rel hyps (lift i v)
+            | _ -> c)
+         with Not_found -> c)
+    | _ -> c
+
+(* Expand de Bruijn indices bound to a value *)
+let rec nf_rel hyps c =
+  map_constr_with_full_binders Sign.add_rel_decl nf_rel hyps (whd_rel hyps c)
+
+(* [m] is not evaluated because it is called only with terms for [m] which
+   have been lifted of the length of [hyps], hence [nf_rel] would have no
+   effect. *)
+let compare_zeta hyps m n = zeta_eq_constr m (nf_rel hyps n)
+
 (* First utilities for avoiding telescope computation for subst_term *)
 
-let prefix_application (k,c) (t : constr) = 
+let prefix_application eq_fun (e,k,c) (t : constr) = 
   let c' = collapse_appl c and t' = collapse_appl t in
   match kind_of_term c', kind_of_term t' with
     | App (f1,cl1), App (f2,cl2) ->
 	let l1 = Array.length cl1
 	and l2 = Array.length cl2 in
 	if l1 <= l2
-	   && eq_constr c' (mkApp (f2, Array.sub cl2 0 l1)) then
+	   && eq_fun e c' (mkApp (f2, Array.sub cl2 0 l1)) then
 	  Some (mkApp (mkRel k, Array.sub cl2 l1 (l2 - l1)))
 	else 
 	  None
     | _ -> None
 
-let my_prefix_application (k,c) (by_c : constr) (t : constr) = 
+let my_prefix_application eq_fun (e,k,c) (by_c : constr) (t : constr) = 
   let c' = collapse_appl c and t' = collapse_appl t in
   match kind_of_term c', kind_of_term t' with
     | App (f1,cl1), App (f2,cl2) ->
 	let l1 = Array.length cl1
 	and l2 = Array.length cl2 in
 	if l1 <= l2
-	   && eq_constr c' (mkApp (f2, Array.sub cl2 0 l1)) then
+	   && eq_fun e c' (mkApp (f2, Array.sub cl2 0 l1)) then
 	  Some (mkApp ((lift k by_c), Array.sub cl2 l1 (l2 - l1)))
 	else 
 	  None
@@ -351,18 +389,17 @@ let my_prefix_application (k,c) (by_c : constr) (t : constr) =
 (*i Bizarre : si on cherche un sous terme clos, pourquoi le lifter ? i*)
 
 let subst_term_gen eq_fun c t = 
-  let rec substrec (k,c as kc) t =
-    match prefix_application kc t with
+  let rec substrec (e,k,c as kc) t =
+    match prefix_application eq_fun kc t with
       | Some x -> x
       | None ->
-    (if eq_fun t c then mkRel k else match kind_of_term t with
-       | Const _ | Ind _ | Construct _ -> t
-       | _ ->
-	   map_constr_with_binders
-	     (fun (k,c) -> (k+1,lift 1 c))
-	     substrec kc t)
+    (if eq_fun e c t then mkRel k
+     else
+       map_constr_with_full_binders
+         (fun d (e,k,c) -> (Sign.add_rel_decl d e,k+1,lift 1 c))
+         substrec kc t)
   in 
-  substrec (1,c) t
+  substrec (empty_rel_context,1,c) t
 
 (* Recognizing occurrences of a given (closed) subterm in a term :
    [replace_term c1 c2 t] substitutes [c2] for all occurrences of (closed)
@@ -370,73 +407,26 @@ let subst_term_gen eq_fun c t =
 (*i Meme remarque : a priori [c] n'est pas forcement clos i*)
 
 let replace_term_gen eq_fun c by_c in_t = 
-  let rec substrec (k,c as kc) t =
-    match my_prefix_application kc by_c t with
+  let rec substrec (e,k,c as kc) t =
+    match my_prefix_application eq_fun kc by_c t with
       | Some x -> x
       | None ->
-    (if eq_fun t c then (lift k by_c) else match kind_of_term t with
-       | Const _ | Ind _ | Construct _ -> t
-       | _ ->
-	   map_constr_with_binders
-	     (fun (k,c) -> (k+1,lift 1 c))
-	     substrec kc t)
+    (if eq_fun e c t then (lift k by_c) else
+      map_constr_with_full_binders
+	(fun d (e,k,c) -> (Sign.add_rel_decl d e,k+1,lift 1 c))
+	substrec kc t)
   in 
-  substrec (0,c) in_t
+  substrec (empty_rel_context,0,c) in_t
 
-let subst_term = subst_term_gen eq_constr
+let subst_term = subst_term_gen (fun _ -> eq_constr)
 
-let replace_term = replace_term_gen eq_constr
+let replace_term = replace_term_gen (fun _ -> eq_constr)
 
 let rec subst_meta bl c = 
   match kind_of_term c with
     | Meta i -> (try List.assoc i bl with Not_found -> c)
     | _ -> map_constr (subst_meta bl) c
 
-(* strips head casts and flattens head applications *)
-let rec strip_head_cast c = match kind_of_term c with
-  | App (f,cl) -> 
-      let rec collapse_rec f cl2 = match kind_of_term f with
-	| App (g,cl1) -> collapse_rec g (Array.append cl1 cl2)
-	| Cast (c,_) -> collapse_rec c cl2
-	| _ -> if cl2 = [||] then f else mkApp (f,cl2)
-      in 
-      collapse_rec f cl
-  | Cast (c,t) -> strip_head_cast c
-  | _ -> c
-
-(* On reduit une serie d'eta-redex de tete ou rien du tout  *)
-(* [x1:c1;...;xn:cn]@(f;a1...an;x1;...;xn) --> @(f;a1...an) *)
-(* Remplace 2 versions précédentes buggées                  *)
-
-let rec eta_reduce_head c =
-  match kind_of_term c with
-    | Lambda (_,c1,c') ->
-	(match kind_of_term (eta_reduce_head c') with
-           | App (f,cl) ->
-               let lastn = (Array.length cl) - 1 in 
-               if lastn < 1 then anomaly "application without arguments"
-               else
-                 (match kind_of_term cl.(lastn) with
-                    | Rel 1 ->
-			let c' =
-                          if lastn = 1 then f
-			  else mkApp (f, Array.sub cl 0 lastn)
-			in
-			if not (dependent (mkRel 1) c')
-                        then lift (-1) c'
-                        else c
-                    | _   -> c)
-           | _ -> c)
-    | _ -> c
-
-(* alpha-eta conversion : ignore print names and casts *)
-let eta_eq_constr =
-  let rec aux t1 t2 =
-    let t1 = eta_reduce_head (strip_head_cast t1)
-    and t2 = eta_reduce_head (strip_head_cast t2) in
-    t1=t2 or compare_constr aux t1 t2
-  in aux
-
 (* Substitute only a list of locations locs, the empty list is
    interpreted as substitute all, if 0 is in the list then no
    substitution is done. The list may contain only negative occurrences
@@ -450,10 +440,10 @@ let subst_term_occ_gen locs occ c t =
   if except & (List.exists (fun n -> n>=0) locs) 
   then error "mixing of positive and negative occurences"
   else
-   let rec substrec (k,c as kc) t =
+   let rec substrec (e,k,c as kc) t =
     if (not except) & (!pos > maxocc) then t
     else
-    if eq_constr t c then
+    if compare_zeta e c t then
       let r = 
 	if except then 
 	  if List.mem (- !pos) locs then t else (mkRel k)
@@ -461,18 +451,16 @@ let subst_term_occ_gen locs occ c t =
 	  if List.mem !pos locs then (mkRel k) else t
       in incr pos; r
     else
-      match kind_of_term t with
-	| Const _ | Construct _ | Ind _ -> t
-	| _ ->
-	    map_constr_with_binders_left_to_right
-	      (fun (k,c) -> (k+1,lift 1 c)) substrec kc t
+      map_constr_with_binders_left_to_right
+	(fun d (e,k,c) -> (Sign.add_rel_decl d e,k+1,lift 1 c))
+        substrec kc t
   in
-  let t' = substrec (1,c) t in
+  let t' = substrec (empty_rel_context,1,c) t in
   (!pos, t')
 
 let subst_term_occ locs c t = 
   if locs = [] then
-    subst_term c t
+    subst_term_gen compare_zeta c t
   else if List.mem 0 locs then 
     t
   else 
@@ -497,7 +485,6 @@ let subst_term_occ_decl locs c (id,bodyopt,typ as d) =
 	  (id,Some body',t')
 
 
-
 (* First character of a constr *)
 
 let first_char id =
@@ -653,6 +640,7 @@ let occur_id env nenv id0 c =
   in 
   try occur 1 c; false
   with Occur -> true
+    | Not_found -> false (* Case when a global is not in the env *)
 
 let next_name_not_occuring env name l env_names t =
   let rec next id =
@@ -663,13 +651,47 @@ let next_name_not_occuring env name l env_names t =
     | Name id   -> next id
     | Anonymous -> id_of_string "_"
 
+(* On reduit une serie d'eta-redex de tete ou rien du tout  *)
+(* [x1:c1;...;xn:cn]@(f;a1...an;x1;...;xn) --> @(f;a1...an) *)
+(* Remplace 2 versions précédentes buggées                  *)
+
+let rec eta_reduce_head c =
+  match kind_of_term c with
+    | Lambda (_,c1,c') ->
+	(match kind_of_term (eta_reduce_head c') with
+           | App (f,cl) ->
+               let lastn = (Array.length cl) - 1 in 
+               if lastn < 1 then anomaly "application without arguments"
+               else
+                 (match kind_of_term cl.(lastn) with
+                    | Rel 1 ->
+			let c' =
+                          if lastn = 1 then f
+			  else mkApp (f, Array.sub cl 0 lastn)
+			in
+			if noccurn 1 c'
+                        then lift (-1) c'
+                        else c
+                    | _   -> c)
+           | _ -> c)
+    | _ -> c
+
+(* alpha-eta conversion : ignore print names and casts *)
+let eta_eq_constr =
+  let rec aux t1 t2 =
+    let t1 = eta_reduce_head (strip_head_cast t1)
+    and t2 = eta_reduce_head (strip_head_cast t2) in
+    t1=t2 or compare_constr aux t1 t2
+  in aux
+
+
 (* Remark: Anonymous var may be dependent in Evar's contexts *)
 let concrete_name env l env_names n c =
-  if n = Anonymous & not (dependent (mkRel 1) c) then
+  if n = Anonymous & noccurn 1 c then
     (None,l)
   else
     let fresh_id = next_name_not_occuring env n l env_names c in
-    let idopt = if dependent (mkRel 1) c then (Some fresh_id) else None in
+    let idopt = if noccurn 1 c then None else (Some fresh_id) in
     (idopt, fresh_id::l)
 
 let concrete_let_name env l env_names n c =
@@ -681,13 +703,13 @@ let global_vars env ids = Idset.elements (global_vars_set env ids)
 let rec rename_bound_var env l c =
   match kind_of_term c with
   | Prod (Name s,c1,c2)  ->
-      if dependent (mkRel 1) c2 then
+      if noccurn 1 c2 then
+        let env' = push_rel (Name s,None,c1) env in
+	mkProd (Name s, c1, rename_bound_var env' l c2)
+      else 
         let s' = next_ident_away s (global_vars env c2@l) in
         let env' = push_rel (Name s',None,c1) env in
         mkProd (Name s', c1, rename_bound_var env' (s'::l) c2)
-      else 
-        let env' = push_rel (Name s,None,c1) env in
-	mkProd (Name s, c1, rename_bound_var env' l c2)
   | Prod (Anonymous,c1,c2) ->
         let env' = push_rel (Anonymous,None,c1) env in
         mkProd (Anonymous, c1, rename_bound_var env' l c2)
diff --git a/pretyping/termops.mli b/pretyping/termops.mli
index e47570f47..ae28029c5 100644
--- a/pretyping/termops.mli
+++ b/pretyping/termops.mli
@@ -45,13 +45,16 @@ val it_mkNamedLambda_or_LetIn : init:constr -> named_context -> constr
 
 val map_constr_with_named_binders :
   (name -> 'a -> 'a) ->
-  ('a -> types -> types) -> 'a -> constr -> constr
+  ('a -> constr -> constr) -> 'a -> constr -> constr
 val map_constr_with_binders_left_to_right :
-  ('a -> 'a) -> ('a -> types -> types) -> 'a -> constr -> constr
+  (rel_declaration -> 'a -> 'a) -> 
+  ('a -> constr -> constr) ->
+    'a -> constr -> constr
 val map_constr_with_full_binders :
-  (name * types option * types -> 'a -> 'a) ->
-  ('a -> types -> types) -> 'a -> constr -> constr
-val iter_constr : (types -> unit) -> constr -> unit
+  (rel_declaration -> 'a -> 'a) ->
+  ('a -> constr -> constr) -> 'a -> constr -> constr
+
+val strip_head_cast : constr -> constr
 
 (* occur checks *)
 exception Occur
@@ -64,32 +67,29 @@ val occur_var : env -> identifier -> types -> bool
 val occur_var_in_decl :
   env ->
   identifier -> 'a * types option * types -> bool
-val dependent : constr -> constr -> bool
 val free_rels : constr -> Intset.t
 
-(* substitution *)
-val prefix_application :
-  int * constr -> constr -> constr option
-val my_prefix_application :
-  int * constr -> constr -> constr -> constr option
+(* substitution of an arbitrary large term. Uses equality modulo
+   reduction of let *)
+val dependent : constr -> constr -> bool
 val subst_term_gen :
-  (constr -> constr -> bool) ->
-  constr -> constr -> constr
+  (rel_context -> constr -> constr -> bool) -> constr -> constr -> constr
 val replace_term_gen :
-  (constr -> constr -> bool) ->
-  constr -> constr -> constr -> constr
+  (rel_context -> constr -> constr -> bool) -> constr -> constr -> constr -> constr
 val subst_term : constr -> constr -> constr
 val replace_term : constr -> constr -> constr -> constr
 val subst_meta : (int * constr) list -> constr -> constr
-val strip_head_cast : constr -> constr
-val eta_reduce_head : constr -> constr
-val eta_eq_constr : constr -> constr -> bool
 val subst_term_occ_gen :
   int list -> int -> constr -> types -> int * types
 val subst_term_occ : int list -> constr -> types -> types
 val subst_term_occ_decl :
   int list -> constr -> named_declaration -> named_declaration
 
+(* Alternative term equalities *)
+val zeta_eq_constr : constr -> constr -> bool
+val eta_reduce_head : constr -> constr
+val eta_eq_constr : constr -> constr -> bool
+
 (* finding "intuitive" names to hypotheses *)
 val first_char : identifier -> string
 val lowercase_first_char : identifier -> string
diff --git a/tactics/auto.ml b/tactics/auto.ml
index 5c1729108..9911e449f 100644
--- a/tactics/auto.ml
+++ b/tactics/auto.ml
@@ -190,7 +190,7 @@ let (inAutoHint,outAutoHint) =
 (**************************************************************************)
 
 let rec nb_hyp c = match kind_of_term c with
-  | Prod(_,_,c2) -> if dependent (mkRel 1) c2 then nb_hyp c2 else 1+(nb_hyp c2)
+  | Prod(_,_,c2) -> if noccurn 1 c2 then 1+(nb_hyp c2) else nb_hyp c2
   | _ -> 0 
 
 (* adding and removing tactics in the search table *)
diff --git a/tactics/tauto.ml4 b/tactics/tauto.ml4
index ce9f3a8c6..496369901 100644
--- a/tactics/tauto.ml4
+++ b/tactics/tauto.ml4
@@ -133,7 +133,7 @@ open Environ
 let rec reduce env sigma c =
   let c = Tacred.hnf_constr env sigma c in
   match Term.kind_of_term c with
-    | Prod (na,t,u) when not (dependent (mkRel 1) u) ->
+    | Prod (na,t,u) when noccurn 1 u ->
       mkProd (na,reduce env sigma t, reduce (push_rel (na,None,t) env) sigma u)
     | _ -> c