I am trying to write a substitution function for lambda calculus and in case of lambda abstraction (\x.e) before recursively calling substitution on e, I have to rename variables in e. How can I represent this kind of logic in Coq?
Following is a bare minimum example for which Coq gives the error that it can not guess the decreasing argument. In the simplified replace why can Coq not get that e remains of same Inductive size?
Fixpoint replace (x: nat) (y: nat) (e: exp): exp := e.
Fixpoint substitute (x: nat) (t: exp) (body: exp): exp :=
match body with
| Abs xp e => Abs 0 (substitute x t (replace x 0 e))
| _ => Unit
end.
Actual replace looks like this
Fixpoint replace (x: nat) (y: nat) (e: exp): exp :=
match e with
| Val => Val
| Var xp => if beq_nat x xp then Var y else e
| Ref f => Ref (replace x y f)
| Abs xp bd => Abs xp (replace x y bd)
| App e1 e2 => App (replace x y e1) (replace x y e2)
| Deref f => Deref (replace x y f)
| Loc l => Loc l
| Assign e1 e2 => Assign (replace x y e1) (replace x y e2)
| Unit => Unit
end.
In general, Coq will not accept recursive Fixpoints of the form f(x) = f(g(subterm of x)). This makes sense, of course, because g could be a function that increases the size of the term.
In general, a solution is to find a termination measure, other than the plain "is a subterm" which Fixpoint uses. Here, you could define a function height : exp -> nat, which is 0 for the leaf nodes and otherwise the max of subtrees. Coq then has several ways of defining terminating functions based on such a measure, e.g. Program Fixpoint and Function, or you can even manually define a Fixpoint which takes an additional argument representing a bound on the height (and returns a dummy value if that argument ever goes to 0). Program Fixpoint will give you a proof obligation that the measure decreases for each recursive call, and to prove that you will need to prove a lemma that replace preserves the height.
In the particular case of substitutions, a different trick you can try is to define a function to apply multi-substitutions (maps from variables to expressions), instead of a function to substitute for a single variable. This way, in the Abs-case you can add the renaming to the substitution to be applied rather than doing it directly, and then the function is structurally recursive.