April 2006 - Haskell-prime

Re: FDs and confluence
by tom.schrijvers＠cs.kuleuven.be 10 Apr '06

10 Apr '06

On Mon, 10 Apr 2006, Claus Reinke wrote: >> (see the FunctionalDependencies page for background omitted here) > > which seems to ignore much of the discussion of confluence we had here some > weeks ago? I thought this list was for communication with the committee, and > since the ticket exists, I had been hoping that the > type class subcommittee would ensure that the wiki would be updated. > but it seems I have been talking to myself.. Yes, I wondered what had happened to your previous argument for the memo constraint. >> One of the problems with the relaxed coverage condition implemented >> by GHC and Hugs is a loss of confluence. Here is a slightly cut-down >> version of Ex. 18 from the FD-CHR paper: >> >> class B a b | a -> b >> class C a b c | a -> b >> >> instance B a b => C [a] b Bool >> >> Starting from a constraint set C [a] b Bool, C [a] c d, we have two >> possible reductions: >> >> 1) C [a] b Bool, C [a] c d >> => c = b, C [a] b Bool, C [a] b d (use FD on C) >> => c = b, B a b, C [a] b d (reduce instance) >> >> 2) C [a] b Bool, C [a] c d >> => C a b, C [a] c d (reduce instance) > > CHR-alt: > > B a b <=> infer_B a b, memo_B a b. > memo_B a b1, memo_B a b2 ==>b1=b2. > > C a b c <=> infer_C a b c, memo_C a b c. > memo_C a b1 c1, memo_C a b2 c2 ==> b1=b2. > infer_C [a] b Bool <=> B a b. > memo_C [a] b' c' ==> b'=b. What's this last rule for? It mentions a b that does not appear in the head of the rule. If you mean the rule memo_C [a] b c, memo_C [a] b' c' ==> b = b'. then it is already subsumed by the more general memo_C a b1 c1, memo_C a b2 c2 ==> b1=b2. Tom -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: tom.schrijvers(a)cs.kuleuven.be

1 0

RE: FDs and confluence
by Simon Peyton-Jones 10 Apr '06

10 Apr '06

Interesting! It'd be great if you've found a simpler more uniform rule. (Which you seem to be getting rather good at.) Let's see if you can convince Martin, first, and then articulate the proposed rules. I'll look fwd to that. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Ross Paterson | Sent: 10 April 2006 09:53 | To: haskell-prime(a)haskell.org | Subject: FDs and confluence | | (see the FunctionalDependencies page for background omitted here) | | One of the problems with the relaxed coverage condition implemented | by GHC and Hugs is a loss of confluence. Here is a slightly cut-down | version of Ex. 18 from the FD-CHR paper: | | class B a b | a -> b | class C a b c | a -> b | | instance B a b => C [a] b Bool | | Starting from a constraint set C [a] b Bool, C [a] c d, we have two | possible reductions: | | 1) C [a] b Bool, C [a] c d | => c = b, C [a] b Bool, C [a] b d (use FD on C) | => c = b, B a b, C [a] b d (reduce instance) | | 2) C [a] b Bool, C [a] c d | => C a b, C [a] c d (reduce instance) | | The proposed solution was to tighten the restrictions on instances to | forbid those like the above one for C. However there may be another | way out. | | The consistency condition implies that there cannot be another | instance C [t1] t2 t3: a substitution unifying a and t1 need not | unify b and t2. Thus we could either | | 1) consider the two constraint sets equivalent, since they describe | the same set of ground instances, or | | 2) enhance the instance improvement rule: in the above example, we | must have d = Bool in both cases, so both reduce to | | c = b, d = Bool, B a b | | More precisely, given a dependency X -> Y and an instance C t, if | tY is not covered by tX, then for any constraint C s with sX = S tX | for some substitution S, we can unify s with S t. | | We would need a restriction on instances to guarantee termination: | each argument of the instance must either be covered by tX or be | a single variable. That is less restrictive (and simpler) than | the previous proposal, however. | | Underlying this is an imbalance between the two restrictions on instances. | In the original version, neither took any account of the context of the | instance declaration. The implementations change this for the coverage | condition but not the consistency condition. Indeed the original form of | the consistency condition is necessary for the instance improvement rule. | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

1 0

RE: MPTCs and functional dependencies
by Simon Peyton-Jones 10 Apr '06

