Add BangPatterns

[quchen]

trafficstars

Rendered version: https://github.com/quchen/rfcs/blob/bang-patterns/texts/0000-bang-patterns.rst

[cartazio]

why is this marked a breaking change? (either way thanks for exercising this )

[quchen]

f !x = ...

has different semantics when bang patterns are enabled than in current Haskell: it’s strict in x, or defines the infix ! operator. I wasn’t sure whether this tiny corner case that’s statically catchable was worth the label, and I decided to just add it.

[cartazio]

huh, whats that difference in semantics per se?

On Thu, Aug 11, 2016 at 11:53 AM, David Luposchainsky < [email protected]> wrote:

f !x

has different semantics when bang patterns are enabled than in current Haskell. I wasn’t sure whether this tiny corner case that’s statically catchable was worth the label, and I decided to just add it.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/rfcs/pull/7#issuecomment-239204363, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwl-VoTglocRx2MF-wL52-kug963qks5qe0V9gaJpZM4JgPhh .

[quchen]

f !x = x

defines a (unnecessarily) strict identity function if BangPatterns are enabled, and the constant function that ignores its first argument (flip const) if it is not. We currently resolve this by making the bang stand for a bang pattern, with (!) being the right way to define the infix bang operator without ambiguity.

[cartazio]

I'm not understanding that combinator remark. And how would the ! Be valid sans bang patterns? Maybe I'm not understanding something obvious

On Thursday, August 11, 2016, David Luposchainsky [email protected] wrote:

f !x = x

defines a (unnecessarily) strict identity function if BangPatterns are enabled, and the constant function that ignores its first argument (flip const) if it is not.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/rfcs/pull/7#issuecomment-239256981, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwhd4z1EuMw9RsIQPM-pKboB3dZqjks5qe3B4gaJpZM4JgPhh .

[llelf]

@cartazio:

λ> let f !x = ()
λ> :t (!)
(!) :: t -> t1 -> ()

vs

λ> :set -XBangPatterns
λ> let f !x = ()
λ> :t f
f :: t -> ()

[cartazio]

... You mean it's parsed as a infix operator when there's no type sig for f in the top level? Or is that specific to ghci? Gotcha

On Friday, August 12, 2016, Antonio Nikishaev [email protected] wrote:

@cartazio https://github.com/cartazio:

λ> let f !x = () λ> :t (!)(!) :: t -> t1 -> ()

vs

λ> :set -XBangPatterns λ> let f !x = () λ> :t ff :: t -> ()

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/haskell/rfcs/pull/7#issuecomment-239388425, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwg-I76N3dhezjmBeAdY8rQhKdA5qks5qfCyBgaJpZM4JgPhh .

[quchen]

It doesn’t have anything to do with type signatures, those were just to clarify the issue. BangPatterns change the syntax in a way that changes semantics of existing programs I hope the following program makes the problem clear; try running it with and without bang patterns enabled:

main = putStrLn bang

(!) = const

bang = "BangPatterns enabled" ! ()
  where
    f !x = "BangPatterns NOT enabled"

[cartazio]

One thing that I think was only recently clarified was when we can have mutually recursive !'d bindings, right? (was sketched out as part of the Language Strict work, and probably winds up being similar or related to how letrec in scheme is articulated?)

[goldfirere]

I strongly dislike the treatment of let and where in this proposal. When I first came across this behavior, I was very befuddled for a long time, because there is a new magical rule that comes into play when a ! is at the top-level of a let- or where-bound pattern. For example, let (!x) = ... and let !x = ... have subtly different behavior. The similarity between the semantics makes it even worse, because it's all so hard to disentangle.

I'm all for a strict let and a strict where, but I propose not to confuse these forms with bang patterns. Concretely, I propose the following:

• Use whitespace to disambiguate uses of !. A bang in a bang-pattern must have a non-alphanumeric character preceding it and something other than {whitespace or comment} following it. This means that f ! x = ... and f !{- hi -}x = ... and f!x = ... all define ! while f !x = ... and f{- hi -}!x defines f.
• Introduce new keywords let! and where! that do strict binding. Note that, due to the previous bullet, those bangs are surely not bang-patterns.

