Is there any way to use RULES substitutions with type classes? I'm writing a reactive programming arrow (same idea as Yampa, different design goals), and it would help performance (and not just in the speed sense) to be able to tell when a value derived with arr hasn't changed. So I'd like to be able to specialize arr to functions whose result is an instance of Eq. I tried {-# RULES "reactiveArr/Eq" reactiveArr = reactiveArrEq #-} but got the message Control/Arrow/Reactive/Reactive.hs:89:41: No instance for (Eq b) arising from instantiating a type signature at Control/Arrow/Reactive/Reactive.hs:89:41-89 Possible fix: add (Eq b) to the tcRule When checking the transformation rule "reactiveArr/Eq" I tried adding various sorts of type signatures, but I couldn't find any way around this... is it a restriction in the RULES rewrite engine? Is there a workaround, or some mechanism other than RULES that I should be using? I could write a special "arrEq" function, but I'd like to minimize the number of extraneous operations outside the Arrow class. Thanks, Mike Hamburg
haskell:
Is there any way to use RULES substitutions with type classes?
I'm writing a reactive programming arrow (same idea as Yampa, different design goals), and it would help performance (and not just in the speed sense) to be able to tell when a value derived with arr hasn't changed. So I'd like to be able to specialize arr to functions whose result is an instance of Eq.
I tried {-# RULES "reactiveArr/Eq" reactiveArr = reactiveArrEq #-} but got the message
Control/Arrow/Reactive/Reactive.hs:89:41: No instance for (Eq b) arising from instantiating a type signature at Control/Arrow/Reactive/Reactive.hs:89:41-89 Possible fix: add (Eq b) to the tcRule When checking the transformation rule "reactiveArr/Eq"
I tried adding various sorts of type signatures, but I couldn't find any way around this... is it a restriction in the RULES rewrite engine? Is there a workaround, or some mechanism other than RULES that I should be using? I could write a special "arrEq" function, but I'd like to minimize the number of extraneous operations outside the Arrow class.
Thanks, Mike Hamburg
In particular, it would be nice to be able to specialise based on the instances, as we do for [a] --> [Int], e.g. RULES sum = sumInt :: [Int] -> Int is fine in the current system. So I could imagine some nice specialisations based on say, the good old Ord: RULES nub = nubOrd :: (Eq a, Ord a) => [a] -> [a] which might use a Map, say. I don't know how costly this instance matching would be. -- Don
| In particular, it would be nice to be able to specialise based on the | instances, as we do for [a] --> [Int], e.g. | | RULES sum = sumInt :: [Int] -> Int | | is fine in the current system. So I could imagine some nice | specialisations based on say, the good old Ord: | | RULES nub = nubOrd :: (Eq a, Ord a) => [a] -> [a] | | which might use a Map, say. | | I don't know how costly this instance matching would be. At the moment, RULES are a pure term rewriting system. That is, when the simplifer sees an instance of the LHS it rewrites it to the RHS Every variable used on the RHS of the rule is either a constant, or is bound on the LHS. What you want is different. Remember nub :: Eq a => [a] -> [a] You want to the rule forall a:*, d1:Eq a, nub a d1 ---> nubOrd a d1 d2 where d2:Ord a. But where did d2 come from? Out of thin air! The simplifier does not do this. It knows nothing of type classes and instances; it just does term rewrites. Now it would be quite reasonable to have something more sophisticated that *does* know about how to construct instance dictionaries "out of thin air", but that goes significantly beyond what the current RULES system does. Would someone care to add this info to the Wiki? http://haskell.org/haskellwiki/GHC/Using_rules Simon
Hi
I was thinking about this, and I think pattern matching with rules and
class context pretty much _guarantees_ a change in semantics. If you
match on a class constraint, the pretty much only reason to do so is
to exploit that type class. Unfortunately, this isn't safe.
The user has called a function which explicitly annotates which
classes it requires. The user is completely allowed to write "instance
Ord a where compare = undefined", and they should have a reasonable
expectation that unless Ord a => is in the context, Ord is not
involved.
So perhaps before you tackle the issue of adding classes to rules, you
need to tackle the issue of getting rules to check what they really
mean...
Thanks
Neil
On 3/30/07, Simon Peyton-Jones
| In particular, it would be nice to be able to specialise based on the | instances, as we do for [a] --> [Int], e.g. | | RULES sum = sumInt :: [Int] -> Int | | is fine in the current system. So I could imagine some nice | specialisations based on say, the good old Ord: | | RULES nub = nubOrd :: (Eq a, Ord a) => [a] -> [a] | | which might use a Map, say. | | I don't know how costly this instance matching would be.
At the moment, RULES are a pure term rewriting system. That is,
when the simplifer sees an instance of the LHS it rewrites it to the RHS
Every variable used on the RHS of the rule is either a constant, or is bound on the LHS.
What you want is different. Remember nub :: Eq a => [a] -> [a]
You want to the rule
forall a:*, d1:Eq a, nub a d1 ---> nubOrd a d1 d2
where d2:Ord a. But where did d2 come from? Out of thin air!
The simplifier does not do this. It knows nothing of type classes and instances; it just does term rewrites.
Now it would be quite reasonable to have something more sophisticated that *does* know about how to construct instance dictionaries "out of thin air", but that goes significantly beyond what the current RULES system does.
Would someone care to add this info to the Wiki? http://haskell.org/haskellwiki/GHC/Using_rules
Simon
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Neil Mitchell wrote:
Hi
I was thinking about this, and I think pattern matching with rules and class context pretty much _guarantees_ a change in semantics. If you match on a class constraint, the pretty much only reason to do so is to exploit that type class. Unfortunately, this isn't safe.
The user has called a function which explicitly annotates which classes it requires. The user is completely allowed to write "instance Ord a where compare = undefined", and they should have a reasonable expectation that unless Ord a => is in the context, Ord is not involved.
So perhaps before you tackle the issue of adding classes to rules, you need to tackle the issue of getting rules to check what they really mean...
If it's a type class introduced in the same place as the rule... maybe it's no worse than the strictness-removing transformations we have for ByteString optimizations? (a horrible excuse, I know) What we really need is some sort of library/tool for testing all known instances of type-classes so we can get an overview of which existing instances are a little sleazy, and how. (although that could be difficult. Will quickcheck-style generation be enough to reliably find corner cases like Doubles that are NaN or very large (where e.g. n+1==n), or the effects of Ints having a maximum value?) Isaac -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.3 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGDYf3HgcxvIWYTTURAjmuAJ47pUupxyI4mhIdJnfDPXmlW7RWIACdE5Ut UEcshnboU6W952/qQ0WUk4g= =mm1x -----END PGP SIGNATURE-----
On Fri, 2007-03-30 at 17:06 +0100, Neil Mitchell wrote:
The user has called a function which explicitly annotates which classes it requires. The user is completely allowed to write "instance Ord a where compare = undefined", and they should have a reasonable expectation that unless Ord a => is in the context, Ord is not involved.
Sure it's not safe in general for existing classes, but I really want to say this... class SmallStrictAtomic a -- only add your type to this class if the ops are strict and total instance StrictNum Int instance StrictNum Char instance StrictNum Int8 ... instance StrictNum Integer {-# RULES "strict maximum" forall (xs :: SmallStrictAtomic x => [x]). maximum xs = strictMaximum xs #-} This is a whole lot easier and more extensible than adding lots of SPECIALISE pragmas: {-# SPECIALISE maximum :: [Int] -> Int #-} {-# SPECIALISE maximum :: [Char] -> Char #-} {-# SPECIALISE maximum :: [Int8] -> Int8 #-} ... {-# SPECIALISE maximum :: [Integer] -> Integer #-} So yeah, the laws for this class are not checked (and I didn't specify them either ;-) though of course I should if we want to let other modules add instances), but it's a class specifically created for the purpose of taking advantage of those laws so if you worry then don't add your type to that class. It doesn't silently rewrite existing programs. More generally I'd like to have ways for programmers to make promises about properties of their values or types so that optimisation rules could take advantage of them, ie rules with side conditions where we can look up and see if the programmer asserts the properties needed to fulfil the side condition. Duncan
On 29/03/2007, at 11:38, Mike Hamburg wrote:
Is there any way to use RULES substitutions with type classes?
I'm writing a reactive programming arrow (same idea as Yampa, different design goals), and it would help performance (and not just in the speed sense) to be able to tell when a value derived with arr hasn't changed. So I'd like to be able to specialize arr to functions whose result is an instance of Eq.
I tried {-# RULES "reactiveArr/Eq" reactiveArr = reactiveArrEq #-} but got the message
Control/Arrow/Reactive/Reactive.hs:89:41: No instance for (Eq b) arising from instantiating a type signature at Control/Arrow/Reactive/Reactive.hs:89:41-89 Possible fix: add (Eq b) to the tcRule When checking the transformation rule "reactiveArr/Eq"
I tried adding various sorts of type signatures, but I couldn't find any way around this... is it a restriction in the RULES rewrite engine? Is there a workaround, or some mechanism other than RULES that I should be using? I could write a special "arrEq" function, but I'd like to minimize the number of extraneous operations outside the Arrow class.
I thought this could be done already. In ghc 6.7: \begin{code} {-# RULES "hello/helloBool" hello = helloBool #-} {-# RULES "hello/helloEq" forall (x::Eq a=>a) . hello x = helloEq x #-} {-# RULES "hello/helloF" forall (f::Eq b=>a->b) . hello f = helloF f #-} data O = O hello _ = "hello" helloBool :: Bool -> String helloBool _ = "hello bool" helloEq :: Eq a => a -> String helloEq _ = "hello Eq" helloF :: Eq b => (a->b) -> String helloF _ = "hello F" f :: Eq b => String -> b f = undefined normal = hello O bool = hello False char = hello 'a'feq :: String feq = hello (f::String -> Bool) \end{code} pep:~/code/snippets$ ghc -O -fglasgow-exts -c rules.hs pep:~/code/snippets$ ghci rules.hs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.7.20070303, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. [1 of 1] Skipping Rules ( rules.hs, rules.o ) Ok, modules loaded: Rules. Prelude Rules> normal "hello" Prelude Rules> bool "hello bool" Prelude Rules> char "hello Eq" Prelude Rules> feq "hello F" Is that what you wanted? pepe
Several things to say on this thread. First, Pepe's examples below only work because of a bug in GHC. Consider RULE forall (x::a->Int). f x = g You'd only expect this to match on arguments of the given type; but it (wrongly) matches always. That's bad. I'm fixing it; and that will stop Pepe's program working. It was only a fluke before. More in another msg. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On | Behalf Of Pepe Iborra | Sent: 29 March 2007 11:25 | To: Mike Hamburg | Cc: glasgow-haskell-users@haskell.org | Subject: Re: RULES and type classes | | | On 29/03/2007, at 11:38, Mike Hamburg wrote: | | > Is there any way to use RULES substitutions with type classes? | > | > I'm writing a reactive programming arrow (same idea as Yampa, | > different | > design goals), and it would help performance (and not just in the | > speed | > sense) to be able to tell when a value derived with arr hasn't | > changed. | > So I'd like to be able to specialize arr to functions whose result | > is an | > instance of Eq. | > | > I tried | > {-# RULES "reactiveArr/Eq" reactiveArr = reactiveArrEq #-} | > but got the message | > | > Control/Arrow/Reactive/Reactive.hs:89:41: | > No instance for (Eq b) | > arising from instantiating a type signature | > at Control/Arrow/Reactive/Reactive.hs:89:41-89 | > Possible fix: add (Eq b) to the tcRule | > When checking the transformation rule "reactiveArr/Eq" | > | > I tried adding various sorts of type signatures, but I couldn't | > find any | > way around this... is it a restriction in the RULES rewrite | > engine? Is | > there a workaround, or some mechanism other than RULES that I | > should be | > using? I could write a special "arrEq" function, but I'd like to | > minimize the number of extraneous operations outside the Arrow class. | | | I thought this could be done already. In ghc 6.7: | | \begin{code} | {-# RULES "hello/helloBool" hello = helloBool #-} | {-# RULES "hello/helloEq" forall (x::Eq a=>a) . hello x = helloEq x #-} | {-# RULES "hello/helloF" forall (f::Eq b=>a->b) . hello f = helloF f #-} | | data O = O | | hello _ = "hello" | | helloBool :: Bool -> String | helloBool _ = "hello bool" | | helloEq :: Eq a => a -> String | helloEq _ = "hello Eq" | | helloF :: Eq b => (a->b) -> String | helloF _ = "hello F" | | f :: Eq b => String -> b | f = undefined | | normal = hello O | bool = hello False | char = hello 'a'feq :: String | feq = hello (f::String -> Bool) | | \end{code} | | pep:~/code/snippets$ ghc -O -fglasgow-exts -c rules.hs | pep:~/code/snippets$ ghci rules.hs | ___ ___ _ | / _ \ /\ /\/ __(_) | / /_\// /_/ / / | | GHC Interactive, version 6.7.20070303, for | Haskell 98. | / /_\\/ __ / /___| | http://www.haskell.org/ghc/ | \____/\/ /_/\____/|_| Type :? for help. | | Loading package base ... linking ... done. | [1 of 1] Skipping Rules ( rules.hs, rules.o ) | Ok, modules loaded: Rules. | Prelude Rules> normal | "hello" | Prelude Rules> bool | "hello bool" | Prelude Rules> char | "hello Eq" | Prelude Rules> feq | "hello F" | | | Is that what you wanted? | | pepe | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
participants (7)
-
dons＠cse.unsw.edu.au -
Duncan Coutts -
Isaac Dupree -
Mike Hamburg -
Neil Mitchell -
Pepe Iborra -
Simon Peyton-Jones