Monday, October 17, 2011

Adding Equations to System F

Nick and I have a new draft out, on adding types for term-level equations to System F. Contrary to the experience of dependent types, this is not a very hairy extension -- in fact, I would not even hesitate to call it simple.

However, it does open the door to all sorts of exciting things, such as many peoples' long-standing goal of putting semantic properties of modules into the module interfaces. This is good for documentation, and also (I would hope) good for compilers --- imagine Haskell, if the Monad typeclass definition also told you (and ghc!)  all the equational rewriting that it was supposed to do.

7 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Will this hypothetical version of Haskell allow us to write machine-checkable proofs of e.g. monad laws for custom Monad instances in the language itself?

    ReplyDelete
  4. In fact, quite the opposite -- the whole point of our design is to *not* compel the use of the language itself for proofs. If you try to combine the two, you get systems of dependent types. Unfortunately, getting dependent types to play nicely with data abstraction is kind of an open reseach problem.

    So our idea is to give a language that doesn't support proving internal to the language, but does (a) support data abstraction well, and (b) gives you a clean way of shipping proof obligations to proof assistants like Coq. (After all, Coq already exists and there's no reason not to use it!)

    ReplyDelete
  5. There's a typo in the first sentence of the first paragraph of your Introduction.

    ReplyDelete
  6. Karl: that's a hilariously awful typo. :(

    ReplyDelete