[Agda] cong with wildcard

Sergei Meshveliani mechvel at botik.ru
Tue Jul 10 13:30:55 CEST 2018


Dear all,

There is a problem of unnecessary large terms in proofs in a source
program. For example, in an equality proof by EquationalReasoning of 

      begin T1  ≡⟨ cong foo1 eq1 ⟩ 
            T2  ≡⟨ cong foo2 eq2 ⟩
            T3  
            ...
      ∎

foo1, foo2 ...  often occur large terms which can be replaced with `_'.
But Agda cannot solve this.
For example, for the Nat arithmetic, the line

   (a * 1 + 1+m * n)    ≡⟨ cong (_+ (1+m * n)) (Nat0.*1 a) ⟩

means replacing  a * 1  with  a.
And from the term triple

   (a * 1 + 1+m * n)  ,  (cong (_+ _) (Nat0.*1 a)) ,
   (a + 1+m * n)

it is clear (to a human) which term  t  to substitute for `_' in order
to obtain the third term  
-- provided that this  t  is a subterm in (a * 1 + 1+m * n).

More general: the derivation is 

              E1   -- cong (op _) foo  -->
              E2

where op is an operator, and the prover needs to search in E1 all
subterms to which (op X) matches, and which substitution derives E2.
  
Does there exist a library for Agda that has tools for this? 
Can something easy be done towards such a tool?

Regards,

------
Sergei






More information about the Agda mailing list