coq-club AT inria.fr
Subject: The Coq mailing list
List archive
- From: Agnishom Chattopadhyay <agnishom AT cmi.ac.in>
- To: Li-yao Xia <lysxia AT gmail.com>, coq-club AT inria.fr
- Subject: Re: [Coq-Club] How do I convince Coq that my recursion is guarded?
- Date: Sat, 8 Feb 2020 11:57:04 -0600
- Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=agnishom AT cmi.ac.in; spf=Pass smtp.mailfrom=agnishom AT cmi.ac.in; spf=None smtp.helo=postmaster AT mail.cmi.ac.in
- Ironport-phdr: 9a23:c6/pXRLb9KD11pykT9mcpTZWNBhigK39O0sv0rFitYgeKvrxwZ3uMQTl6Ol3ixeRBMOHsq4C1rWd6viwESxYuNDd6StEKMQNHzY+yuwu1zQ6B8CEDUCpZNXLVAcdWPp4aVl+4nugOlJUEsutL3fbo3m18CJAUk6nbVk9Kev6AJPdgNqq3O6u5ZLTfx9IhD2gar9uMRm6twrcutQZjId4Kqs8yBTFrmZUd+lV2GhkIU6fkwvm6sq/4ZJu/T5ct+49+8JFTK73Y7k2QbtEATo8Lms7/tfrtR7NTQuO4nsTTGAbmQdWDgbG8R/3QI7/vjP1ueRh1iaaO9b2Ta0vVjS586hrUh7ohzwZODM/7Wral9Z/jKNfoBKmuhx/34vZa5ybOfZiYq/Qe84RSGxcVchTSiNBGJuxYIQBD+UDPehWoYrzqUYQoxSiHgSjHv/jxyVSi3PqwaE30eIsGhzG0gw6GNIOtWzZocn6NKcUUOC116nIzTLGb/hLxzr96JLHcgw9ofGLRbJ/a9feyUkvFgzfjlSbtIvoMCma1uQLsmib9OpgVeWqi2M8tw5xpzmvyt02hYbVnI4Vy1bE+Dx/zY0oJtO4UFZ2bcO6HJZerS2XNoV7Ttk8T210tis20KMKtYOlcCQS1pgr2xrSZ+aEfoWI+B7vSeecLDZiiH9qdr+ygQu5/1K6xe3mTMa01U5HripbndnIsXAAzxnT5dKGSvt55EuuxTOP1wHJ5u5ePU84j6vbK5g5zr4xkJocr1jDEzfrlEnogqKabEQp9+ay5+j5frnrqIWQO5Fphg3gKqgun9awAeU8MggARWib/uG82aX58k32RrVKj+Y2kqnesJDfPskUuqu5Aw5P3ok59xmzFTam0NIAkXkdMF1FYA6Hj5TuO1zWPP/4Cu6/j02wnzdv2vDJJabsAo7NL3jGiLfuZ6xx609ayAopzNBQ/YhYCr8bIKG7ZkikkN2dHxY+ezy1yq6zDMRmxoIXcW2KC66ddqjVtAnMrukoOqyHYJIfkDf7MfksofD03lEjnlpIVKav3IAXb3XwNfRvP1meeXPggsYIAC9etwU4Tffqj1iqWjtSIX+5GaM6sGJoQLm6BJvOE9j+yIeK2z22S8UPOzJ2T2uUGHKtTL2qHvcBbCXLfJ1kmz0AE7OkSsko3levsl2ikuY1Hq/v4iQd8Knb+p1t/eSKzEM58D0yBs/b0mffFzglzFNNfCc/2eVEmWI4z16C1aZihPkBTI5Y4vIPWwx8NJiOluE=
Thank you, Li-Yao!
The second case was a small typo indeed.
In the first case, you correctly pointed out that mNext is not a constructor but a projection. However, is there a way to rewrite the definition of MonDelayWith with the constructor Build_Monitor (which was automatically generated) and let cofix so that MonDelayWith is guarded and my attempted definition of MonJustBefore works?
I had never heard of one sized types or clocked type theory. Thanks for the pointers!
--Agnishom
On Sat, Feb 8, 2020 at 10:59 AM Li-yao Xia <lysxia AT gmail.com> wrote:
Hi Agnishom,
> but that does not seem to work. The definition intuitively seems to make
> sense. Also, if we unroll the definition of MonJustBefore, it appears
> (to me) that the recursive call is guarded within the mNext constructor
> in MonDelayWith. How do I make Coq believe this?
mNext is not a constructor, it's a projection (a destructor). That's why
this definition is not guarded. It is productive, but the guardedness
checker is too restrictive for one to encode a proof of that fact. You
have to rewrite the definition altogether to make it guarded.
Your second attempt is basically correct. It's a small mistake: you
wrote a period after the type instead of ":=". That's why you then enter
proof mode. That period separates the CoFixpoint command from the
following record "{| ... |}", which seems to get recognized as a tactic
that does nothing.
(* You wrote *)
CoFixpoint MonSometime {A: Type} (mon: Monitor A) : Monitor A.
(* but it should be *)
CoFixpoint MonSometime {A: Type} (mon: Monitor A) : Monitor A :=
Your initial attempt is actually a common example of the limitations of
the "guardedness" criterion. Other implementations of coinductive types
based one sized types or clocked type theory make it possible to
formalize the first definition directly.
Regards,
Li-yao
- [Coq-Club] How do I convince Coq that my recursion is guarded?, Agnishom Chattopadhyay, 02/08/2020
- Re: [Coq-Club] How do I convince Coq that my recursion is guarded?, Li-yao Xia, 02/08/2020
- Re: [Coq-Club] How do I convince Coq that my recursion is guarded?, Agnishom Chattopadhyay, 02/08/2020
- Re: [Coq-Club] How do I convince Coq that my recursion is guarded?, Li-yao Xia, 02/08/2020
- Re: [Coq-Club] How do I convince Coq that my recursion is guarded?, Agnishom Chattopadhyay, 02/08/2020
- Re: [Coq-Club] How do I convince Coq that my recursion is guarded?, Li-yao Xia, 02/08/2020
Archive powered by MHonArc 2.6.18.