Documenting EConstr for developpers.

1 files changed, 129 insertions, 0 deletions

diff --git a/dev/doc/econstr.md b/dev/doc/econstr.md
new file mode 100644
index 000000000..bb17e8fb6
--- /dev/null
+++ b/dev/doc/econstr.md
@@ -0,0 +1,129 @@
+# Evar-insensitive terms (EConstr)
+
+Evar-insensitive terms were introduced in 8.7, following
+[CEP #10](https://github.com/coq/ceps/blob/master/text/010-econstr.md). We will
+not recap the motivations in this document and rather summarize the code changes
+to perform.
+
+## Overview
+
+The essential datastructures are defined in
+[the `EConstr` module](/engine/eConstr.mli) module. It defines
+the tactic counterparts of kernel data structures such as terms
+(`EConstr.constr`), universes (`EConstr.ESorts.t`) and contexts
+(`EConstr.*_context`).
+
+The main difference with kernel-side types is that observing them requires
+an evar-map at hand in order to normalize evars on the fly. The basic primitive
+to observe an `EConstr.t` is the following function:
+```
+val kind : Evd.evar_map -> t -> (t, t, ESorts.t, EInstance.t) Constr.kind_of_term
+(** Same as {!Constr.kind} except that it expands evars and normalizes
+    universes on the fly. *)
+```
+
+Essentially, each time it sees an evar which happens to be defined in the
+provided evar-map, it replaces it with the corresponding body and carries on.
+
+Due to universe unification occuring at the tactic level, the same goes for
+universe instances and sorts. See the `ESort` and `EInstance` modules in
+`EConstr`.
+
+This normalization is critical for the soundness of tactics. Before EConstr, a
+lot of bugs were lurking in the code base, a few still are (most notably in
+meta-based unification) and failure to respect the guidelines thereafter may
+result in nasal demons.
+
+## Transition path
+
+### Types
+
+As a rule of thumb, all functions living at the tactic level should manipulate
+`EConstr.t` instead of `Constr.t`, and similarly for the other data structures.
+
+To ease the transition, the `EConstr` module defines a handful of aliases to
+shadow the type names from the kernel.
+
+It is recommended to perform the following replacement in headers.
+```ocaml
+(** Kernel types. You may remove the two following opens if you want. Beware
+    that [kind_of_term] needs to be in scope if you use [EConstr.kind] so that
+    you may still need to open one of the two. *)
+open Term
+open Constr
+(** Tactic types. Open this after to shadow kernel types. *)
+open EConstr
+```
+
+Note that the `EConstr` module also redefines a `Vars` submodule.
+
+### Evar-map-passing
+
+All functions deconstructing an econstr need to take an evar-map as a parameter.
+Therefore, you need to pass one as an argument virtually everywhere.
+
+In the Coq source code, it is recommended to take the evar-map as a first
+argument called `sigma`, except if the function also takes an environment in
+which case it is passed second. Namely, the two typical instances are:
+```ocaml
+let foo sigma c = mycode
+val foo : Evd.evar_map -> EConstr.t -> Foo.t
+
+let bar env sigma c = mycode
+val bar : Environ.env -> Evd.evar_map -> EConstr.t -> Bar.t
+```
+
+The EConstr API makes the code much more sensitive to evar-maps, because a
+lot of now useless normalizations were removed. Thus one should be cautious of
+**not** dropping the evar-map when it has been updated, and should rather stick
+to a strict state-passing discipline. Unsound primitives like
+`Typing.unsafe_type_of` are also a known source of problems, so you should
+replace them with the corresponding evar-map-returning function and thread it
+properly.
+
+### Functions
+
+Many functions from `Constr` and `Term` are redefined to work on econstr in
+the `EConstr` module, so that it is often enough to perform the `open` as
+described above to replace them. Their type may differ though, because they now
+need access to an evar-map. A lot of econstr-manipulating functions are also
+defined in [`Termops`](/engine/termops.mli).
+
+Functions manipulating tactic terms and kernel terms share the same name if they
+are the equivalent one of the other. Do not hesitate to grep Coq mli files to
+find the equivalent of a function you want to port if it is neither in `EConstr`
+nor in `Termops` (this should be very rare).
+
+### Conversion
+
+Sometimes you do not have any other choice than calling kernel-side functions
+on terms, and conversely to turn a kernel term into a tactic term.
+
+There are two functions to do so.
+* `EConstr.of_constr` turns kernel terms into tactic terms. It is currently
+the physical identity, and thus O(1), but this may change in the future.
+* `EConstr.to_constr` turns tactic terms into kernel terms. It performs a
+full-blown normalization of the given term, which is O(n) and potentially
+costly.
+
+For performance reasons, avoiding to jump back and forth between kernel and
+tactic terms is recommended.
+
+There are also a few unsafe conversion functions that take advantage of the
+fact that `EConstr.t` is internally the same as `Constr.t`. Namely,
+`EConstr.Unsafe.to_constr` is the physical identity. It should **not** be used
+in typical code and is instead provided for efficiency **when you know what you
+are doing**. Either use it to reimplement low-level functions that happen to
+be insensitive externally, or use it to provide backward compatibility with
+broken code that relies on evar-sensitivity. **Do not use it because it is
+easier than stuffing evar-maps everywhere.** You've been warned.
+
+## Notes
+
+The EConstr branch fixed a lot of eisenbugs linked to lack of normalization
+everywhere, most notably in unification. It may also have introduced a few, so
+if you see a change in behaviour *that looks like a bug*, please report it.
+Obviously, unification is not specified, so it's hard to tell apart, but still.
+
+Efficiency has been affected as well. We now pay an overhead when observing a
+term, but at the same time a lot of costly upfront normalizations were removed.