10 Apr '06

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(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Ross Paterson | Sent: 02 February 2006 11:25 | To: haskell-prime(a)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(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

6 6

RE: New syntax
by Simon Peyton-Jones 10 Apr '06

10 Apr '06

| > | It's very bad that with TH enabled you cannot write sections of the | > form ($ x) | > | anymore which are sometimes very handy. | > | > I'd prefer it if TH only sprang into action when you wrote | > $x | > or | > $(f x) | > | > That is, no space after the $. If you put spaces, you should get the | > H98 $. | | Isn't that the current behaviour? So it is! It's even documented as such. SImon

1 0

RE: Exceptions
by Simon Marlow 10 Apr '06

10 Apr '06

[oops, sent by accident...] On 08 April 2006 10:18, John Meacham wrote: > On Sat, Apr 08, 2006 at 12:11:51AM -0400, David Menendez wrote: >>> newtype ArithException a = ArithException a >>> >>> data DivideByZero >>> >>> throw (ArithException DivideByZero) >>> >>> your code: >>> >>> data MultiplyByZero >>> throw (ArithException MultiplyByZero) >> >> How would you use this to write a handler that captures any >> ArithException? > > You would use the Typeable1 class in Data.Typeable. not perfect, but > exception hierarchies shouldn't be too deep so it is not so bad. I mentioned this solution to John G. off-list; the problem is that you end up needing to parameterise all the classes of exceptions (we'd have IOException a, ArrayException a, AsyncException a, etc.), and that seems ugly. Given that we've already made the Exception type sideways extensible with a simple application of type classes and dynamic types, we can take the technique a bit further to create an extensible hierarchy of exceptions, which is what John's arguing for. To create a new subclass of exceptions: --------- class (Typeable x, Show x) => ArithException x newtype AnyArithException = AnyArithException Dynamic deriving Typeable instance Exception AnyArithException instance Show AnyArithException where show (AnyArithException x) = show x throwArith :: ArithException x => x -> a throwArith x = throw (AnyArithException (toDyn x)) matchArith :: ArithException x => AnyArithException -> Maybe x matchArith (AnyArithException x) = fromDynamic x --------- and populating the subclass is just as easy as populating the root: --------- data DivideByZero = DivideByZero deriving (Typeable, Show) data Overflow = Overflow deriving (Typeable, Show) instance ArithException DivideByZero instance ArithException Overflow --------- catching is easy too. To catch *any* ArithException: --------- x `catch` \(e :: AnyArithException) -> print e --------- To catch a particular ArithException: --------- x `catch` \e -> case () of _ | Just DivideByZero <- matchArith e -> print e | otherwise -> throw e --------- To catch a mixture of ArithException and other exceptions: --------- x `catchAny` \e -> case () of _ | Just (IOException x) <- matchException e -> print x | Just arith <- matchException e, Just DivideByZero <- matchArith arith -> print arith | otherwise -> throwAny e --------- I like this, it seems like a natural extension of what we've already proposed. The fact that you have to use 'throwArith' rather than plain 'throw' is slightly annoying, though. Cheers, Simon

1 0

RE: Exceptions
by Simon Marlow 10 Apr '06

10 Apr '06

On 08 April 2006 10:18, John Meacham wrote: > On Sat, Apr 08, 2006 at 12:11:51AM -0400, David Menendez wrote: >>> newtype ArithException a = ArithException a >>> >>> data DivideByZero >>> >>> throw (ArithException DivideByZero) >>> >>> your code: >>> >>> data MultiplyByZero >>> throw (ArithException MultiplyByZero) >> >> How would you use this to write a handler that captures any >> ArithException? > > You would use the Typeable1 class in Data.Typeable. not perfect, but > exception hierarchies shouldn't be too deep so it is not so bad. I mentioned this solution to John G. off-list; the problem is that you end up needing to parameterise all the classes of exceptions (we'd have IOException a, ArrayException a, AsyncException a, etc.). Given that we've already made the Exception type sideways extensible with a simple application of type classes and dynamic types, we can take the technique a bit further to create an extensible hierarchy of exceptions, which is what John wants. To create a new subclass of exceptions:

1 0

RE: Signals + minimal proposal (was Re: asynchronous exceptions)
by Simon Marlow 09 Apr '06

09 Apr '06

