theorem proving - Coq can't find subterm when using rewrite tactic -

i'm trying modified proof of compile_correct first chapter of certified programming dependent types. in version, try make use of fact progdenote fold, , use weaker inductive hypothesis in proof of main lemma in priving compile_correct.

the code identical book is:

require import bool arith list. set implicit arguments.  inductive binop : set := plus | times.  inductive exp : set :=   | const : nat -> exp   | binop : binop -> exp -> exp -> exp.  definition binopdenote (b : binop) : nat -> nat -> nat :=   match b     | plus => plus     | times => mult   end.  fixpoint expdenote (e : exp) : nat :=   match e     | const n => n     | binop b e1 e2 => (binopdenote b) (expdenote e1) (expdenote e2)   end.  inductive instr : set :=   | iconst : nat -> instr   | ibinop : binop -> instr.  definition prog := list instr. definition stack := list nat.  definition instrdenote (i : instr) (s : stack) : option stack :=   match     | iconst n => (n :: s)     | ibinop b =>       match s         | arg1 :: arg2 :: s' => ((binopdenote b) arg1 arg2 :: s')         | _ => none       end   end.  fixpoint compile (e : exp) : prog :=   match e     | const n => iconst n :: nil     | binop b e1 e2 => compile e2 ++ compile e1 ++ ibinop b :: nil   end. 

then define own version of prog_denote fold on list of instructions in program:

definition bind {a b : type} (a : option a) (f : -> option b) : option b :=   match     | x => f x     | none => none   end.  definition instrdenote' (s : option stack) (i : instr) : option stack :=   bind s (instrdenote i).  definition progdenote (p : prog) (s : stack) : option stack :=   fold_left instrdenote' p (some s). 

i try prove weaker version of compile_correct book:

lemma compile_correct' : forall e s,   progdenote (compile e) s = (expdenote e :: s). induction e. intro s. unfold compile. unfold expdenote. unfold progdenote @ 1. simpl. reflexivity. intro s. unfold compile. fold compile. unfold expdenote. fold expdenote. unfold progdenote. rewrite fold_left_app. rewrite fold_left_app. unfold progdenote in ihe2. rewrite (ihe2 s). unfold progdenote in ihe1. rewrite (ihe1 (expdenote e2 :: s)). 

my proof breaks @ last line, proof state

1 subgoal b : binop e1 : exp e2 : exp ihe1 : forall s : stack,        fold_left instrdenote' (compile e1) (some s) =        (expdenote e1 :: s) ihe2 : forall s : stack,        fold_left instrdenote' (compile e2) (some s) =        (expdenote e2 :: s) s : stack ______________________________________(1/1) fold_left instrdenote' (ibinop b :: nil)   (fold_left instrdenote' (compile e1) (some (expdenote e2 :: s))) = (binopdenote b (expdenote e1) (expdenote e2) :: s) 

and error is

error: found no subterm matching "fold_left instrdenote' (compile e1)                              (some (expdenote e2 :: s))" in current goal. 

at stage in proof, doing induction on e, expression being compiled, , dealing binop constructor of exp. don't understand why getting error, because once apply ihe1 expdenote e2 :: s there no bound variables. seems usual problem applying rewrite rules doesn't work. checked term i'm trying create:

fold_left instrdenote' (ibinop b :: nil)   (some (expdenote e1 :: expdenote e2 :: s)) = (binopdenote b (expdenote e1) (expdenote e2) :: s) 

type checks.

what else can go wrong rewrite rule, when subexpression it's complaining there in goal?

edit: suggested, changed display settings in coqide equivalent of set printing all. revealed problem definition of stack had been unfolded list nat @ 1 place in goal, prevented subterm being recognized. goal printed new settings was

1 subgoal b : binop e1 : exp e2 : exp ihe1 : forall s : stack,        @eq (option stack)          (@fold_left (option stack) instr instrdenote' (compile e1)             (@some stack s)) (@some (list nat) (@cons nat (expdenote e1) s)) ihe2 : forall s : stack,        @eq (option stack)          (@fold_left (option stack) instr instrdenote' (compile e2)             (@some stack s)) (@some (list nat) (@cons nat (expdenote e2) s)) s : stack ______________________________________(1/1) @eq (option stack)   (@fold_left (option stack) instr instrdenote'      (@cons instr (ibinop b) (@nil instr))      (@fold_left (option stack) instr instrdenote' (compile e1)         (@some (list nat) (@cons nat (expdenote e2) s))))   (@some (list nat)      (@cons nat (binopdenote b (expdenote e1) (expdenote e2)) s)) 

and error was

error: found no subterm matching "@fold_left (option stack) instr instrdenote'                              (compile e1)                              (@some stack (@cons nat (expdenote e2) s))" in current goal. 

even though default display settings, subterm seems appear in goal, set printing all enabled, becomes clear the subterm not match goal because in goal, stack has been unfolded list nat. fold stack needed turn list nat stack in goal.

it seems beginner tripped combination of following:

• the unfold tactic unfolds more definitions beginner expect.

• the default display settings (in coqide in case) can hide because fold terms.

thanks arthur azevedo de amorim suggesting enabling set printing all.