Monadic grammar, threaded lexer, `-a` enabled, but no type signature, fails to compile #94

harpocrates · 2017-08-03T17:07:08Z

I noticed that when I have a monadic grammar with a threaded lexer, generated with ~~(just)~~ -a enabled, and do not include a type signature on a production, I get type errors in the generated code. I don’t think this is the expected behaviour. Here is an example of such a grammar:

-- compileBug.y
%name parse prod

%tokentype { Token }

%monad { P } { bindP } { returnP }
%error { error "parse error" }
%lexer { lexer } { EOF }

%token
  IDENT  { Identifier $$ }

%%

-- Uncommenting the type signature below makes the generated code compile
prod -- :: { () }
  : IDENT { () }

{
data Token = EOF | Identifier String

type P a = String -> (a, String)

bindP :: P a -> (a -> P b) -> P b
bindP p f s = let (x,s') = p s in f x s'

returnP :: a -> P a
returnP = (,)

lexer :: (Token -> P a) -> P a
lexer cont s = cont (case s of { "" -> EOF; _ -> Identifier s }) ""

main = return ()
 }

Without the type signature:

$ happy -a -o compileBug.hs compileBug.y
$ ghc compileBug.hs
[1 of 1] Compiling Main             ( compileBug.hs, compileBug.o )

compileBug.hs:61:17: error:
    • Couldn't match type ‘t4’ with ‘()’
      ‘t4’ is a rigid type variable bound by
        the type signature for:
          happyReduce_1 :: forall t4.
                           Int
                           -> Token
                           -> Int
                           -> Happy_IntList
                           -> HappyStk (HappyAbsSyn t4)
                           -> P (HappyAbsSyn t4)
        at compileBug.hs:60:18
      Expected type: Int
                     -> Token
                     -> Int
                     -> Happy_IntList
                     -> HappyStk (HappyAbsSyn t4)
                     -> P (HappyAbsSyn t4)
        Actual type: Int
                     -> Token
                     -> Int
                     -> Happy_IntList
                     -> HappyStk (HappyAbsSyn ())
                     -> P (HappyAbsSyn ())
    • In the expression: happySpecReduce_1 0 happyReduction_1
      In an equation for ‘happyReduce_1’:
          happyReduce_1 = happySpecReduce_1 0 happyReduction_1
    • Relevant bindings include
        happyReduce_1 :: Int
                         -> Token
                         -> Int
                         -> Happy_IntList
                         -> HappyStk (HappyAbsSyn t4)
                         -> P (HappyAbsSyn t4)
          (bound at compileBug.hs:61:1)
$

With the type signature uncommented:

$ happy -a -o compileBug.hs compileBug.y
$ ghc compileBug.hs
[1 of 1] Compiling Main             ( compileBug.hs, compileBug.o )
Linking compileBug ...
$

Note that this is a regression (I have at least some older version of Happy on which the type signature is not required to generate compiling code). This bug seems present in at least ~~1.19.5 and~~ HEAD.

The text was updated successfully, but these errors were encountered:

Blaisorblade · 2017-09-04T18:21:10Z

@harpocrates Isn't there's a chance this is due to GHC changes?

But I do get superficially similar errors in 1.19.6 over 1.19.5 (details in linked Agda issue). If your bug is with 1.19.5, however, it might be a different one (sorry, can't tell right now).

harpocrates · 2017-09-04T21:32:17Z

@Blaisorblade I just double-checked again and you are right - I can only trigger the bug with HEAD, not 1.19.5. I'll try to do a git-bisect and report back.

That said, are you compiling happy with only -a? I was able to avoid this bug by adding type signatures or also enabling -gc.

Blaisorblade · 2017-09-04T21:44:41Z

I'm somewhat clueless honestly—Agda build seems to use happy in as default a way as possible. I could only tell my symptoms were somewhat similar.

I just installed happy, tried building Agda and did a report, and this was the only issue that seemed relevant — people on the linked agda issue (agda/agda#2731) might have a clue on their side.

I mean, the whole config is https://github.com/agda/agda/blob/4ea8f42f3c9f517750127a03f5c4cacb89c63997/Agda.cabal#L320, which tells cabal to build https://github.com/agda/agda/blob/release-2.5.2/src/full/Agda/Syntax/Parser/Parser.y automatically (using support documented here: https://www.haskell.org/cabal/users-guide/developing-packages.html).

Blaisorblade · 2017-09-04T21:51:18Z

Update: the output uses unsafeCoerce#, mentions GHC and uses Data.Array — suggesting (to ignorant me who skimmed https://www.haskell.org/happy/doc/html/sec-invoking.html) that cabal might be enabling -agc automatically for speed.

#include "undefined.h"
import qualified Data.Array as Happy_Data_Array
import qualified Data.Bits as Bits
import qualified GHC.Exts as Happy_GHC_Exts
import Control.Applicative(Applicative(..))
import Control.Monad (ap)

-- parser produced by Happy Version 1.19.6

newtype HappyAbsSyn t13 t14 t15 t38 t41 t44 t45 t46 t54 t55 t84 = HappyAbsSyn HappyAny
#if __GLASGOW_HASKELL__ >= 607
type HappyAny = Happy_GHC_Exts.Any
#else
type HappyAny = forall a . a
#endif
happyIn9 :: ([Token]) -> (HappyAbsSyn t13 t14 t15 t38 t41 t44 t45 t46 t54 t55 t84)
happyIn9 x = Happy_GHC_Exts.unsafeCoerce# x
{-# INLINE happyIn9 #-}

EDIT: also, forgot to thank you for your quick followup investigation!

harpocrates · 2017-09-04T22:08:29Z

Alright. I did some bisecting (using the above sample file compileBug.y) and it looks like the bug was indeed introduced after 1.19.5.

The last working commit is 6ad73f2.
Afterwards, there are two commits 00d561c and 35a5a19 for which the error message is different.

$ happy -a -o compileBug.hs compileBug.y
$ ghc compileBug.hs
[1 of 1] Compiling Main             ( compileBug.hs, compileBug.o )

compileBug.hs:60:73: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘HappyStk’, namely ‘HappyAbsSyn’
      In the type signature:
        happyReduce_1 :: Int
                         -> Token
                            -> Int -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn

compileBug.hs:60:90: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘P’, namely ‘HappyAbsSyn’
      In the type signature:
        happyReduce_1 :: Int
                         -> Token
                            -> Int -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn

compileBug.hs:89:30: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘P’, namely ‘HappyAbsSyn’
      In the type signature:
        happyParse :: Int -> P HappyAbsSyn

compileBug.hs:91:57: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘HappyStk’, namely ‘HappyAbsSyn’
      In the type signature:
        happyNewToken :: Int
                         -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn

compileBug.hs:91:74: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘P’, namely ‘HappyAbsSyn’
      In the type signature:
        happyNewToken :: Int
                         -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn

compileBug.hs:93:73: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘HappyStk’, namely ‘HappyAbsSyn’
      In the type signature:
        happyDoAction :: Int
                         -> Token
                            -> Int -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn

compileBug.hs:93:90: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘P’, namely ‘HappyAbsSyn’
      In the type signature:
        happyDoAction :: Int
                         -> Token
                            -> Int -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn

compileBug.hs:95:102: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘HappyStk’, namely ‘HappyAbsSyn’
      In the second argument of ‘Happy_Data_Array.Array’, namely
        ‘Int
         -> Token
            -> Int -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn’
      In the type signature:
        happyReduceArr :: Happy_Data_Array.Array Int (Int
                                                      -> Token
                                                         -> Int
                                                            -> Happy_IntList
                                                               -> HappyStk HappyAbsSyn
                                                                  -> P HappyAbsSyn)

compileBug.hs:95:119: error:
    • Expecting one more argument to ‘HappyAbsSyn’
      Expected a type, but ‘HappyAbsSyn’ has kind ‘* -> *’
    • In the first argument of ‘P’, namely ‘HappyAbsSyn’
      In the second argument of ‘Happy_Data_Array.Array’, namely
        ‘Int
         -> Token
            -> Int -> Happy_IntList -> HappyStk HappyAbsSyn -> P HappyAbsSyn’
      In the type signature:
        happyReduceArr :: Happy_Data_Array.Array Int (Int
                                                      -> Token
                                                         -> Int
                                                            -> Happy_IntList
                                                               -> HappyStk HappyAbsSyn
                                                                  -> P HappyAbsSyn)

Finally, commit c00e6dc introduces the current (buggy) behaviour:

$ happy -a -o compileBug.hs compileBug.y
$ ghc compileBug.hs
[1 of 1] Compiling Main             ( compileBug.hs, compileBug.o )

compileBug.hs:61:17: error:
    • Couldn't match type ‘t4’ with ‘()’
      ‘t4’ is a rigid type variable bound by
        the type signature for:
          happyReduce_1 :: forall t4.
                           Int
                           -> Token
                           -> Int
                           -> Happy_IntList
                           -> HappyStk (HappyAbsSyn t4)
                           -> P (HappyAbsSyn t4)
        at compileBug.hs:60:18
      Expected type: Int
                     -> Token
                     -> Int
                     -> Happy_IntList
                     -> HappyStk (HappyAbsSyn t4)
                     -> P (HappyAbsSyn t4)
        Actual type: Int
                     -> Token
                     -> Int
                     -> Happy_IntList
                     -> HappyStk (HappyAbsSyn ())
                     -> P (HappyAbsSyn ())
    • In the expression: happySpecReduce_1 0 happyReduction_1
      In an equation for ‘happyReduce_1’:
          happyReduce_1 = happySpecReduce_1 0 happyReduction_1
    • Relevant bindings include
        happyReduce_1 :: Int
                         -> Token
                         -> Int
                         -> Happy_IntList
                         -> HappyStk (HappyAbsSyn t4)
                         -> P (HappyAbsSyn t4)
          (bound at compileBug.hs:61:1)

Here is what happened over the course of those three commits.

Blaisorblade · 2017-09-05T02:02:25Z

So those commits are from #49. The PR allows me to form an initial hypothesis. I have a million question marks and details won't be quite right, but hope this helps and isn't too much nonsense.

@simonmar, @emc2, does that make sense?

This pull requests causes happy to generate some new signatures that allow typeclasses to be used in monadic parsers. This makes no changes to actual code; it only generates some signatures.

For our purposes, we can simplify the failed generated code to the following incorrect code:

v :: t13
v = ()

Though my real output is closer to the following (where only t13 matters):

happyReduce_114 :: () => Happy_GHC_Exts.Int# -> Token -> Happy_GHC_Exts.Int# -> Happy_IntList -> HappyStk (HappyAbsSyn t13 t14 t15 t38 t41 t44 t45 t46 t54 t55 t84) -> Parser (HappyAbsSyn t13 t14 t15 t38 t41 t44 t45 t46 t54 t55 t84)
happyReduce_114 = happySpecReduce_0  4# happyReduction_114
happyReduction_114  =  happyIn13 (())

happyIn13 :: t13 -> (HappyAbsSyn t13 t14 t15 t38 t41 t44 t45 t46 t54 t55 t84)
happyIn13 x = Happy_GHC_Exts.unsafeCoerce# x

Before, no type declaration was generated—now the above is generated. If you declare a return type () for your production, the generated code will not use t13 as above, so it won't demand that () has type t13 and will compile.

A problem we are seeing is just that happy does NOT infer the return type of productions — it didn't need to before. The patch seems to assume that those parsers must be universally quantified. That's not good.

It's also not clear to me why using type classes requires generating signatures. I can only see it requires disabling the monomorphism restriction if you have definitions without arguments.

==

The PR suggests it affects parser specifying a monad and a lexer, like both your example and mine:

This patch only generates signature for parsers that combine %monad and %lexer directives. There appear to be some non-trivial issues that arise when %monad is used without %lexer.

We added the signatures following a suggestion by Paolo G. Giarrusso. See also haskell/happy#94.

simonmar · 2017-09-05T06:28:34Z

@emc2 could you take a look at this please?

Blaisorblade · 2017-09-05T20:28:53Z

That said, are you compiling happy with only -a? I was able to avoid this bug by adding type signatures or also enabling -gc.

@harpocrates I was confused because I suffered the bug but I have -agc all enabled, maybe the mismatch is because you were using merged but unreleased PR #97 ? Not sure why though.

harpocrates · 2017-09-05T20:41:03Z

@Blaisorblade I think #97 was indeed the interfering problem I had. I ran into several problems all at once and had some difficulty initially separating them in my bug reports :). I just checked and I can reproduce the bug with -a, -agc, but not without -a.

To set the record straight and avoid any more confusion: you need at least -a to trigger this bug and the workaround is to add type signatures everywhere. Correct?

Also, to back up your comment

It's also not clear to me why using type classes requires generating signatures. I can only see it requires disabling the monomorphism restriction if you have definitions without arguments.

I actually did precisely this a while ago and it worked fine with Happy 1.19.5.

Blaisorblade · 2017-09-05T20:53:10Z

To set the record straight and avoid any more confusion: you need at least -a to trigger this bug and the workaround is to add type signatures everywhere. Correct?

Haven't checked the 1st part myself, but agda/agda@888cb9a seems to confirm that this workaround indeed works.

(To be sure, my understanding of this is very shallow and built very lazily — apologies for any nonsense).

It's also not clear to me why using type classes requires generating signatures. I can only see it requires disabling the monomorphism restriction if you have definitions without arguments.

I actually did precisely this a while ago and it worked fine with Happy 1.19.5.

OK, so the silly question is: could one revert that patch, enable the monomorphism restriction or suggest that users enable it, and remove the regression? I'll leave the answer to somebody with more clue. Luckily, #49 includes some tests, so it should be easy to verify this works.

I do understand there are downsides to disabling the monomorphism restriction: the generated class constraint might turn a one-time computation into something that is regenerated at each call, even if you always use a single monad. But I doubt this is relevant here: adding signatures does not improve performance, it just silences a warning.
I also hope we don't need to disable the monomorphism restrictions on compilers that don't get the GHC syntax for it?

simonmar · 2017-09-08T11:28:17Z

Should I just revert the offending commits here?

Blaisorblade · 2017-09-08T14:19:22Z

@simonmar That makes sense to me — just please, don't take my word for it as explained :-). @harpocrates ?

harpocrates · 2017-09-14T19:29:20Z

I've been thinking about what we could do to fix this, but nothing simple comes to mind. The only easy fix is reverting. Here are some other more constructive ideas:

only generate the signatures added by (Add signature generation for using typeclasses in parsers #49) when all productions have type signatures (grammars that rely on this feature currently must already have type signatures everywhere, else they would have hit this bug - so no breakage).
for versions of GHC >= 7.10.3, use -XPartialTypeSignatures and put in _ wildcards instead of type variables in a handful of places (as @Blaisorblade has said, these should be inferred instead of universally quantified). I've tried this manually and it seems to work just fine. Again, this maintains backwards compatibility.

The first bullet point is the simplest to implement, and pretty tidy IMO. Seems like a net gain compared to just reverting.

That said, it also means that as soon as you are missing even just one signature, you fall off a cliff and the generated code will suddenly have a lot less signatures and won't support type classes without enabling -XNoMonomorphismRestriction. The second bullet point would address that problem, but only for grammars with --ghc enabled, and on new enough versions of GHC.

Thoughts @simonmar? FWIW, I'd be willing to put together a quick PR for the first point, just to fix the breakage this is causing.

* for versions of GHC >= 7.10.3, use `-XPartialTypeSignatures` and put in `_` wildcards instead of type variables for the type variables on `HappyAbsSyn` * otherwise, only generate problematic signatures when all productions have type signatures

ilovezfs · 2017-10-08T07:00:39Z

@simonmar a gentle ping on this.

Blaisorblade mentioned this issue Sep 4, 2017

Agda fails to build with happy 1.19.6 agda/agda#2731

Closed

asr added a commit to agda/agda that referenced this issue Sep 5, 2017

[ fixed #2731 ] Added missing type signatures to the productions.

888cb9a

We added the signatures following a suggestion by Paolo G. Giarrusso. See also haskell/happy#94.

harpocrates mentioned this issue Sep 11, 2017

New generated type signatures are overly general and cause type errors #104

Closed

harpocrates mentioned this issue Sep 15, 2017

Issue 94 #106

Merged

This was referenced Oct 7, 2017

hopenpgp-tools does not build from source Homebrew/homebrew-core#19041

Closed

cryptol fails to build due to happy commercialhaskell/stackage#2927

Closed

hvr mentioned this issue Oct 9, 2017

happy-1.19.6/1.19.7 haskell-infra/hackage-trustees#115

Closed

simonmar closed this as completed in #106 Oct 9, 2017

athas mentioned this issue Dec 20, 2017

GHC takes a very long time to compile parser generated by Happy 1.19.8 compared to Happy 1.19.5 #109

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Monadic grammar, threaded lexer, `-a` enabled, but no type signature, fails to compile #94

Monadic grammar, threaded lexer, `-a` enabled, but no type signature, fails to compile #94

harpocrates commented Aug 3, 2017 •

edited

Loading

Blaisorblade commented Sep 4, 2017

harpocrates commented Sep 4, 2017

Blaisorblade commented Sep 4, 2017

Blaisorblade commented Sep 4, 2017 •

edited

Loading

harpocrates commented Sep 4, 2017

Blaisorblade commented Sep 5, 2017

simonmar commented Sep 5, 2017

Blaisorblade commented Sep 5, 2017

harpocrates commented Sep 5, 2017 •

edited

Loading

Blaisorblade commented Sep 5, 2017

simonmar commented Sep 8, 2017

Blaisorblade commented Sep 8, 2017

harpocrates commented Sep 14, 2017

ilovezfs commented Oct 8, 2017

Monadic grammar, threaded lexer, -a enabled, but no type signature, fails to compile #94

Monadic grammar, threaded lexer, -a enabled, but no type signature, fails to compile #94

Comments

harpocrates commented Aug 3, 2017 • edited Loading

Blaisorblade commented Sep 4, 2017

harpocrates commented Sep 4, 2017

Blaisorblade commented Sep 4, 2017

Blaisorblade commented Sep 4, 2017 • edited Loading

harpocrates commented Sep 4, 2017

Blaisorblade commented Sep 5, 2017

simonmar commented Sep 5, 2017

Blaisorblade commented Sep 5, 2017

harpocrates commented Sep 5, 2017 • edited Loading

Blaisorblade commented Sep 5, 2017

simonmar commented Sep 8, 2017

Blaisorblade commented Sep 8, 2017

harpocrates commented Sep 14, 2017

ilovezfs commented Oct 8, 2017

Monadic grammar, threaded lexer, `-a` enabled, but no type signature, fails to compile #94

Monadic grammar, threaded lexer, `-a` enabled, but no type signature, fails to compile #94

harpocrates commented Aug 3, 2017 •

edited

Loading

Blaisorblade commented Sep 4, 2017 •

edited

Loading

harpocrates commented Sep 5, 2017 •

edited

Loading