On 07 April 2006 13:58, John Meacham wrote: > all threads keep running while the exit handers are running, all > blockExit would do is grab and release an MVar. exit itself takes > that MVar on starting to get rid of races to exit as well as protect > itsesf from 'blockExit' (but won't ever put the MVar back). That sounds hard to program with - surely you want to stop the program in order to clean up? Otherwise the program is going to continue working, generating more exit handlers, and we might never get to exit. Of course you could implement some global flag to say that an exit is in progress, but that implies explicit checking of the flag all over the place, which is what asynchronous exceptions are designed to avoid. When *do* we exit, in fact? When all the exit handlers have finished? >> Exceptions are the right way to handle releasing resources, and they >> are the right way to register cleanup actions. Therefore I believe >> exceptions are the right way to handle cleaning up on exit, too. > > Well, We really need 'onExit' for other reasons as well, I think it > should make it into the standard independently. Sure, I'm happy with onExit. > I think you have that backwards, releasing resources is the right > thing > to do when you get an exception, but there are lots of other reasons > you > want to release resources that have nothing to do with exceptions. you > don't use 'throwTo' to close all your files :) No, but you do use an exception handler, or something built using exception handlers like 'finally'. I don't want to have to use *both* exception handlers and exit handlers. >> Since async exceptions are no problem to implement in a coop system, >> shouldn't we use them for exit too? > > but then only one thread gets to clean up after itself, I think all threads should get the exit exception (I know GHC doesn't currently do this). > and you have > the issue that you can't interrupt a foreign function by throwing to > it. The situation is the same as in your proposal - the foreign call continues running. However, as soon as it returns, the Haskell thread will receive an exception. I propose this: When System.Exit.exitWith is called, all currently running threads are sent an exit exception as soon as possible. Exit handlers registered with onExit are started immediately. The system exits when (a) the main thread has stopped, and (b) all exit handlers have completed. Subsequent calls to exitWith simply throw an exit exception in the current thread. Cheers, Simon

3 2

limitations of newtype-deriving
by John Meacham 09 Apr '06

09 Apr '06

The newtype deriving extension is one of the most powerful tools for writing robust, typesafe code. However it suffers from a couple limitations. * you can only newtype derive the last argument to a MPTC. * you cannot co-derive an instance for multiple newtype renamings. it seems that both these can be solved when combined with the other proposed extension, allowing deriving clauses to be separate from data definitions. basically, we would allow deriving anywhere. > deriving (Show Foo) means the same thing as > data Foo = ... > deriving (Show) will derive an instance of Show for Foo. now we are no longer bound by either of the above constraints.. imagine we have a class > class MapLike k v | v -> k where > insert :: .. > delete :: ... > ... > instance MapLike Int (IM.IntMap a) where > insert = IM.insert > .... now, we want a newtype that describes Id's. > newtype Id = Id Int > deriving(Eq,Ord) now, we want to create a type of substitutions from Ids -> Terms > newtype Subst = Subst (IM.IntMap Term) ideally, we'd like an MapLike instance, but we'd have to tediously write it ourselves. if we allow the supergeneralized newtype deriving, we can do: > deriving(MapLike Id Subst) and be done with it. this would be worlds of useful. John -- John Meacham - ⑆repetae.net⑆john⑈

1 1

Re: Exceptions
by John Meacham 08 Apr '06

08 Apr '06

On Sat, Apr 08, 2006 at 12:11:51AM -0400, David Menendez wrote: > > newtype ArithException a = ArithException a > > > > data DivideByZero > > > > throw (ArithException DivideByZero) > > > > your code: > > > > data MultiplyByZero > > throw (ArithException MultiplyByZero) > > How would you use this to write a handler that captures any > ArithException? You would use the Typeable1 class in Data.Typeable. not perfect, but exception hierarchies shouldn't be too deep so it is not so bad. John -- John Meacham - ⑆repetae.net⑆john⑈

1 0

Re: Exceptions
by Dave Menendez 08 Apr '06

08 Apr '06

John Meacham writes: > On Fri, Apr 07, 2006 at 10:00:21AM -0500, John Goerzen wrote: > > But here's my concern. Let's say that I wanted to, for some > > reason, create a MultiplyByZero exception. It should be broadly > > considered an ArithException, and any code that catches an > > ArithException should be able to catch my MultiplyByZero exception. > > > > But the ArithException type is limited to storing errors that are > > defined by Control.Exception.ArithException. My MultiplyByZero is > > not defined there, so I am out of luck. The best I could do is > > define a new MultiplyByZero, and catch it in my own code. But any > > code that others have written to catch ArithExceptions would be > > blind to MultiplyByZero. > > newtype ArithException a = ArithException a > > data DivideByZero > > throw (ArithException DivideByZero) > > your code: > > data MultiplyByZero > throw (ArithException MultiplyByZero) How would you use this to write a handler that captures any ArithException? -- David Menendez <zednenem(a)psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"

1 0