Hi, I know that this is probably not the correct place to ask as my question is not directly related to GHC itself, but I thought here are the people that can most likely answer this. To better understand PL papers, especially those involving System Fc and its extensions, I started to write a formal proof of type safety including alpha-equivalence. Currently I have a complete proof for System F (without coercions and data types yet). I mainly used the System Fc paper as reference, ignoring all the parts about coercions. 1. In the Fc paper, the rule `AppT` has a judgement delta as assumption, which does not exist. I assumed the `ty` judgement was meant there by looking at the arguments. Is this correct? 2. In the `Abs` rule, the type of the variable is required to be valid and of kind star by the judgement `ty`. In the `Let` rule, this assumption is missing. I tried it like that, but was not able to complete the proofs. Is such an assumption missing there or should I be able to proof it without? 3. In the Fc paper, the types and kinds of datatype declarations are added to the context with a separate judgement that interprets the datatype declarations. In the System Fc pro paper (from what I can tell) those types and kinds are assumed to be already part of the initial context. At the moment I prove progress against the empty context, so I guess I would have to relax that to an initial context that only contains types and kinds of type constants and nothing else. Is that correct? What is here the "best practice" in terms of PL research? Thank you all _______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
In the grammar figure (Fig. 1), we see that \delta is either TY or CO. Both the TY and CO judgments are included in Fig. 2. So, in effect, you're assumption is correct, but the rule covers also coercion application, as well as type application.
Lemma (Regularity). If G |e- e : s, then G |TY- s : *. (You might also need to assert that the size of the resulting derivation is strictly smaller than the input -- not sure if your application would need that to power an induction hypothesis.) With that lemma, you could essentially recreate the premise you were hoping to spot on Let.
I would encourage you to take a look also at the proof of type safety in https://richarde.dev/papers/2016/coercible-jfp/coercible-jfp.pdf. That paper is concerned with roles (which, presumably, you are not), but the proof is (to my knowledge) the most careful proof presented about System FC. Other papers since have mechanized parts of the proof, but those work with a variant of FC that is dependently typed. I hope this helps! Richard
_______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
Thank you for those answers! Back to proving again :) On 23.11.20 04:48, Richard Eisenberg
wrote:
_______________________________________________ ghc-devs mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs |
Free forum by Nabble | Edit this page |