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: 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
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/MultiParamTypeClassesDile... Could someone flesh out the wiki w/ Simon's data and links to the new information from Martin? peace, isaac
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
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
On Mon, Apr 10, 2006 at 01:31:18PM +0800, Martin Sulzmann wrote:
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
I find them unsatisfactory because the versions that are powerful enough (e.g. to allow the instances in the monad transformer library) need complex restrictions on the form of instances to ensure termination and confluence. They would make the language complex and unwieldy.
Ross Paterson writes:
On Mon, Apr 10, 2006 at 01:31:18PM +0800, Martin Sulzmann wrote:
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
I find them unsatisfactory because the versions that are powerful enough (e.g. to allow the instances in the monad transformer library) need complex restrictions on the form of instances to ensure termination and confluence. They would make the language complex and unwieldy.
"Complex" termination condition I agree but the confluence conditions are natural. When it comes to termination it's pretty unlikely that simple conditions are sufficient (e.g. consider the simple AT extensions which results in undecidable inference). But I'm happy to be proven wrong. Martin
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 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.
participants (6)
-
Henrik Nilsson -
isaac jones -
Manuel M T Chakravarty -
Martin Sulzmann -
Ross Paterson -
Simon Peyton-Jones