[Agda] Problem with a simple proof
Caylee Hogg
caylee.hogg at gmail.com
Wed May 4 21:03:16 CEST 2011
Hello!
I'm a bit of an Agda newbie, so to learn it I started converting Pierce's
Software Foundations book. I hit a bit of a roadblock when I needed to prove
that an optimization preserves the semantics of a simple expression
language. I'm including the relevant code below - the problem is that while
I was able to define the optimization using the overlapping patterns, but
when trying to write the proof the fact that y in the overlapping case can't
be an (ANum zero) doesn't seem obvious to the type checker.
How should I actually finish the proof? Please feel free to critique any of
it.
Cheers,
Caylee Hogg
open import Data.Nat
data _==_ {A : Set}(x : A) : A -> Set where
refl : x == x
eq-subst : {A : Set} -> (C : A -> Set) -> (a' a'' : A) -> a' == a'' -> C a'
-> C a''
eq-subst c .a'' a'' refl p = p
eq-subst' : {A B : Set} {x x' y y' : A} (f : A -> A -> B) -> x == x' -> y ==
y' -> f x y == f x' y'
eq-subst' f refl refl = refl
data aexp : Set where
ANum : ℕ -> aexp
APlus : aexp -> aexp -> aexp
AMinus : aexp -> aexp -> aexp
AMult : aexp -> aexp -> aexp
aeval : aexp -> ℕ
aeval (ANum y) = y
aeval (APlus y y') = aeval y + aeval y'
aeval (AMinus y y') = aeval y ∸ aeval y'
aeval (AMult y y') = aeval y * aeval y'
optimize-0plus : aexp -> aexp
optimize-0plus (ANum y) = ANum y
optimize-0plus (APlus (ANum zero) y') = optimize-0plus y'
optimize-0plus (APlus y y') = APlus (optimize-0plus y) (optimize-0plus y')
optimize-0plus (AMinus y y') = AMinus (optimize-0plus y) (optimize-0plus y')
optimize-0plus (AMult y y') = AMult (optimize-0plus y) (optimize-0plus y')
optimize-0plus-sound : (e : aexp) -> aeval (optimize-0plus e) == aeval e
optimize-0plus-sound (ANum y) = refl
optimize-0plus-sound (APlus (ANum zero) y') = optimize-0plus-sound y'
optimize-0plus-sound (APlus y y') = {!!}
optimize-0plus-sound (AMinus y y') = eq-subst' _∸_ (optimize-0plus-sound y)
(optimize-0plus-sound y')
optimize-0plus-sound (AMult y y') = eq-subst' (_*_) (optimize-0plus-sound y)
(optimize-0plus-sound y')
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20110504/232c291b/attachment.html
More information about the Agda
mailing list