Opened 9 years ago

Closed 6 years ago

#3108 closed bug (fixed)

Do a better job of solving recursive type-class constraints with functional dependencies

Reported by: simonpj Owned by:
Priority: high Milestone: 7.6.1
Component: Compiler (Type checker) Version: 6.10.1
Keywords: Cc: dimitris@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: typecheck/should_compile/T3108.hs
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

This ticket is just to track this interesting thread on the Haskell list, concerning recursive type-class constraints: http://www.haskell.org/pipermail/haskell/2009-March/021115.html. We might want to get back to this when the new constraint solver is in place.

The question concerns the interaction of solving recursive type-class constraints, where it is important to aggressively apply functional dependencies. Here's Tom Schrijvers's analysis of Ralf's example:

"The cyclic dictionaries approach is a bit fragile. The problem appears to be here that GHC alternates exhaustive phases of constraint reduction and functional dependency improvement. The problem is that in your example you need both for detecting a cycle.

This can happen:

        C1 Int
        ==> 3rd C1 inst
        C2 Int y, C1 (y,Bool)
        ==> 1st C1 inst
        C2 Int y, C1 y, C1 Bool
        ==> 2nd C1 inst
        C2 Int y, C1 y
        ==> 3rd C1 inst
        C2 Int y, C2 y z, C1 (z,Bool)
        ==>
        ...

where all the constraint are different because fresh variables are introduced.

What you want to happen is:

        C1 Int
        ==> 3rd C1 inst
        C2 Int y, C1 (y,Bool)
        ==> 1st C1 inst
        C2 Int y, C1 y, C1 Bool
        ==> 2nd C1 inst
        C2 Int y, C1 y
        ==> C2 FD improvement {Int/y}  <<<<
        C2 Int Int, C1 Int
        ==> C1 Int cycle detected
        C2 Int Int
        ==> C2 1st instance
        {}

It seems that you want improvement to happen at a higher priority than GHC does now."

Change History (11)

comment:1 Changed 8 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:2 Changed 7 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:3 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:4 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:5 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:6 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:7 Changed 6 years ago by simonpj

Cc: dimitris@… added
Priority: lowesthigh
Type of failure: None/Unknown

With the new constraint solver we an ASSERT error for this program:

{-# LANGUAGE OverlappingInstances, UndecidableInstances, MultiParamTypeClasses, 
             FunctionalDependencies, FlexibleInstances #-}

module T3108 where

-- Direct recursion terminates (typechecking-wise)

class C0 x
 where
 m0 :: x -> ()
 m0 = const undefined

instance (C0 x, C0 y) => C0 (x,y)
instance C0 Bool
instance C0 (x,Bool) => C0 x

foo :: ()
foo = m0 (1::Int)


-- Indirect recursion does not terminate (typechecking-wise)

class C1 x
 where
 m1 :: x -> ()
 m1 = const undefined

instance (C1 x, C1 y) => C1 (x,y)
instance C1 Bool
instance (C2 x y, C1 (y,Bool)) => C1 x

class C2 x y | x -> y
instance C2 Int Int

-- It is this declaration that causes nontermination of typechecking.
bar :: ()
bar = m1 (1::Int)

Thus:

simonpj@cam-05-unx:~/tmp$ ~/5builds/HEAD/inplace/bin/ghc-stage1 -c T3108.hs -dcore-lint -fforce-recomp
setEvBind
    Cycle in evidence binds, evvar = $dC1{v aep} [lid]
    {$dC1{v adw} [lid]
       = main:T3108.$fC1x{v r1} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                     y{tv aej} [tcs]]
                                                   [$dC2{v aek} [lid], $dC1{v ael} [lid]],
     $dC2{v aek} [lid]
       = $dC2{v aeo} [lid] `cast` (main:T3108.C2{tc r7}
                                     <ghc-prim:GHC.Types.Int{(w) tc 3J}> (Sym cobox{v aen} [lid])),
     $dC1{v ael} [lid]
       = $dC1{v aep} [lid] `cast` (main:T3108.C1{tc r9}
                                     (Sym cobox{v aen} [lid],
                                      <ghc-prim:GHC.Types.Bool{(w) tc 3c}>)),
     cobox{v aen} [lid] = CO <ghc-prim:GHC.Types.Int{(w) tc 3J}>,
     $dC2{v aeo} [lid]
       = main:T3108.$fC2IntInt{v r0} [lidx[DFunId]] @[] [],
     $dC1{v aep} [lid]
       = main:T3108.$fC1(,){v r3} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                       ghc-prim:GHC.Types.Bool{(w) tc 3c}]
                                                     [$dC1{v adw} [lid], $dC1{v aeq} [lid]]}
setEvBind
    Cycle in evidence binds, evvar = $dC0{v aer} [lid]
    {$dC1{v adw} [lid]
       = main:T3108.$fC1x{v r1} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                     y{tv aej} [tcs]]
                                                   [$dC2{v aek} [lid], $dC1{v ael} [lid]],
     $dC0{v ady} [lid]
       = main:T3108.$fC0x{v r4} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J}]
                                                   [$dC0{v aer} [lid]],
     $dC2{v aek} [lid]
       = $dC2{v aeo} [lid] `cast` (main:T3108.C2{tc r7}
                                     <ghc-prim:GHC.Types.Int{(w) tc 3J}> (Sym cobox{v aen} [lid])),
     $dC1{v ael} [lid]
       = $dC1{v aep} [lid] `cast` (main:T3108.C1{tc r9}
                                     (Sym cobox{v aen} [lid],
                                      <ghc-prim:GHC.Types.Bool{(w) tc 3c}>)),
     cobox{v aen} [lid] = CO <ghc-prim:GHC.Types.Int{(w) tc 3J}>,
     $dC2{v aeo} [lid]
       = main:T3108.$fC2IntInt{v r0} [lidx[DFunId]] @[] [],
     $dC1{v aep} [lid]
       = main:T3108.$fC1(,){v r3} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                       ghc-prim:GHC.Types.Bool{(w) tc 3c}]
                                                     [$dC1{v adw} [lid], $dC1{v aeq} [lid]],
     $dC1{v aeq} [lid]
       = main:T3108.$fC1Bool{v r2} [lidx[DFunId(nt)]] @[] [],
     $dC0{v aer} [lid]
       = main:T3108.$fC0(,){v r6} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                       ghc-prim:GHC.Types.Bool{(w) tc 3c}]
                                                     [$dC0{v ady} [lid], $dC0{v aes} [lid]]}
simonpj@cam-05-unx:~/tmp$ ~/5builds/HEAD/inplace/bin/ghc-stage1 -c T3108.hs -dcore-lint -fforce-recomp
setEvBind
    Cycle in evidence binds, evvar = $dC1{v aep} [lid]
    {$dC1{v adw} [lid]
       = main:T3108.$fC1x{v r1} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                     y{tv aej} [tcs]]
                                                   [$dC2{v aek} [lid], $dC1{v ael} [lid]],
     $dC2{v aek} [lid]
       = $dC2{v aeo} [lid] `cast` (main:T3108.C2{tc r7}
                                     <ghc-prim:GHC.Types.Int{(w) tc 3J}> (Sym cobox{v aen} [lid])),
     $dC1{v ael} [lid]
       = $dC1{v aep} [lid] `cast` (main:T3108.C1{tc r9}
                                     (Sym cobox{v aen} [lid],
                                      <ghc-prim:GHC.Types.Bool{(w) tc 3c}>)),
     cobox{v aen} [lid] = CO <ghc-prim:GHC.Types.Int{(w) tc 3J}>,
     $dC2{v aeo} [lid]
       = main:T3108.$fC2IntInt{v r0} [lidx[DFunId]] @[] [],
     $dC1{v aep} [lid]
       = main:T3108.$fC1(,){v r3} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                       ghc-prim:GHC.Types.Bool{(w) tc 3c}]
                                                     [$dC1{v adw} [lid], $dC1{v aeq} [lid]]}
setEvBind
    Cycle in evidence binds, evvar = $dC0{v aer} [lid]
    {$dC1{v adw} [lid]
       = main:T3108.$fC1x{v r1} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                     y{tv aej} [tcs]]
                                                   [$dC2{v aek} [lid], $dC1{v ael} [lid]],
     $dC0{v ady} [lid]
       = main:T3108.$fC0x{v r4} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J}]
                                                   [$dC0{v aer} [lid]],
     $dC2{v aek} [lid]
       = $dC2{v aeo} [lid] `cast` (main:T3108.C2{tc r7}
                                     <ghc-prim:GHC.Types.Int{(w) tc 3J}> (Sym cobox{v aen} [lid])),
     $dC1{v ael} [lid]
       = $dC1{v aep} [lid] `cast` (main:T3108.C1{tc r9}
                                     (Sym cobox{v aen} [lid],
                                      <ghc-prim:GHC.Types.Bool{(w) tc 3c}>)),
     cobox{v aen} [lid] = CO <ghc-prim:GHC.Types.Int{(w) tc 3J}>,
     $dC2{v aeo} [lid]
       = main:T3108.$fC2IntInt{v r0} [lidx[DFunId]] @[] [],
     $dC1{v aep} [lid]
       = main:T3108.$fC1(,){v r3} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                       ghc-prim:GHC.Types.Bool{(w) tc 3c}]
                                                     [$dC1{v adw} [lid], $dC1{v aeq} [lid]],
     $dC1{v aeq} [lid]
       = main:T3108.$fC1Bool{v r2} [lidx[DFunId(nt)]] @[] [],
     $dC0{v aer} [lid]
       = main:T3108.$fC0(,){v r6} [lidx[DFunId(nt)]] @[ghc-prim:GHC.Types.Int{(w) tc 3J},
                                                       ghc-prim:GHC.Types.Bool{(w) tc 3c}]
                                                     [$dC0{v ady} [lid], $dC0{v aes} [lid]]}

comment:8 Changed 6 years ago by simonpj

Turns out that the new constraint solver is doing the Right Thing; but it has a pprTrace that emits messages when it should not.

Dimitrios, can you

  • Commit the fix to pprTrace?
  • Add the above program to the testsuite, in typecheck/should_compile?

Thanks

Simon

comment:9 Changed 6 years ago by dimitris

Test Case: typecheck/should_compile/T3108.hs

Done, part of the bigger commit: f15977c24f2ec96ea324cc7e8122f17ffe8b931c Also test added in typecheck/should_compile.

comment:10 Changed 6 years ago by simonmar

dimitris: you left the ticket open, should it be closed now?

comment:11 Changed 6 years ago by dimitris

Resolution: fixed
Status: newclosed

Yes, fixed. Sorry.

Note: See TracTickets for help on using tickets.