RE: MPTCs and functional dependencies
I'm confident that it is premature to standardise functional dependencies at this stage, very useful though they are. If you doubt me, read the JFP journal submission that Martin Sulzmann and Peter Stuckey and I have been working on. http://research.microsoft.com/%7Esimonpj/papers/fd-chr Fundeps are very, very tricky. My own view is that associated types are a more promising way forward at the programming language level. They are a little less expressive than fundeps, I think, but a whole lot less tricky. But we don't have an implementation of them yet, so we can hardly standardise them! Multi-parameter type classes, yes. Functional dependencies, no. Simon | -----Original Message----- | From: haskell-prime-bounces@haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Ross Paterson | Sent: 02 February 2006 11:25 | To: haskell-prime@haskell.org | Subject: MPTCs and functional dependencies | | On Thu, Feb 02, 2006 at 11:38:07AM +0100, John Hughes wrote: | > The problem with Haskell 98 is that it *lacks* features which | > have become absolutely essential to Haskell programmers today. Those | > features are what really *need* discussion and energy spent on them. | > | > [...] | > | > Multi-parameter classes with functional dependencies | > - used everywhere... for example in monad transformers... so | > *must* be included this time | > - omitted from Haskell 98 because "the right design" wasn't clear | > - it's still unclear! Functional dependencies *in some form* | > are essential, but associated types and datatypes look nicer | > in many ways! | > - is it too late, in practice, to replace fundeps by something | > else? How will we know? If we are to standardize on associated | > types instead, we need a major effort to *make sure* all | > important applications of fundeps can be represented. How will | > we organize that? | | I agree that MPTCs are much less useful (though not completely useless) | without something like FDs or associated types. But the specification | of FDs is far from clear: the system described in Mark's paper is quite | a bit weaker than what is implemented by GHC and (more shakily) by Hugs. | It seems that associated types aren't ready yet, but I don't think FDs | are either, accustomed as people are to them. | | I have another worry about MPTCs. They require require relaxations on | the form of instances (FlexibleInstances on the wiki), which in turn | require relaxations on contexts and thus deferred context reduction (see | FlexibleContexts). The result is that missing instances get reported | later than they do now. MPTCs are very useful and probably necessary, | but there is a cost. | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime@haskell.org | http://haskell.org/mailman/listinfo/haskell-prime
Dear all, Simon PJ wrote:
Multi-parameter type classes, yes. Functional dependencies, no.
My experience is that even with very simple applications of MPTCs, I often end up needing functional dependencies to make things work. Thus, if my hunch is right, and other people have a similar experience, my fear would be that omitting FDs or something similar would result in a Haskell' standard that ends up being out of date even before it is finalised, in that a large number of real world applications and libraries would fail to be standard compliant and could not easily be adapted to be. I think that would be very unfortunate, even though I do agree that the Haskell' effort should strive to be as conservative as possible. Might it be possible to at least allow some simple forms of FDs that would cover the most common cases, e.g. like what's described in Mark's original paper? I personally would not be too worried about adopting a possibly non "future-proof" solution in this respect, as I would expect that the amount of code that would have to be change would be fairly small if some scheme like associated types later are adopted as a replacement. What would worry me is the lack of ANY functionality like FDs, as having to work without them means that code often would have to be too type specific, which in the end might result in lots of code duplication. Refactoring such code later would seem to be much more work (even if it might not be strictly necessary to do so, as the code would continue to work). But maybe other people have a somewhat difference experience, and feel that this is less of an issue than I believe it is? All the best, /Henrik -- Henrik Nilsson School of Computer Science and Information Technology The University of Nottingham nhn@cs.nott.ac.uk This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.
Henrik Nilsson wrote:
Dear all,
Simon PJ wrote:
Multi-parameter type classes, yes. Functional dependencies, no.
My experience is that even with very simple applications of MPTCs, I often end up needing functional dependencies to make things work.
As a user, I'll echo this. It seems to me that when you create a multi-parameter typeclass, there are often constraints among the different parameters that need to be expressed. As an example, consider writing a multi-parameter typeclass to capture the idea of being able to "select" an object out of an indexed collection (e.g. a list or an array). One dependency you'd like to have might be that the collection type determines the type of the item you're selecting (so that the type of the item can be inferred from the type of the collection). As a second data point, I looked at the monad transformer library. The multi-parameter classes MonadState, MonadError, MonadReader and MonadWriter all use functional dependencies among their parameters. I think monad transformers are a significant part of the motivation to include multi-parameter typeclasses. This, to me, implies that we need some answer for their use of functional dependencies. - Ravi
Ravi Nanavati wrote:
Multi-parameter type classes, yes. Functional dependencies, no.
My experience is that even with very simple applications of MPTCs, I often end up needing functional dependencies to make things work.
As a user, I'll echo this.
Me three, etc. Might it be worth holding off on MPTCs altogether if we don't also have fundeps or associated types? -- Ashley Yakeley
On Thu, Feb 02, 2006 at 11:36:34AM -0000, Simon Peyton-Jones wrote:
I'm confident that it is premature to standardise functional dependencies at this stage, very useful though they are. If you doubt me, read the JFP journal submission that Martin Sulzmann and Peter Stuckey and I have been working on. http://research.microsoft.com/%7Esimonpj/papers/fd-chr Fundeps are very, very tricky.
My own view is that associated types are a more promising way forward at the programming language level. They are a little less expressive than fundeps, I think, but a whole lot less tricky. But we don't have an implementation of them yet, so we can hardly standardise them!
Multi-parameter type classes, yes. Functional dependencies, no.
Yeah, I have been coming to the same conclusion myself. it pains me a lot. (monad transformers! I need thee!) but its not like fundeps will go away, they will just still be experimental so it isn't the end of the world. My main reasons for feeling this way are that assosiated type synonyms seem to solve the problems fundeps were meant to solve, and the other uses seem to be various tricks in order to finagle the class system into giving a sort of type-level programming. which is cool, but it makes me think there is room for an actual type-level programming extension there somewhere. (user defined kinds + GADTs?) John -- John Meacham - ⑆repetae.net⑆john⑈
Dear all, John Mecham wrote:
Yeah, I have been coming to the same conclusion myself. it pains me a lot. (monad transformers! I need thee!) but its not like fundeps will go away, they will just still be experimental so it isn't the end of the world.
But isn't the whole point of Haskell' to standardise those features that are agreed to be necessary for writing real-world applications and libraries in a reasonable way? My concern is not that I fear not being able to compile my programs after Haskell' is done. I'm worried about too much code not being Haskell' compliant in the end, and, worse, too many people deciding that they still have to rely on extensions beyond Haskell' for writing "real" applications and libraries. Should this be the case in the end, then Haskell' will qucikly become irrelevant, and I think that would be very unfortunate. Now, I'm not saying that FDs are that important, only that it seems to me they are. I'd be happy to be convinced of the opposite. But from the above, it at least seems that John M. too actually says that FDs are important? Best regards, /Henrik -- Henrik Nilsson School of Computer Science and Information Technology The University of Nottingham nhn@cs.nott.ac.uk This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.
But isn't the whole point of Haskell' to standardise those features that are agreed to be necessary for writing real-world applications and libraries in a reasonable way?
Assuming for a little while that we'd actually want to incorporate FDs in Haskell'. Could we even do it? Is there a document describing *all* the aspects of FDs in a reasonable complexity and abstraction level that would be appropriate for a standard. If not, could such a document easily be written with the knowledge of today? After all, I don't want Haskell' to read "... and we incorporate FDs as they are implemented in GHC". On the other extreme, I don't want the Haskell' report to have a chapter on FDs that makes up 50% of the whole report. In any case, I will sit down and read the papers at http://research.microsoft.com/Users/simonpj/papers/fd-chr/ Maybe this will answer my question. Cheers, Andres
On Thu, Feb 02, 2006 at 03:09:35PM +0000, Henrik Nilsson wrote:
Now, I'm not saying that FDs are that important, only that it seems to me they are. I'd be happy to be convinced of the opposite. But from the above, it at least seems that John M. too actually says that FDs are important?
Oh, I don't think anyone is disagreeing that they are important. they are just quite underspecified at the moment, and it looks like they will be replaced at some point anyway. It would be great if we can figure out some well specified subset that works for most uses that is ready to put into haskell prime. John -- John Meacham - ⑆repetae.net⑆john⑈
Am Freitag, 3. Februar 2006 00:06 schrieb John Meacham:
On Thu, Feb 02, 2006 at 03:09:35PM +0000, Henrik Nilsson wrote:
Now, I'm not saying that FDs are that important, only that it seems to me they are. I'd be happy to be convinced of the opposite. But from the above, it at least seems that John M. too actually says that FDs are important?
Oh, I don't think anyone is disagreeing that they are important. they are just quite underspecified at the moment, and it looks like they will be replaced at some point anyway. It would be great if we can figure out some well specified subset that works for most uses that is ready to put into haskell prime.
John
From the users point of view, the implementation in GHC works quite well and a lot people use it. It would be a pitty if they are not included in the new standard. What is the problem of specifiing what is implemented. If they are replaced in the future we will have haskell'' anyway :-). Cheers, Georg -- ---- Georg Martius, Tel: (+49 34297) 89434 ---- ------- http://www.flexman.homeip.net ----------
On Tue, Feb 07, 2006 at 10:04:35AM +0100, Georg Martius wrote:
From the users point of view, the implementation in GHC works quite well and a lot people use it. It would be a pity if they are not included in the new standard. What is the problem of specifying what is implemented.
They work well most of the time, but people keep discovering strange behaviour around the edges. For example, the following (example 6 of Sulzmann et al) sends GHC into a loop: class Mul a b c | a b -> c where (.*.) :: a -> b -> c instance Mul Int Int Int where (.*.) = (*) instance Mul Int Float Float where x .*. y = fromIntegral x * y instance Mul a b c => Mul a [b] [c] where x .*. v = map (x.*.) v f = \ b x y -> if b then x .*. [y] else y Noone knows how to specify them (short of pointing at GHC, which won't do). The closest is Sulzmann et al, which makes the problems clearer.
Henrik Nilsson
Dear all,
John Mecham wrote:
Yeah, I have been coming to the same conclusion myself. it pains me a lot. (monad transformers! I need thee!) but its not like fundeps will go away, they will just still be experimental so it isn't the end of the world.
But isn't the whole point of Haskell' to standardise those features that are agreed to be necessary for writing real-world applications and libraries in a reasonable way?
My concern is not that I fear not being able to compile my programs after Haskell' is done. I'm worried about too much code not being Haskell' compliant in the end, and, worse, too many people deciding that they still have to rely on extensions beyond Haskell' for writing "real" applications and libraries.
I am very concerned about this as well. In most of my production code, I avoid extensions, but MPTC and functional dependencies are two that I have not been able to avoid. Any time I use the class system, I use MPTC, anytime I use MPTC, I use fundeps. The trouble with "blessing" fundeps is that they might not pan out in the end, and it would be a shame to add them to Haskell' and then remove them again for Haskell'' (if there were such a thing) in favor of associated types, for instance. How do we solve this dilemma? Some proposals that have come up: - Simon has proposed that we examine a limited version of functional dependencies. - Another option, though a scary one at this point, is to look closely at associated types. - Another option is to punt; we declare them as an extension and figure out a way to "bless" extensions (beyond Cabal, I guess). - Any others? Can someone put together a wiki page these choices with trade-offs? Ravi, Manuel? peace, isaac
participants (9)
-
Andres Loeh -
Ashley Yakeley -
Georg Martius -
Henrik Nilsson -
Isaac Jones -
John Meacham -
Ravi Nanavati -
Ross Paterson -
Simon Peyton-Jones