Implement the Strict language extension

Add a new language extension `-XStrict` which turns all bindings strict
as if the programmer had written a `!` before it. This also upgrades
ordinary Haskell to allow recursive and polymorphic strict bindings.

See the wiki[1] and the Note [Desugar Strict binds] in DsBinds for
specification and implementation details.

[1] https://ghc.haskell.org/trac/ghc/wiki/StrictPragma

Reviewers: austin, tibbe, simonpj, bgamari

Reviewed By: tibbe, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1142

GHC Trac Issues: #8347

1 files changed, 289 insertions, 20 deletions

diff --git a/docs/users_guide/glasgow_exts.rst b/docs/users_guide/glasgow_exts.rst
index ec026947be..ed47dae6a0 100644
--- a/docs/users_guide/glasgow_exts.rst
+++ b/docs/users_guide/glasgow_exts.rst
@@ -10332,22 +10332,12 @@ the top level of a ``let`` or ``where`` binding makes the binding
 strict, regardless of the pattern. (We say "apparent" exception because
 the Right Way to think of it is that the bang at the top of a binding is
 not part of the *pattern*; rather it is part of the syntax of the
-*binding*, creating a "bang-pattern binding".) For example:
+*binding*, creating a "bang-pattern binding".) See :ref:`Strict recursive and
+polymorphic let bindings <recursive-and-polymorphic-let-bindings> for
+how bang-pattern bindings are compiled.
 
-::
-
-    let ![x,y] = e in b
-
-is a bang-pattern binding. Operationally, it behaves just like a case
-expression:
-
-::
-
-    case e of [x,y] -> b
-
-Like a case expression, a bang-pattern binding must be non-recursive,
-and is monomorphic. However, *nested* bangs in a pattern binding behave
-uniformly with all other forms of pattern matching. For example
+However, *nested* bangs in a pattern binding behave uniformly with all
+other forms of pattern matching. For example
 
 ::
 
@@ -12434,10 +12424,11 @@ Strict Haskell
 
 High-performance Haskell code (e.g. numeric code) can sometimes be
 littered with bang patterns, making it harder to read. The reason is
-that lazy evaluation isn't the right default in this particular code but
-the programmer has no way to say that except by repeatedly adding bang
-patterns. Below ``-XStrictData`` is detailed that allows the programmer
-to switch the default behavior on a per-module basis.
+that lazy evaluation isn't the right default in this particular code
+but the programmer has no way to say that except by repeatedly adding
+bang patterns. Below ``-XStrictData`` and ``-XStrict`` are detailed
+that allows the programmer to switch the default behavior on a
+per-module basis.
 
 .. _strict-data:
 
@@ -12455,7 +12446,7 @@ When the user writes
           data T = C a
           data T' = C' ~a
 
-we interpret it as if she had written
+we interpret it as if they had written
 
 ::
 
@@ -12463,3 +12454,281 @@ we interpret it as if she had written
           data T' = C' a
 
 The extension only affects definitions in this module.
+
+
+.. _strict:
+
+Strict-by-default pattern bindings
+----------------------------------
+
+Informally the ``Strict`` language extension switches functions, data
+types, and bindings to be strict by default, allowing optional laziness
+by adding ``~`` in front of a variable. This essentially reverses the
+present situation where laziness is default and strictness can be
+optionally had by adding ``!`` in front of a variable.
+
+``Strict`` implies :ref:`StrictData <strict-data>`.
+
+-  **Function definitions.**
+
+   When the user writes ::
+
+       f x = ...
+
+   we interpret it as if they had written ::
+
+       f !x = ...
+
+   Adding ``~`` in front of ``x`` gives the regular lazy behavior.
+
+-  **Let/where bindings.**
+
+   When the user writes ::
+
+     let x = ...
+     let pat = ...
+
+   we interpret it as if they had written ::
+
+     let !x = ...
+     let !pat = ...
+
+   Adding ``~`` in front of ``x`` gives the regular lazy
+   behavior. Notice that we do not put bangs on nested patterns. For
+   example ::
+
+     let (p,q) = if flob then (undefined, undefined) else (True, False)
+     in ...
+
+   will behave like ::
+
+     let !(p,q) = if flob then (undefined, undefined) else (True,False)
+     in ...
+
+   which will strictly evaluate the right hand side, and bind ``p``
+   and ``q`` to the components of the pair. But the pair itself is
+   lazy (unless we also compile the ``Prelude`` with ``Strict``; see
+   :ref:`strict-modularity` below). So ``p`` and ``q`` may end up bound to
+   undefined. See also :ref:`recursive-and-polymorphic-let-bindings` below.
+
+-  **Case expressions.**
+
+   The patterns of a case expression get an implicit bang, unless
+   disabled with ``~``. For example ::
+
+       case x of (a,b) -> rhs
+
+   is interpreted as ::
+
+       case x of !(a,b) -> rhs
+
+   Since the semantics of pattern matching in case expressions is
+   strict, this usually has no effect whatsoever. But it does make a
+   difference in the degenerate case of variables and newtypes. So ::
+
+       case x of y -> rhs
+
+   is lazy in Haskell, but with ``Strict`` is interpreted as ::
+
+       case x of !y -> rhs
+
+   which evalutes ``x``. Similarly, if ``newtype Age = MkAge Int``, then ::
+
+       case x of MkAge i -> rhs
+
+   is lazy in Haskell; but with ``Strict`` the added bang makes it
+   strict.
+
+-  **Top level bindings.**
+
+   are unaffected by ``Strict``. For example: ::
+
+       x = factorial 20
+       (y,z) = if x > 10 then True else False
+
+   Here ``x`` and the pattern binding ``(y,z)`` remain lazy. Reason:
+   there is no good moment to force them, until first use.
+
+-  **Newtypes.**
+
+   There is no effect on newtypes, which simply rename existing types.
+   For example: ::
+
+       newtype T = C a
+       f (C x)  = rhs1
+       g !(C x) = rhs2
+
+   In ordinary Haskell, ``f`` is lazy in its argument and hence in
+   ``x``; and ``g`` is strict in its argument and hence also strict in
+   ``x``. With ``Strict``, both become strict because ``f``'s argument
+   gets an implict bang.
+
+
+.. _strict-modularity:
+
+Modularity
+----------
+
+``Strict`` and ``StrictData`` only affects definitions in the module
+they are used in. Functions and data types imported from other modules
+are unaffected. For example, we won't evaluate the argument to
+``Just`` before applying the constructor.  Similarly we won't evaluate
+the first argument to ``Data.Map.findWithDefault`` before applying the
+function.
+
+This is crucial to preserve correctness. Entities defined in other
+modules might rely on laziness for correctness (whether functional or
+performance).
+
+Tuples, lists, ``Maybe``, and all the other types from ``Prelude``
+continue to have their existing, lazy, semantics.
+
+.. _recursive-and-polymorphic-let-bindings:
+
+Recursive and polymorphic let bindings
+--------------------------------------
+
+**Static semantics**
+
+Exactly as in Haskell, unaffected by ``Strict``. This is more permissive
+than past rules for bang patterns in let bindings, because it supports
+bang-patterns for polymorphic and recursive bindings.
+
+**Dynamic semantics**
+
+Consider the rules in the box of `Section 3.12 of the Haskell
+report <http://www.haskell.org/onlinereport/exps.html#sect3.12>`__.
+Replace these rules with the following ones, where ``v`` stands for a
+variable:
+
+.. admonition:: FORCE
+
+    Replace any binding ``!p = e`` with ``v = e; p = v`` and replace
+    ``e0`` with ``v seq e0``, where ``v`` is fresh. This translation works fine if
+    ``p`` is already a variable ``x``, but can obviously be optimised by not
+    introducing a fresh variable ``v``.
+
+.. admonition:: SPLIT
+
+    Replace any binding ``p = e``, where ``p`` is not a variable, with
+    ``v = e; x1 = case v of p -> x1; ...; xn = case v of p -> xn``, where
+    ``v`` is fresh and ``x1``.. ``xn`` are the bound variables of ``p``.
+    Again if ``e`` is a variable, you can optimised his by not introducing a
+    fresh variable.
+
+The result will be a (possibly) recursive set of bindings, binding
+only simple variables on the left hand side. (One could go one step
+further, as in the Haskell Report and make the recursive bindings
+non-recursive using ``fix``, but we do not do so in Core, and it only
+obfuscates matters, so we do not do so here.)
+
+Here are some examples of how this translation works. The first
+expression of each sequence is Haskell source; the subsequent ones are
+Core.
+
+Here is a simple non-recursive case: ::
+
+    let x :: Int     -- Non-recursive
+        !x = factorial y
+    in body
+
+    ===> (FORCE)
+        let x = factorial y in x `seq` body
+
+    ===> (inline seq)
+        let x = factorial y in case x of x -> body
+
+    ===> (inline x)
+        case factorial y of x -> body
+
+Same again, only with a pattern binding: ::
+
+    let !(x,y) = if blob then (factorial p, factorial q) else (0,0)
+    in body
+
+    ===> (FORCE)
+        let v = if blob then (factorial p, factorial q) else (0,0)
+            (x,y) = v
+        in v `seq` body
+
+    ===> (SPLIT)
+        let v = if blob then (factorial p, factorial q) else (0,0)
+            x = case v of (x,y) -> x
+            y = case v of (x,y) -> y
+        in v `seq` body
+
+    ===> (inline seq, float x,y bindings inwards)
+        let v = if blob then (factorial p, factorial q) else (0,0)
+        in case v of v -> let x = case v of (x,y) -> x
+                                y = case v of (x,y) -> y
+                            in body
+
+    ===> (fluff up v's pattern; this is a standard Core optimisation)
+        let v = if blob then (factorial p, factorial q) else (0,0)
+        in case v of v@(p,q) -> let x = case v of (x,y) -> x
+                                    y = case v of (x,y) -> y
+                                in body
+
+    ===> (case of known constructor)
+        let v = if blob then (factorial p, factorial q) else (0,0)
+        in case v of v@(p,q) -> let x = p
+                                    y = q
+                                in body
+
+    ===> (inline x,y)
+        let v = if blob then (factorial p, factorial q) else (0,0)
+        in case v of (p,q) -> body[p/x, q/y]
+
+The final form is just what we want: a simple case expression.
+
+Here is a recursive case ::
+
+    letrec xs :: [Int]  -- Recursive
+            !xs = factorial y : xs
+    in body
+
+    ===> (FORCE)
+        letrec xs = factorial y : xs in xs `seq` body
+
+    ===> (inline seq)
+        letrec xs = factorial y : xs in case xs of xs -> body
+
+    ===> (eliminate case of value)
+        letrec xs = factorial y : xs in body
+
+and a polymorphic one: ::
+
+    let f :: forall a. [a] -> [a]    -- Polymorphic
+        !f = fst (reverse, True)
+    in body
+
+    ===> (FORCE)
+        let f = /\a. fst (reverse a, True) in f `seq` body
+    ===> (inline seq, inline f)
+        case (/\a. fst (reverse a, True)) of f -> body
+
+Notice that the ``seq`` is added only in the translation to Core
+If we did it in Haskell source, thus ::
+
+   let f = ... in f `seq` body
+
+then ``f``\ 's polymorphic type would get intantiated, so the Core
+translation would be ::
+
+   let f = ... in f Any `seq` body
+
+
+When overloading is involved, the results might be slightly counter
+intuitive: ::
+
+    let f :: forall a. Eq a => a -> [a] -> Bool    -- Overloaded
+        !f = fst (member, True)
+    in body
+
+    ===> (FORCE)
+        let f = /\a \(d::Eq a). fst (member, True) in f `seq` body
+
+    ===> (inline seq, case of value)
+        let f = /\a \(d::Eq a). fst (member, True) in body
+
+Note that the bang has no effect at all in this case