StrictData and the parser

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

StrictData and the parser

Adam Sandberg Eriksson
Hello *,

I'm working on the -XStrict language extension[1] for this years Google
summer of code. I've started with the smaller -XStrictData (as
documented at the wiki) and have the internals mostly figured out.

However after adding relevant rules for '~' in the parser[2] I get an
explosion of shift/reduce conflicts as well as 4 extra reduce/reduce
conflicts, see [3] for the happy info (the states with 36 shift/reduce
conflicts seem to be the problematic ones), I also fail to parse the
test file [4] with the error

DsStrictData.hs:15:1: error:
    parse error (possibly incorrect indentation or mismatched brackets)

Can anyone offer some guidance on what the appropriate changes to the
parser are to make these "lazyness" marks work?

Thanks,
Adam

[1]: https://ghc.haskell.org/trac/ghc/wiki/StrictPragma
[2]:
https://github.com/adamse/ghc/blob/strict-pragma/compiler/parser/Parser.y#L1547-L1563
[3]:
https://gist.githubusercontent.com/adamse/8d6c54b6ae660fca8b97/raw/detailed-info
[4]:
https://github.com/adamse/ghc/blob/strict-pragma/testsuite/tests/deSugar/should_run/DsStrictData.hs#L13
--
Adam Sandberg Eriksson
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: StrictData and the parser

Edward Z. Yang
Hello Adam,

At a guess, ~ is ambiguous with the type equality syntax a ~ b.
You'll probably have to add a new production for types (similar
to atype) which are at the top level of a data constructor definition.

I recently wrote some documentation on how to interpret Happy
info files.  There hasn't been a release yet but the docs
are here:
https://github.com/ezyang/happy/commit/daf84f5aa6f6453a118944f77393537f323d1adb

Cheers,
Edward

Excerpts from Adam Sandberg Eriksson's message of 2015-06-04 12:52:02 -0700:

> Hello *,
>
> I'm working on the -XStrict language extension[1] for this years Google
> summer of code. I've started with the smaller -XStrictData (as
> documented at the wiki) and have the internals mostly figured out.
>
> However after adding relevant rules for '~' in the parser[2] I get an
> explosion of shift/reduce conflicts as well as 4 extra reduce/reduce
> conflicts, see [3] for the happy info (the states with 36 shift/reduce
> conflicts seem to be the problematic ones), I also fail to parse the
> test file [4] with the error
>
> DsStrictData.hs:15:1: error:
>     parse error (possibly incorrect indentation or mismatched brackets)
>
> Can anyone offer some guidance on what the appropriate changes to the
> parser are to make these "lazyness" marks work?
>
> Thanks,
> Adam
>
> [1]: https://ghc.haskell.org/trac/ghc/wiki/StrictPragma
> [2]:
> https://github.com/adamse/ghc/blob/strict-pragma/compiler/parser/Parser.y#L1547-L1563
> [3]:
> https://gist.githubusercontent.com/adamse/8d6c54b6ae660fca8b97/raw/detailed-info
> [4]:
> https://github.com/adamse/ghc/blob/strict-pragma/testsuite/tests/deSugar/should_run/DsStrictData.hs#L13
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: StrictData and the parser

Brandon Allbery
In reply to this post by Adam Sandberg Eriksson
On Thu, Jun 4, 2015 at 3:52 PM, Adam Sandberg Eriksson <[hidden email]> wrote:
However after adding relevant rules for '~' in the parser[2] I get an
explosion of shift/reduce conflicts as well as 4 extra reduce/reduce
conflicts, see [3] for the happy info (the states with 36 shift/reduce
conflicts seem to be the problematic ones)

Looks to me like it's confused about whether a ~ is part of an equality constraint or is a laziness annotation. The former would be illegal at that point, though, I'd think? Somewhere it believes a constraint might be possible there, via btype.

As ezyang says in the message I see just came in, you'll need extra production rules to distinguish that top level. Although I'd wonder why it believes an equality constraint is acceptable there in the first place; is that a lurking bug in the parser?

--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: StrictData and the parser

Edward Z. Yang
Excerpts from Brandon Allbery's message of 2015-06-04 13:06:52 -0700:
> Looks to me like it's confused about whether a ~ is part of an equality
> constraint or is a laziness annotation. The former would be illegal at that
> point, though, I'd think? Somewhere it believes a constraint might be
> possible there, via btype.
>
> As ezyang says in the message I see just came in, you'll need extra
> production rules to distinguish that top level. Although I'd wonder why it
> believes an equality constraint is acceptable there in the first place; is
> that a lurking bug in the parser?

In general, the parser is more liberal than is actually required; we
can give better error messages this way.

Second, here is where it's ambiguous:

    T a ~b

where T is a TyCon.  Does this parse as

    T a (~b)

or

    T a ~ b

Parser doesn't currently distinguish these cases.

Edward
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: StrictData and the parser

Simon Peyton Jones
In reply to this post by Adam Sandberg Eriksson
You need to understand why the shift/reduce conflicts are happening.  Happy has a flag that makes it dump out the state transition tables, and you have to look at them.  there probably is some genuine ambiguity.

Simon

