[Agda] Rewrite rules for both Set and Prop
Jesper Cockx
Jesper at sikanda.be
Thu Jan 30 16:33:27 CET 2020
Hi Filippo,
Matching rewrite rules is done up to definitional equality, so in your
example both foo and bar should typecheck. Since bar doesn't, it seems
you've found a bug in the implementation, congratulations! It's now fixed
in the development version of Agda, see
https://github.com/agda/agda/issues/4410. Thanks for the example.
-- Jesper
On Thu, Jan 30, 2020 at 2:33 PM Filippo Sestini <
Filippo.Sestini at nottingham.ac.uk> wrote:
> Hi Jesper,
>
> The problem as I see it is that even though all elements of a Prop are
> definitionally equal, there might be some other rewrite rules defined
> elsewhere that involve elements of a Prop as arguments, in a way that they
> are only triggered when such propositional arguments are of a certain
> shape. The "canonical" example would be when defining computation rules
> that only compute on canonical forms.
>
> Let me give a quick example. Suppose we have the following
>
> postulate
> P : Prop
> p : P
> f : P -> P
>
> g : {A : Set} -> P -> A -> A
> eq : ∀{A} {x : A} -> g p x ≡ x
>
> {-# REWRITE eq #-}
>
> module _ {A : Set} {x : A} {y : P} where
>
> foo : g p x ≡ x
> foo = refl
>
> bar : g (f y) x ≡ x
> bar = refl
>
> Here, "foo" typechecks just fine, because the arguments of "g" in "g p x"
> match the rewrite rule "eq". However, "bar" doesn't because although "f y"
> is indeed definitionally equal to "p", it is still syntactically different
> from "p" so the previous rewrite rule doesn't get triggered. Of course Agda
> has no way to figure out that "p" is what is needed here, but I though that
> if we had a way to add the following rule
>
> postulate
> f-eq : {x : P} -> f x ≡ p
>
> then the "bar" example above would work. Any thoughts?
>
> Cheers
> --
> Filippo
>
> On 1/30/20, 12:08 PM, "Jesper Cockx" <Jesper at sikanda.be> wrote:
>
> Hi Filippo,
>
>
> You're correct that you currently cannot do this, as there's no way to
> define types that are polymorphic over both Set and Prop (
> https://github.com/agda/agda/issues/3328), and you can only have one
> rewriting relation. However, I don't understand why you would want
> rewrite rules to rewrite elements of a Prop, since they are anyway all
> equal?
>
>
> -- Jesper
>
>
>
> On Thu, Jan 30, 2020 at 12:31 PM Filippo Sestini <
> Filippo.Sestini at nottingham.ac.uk> wrote:
>
>
> Hi all,
>
> I'm trying to encode an equality type in Agda using rewrite rules.
> I want the type to be a strict proposition, so I value it in the Prop
> universe.
> However, this also means that among the equations that I want to
> encode as rewrite rules, some will end up being between elements of a Set
> (for example, when rewriting the eq type itself) and some will be between
> elements of a Prop (for example, the elements
> of the identity type itself).
>
> I'm struggling to find a way to do this with Agda's rewriting system.
> As far as I know there is no way to define an identity type that works for
> both types in Set and in Prop. One could define two different identity
> types for each, but unfortunately Agda doesn't
> seem to allow declaring two different relations for BUILTIN REWRITE.
>
> Am I missing something here? Does anybody know a way out of this?
>
> Thank you
> --
> Filippo Sestini
>
>
>
>
>
> This message and any attachment are intended solely for the addressee
> and may contain confidential information. If you have received this
> message in error, please contact the sender and delete the email and
> attachment.
>
> Any views or opinions expressed by the author of this email do not
> necessarily reflect the views of the University of Nottingham. Email
> communications with the University of Nottingham may be monitored
> where permitted by law.
>
>
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>
>
>
>
>
>
>
>
> This message and any attachment are intended solely for the addressee
> and may contain confidential information. If you have received this
> message in error, please contact the sender and delete the email and
> attachment.
>
> Any views or opinions expressed by the author of this email do not
> necessarily reflect the views of the University of Nottingham. Email
> communications with the University of Nottingham may be monitored
> where permitted by law.
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20200130/1c67fcbe/attachment.html>
More information about the Agda
mailing list