I recognize that this change is not backward compatible with GHC. However, it's very easy to detect when a user has written code that will change meaning under my proposal and we could come up with some migration process.

To be clear, I'm not convinced that my proposal is worth it just to clean up GHC. But if our goal is to define the language Haskell, I think the let and where portion of the proposal is too ugly to make it in. Note that the second example under "Pattern-matching semantics" and the whole "Nested bangs" section is about unraveling the relationship between bang patterns and strict-let/where.

[quchen]

For example, let (!x) = ... and let !x = ... have subtly different behavior.

Can you show how this is the case? I do not see this result from the semantics of pattern matching giving in the Report plus any BangPatterns extension rule.

I am opposed to discussing strict let/where bindings here. I think the right place for these things is in a new compiler extension, since it might change Haskell land quite a bit. Let’s see how the new strict extensions do before we consider something like this for language-level inclusion.

[goldfirere]

Consider let !x = undefined in (). We will consider the semantics of this expression without the special rule for strict let and then again with the special rule. All section numbers refer to the Haskell 2010 Report.

Without:

• Section 3.12 tells us to desugar to case undefined of { ~!x -> () }.
• Section 3.17.3(a) tells us to desugar to (\y -> case y of { ~!x -> () }) undefined
• Section 3.17.3(b) tells us to desugar to (\y -> case y of { ~!x -> (); _ -> error "No match" }) undefined
• Section 3.17.3(d) tells us to desugar to (\y -> (\x -> ()) (case y of { !x -> x })) undefined
• Section 3.17.3(b) tells us to desugar to (\y -> (\x -> ()) (case y of { !x -> x; _ -> error "No match" })) undefined
• The proposal tells us to desugar to (\y -> (\x -> ()) (y seq case y of { x -> x; _ -> error "No match" })) undefined
• Section 3.17.3(i) tells us to desugar to (\y -> (\x -> ()) (y seq case y of { x -> x })) undefined
• Section 3.17.3(j) tells us to desugar to (\y -> (\x -> ()) (y seq (\x -> x) y)) undefined
• Step to (\x -> ()) (undefined seq (\x -> x) undefined)
• Step to ()

We are done, with a result of (). Because let is lazy, we never even look at the pattern or the right-hand side.

With:

• Start, once again, with let !x = undefined in ().
• The proposal translates this to let z@x = undefined in z seq ()
• Section 3.12 tells us to desugar to case undefined of { ~(z@x) -> z seq () }
• Section 3.17.3(a) tells us to desugar to (\y -> case y of { ~(z@x) -> z seq () }) undefined
• Section 3.17.3(b) tells us to desugar to (\y -> case y of { ~(z@x) -> z seq (); _ -> error "No match" }) undefined
• Section 3.17.3(d) tells us to desugar to (\y -> (\z x -> z seq ()) (case y of { z@x -> z }) (case y of { z@x -> x })) undefined
• Section 3.17.3(b) (used twice) tells us desugar to (\y -> (\z x -> z seq ()) (case y of { z@x -> z; _ -> error "No match" }) (case y of { z@x -> x; _ -> error "No match" })) undefined
• Section 3.17.3(e) (used twice) tells us to desugar to (\y -> (\z x -> z seq ()) (case y of { x -> (\z -> z) y; _ -> error "No match" }) (case y of { x -> (\z -> x) y; _ -> error "No match" })) undefined
• Section 3.17.3(i) (used twice) tells us to desugar to (\y -> (\z x -> z seq ()) (case y of { x -> (\z -> z) y }) (case y of { x -> (\z -> x) y })) undefined
• Section 3.17.3(j) (used twice) tells us to desugar to (\y -> (\z x -> z seq ()) ((\x -> (\z -> z) y) y) ((\x -> (\z -> x) y) y)) undefined
• Step to (\z x -> z seq ()) ((\x -> (\z -> z) undefined) undefined) ((\x -> (\z -> x) undefined) undefined)
• Step to (\x -> ((\x -> (\z -> z) undefined) undefined) seq ()) ((\x -> (\z -> x) undefined) undefined)
• Step to ((\x -> (\z -> z) undefined) undefined) seq ()
• Step to ((\z -> z) undefined) seq ()
• Step to undefined seq ()
• Step to undefined

