Re: MPTCs and functional dependencies
Hi all, Manuel Chakravarty wrote: My conclusion is that we should not include FDs or ATs into the standard at the moment. Standardising FDs as a stopgap measure may easily put us into the same situation that we are having with records at the moment. Nobody is really happy with it, but we don't dare to change it either. Martin Sulzmann The situation here is clearly different. Whatever comes next (after FDs) will be a conservative extension. So, standardising FDs is a good thing because they have proven to be a useful (somewhat essential for MPTCs) feature. Hence, I will go with Simon: H' should have MPTC + FDs, but not ATs. I basically agree with Simon PJ and Martin: MPTCs are necessary for H', and MPTCs pretty much necessitates at least some limited form of FD/AT. Thus I view FD/AT as so important, that I think it is a secondary concern if it ends up being a stop gap measure. Moreover, it seems to me that FD/AT declarations in practical applications amounts to very little code. Thus, the likely work impact if FD/AT is completely replaced with some other mechanism providing the same functionality should be very limited. This is unlike records, say, where record notation is likely to be used pretty much throughout an application. Also, the alternative of NOT having FD/AT would seem to lead to rather convoluted solutions in many cases, so the work of adapting non FD/AT MPTC code to an hypotetical H'' setting where an FD/AT replacement is available, is potentially quite big. But of couse, the above discussion on likely change impact is just my gut feeling. My key argument is that MPTCs and thus some form of FDs/ATs are really important in practice. All the best, /Henrik -- Henrik Nilsson School of Computer Science and Information Technology The University of Nottingham [EMAIL PROTECTED] 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. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: MPTCs and functional dependencies
Simon Peyton-Jones: My current take, FWIW. * MPTCs are very useful. They came along very rapidly (well before H98). I think we must put them in H' * But MPTCs are hamstrung without FDs or ATs * FDs and ATs are of the same order of technical difficulty, as Martin says Both FDs and ATs come in various versions of different levels of expressiveness. They may be of the same level of difficulty with all bells and whistles, but that's a bit of a red herring. The real question is how do the levels of difficulty compare at the level of expressiveness that we want. Or phrased differently, for a version that is not too difficult, how does the expressiveness compare. * ATs are (I believe) a bit weaker from the expressiveness point of view (zip example), but are (I believe) nicer to program with. The zip example can be done with ATs - it's actually in one of Martin's papers. I currently don't know of any FD example that you can't do with ATs. It's a matter of what forms of AT definitions you want to allow. * BUT we have way more experience with actually programming with FDs. ATs fail the well-established test by a mile. Indeed! * Largely due to Martin's work, we now have a much better handle on just what restrictions on FDs make type inference tractable. So I believe there is a solid MPTC+FD story that we could embody in H'. * Medium term, I think ATs may *at the programming-language level* displace FDs, because they are nicer to program with. But that's just my opinion, and we don't have enough experience to know one way or the other. Maybe not only at the programming-language level. Given our latest paper, http://www.cse.unsw.edu.au/~chak/papers/SCP06.html for example, the translation of ATs is simpler than FDs if we also have existential types (but admittedly that became clear to us only after your email message). Tentative conclusion: H' should have MPTC + FDs, but not ATs. My conclusion is that we should not include FDs or ATs into the standard at the moment. Standardising FDs as a stopgap measure may easily put us into the same situation that we are having with records at the moment. Nobody is really happy with it, but we don't dare to change it either. Manuel ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: MPTCs and functional dependencies
Manuel M T Chakravarty writes: Simon Peyton-Jones: My current take, FWIW. [...] Tentative conclusion: H' should have MPTC + FDs, but not ATs. My conclusion is that we should not include FDs or ATs into the standard at the moment. Standardising FDs as a stopgap measure may easily put us into the same situation that we are having with records at the moment. Nobody is really happy with it, but we don't dare to change it either. Manuel The situation here is clearly different. Whatever comes next (after FDs) will be a conservative extension. So, standardising FDs is a good thing because they have proven to be a useful (somewhat essential for MPTCs) feature. Hence, I will go with Simon: H' should have MPTC + FDs, but not ATs. You mention that nobody is really happy with FDs at the moment, but you don't provide concrete arguments why. I assume you refer to the following two issues: 1) FDs may threaten complete and decidable type inference 2) FDs are more verbose than say ATs Issue 1) is not limited to FDs. ATs share the same problem. I'll spare the details. Issue 2) may be a matter of taste. In fact, sometimes it's easier to write decidable (but more verbose) FDs than writing an equivalent *and* decidable AT program. Recall the following discussion. Somebody asked how to write the MonadReader class with ATs: http://www.haskell.org//pipermail/haskell-cafe/2006-February/014489.html This requires an AT extension which may lead to undecidable type inference: http://www.haskell.org//pipermail/haskell-cafe/2006-February/014609.html It is possible to recover decidable AT inference (I hinted how, see the above email thread), but the sufficient conditions get more and more complex. * MPTCs are very useful. They came along very rapidly (well before H98). I think we must put them in H' * But MPTCs are hamstrung without FDs or ATs * FDs and ATs are of the same order of technical difficulty, as Martin says Both FDs and ATs come in various versions of different levels of expressiveness. They may be of the same level of difficulty with all bells and whistles, but that's a bit of a red herring. The real question is how do the levels of difficulty compare at the level of expressiveness that we want. Or phrased differently, for a version that is not too difficult, how does the expressiveness compare. See the MonadReader example above! * ATs are (I believe) a bit weaker from the expressiveness point of view (zip example), but are (I believe) nicer to program with. The zip example can be done with ATs - it's actually in one of Martin's papers. I currently don't know of any FD example that you can't do with ATs. It's a matter of what forms of AT definitions you want to allow. The zip example canNOT be expressed with ATs as described in the ICFP'05 paper! The point here is really that it's fairly easy to write down the zip instances and let FDs automatically derive the necessary improvement rules. In case of ATs (using an extension which has been sketched in the Associated FD paper), the programmer has to write down all improvement rules (as type functions) herself. This can be a non-trivial task! * Medium term, I think ATs may *at the programming-language level* displace FDs, because they are nicer to program with. But that's just my opinion, and we don't have enough experience to know one way or the other. Maybe not only at the programming-language level. Given our latest paper, http://www.cse.unsw.edu.au/~chak/papers/SCP06.html for example, the translation of ATs is simpler than FDs if we also have existential types (but admittedly that became clear to us only after your email message). Be careful, somebody could argue the opposite. ATs are now redundant because all FD programs can now be translated. Hence, the AT via FD encoding scheme which I once sketched is now type preserving. The fact that the FD translation is more complex is not a serious issue. After all, there's an automatic translation scheme. Martin ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: MPTCs and functional dependencies
My current take, FWIW. * MPTCs are very useful. They came along very rapidly (well before H98). I think we must put them in H' * But MPTCs are hamstrung without FDs or ATs * FDs and ATs are of the same order of technical difficulty, as Martin says * ATs are (I believe) a bit weaker from the expressiveness point of view (zip example), but are (I believe) nicer to program with. * BUT we have way more experience with actually programming with FDs. ATs fail the well-established test by a mile. * Largely due to Martin's work, we now have a much better handle on just what restrictions on FDs make type inference tractable. So I believe there is a solid MPTC+FD story that we could embody in H'. * Medium term, I think ATs may *at the programming-language level* displace FDs, because they are nicer to program with. But that's just my opinion, and we don't have enough experience to know one way or the other. Tentative conclusion: H' should have MPTC + FDs, but not ATs. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] 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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: MPTCs and functional dependencies
On Tue, 2006-03-28 at 14:32 +0100, Simon Peyton-Jones wrote: My current take, FWIW. * MPTCs are very useful. They came along very rapidly (well before H98). I think we must put them in H' * But MPTCs are hamstrung without FDs or ATs * FDs and ATs are of the same order of technical difficulty, as Martin says * ATs are (I believe) a bit weaker from the expressiveness point of view (zip example), but are (I believe) nicer to program with. * BUT we have way more experience with actually programming with FDs. ATs fail the well-established test by a mile. * Largely due to Martin's work, we now have a much better handle on just what restrictions on FDs make type inference tractable. So I believe there is a solid MPTC+FD story that we could embody in H'. * Medium term, I think ATs may *at the programming-language level* displace FDs, because they are nicer to program with. But that's just my opinion, and we don't have enough experience to know one way or the other. This analysis is similar to what I have here: http://hackage.haskell.org/trac/haskell-prime/wiki/MultiParamTypeClassesDilemma Could someone flesh out the wiki w/ Simon's data and links to the new information from Martin? peace, isaac ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
Am Freitag, 3. Februar 2006 00:06 schrieb John Meacham: On Thu, Feb 02, 2006 at 03:09:35PM +, 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 -- pgpapSKrhJlxf.pgp Description: PGP signature ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
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. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
Henrik Nilsson [EMAIL PROTECTED] writes: 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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] 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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
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 [EMAIL PROTECTED] 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. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
CHRs, was Re: MPTCs and functional dependencies
... 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 Has this list discussed using CHRs instead of fundeps? Jim ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
On Thu, Feb 02, 2006 at 11:36:34AM -, 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⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
On Thu, Feb 02, 2006 at 03:09:35PM +, 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⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: MPTCs and functional dependencies
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 ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
