Opened 2 years ago

Last modified 2 years ago

#10595 new bug

BuiltinRules override other rules in some cases.

Reported by: gjsimms Owned by:
Priority: high Milestone:
Component: Compiler Version: 7.11
Keywords: Cc: bgamari
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

It seems that the Class op * rules will override a user defined rule for class functions.

This seems to be a long outstanding issue: http://stackoverflow.com/questions/9811294/rewrite-rules-not-firing-for-rules-matching-multiple-instance-methods

I also just ran into someone else on the haskell IRC channel who had an even simpler example then the one on that page:

{-# NOINLINE d #-}
{-# RULES "d exp" d exp = exp #-}
d :: (Double -> Double) -> (Double -> Double)
d f = f . (+20.0)

g :: Double -> Double
g = (+5.0)

main = do
  print $ d exp 1.0     -- FAIL should print 2.718281828459045  >>  printed exp 21.0 instead
  print $ d g 3.0       -- PASS should print 28.0

-- Compiled with:
--   ghc -fenable-rewrite-rules -O rules.hs

Attachments (3)

rulesTest.hs (408 bytes) - added by gjsimms 2 years ago.
Test File #1
rulesTest2.hs (526 bytes) - added by gjsimms 2 years ago.
Rewrite rule is never used
rules.hs (974 bytes) - added by NicX 2 years ago.
Thorough demonstration of issue

Download all attachments as: .zip

Change History (18)

Changed 2 years ago by gjsimms

Attachment: rulesTest.hs added

Test File #1

Changed 2 years ago by gjsimms

Attachment: rulesTest2.hs added

Rewrite rule is never used

comment:1 Changed 2 years ago by gjsimms

Well, I don't really know how to use trac to modify files... Anyway the ruleTest.hs file is a working version (rule gets hit) of example in the description.

ruleTest2.hs is a failing case.

comment:2 Changed 2 years ago by NicX

Seconding gjsimms comment re. rulesTest.hs. That version uses exp' (defined on lines 6-7) instead of exp so the comment on line 13 should say:

-- PASS should print 2.718281828459045

Changed 2 years ago by NicX

Attachment: rules.hs added

Thorough demonstration of issue

comment:3 Changed 2 years ago by gjsimms

Version: 7.10.17.11

Tested this occurs in HEAD on my machine.

I think I have determined why this occurs, I don't see an easy fix offhand. If this is an know issue or if it is not a priority feel free to change the priority/close.

Evaluation of rewrite rules seems to work up the syntax tree (lower leafs will be rewritten before the final expressions).

So given a BuiltinRule for exp (exp -> exp???) and the Rule (f . exp -> exp) for some fixed f.

Processing 1) f . exp 2) (.) f exp Rewrite branches, f has no rule. 3) (.) f exp??? Done, no more rewrites possible.

Some code which I believe demonstrates this correctly. (compile with rewrite rules active)

class A a where 
    ida :: a -> a 
    idb :: a -> a 
 
class B a where 
    idB :: a -> a 

 
instance A Bool where 
    ida _ = False 
    idb _ = True 
 
instance B Bool where 
    idB False = True 
    idB True = False 
 
