[Agda] aggressive with, VFPiA

Aaron Stump aaron-stump at uiowa.edu
Wed Jan 27 19:52:24 CET 2016


Dear Agda developers,

Starting in Agda version 2.4.2.5, the abstraction performed by "with" 
has (as the CHANGELOG tells us) become more aggressive.  I am sure you 
have good reasons for this change, but are you aware that you have made 
it impossible to rewrite with the same assumption twice?  Consider this 
self-contained example:

module test where

data _≡_ {ℓ} {A : Set ℓ} (x : A) : A → Set ℓ where
   refl : x ≡ x

{-# BUILTIN EQUALITY _≡_ #-}
{-# BUILTIN REFL refl #-}

lemma : ∀ {A : Set}(f : A → A)(a : A) → f a ≡ a → f (f a) ≡ a
lemma f a p rewrite p = p

With previous versions of Agda, this would be fine.  But starting with 
2.4.2.5, this does not type check.  If we put a hole on the right-hand 
side of the sole equation for lemma, we will see this goal:

Goal: f a ≡ a
————————————————————————————————————————————————————————————
p  : a ≡ a

The "rewrite p" directive has actually been applied to rewrite the type 
of p itself, rendering it trivial and hence useless.  This is a real 
problem.  I have maybe 25 places in the Iowa Agda Library that have been 
broken by this.  I don't mind fixing them, but I think this is a major 
flaw in the new way "with" works.  One should be able to reuse 
assumptions.  For the particular example above, I actually am struggling 
to find any workaround.  How would you prove this?  Maybe inspect on 
steroids is supposed to be used?  For what I have done, usually inspect 
has been enough.  But being able to apply an assumption twice with 
rewrite seems pretty fundamental.  This is not linear logic!

There is a second issue I want to raise.  As you know (since Jesper and 
Ulf wrote me very helpful and quite detailed reviews), I am bringing 
out, with ACM Books, a textbook called "Verified Functional Programming 
in Agda" (VFPiA) this year.  The book is in the very last stages of 
proofs.  In the book, I refer readers to Agda 2.4.2.2 and IAL release 1.2:

svn co --username=guest --password=guest 
https://svn.divms.uiowa.edu/repos/clc/projects/agda/ial-releases/1.2

So, certainly the book is usable.  But this release does not check with 
Agda 2.4.2.5.  Furthermore, some of what I say in the book is 
invalidated by the fact that we cannot rewrite twice with the same 
assumption.

Of course, whether the book is successful or not is not your 
responsibility, though by reviewing it for me, Ulf and Jesper have made 
some investment in its success.  But if you want to take advantage of my 
efforts here to help spread Agda to new users, it would be really a good 
idea if releases of Agda were compatible with IAL version 1.2.  I do not 
do anything very exotic.  If there are changes to compiler pragmas, that 
is fine.  And of course, I hardly expect you to limit yourself to back 
compatibility with my library. But if you could at least consider 
whether changes you make are breaking this library (and hence, to some 
extent, breaking VFPiA), I would appreciate it, and I hope it would help 
the broader Agda community.

Best wishes,
Aaron


More information about the Agda mailing list