| -----Original Message-----
| From: ghc-devs [mailto:[hidden email]] On Behalf Of Adam
| Sandberg Eriksson
| Sent: 04 June 2015 20:52
| To: [hidden email]; [hidden email]
| Subject: StrictData and the parser
|
| Hello *,
|
| I'm working on the -XStrict language extension[1] for this years Google
| summer of code. I've started with the smaller -XStrictData (as
| documented at the wiki) and have the internals mostly figured out.
|
| However after adding relevant rules for '~' in the parser[2] I get an
| explosion of shift/reduce conflicts as well as 4 extra reduce/reduce
| conflicts, see [3] for the happy info (the states with 36 shift/reduce
| conflicts seem to be the problematic ones), I also fail to parse the
| test file [4] with the error
|
| DsStrictData.hs:15:1: error:
|     parse error (possibly incorrect indentation or mismatched brackets)
|
| Can anyone offer some guidance on what the appropriate changes to the
| parser are to make these "lazyness" marks work?
|
| Thanks,
| Adam
|
| [1]: https://ghc.haskell.org/trac/ghc/wiki/StrictPragma
| [2]:
| https://github.com/adamse/ghc/blob/strict-
| pragma/compiler/parser/Parser.y#L1547-L1563
| [3]:
| https://gist.githubusercontent.com/adamse/8d6c54b6ae660fca8b97/raw/detail
| ed-info
| [4]:
| https://github.com/adamse/ghc/blob/strict-
| pragma/testsuite/tests/deSugar/should_run/DsStrictData.hs#L13
| --
| Adam Sandberg Eriksson
| _______________________________________________
| ghc-devs mailing list
| [hidden email]
| http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: StrictData and the parser

Johan Tibell-2
In reply to this post by Edward Z. Yang
On Thu, Jun 4, 2015 at 10:30 PM, Edward Z. Yang <[hidden email]> wrote:
Excerpts from Brandon Allbery's message of 2015-06-04 13:06:52 -0700:
> Looks to me like it's confused about whether a ~ is part of an equality
> constraint or is a laziness annotation. The former would be illegal at that
> point, though, I'd think? Somewhere it believes a constraint might be
> possible there, via btype.
>
> As ezyang says in the message I see just came in, you'll need extra
> production rules to distinguish that top level. Although I'd wonder why it
> believes an equality constraint is acceptable there in the first place; is
> that a lurking bug in the parser?

In general, the parser is more liberal than is actually required; we
can give better error messages this way.

Second, here is where it's ambiguous:

    T a ~b

where T is a TyCon.  Does this parse as

    T a (~b)

or

    T a ~ b

Parser doesn't currently distinguish these cases.

I guess we should parse it as T a (~b), just as we have unary minus bind "tighter" with the following token.
 

Edward
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: StrictData and the parser

Edward Z. Yang
Excerpts from Johan Tibell's message of 2015-06-04 16:52:30 -0700:
> I guess we should parse it as T a (~b), just as we have unary minus bind
> "tighter" with the following token.

Not in all contexts.

It is true that if you have 'data SLPair a b = SLP a ~ b' you want to
parse 'SLP a (~b)'

But if you have 'Maybe a ~ b' you want to parse '(Maybe a) ~ b'.

But in GADTs, if you have

    data SLPair a b where
        SLP :: a -> ~ b -> SLPair a b

you want a -> (~ b) -> SLPair a b

If the twiddle is not immediately after an arrow you don't want
that, e.g.

    data T a b where
        T :: a -> a ~ b -> SLPair a b

you want T :: a -> (a ~ b) -> SLPair a b

Edward
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: StrictData and the parser

Simon Peyton Jones
There is some similar stuff in GHC already, to do with "!".  It is both an infix operator and (in some contexts) a unary prefix to a function argument
        f !x y = ...rhs...
See RdrHsSyn.splitBang.

Just possibly the same kind of stuff will help with "~"?

S

|  -----Original Message-----
|  From: ghc-devs [mailto:[hidden email]] On Behalf Of
|  Edward Z. Yang
|  Sent: 05 June 2015 01:08
|  To: Johan Tibell
|  Cc: "[hidden email]"
|  Subject: Re: StrictData and the parser
|  
|  Excerpts from Johan Tibell's message of 2015-06-04 16:52:30 -0700:
|  > I guess we should parse it as T a (~b), just as we have unary minus
|  > bind "tighter" with the following token.
|  
|  Not in all contexts.
|  
|  It is true that if you have 'data SLPair a b = SLP a ~ b' you want to
|  parse 'SLP a (~b)'
|  
|  But if you have 'Maybe a ~ b' you want to parse '(Maybe a) ~ b'.
|  
|  But in GADTs, if you have
|  
|      data SLPair a b where
|          SLP :: a -> ~ b -> SLPair a b
|  
|  you want a -> (~ b) -> SLPair a b
|  
|  If the twiddle is not immediately after an arrow you don't want that,
|  e.g.
|  
|      data T a b where
|          T :: a -> a ~ b -> SLPair a b
|  
|  you want T :: a -> (a ~ b) -> SLPair a b
|  
|  Edward
|  _______________________________________________
|  ghc-devs mailing list
|  [hidden email]
|  http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs