SYB gone wild - mysterious <<loop>> in code derived from an syb-with-class example

[dsf]

(From  http://www.haskell.org/pipermail/haskell-cafe/2009-December/070193.html)

In the attached code,

1. if you load the code into ghci and evaluate e it will hang, but (defaultValueD dict) :: Expression returns fine
2. if you change the gunfold instance for Proposition to, error "gunfold" it stops hanging -- even though this code is never called.
3. if you change, ( Data ctx [Expression], Sat (ctx Expression) => Data ctx Expression, to (Data ctx Expression, ....) => ... it stops hanging.

If someone could explain why each of these cases perform as they do, that would be awesome! Right now it is a big mystery to me.. e calls dict .. and there is only one instance of dict available, which should call error right away. I can't see how something could get in the way there...

[dsf]

Also affects 6.10.4.

[JeremyShaw]

I compiled with:

ghc -S Bug.hs -ddump-simpl -dsuppress-uniques -dcore-lint

And I get this:

Main.e :: Main.Expression
[GlobalId]
[]
Main.e =
  case $dSat
       `cast` ((Main.:Co:TSat) (Main.DefaultD Main.Expression)
               :: (Main.:TSat) (Main.DefaultD Main.Expression)
                    ~
                  Main.DefaultD Main.Expression)
  of tpl { Main.DefaultD ipv ->
  ipv
  }

Rec {
$dSat :: Main.Sat (Main.DefaultD Main.Expression)
[GlobalId]
[]
$dSat = $dSat
end Rec }

It seems clear that the loop is caused by:

$dSat = $dSat

The question is whether the simplifier is causing the bug, or if the bug already exists after desugaring/type checking, and the simplifier is doing the right thing.

I also tried dumping the output after -ddump-ds. But I have not studied it enough to figure out if it is doing the right thing or not.

This bug has popped up several different ways in our code base. :( Is there something we can do to get it looked at by someone who might understand what is going on?

thanks! - jeremy

[simonpj]

I looked into this again. I know (or at least I think I know) what the problem is. It turns out to be a bug in the guts of the solver (which wasn't originally intended to solve these recursive constraint sets).

I believe it works ok in the HEAD, although I am far from confident that the bug is thoroughly squashed even there.

I'm not keen on burning cycles to fix this, because I'm in the midst of re-engineering the entire solving apparatus.

However, it's bad if you are stuck. As a workaround, can you use the HEAD? (Snapshot builds should be available.)

Simon

[dsf]

We are looking into the feasability of using HEAD - we need to build about 125 packages with it. We just managed this with 6.12.1 today, so I will try to take the next step. Any idea when that fix went in? An older snapshot may be an easier step than the latest.

[simonpj]

I'm afraid I'm not sure when it got fixed in HEAD; indeed I am not entirely sure that it is properly fixed. My guess is that a snapshot from two or three months ago would also work.

It'll all be part of the grand new solver, but I think that won't be ready for a few months.

Let's hope you can use the HEAD, or some snapshot thereof...

Simon

[dsf]

Ok, we have managed to make our way to HEAD! This did indeed resolve the problem in Bug.hs. However, a very similar issue still affects our application (as you suggested it might), and the example, which I have named Bug2.hs, is attached. It still refers to some Happstack modules, if it would be helpful we could expand it so that those imports go away.

[simonpj]

Oh well that disappointing. If you can make Bug2 not depend on Happstack, that'll make it much easier for me to look at.

But realistically, I'm pretty strongly inclined to wait for the new solver. It's hard to motivate myself to look into a Very Dark Corner of the old solver when I'm about to throw it away entirely.

Can you live with that? Months, not weeks. But not years.

Regardless, a cut-down Bug2 would be very very good, because I'll promise to use it as a test case for the new solver; so when it arrives, it'll solve your problem.

Simon

[dsf]

Test case for ghc-6.13, use with attached Default.hs and NewData?.hs

[dsf]

Definitions copied from Happstack.Data.Default for use with Bug2.hs

[dsf]

Definitions copied from Happstack.Data.DeriveAll?, use with Bug2.hs

[dsf]

Yes, we can wait. I have replaced Bug2.hs with a version that uses the attached Default.hs and NewData?.hs modules instead of the modules from Happstack. Perhaps Andrea Vezossi can expand out the syb-with-class stuff in this as he did for Bug.hs.

[Saizan]

with ghc HEAD from a few days ago none of the two test cases hangs anymore.

[simonpj]

Great. We'll regard it as fixed.

Ian: I'd be happier if there was a regression test. I believe that Bug2.hs, Default.hs, and NewData.hs constitute such a test, but I believe that they in turn depend on the syb library.

I don't really know how to put such a test in our regression suite...notably we don't routinely build syb. Maybe we should? (It's stresses the recursive-dictionary apparatus, and is not a big library.) Or maybe it should be in library tests? I'm not sure. Can you decide, and then close? Thanks

Simon

[Saizan]

self-contained version of Bug2

[Saizan]

Bug2.hs used syb-with-class not syb, so i guess it'd be even more complicated.

sybwc-testcase.tar.gz has all the needed sources, which are small, and needs only base to build.

On success running Bug2 should print "Proposition (Conjunction [])", on failure it hangs.

[simonmar]

We can add packages as extra-packages and then add them to the nightly builds for testing. I already do this for deepseq, parallel and stm, and I intend to do it for QuickCheck? too because we have some tests that depend on QuickCheck? and aren't currently being run.

[simonpj]

In this case probably easier just to just the self-contained bundle that saizan attached. But I don't mind either way. Ian, can you action in due course?

Simon

[igloo]

Test added.