We are done, with a result of undefined. The strict let has done its job well.

Discussion:

Above, I claimed that we could witness a difference in behavior between let !x = undefined in () and let (!x) = undefined in (). I said this because, according to the proposal, the first would be a strict let while the second would not be. So we can consider the "without" example to be dealing with let (!x) = undefined in ().

It turns out that GHC does not implement the proposal as stated, as GHC looks under parentheses to find the outer bang. Thus let !x = undefined in () and let (!x) = undefined in () are both strict lets in GHC, is disagreement with this proposal. (See decideBangHood in DsUtils.)

On the other hand, GHC does not look under newtype constructors, which should be fully transparent to the runtime semantics of the language. Consider

newtype Id a = Id a

newt :: ()
newt = let Id !x = Id undefined in ()

bangPattern :: ()
bangPattern = let (!x) = undefined in ()

strictLet :: ()
strictLet = let !x = undefined in ()

Evaluating newt gives (). Evaluating the others diverges. Considering that GHC ignores the parentheses in bangPattern, this all agrees with my analysis above, that a non-strict let would evaluate to () while a strict one would diverge.

Bottom line:

This is all incredibly subtle! And the subtlety comes from the (to me) very bizarre treatment of strict let, which looks just like a bang pattern but is, in reality, Something Else.

Purview of this process:

You make a valid point that it's awkward for us to standardize something that is not implemented. Yet I recall from earlier discussions that our committee might, in its early stages, come up with suggested improvements to GHC, implement these, get feedback from the community, and then standardize the improvement. I suppose I am suggesting that we do exactly this.

[cartazio]

This is an awesome exposition Richard. Thanks for taking the time to write this up!

On Sunday, August 21, 2016, Richard Eisenberg [email protected] wrote:

Consider let !x = undefined in (). We will consider the semantics of this expression without the special rule for strict let and then again with the special rule. All section numbers refer to the Haskell 2010 Report.

Without:

• Section 3.12 tells us to desugar to case undefined of { ~!x -> () }.
• Section 3.17.3(a) tells us to desugar to (\y -> case y of { ~!x -> () }) undefined
• Section 3.17.3(b) tells us to desugar to (\y -> case y of { ~!x -> (); _ -> error "No match" }) undefined
• Section 3.17.3(d) tells us to desugar to (\y -> (\x -> ()) (case y of { !x -> x })) undefined
• Section 3.17.3(b) tells us to desugar to (\y -> (\x -> ()) (case y of { !x -> x; _ -> error "No match" })) undefined
• The proposal tells us to desugar to (\y -> (\x -> ()) (y seq case y of { x -> x; _ -> error "No match" })) undefined
• Section 3.17.3(i) tells us to desugar to (\y -> (\x -> ()) (y seq case y of { x -> x })) undefined
• Section 3.17.3(j) tells us to desugar to (\y -> (\x -> ()) (y seq (\x -> x) y)) undefined
• Step to (\x -> ()) (undefined seq (\x -> x) undefined)
• Step to ()

We are done, with a result of (). Because let is lazy, we never even look at the pattern or the right-hand side.

With:

• Start, once again, with let !x = undefined in ().
• The proposal translates this to let z@x = undefined in z seq ()
• Section 3.12 tells us to desugar to case undefined of { ~(z@x) -> z seq () }
• Section 3.17.3(a) tells us to desugar to (\y -> case y of { ~(z@x) -> z seq () }) undefined
• Section 3.17.3(b) tells us to desugar to (\y -> case y of { ~(z@x) -> z seq (); _ -> error "No match" }) undefined
• Section 3.17.3(d) tells us to desugar to (\y -> (\z x -> z seq ()) (case y of { z@x -> z }) (case y of { z@x -> x })) undefined
• Section 3.17.3(b) (used twice) tells us desugar to (\y -> (\z x -> z seq ()) (case y of { z@x -> z; _ -> error "No match" }) (case y of { z@x -> x; _ -> error "No match" })) undefined
• Section 3.17.3(e) (used twice) tells us to desugar to (\y -> (\z x -> z seq ()) (case y of { x -> (\z -> z) y; _ -> error "No match" }) (case y of { x -> (\z -> x) y; _ -> error "No match" })) undefined
• Section 3.17.3(i) (used twice) tells us to desugar to (\y -> (\z x -> z seq ()) (case y of { x -> (\z -> z) y }) (case y of { x -> (\z -> x) y })) undefined
• Section 3.17.3(j) (used twice) tells us to desugar to (\y -> (\z x -> z seq ()) ((\x -> (\z -> z) y) y) ((\x -> (\z -> x) y) y)) undefined
• Step to (\z x -> z seq ()) ((\x -> (\z -> z) undefined) undefined) ((\x -> (\z -> x) undefined) undefined)
• Step to (\x -> ((\x -> (\z -> z) undefined) undefined) seq ()) ((\x -> (\z -> x) undefined) undefined)
• Step to ((\x -> (\z -> z) undefined) undefined) seq ()
• Step to ((\z -> z) undefined) seq ()
• Step to undefined seq ()
• Step to undefined

We are done, with a result of undefined. The strict let has done its job well.

Discussion:

Above, I claimed that we could witness a difference in behavior between let !x = undefined in () and let (!x) = undefined in (). I said this because, according to the proposal, the first would be a strict let while the second would not be. So we can consider the "without" example to be dealing with let (!x) = undefined in ().

It turns out that GHC does not implement the proposal as stated, as GHC looks under parentheses to find the outer bang. Thus let !x = undefined in () and let (!x) = undefined in () are both strict lets in GHC, is disagreement with this proposal. (See decideBangHood in DsUtils.)

On the other hand, GHC does not look under newtype constructors, which should be fully transparent to the runtime semantics of the language. Consider

newtype Id a = Id a

newt :: () newt = let Id !x = Id undefined in ()

bangPattern :: () bangPattern = let (!x) = undefined in ()

strictLet :: () strictLet = let !x = undefined in ()

Evaluating newt gives (). Evaluating the others diverges. Considering that GHC ignores the parentheses in bangPattern, this all agrees with my analysis above, that a non-strict let would evaluate to () while a strict one would diverge.

Bottom line:

This is all incredibly subtle! And the subtlety comes from the (to me) very bizarre treatment of strict let, which looks just like a bang pattern but is, in reality, Something Else.

Purview of this process:

You make a valid point that it's awkward for us to standardize something that is not implemented. Yet I recall from earlier discussions that our committee might, in its early stages, come up with suggested improvements to GHC, implement these, get feedback from the community, and then standardize the improvement. I suppose I am suggesting that we do exactly this.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/haskell/rfcs/pull/7#issuecomment-241269057, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwnYjkjRj0LbPnhB72Y5jxOmQZ-2Uks5qiIT7gaJpZM4JgPhh .

[simonmar]

Richard, if I understand correctly, you are proposing that let! x = undefined would behave differently from let !x = undefined, right? That would be subtle and surprising, perhaps even more so than the special treatment of strict let, in my opinion. (but I am in general opposed to this kind of whitespace-significance in syntax)

[goldfirere]

Yes, I suppose that's true. My proposal introduces a new syntactic subtlety. I still think this is an improvement over the status quo, however.

Even better would be to somehow label the =. Wouldn't this be nice:

let strict != ...
    lazy = ...

But != is a perfectly valid operator name. (It would also make programmers used to C-style syntax go cross-eyed.) I also considered := but that is a perfectly valid constructor name.

What about <-? That looks too much like do-notation.

I've thought a bit why I want to switch out one syntax for another, and I've hit on the reason: the current behavior (both in GHC and in this proposal) carves out a slice of existing syntax for a subtly different semantics. (That is, let !x = undefined is perfectly grammatical as a normal bang-pattern.) I'd like instead a strict-let to use new syntax. The problem is that new syntax is hard to find. :(

[simonmar]

But in the absence of the special case, let !p = e in ... is useless because it means exactly the same as let p = e in .... So we might as well give it a useful meaning, and one that matches intuition - at least, it matches my intuition, but that might just be because I'm used to it.

[goldfirere]

Another good point -- having let !x = ... be a strict assignment is certainly more useful than treating !x as a plain old bang-pattern (which, I agree, helps no one).

My problem is that I have mental model for how lazy let works and a mental model for how bang-patterns work... and then let !x = ... violates that model. I'll point out that my confusion around this feature was arrived at "in the wild": I was staring at some code utterly unable to understand how it worked. I ran several examples in a dummy file to figure it out. Then I started to file a bug report. Then I discovered that this is a feature, not a bug, and walked away.

Maybe I'm alone here, and maybe I'm several years too late for this debate. I'm just voicing my opinion about this one part of the proposal and am content enough to be outvoted. I've not yet changed my mind, though. (Simon's arguments have weakened the fervor of my opinion, to be fair.)

[strake]

I also dislike all this whitespace-significance. I also dislike losing infix definition of (!). So i had a (not yet fully formalized) idea:

We could define bang-patterns at the same syntactic level as infix patterns (pat in the Haskell 2010 report syntax), and define let ! and where ! as the syntax of strict binding, which is now otherwise illegal in stock Haskell. Thus f (!x) = x would define a strict identity function f and f ! x = x or f !x = x would define the const function (!).

[quchen]

I am not convinced the (!x) issue is such a big problem. Compilers might simply warn on (!x), since it is never a useful thing to express. It is true that we would have to document the strict binding behaviour separately, but I see this as an addition to BangPatterns (in spirit, at least), not a liability.

[cartazio]

Relatedly: do we have strict monadic !x <- fM ? Or some such?

On Friday, August 26, 2016, David Luposchainsky [email protected] wrote:

I am not convinced the (!x) issue is such a big problem. Since the special case is only for the entire pattern, compilers might warn on (!x), which always has undesired properties. It is true that we would have to document the strict binding behaviour separately, but I see this as an addition to BangPatterns (in spirit, at least), not a liability.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/haskell/rfcs/pull/7#issuecomment-242670286, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwij_La4IHnGE9F9NRXMOank0xDT6ks5qjqiygaJpZM4JgPhh .

[wrengr]

I strenuously agree with @simonmar that making things whitespace dependent is terrible. As far as defining a (!) operator goes, I'm far more amenable to having a corner case in the syntax that requires it to be defined via prefix notation.

I also agree with @goldfirere that bang patterns (i.e., in the argument patterns of a function definition) are a different entity than strict binding. However, given as let !x = ... in ... under the bang-pattern reading is no different from let x = ... in ..., I don't see any particular issues with stealing the syntax to mean strict binding. So long as the report is clear that these two are different things, giving them suggestively similar syntax shouldn't be a problem.

The big caveat is to make sure that the syntax behaves consistently with regards to parentheses and newtypes. E.g., contrary to GHC's current implementation, I'd expect all of the following to have the same operational semantics:

• let! x = ... in ...
• let !x = ... in ... (i.e., whitespace doesn't matter)
• let !(x) = ... in ...
• let (!x) = ... in ... (strict-let, not a bang-pattern, because the ! is on the thing being bound)
• let !(New x) = ... in ... (where New is a newtype data constructor)
• let (New !x) = ... in ...
• let New !x = ... in ...
• etc.

N.B., the above equivalence is specifically because newtypes are supposed to be a zero-cost abstraction that doesn't affect operational semantics. When the pattern is a data type constructor, we get differences:

• let !(Con x) = ... in ... (strict-binding, but x matches lazily)
• let (Con !x) = ... in ... (lazy-binding with bang-pattern; x will be forced whenever the case analysis against Con is forced)
• let !(Con !x) = ... in ... (strict-binding with bang-pattern; will force Con x immediately, and also force x)

[goldfirere]

I'm not wedded to the whitespace use here. I also think that Wren's suggestions make this patch smoother. But I still feel strongly that having one syntax with two very subtly different meanings that can be disambiguated only by a subtle analysis (but indeed a well-specified one) is asking for confusion.

In other words, the ideas proposed here are entirely sensible for GHC or other tooling to implement. But I think they will bedevil users. Or at least they bedeviled me. :)

[yav]

I also think that there is a significant difference between the bang patterns on function arguments and the strict declarations.

I think we should certainly standardize bang patterns on function arguments, with the proviso that they can only be applied to variable patterns, as this is the only situation where they make sense.

For strict bindings, I am not sure what to do. I can see that they are useful sometimes, but it is not great that they are not uniform (e.g., currently, you can't have them on the top level of a module, presumable because it is not quite clear when to evaluate them?). The notation is also a bit confusing I think, as they look a lot like strict pattern bindings but are not. Also, in a strict pa

If we do go ahead with strict bindings, and a different notation, I think the annotation should be on the actual binding, not the let or where keyword, as it is quite likely that some bindings would be strict, and others not, and it would be nice to mix these in a single declaration block.

[cartazio]

This is a good idea

On Wednesday, October 12, 2016, Iavor S. Diatchki [email protected] wrote:

I also think that there is a significant difference between the bang patterns on function arguments and the strict declarations.

I think we should certainly standardize bang patterns on function arguments, with the proviso that they can only be applied to variable patterns, as this is the only situation where they make sense.

For strict bindings, I am not sure what to do. I can see that they are useful sometimes, but it is not great that they are not uniform (e.g., currently, you can't have them on the top level of a module, presumable because it is not quite clear when to evaluate them?). The notation is also a bit confusing I think, as they look a lot like strict pattern bindings but are not. Also, in a strict pa

If we do go ahead with strict bindings, and a different notation, I think the annotation should be on the actual binding, not the let or where keyword, as it is quite likely that some bindings would be strict, and others not, and it would be nice to mix these in a single declaration block.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/haskell/rfcs/pull/7#issuecomment-253273486, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwouztE0x_mfR9Ko1GKS9iK6iiDX4ks5qzRIggaJpZM4JgPhh .

[wrengr]

I think we should certainly standardize bang patterns on function arguments, with the proviso that they can only be applied to variable patterns, as this is the only situation where they make sense.

At the very least, I think this is something we can all agree on? Are there any outstanding issues about committing to this part of the proposal (and leaving the strict-binding discussion for another time)? If not, @quchen did you want to revise the pr or should I?

One issue which came up at ICFP but hasn't been discussed here —and which isn't necessarily a "problem" but which I think should be explicitly discussed in the report— is how to handle partial application, especially vis a vis bang patterns on the arguments to data constructors. That is, given a data type data T a b = D !a b one might be led to believe that forcing (D a) will force a, when in fact (in GHC) the forcing of banged arguments to data constructors only occurs once the constructor is fully saturated. Similar issues arise with partially applied functions, though one might be less inclined to expect the partial application to force anything there. Personally, my main concerns here are: (a) that data constructors and non-constructor functions behave the same in terms of when the forcing happens (which they currently do in GHC), and (b) that the report is clear about what is expected here.

If we do go ahead with strict bindings, and a different notation, I think the annotation should be on the actual binding, not the let or where keyword, as it is quite likely that some bindings would be strict, and others not, and it would be nice to mix these in a single declaration block.

+1.

[goldfirere]

Agreed about proceeding about bang patterns on function arguments.

Agreed about specifying the behavior of partial application vis-a-vis bang patterns. But I wish to note that data T a b = D !a b does not contain bang pattern. This wouldn't be a change to the specification as much as a clarification, if I understand correctly. And agreed about consistency between bang patterns and strict fields.

Agreed about marking the binding, not the let/where, retracting my earlier proposal. If it didn't steal syntax and make every C/C++/Java/derivative programmer's head explode, != would make a lovely strict-binding assignment operator, as in

let lazy    = blahblah
    strict != wurble

It has just the right flavor, to me. This is clearly not possible, but maybe this idea inspires someone to come up with something that is possible.

[quchen]

@wrengr

If not, @quchen did you want to revise the pr or should I?

I opened a couple of proposals to get people to start talking. The pull request makes it a bit hard to transfer editing to you. I guess it’s easiest if I just give you access to my fork ..?