{-# NOINLINE ida' #-} 
ida' :: A a => a -> a 
ida' = ida 
 
{-# NOINLINE idb' #-} 
idb' :: A a => a -> a 
idb' = idb 
 
{-# RULES 
"SuccessB" forall f. idB (idB f) = idB f 
"Failure1" forall f. ida (ida f) = idb f 
"Failure2" forall f. ida' (ida f) = idb f 
"Success1" forall f. ida (ida' f) = idb f 
"Success2" forall f. ida' (ida' f) = idb' f #-} 
 
main = do 
  print (ida (ida True))  -- FAIL should print True >> prints False 
  print (ida' (ida True)) -- FAIL should print True >> prints False 
  print (ida' (ida' True))  -- PASS should print True 
  print (ida (ida' True)) -- PASS should print TRUE 
  print (idB (idB False))  -- PASS should print True (INLINING may make this run specific it seems consistent on my machine though)

I would appreciate someone more knowledgeable than me checking this out... I have tried forcing BuiltinRules activation on the last step only -- infinite loop in the rewriter during tests (fixes the issue for simple cases).

comment:4 Changed 2 years ago by simonpj

GHC has a crude-but-effective way to control the order of application of rules, called "phases". See the reference to phase control in 7.23.1 in the manual.

Phases count down; currently 2, 1, 0.

Currently, though, a class-method has a built-in rule (selection from dictionary) which is always active. There is no way for the user to override this, to make it active in (say) phase 1 and later. If you could, that would solve your problem.

The only straightforward solution I can see is to make the built-in rule for class methods inactive in phase 2, so that user-written rules take precedence. The trouble with this is that it will delay the moment at which the per-instance functions (which may have rules of their own) become visible.

Rather than attempt a change with global consequences, I suggest that you simply make a new intermediate function, just as you have done with ida'. Instead of NOINLINE you can say INLINE [1] which will inline it in phase 1. Now write your rules for ida'.

This has the effect of delaying the built-in class-method rule for ida without affecting any other functions.

I'll add a paragraph to the user manual about this. And I'll close this as wont-fix, because there is a good workaround and no obviously better design.

Simon

comment:5 Changed 2 years ago by rwbarton

In this case it seems that what we want to do is rewrite the left hand side of the new rule itself. Not sure if this is a good idea in general though.

comment:6 in reply to:  5 ; Changed 2 years ago by simonpj

Replying to rwbarton:

In this case it seems that what we want to do is rewrite the left hand side of the new rule itself. Not sure if this is a good idea in general though.

That sounds delicate and I have no idea what will really happen. The solution I proposed is simple and robust.

comment:7 Changed 2 years ago by gjsimms

I am happy with the workaround/documentation at this point: Just to note, this can be done almost entirely in the Rule system by substituting into temporary functions. So class-methods can be used normally with rewrite rules.

{-# INLINE [1] f' #-}
f' = f
{-# RULES f = f' #-}
{-# RULES (exp1 (f' ...) ...) = exp2) #-}

Long term I think it would be most clear if BuiltinRules had no effect on user supplied rewrite rules.

This does affect some current libraries e.g. all the RULES in Control.Arrow do nothing, I do not know if/how it affects other libraries.

Feel free to close. I do think it is worthwhile making note of in case the simplifier gets overhauled at any point in the future.

ida' idb' above can be inlined in the above (all phases) and the rule will still fire for me, I figure this may be somewhat random.

comment:8 in reply to:  6 Changed 2 years ago by rwbarton

Replying to simonpj:

Replying to rwbarton:

In this case it seems that what we want to do is rewrite the left hand side of the new rule itself. Not sure if this is a good idea in general though.

That sounds delicate and I have no idea what will really happen. The solution I proposed is simple and robust.

Agreed, but when the method in question belongs to a type class defined in another package (as in the original report), this solution is non-modular. A second library that defines d' cannot define a rule for d' exp that coexists with a rule for d exp unless the two libraries agree on a "exp'".

It would be nicer if the rules could somehow refer directly to the-instance-of-exp-for-Double. Of course, this is in feature request territory.

comment:9 Changed 2 years ago by Simon Peyton Jones <simonpj@…>

In 889824dd5ea37adc0fbfe851f724ca9331278664/ghc:

Document RULES and class methods

Relates to Trac #10595

comment:10 Changed 2 years ago by simonpj

Resolution: invalid
Status: newclosed

comment:11 Changed 2 years ago by Simon Peyton Jones <simonpj@…>

In 2d88a531/ghc:

Improve warnings for rules that might not fire

Two main things here

* Previously we only warned about the "head" function of the rule,
  but actually the warning applies to any free variable on the LHS.

* We now warn not only when one of these free vars can inline, but
  also if it has an active RULE (c.f. Trac #10528)

See Note [Rules and inlining/other rules] in Desugar

This actually shows up quite a few warnings in the libraries, notably
in Control.Arrow, where it correctly points out that rules like
    "compose/arr"   forall f g .
                    (arr f) . (arr g) = arr (f . g)
might never fire, because the rule for 'arr' (dictionary selection)
might fire first.  I'm not really sure what to do here; there is some
discussion in Trac #10595.

A minor change is adding BasicTypes.pprRuleName to pretty-print RuleName.

comment:12 Changed 2 years ago by thomie

Resolution: invalid
Status: closednew

HEAD now shows the following warning for the example from the description:

Test.hs:4:11: warning:
    Rule "d exp" may never fire
      because rule "Class op exp" for ‘exp’ might fire first
    Probable fix: add phase [n] or [~n] to the competing rule

That "Probable fix" is not probable at all, because "Class op exp" is a built-in rule.

comment:13 Changed 2 years ago by simonpj

Yes; I don't know what the right design is here, so currently I'm doing nothing. See also #10528.

comment:14 Changed 2 years ago by simonpj

In a1dd7dd/ghc:

(The changeset message doesn't reference this ticket)

The commit message should have said #10595! Typo.

comment:15 Changed 2 years ago by bgamari

Cc: bgamari added
Note: See TracTickets for help on using tickets.