[GHC] #13073: BooleanFormula implies is wrong
#13073: BooleanFormula implies is wrong -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 (Type checker) | Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- The current implementation looks like this: {{{ implies :: Eq a => BooleanFormula a -> BooleanFormula a -> Bool x `implies` Var y = x `impliesAtom` y x `implies` And ys = all (implies x . unLoc) ys x `implies` Or ys = any (implies x . unLoc) ys x `implies` Parens y = x `implies` (unLoc y) }}} This cannot possibly be correct: this will decompose the formula A \/ B -> A \/ B in the following way {{{ Or [Var a, Var b] `implies` Or [Var a, Var b] Or [Var a, Var b] `implies` Var a || Or [Var a, Var b] `implies` Var b }}} But neither of the decomposed formulas are true. I didn't find a case in the typechecker where this actually mattered. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13073> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13073: BooleanFormula implies is wrong -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by mpickering): I am fairly sure the only place where `BooleanFormula` is used is `MINIMAL` pragmas but I assume you were trying to use it for something else if you found this bug. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13073#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13073: BooleanFormula implies is wrong -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler (Type | Version: 8.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2925 Wiki Page: | -------------------------------------+------------------------------------- Changes (by ezyang): * status: new => patch * differential: => Phab:D2925 Comment: Yes, implies is never used, only impliesAtom which seems to be implemented correctly. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13073#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13073: BooleanFormula implies is wrong -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.2.1 Component: Compiler (Type | Version: 8.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2925 Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * milestone: => 8.2.1 @@ -21,1 +21,2 @@ - But neither of the decomposed formulas are true. + But neither of the decomposed formulas are true, so GHC will never find a + proof. New description: The current implementation looks like this: {{{ implies :: Eq a => BooleanFormula a -> BooleanFormula a -> Bool x `implies` Var y = x `impliesAtom` y x `implies` And ys = all (implies x . unLoc) ys x `implies` Or ys = any (implies x . unLoc) ys x `implies` Parens y = x `implies` (unLoc y) }}} This cannot possibly be correct: this will decompose the formula A \/ B -> A \/ B in the following way {{{ Or [Var a, Var b] `implies` Or [Var a, Var b] Or [Var a, Var b] `implies` Var a || Or [Var a, Var b] `implies` Var b }}} But neither of the decomposed formulas are true, so GHC will never find a proof. I didn't find a case in the typechecker where this actually mattered. -- -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13073#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13073: BooleanFormula implies is wrong -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.2.1 Component: Compiler (Type | Version: 8.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2925 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Edward Z. Yang <ezyang@…>): In [changeset:"5def07fadd386a7a7c3a12963c0736529e377a74/ghc" 5def07f/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="5def07fadd386a7a7c3a12963c0736529e377a74" Revamp Backpack/hs-boot handling of type class signatures. Summary: A basket of fixes and improvements: - The permissible things that one can write in a type class definition in an hsig file has been reduced to encompass the following things: - Methods - Default method signatures (but NOT implementation) - MINIMAL pragma It is no longer necessary nor encouraged to specify that a method has a default if it is mentioned in a MINIMAL pragma; the MINIMAL pragma is assumed to provide the base truth as to what methods need to be implemented when writing instances of a type class. - Handling of default method signatures in hsig was previously buggy, as these identifiers were not exported, so we now treat them similarly to DFuns. - Default methods are merged, where methods with defaults override those without. - MINIMAL pragmas are merged by ORing together pragmas. - Matching has been relaxed: a method with a default can be used to fill a signature which did not declare the method as having a default, and a more relaxed MINIMAL pragma can be used (we check if the signature pragma implies the final implementation pragma, on the way fixing a bug with BooleanFormula.implies, see #13073) Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: validate Reviewers: simonpj, bgamari, austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2925 GHC Trac Issues: #13041 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13073#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#13073: BooleanFormula implies is wrong -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.2.1 Component: Compiler (Type | Version: 8.1 checker) | Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2925 Wiki Page: | -------------------------------------+------------------------------------- Changes (by ezyang): * status: patch => closed * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13073#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC