Bounded Forcing

Artificially forcing evaluation can be useful to relieve space leak, measure and tune performance, influence exception behaviour, make lazy I/O happen in a timely manner, and assure threads don't accidentally pass unevaluated computations to other threads ("time leak"). Bounded forcing (what this package offers) is necessary to work with streams, and other "infinite" data structures, where plain rnf/deepseq/force will diverge.

Show

The bounded forcing functions also have theoretical interest, spanning the seq / deepseq axis. They can be considered in a broader context of, for instance, strictness analysis and evaluation transformers.

Library Design Overview

The NFDataN module is straightforward; the familiar method and functions of DeepSeq have an 'n' appended to their names, and take an integer first argument which is the minimum depth, in levels of recursion of constructor applications, to which to force evaluation.

rnfn      :: NFDataN a => Int -> a -> ()
deepseqn  :: NFDataN a => Int -> a -> b -> b
forcen    :: NFDataN a => Int -> a -> a

It is important to note that this is a minimum bound only, since (for example) the runtime system may have speculatively evaluated more of the value already. Such behaviour is deliberately unspecified, platform dependent, and outside of our control. Also note likewise that, as per DeepSeq, no guarantees are made about order of evaluation in the above method and functions.

With NFDataP, the extent of evaluation is determined by a value of Pattern type. One feature of NFDataP is the ability to control order of evaluation.

Usually a user of this library will prefer to compile their patterns from a string in the embedded pattern DSL, but the Pattern constructors can be worked with directly.

Show

rnfp      :: NFDataP a => Pattern -> a -> ()
deepseqp_ :: NFDataP a => Pattern -> a -> b -> b
forcep_   :: NFDataP a => Pattern -> a -> a

data Pattern = Node PatNode [Pattern]
data PatNode = WR | WS | WW | ...

deepseqp  :: NFDataP a => String -> a -> b -> b
forcep    :: NFDataP a => String -> a -> a

deepseqp = deepseqp_ . compilePat 
forcep   = forcep_ . compilePat 

compilePat :: String -> Pattern

More examples are given further down this page, but here is one example to illustrate the use of NFDataP. There is no essential dependence on rnf (from DeepSeq), but it is available as * and helps to concoct an example.

  expr = (   undefined :: SomeType
           , ( someValueWantToForce, [2,4..] )
           , anotherValueWantToForce
         )


  forcep ".{#.{*#}*}" expr

= forcep_ ( compilePat ".{#.{*#}*}" ) expr

= forcep_ (Node WR [Node WI [],Node WR [Node WW [],Node WI []],Node WW []]) expr

which can be translated as

= let someval = someValueWeWantToForce
      another = anotherValueWeWantToForce
  in
        rnf someval
  `seq` rnf another
  `seq` expr

The pattern ".{#.{*#}*}" will match any ternary constructor, ignoring the first subexpression, completely forcing the third, and recursively matching subpattern ".{*#}" on the middle subexpression.

It's worth emphasising that pattern-matching requires forcing constructors along the way. That is to say, every node in the path from the root to a node being pattern-matched is already forced. So the shape of these forcing functions is always a rooted tree, with the root node corresponding to the outermost redex of the expression being forced.

Formally

In general, the behaviour can be formalised

        b > a  ⇒                forcen b  ≻  forcen a    -- (strict) monotonicity
                  ∨  ∀ c > b .  forcen c  =  forcen a    -- convergence

and

  patB ⊃ patA  ⇒                      forcep patB  ≻  forcep patA
                  ∨  ∀ patC ⊃ patB .  forcep patC  =  forcep patB

where f ≻ g says "f causes deeper evaluation than g".

Only strict monotonicity is interesting, since non-decreasing monotonicity ≽ is axiomatic: you cannot unevaluate anything (push thunks back on the heap?...).

Parallelism

So, revisiting our example

  expr = (   undefined :: SomeType
           , ( someValueWantToForce, [2,4..] )
           , anotherValueWantToForce
         )


  forcep ".{#.{=*#}*}" expr

= forcep_ ( compilePat ".{#.{=*#}*}" ) expr

= forcep_ (Node WR [Node WI [],Node WR [Node PW [],Node WI []],Node WW []]) expr

which translates approximately as

= let someval = someValueWeWantToForce
      another = anotherValueWeWantToForce
  in
        rnf someval
  `par` rnf another   -- note `par` (not `seq`)
  `seq` expr

In particular, rnf someval will be sparked in parallel with the remainder of the forcing (rnf another).

Controlling Evaluation Order

In the previous section, we saw how to force parallel evaluation in NFDataP using par from Control.Parallel. It is also possible to enforce sequencing of computations by leveraging the other primitive of Control.Parallel, namely pseq:

pseq x y = x `seq` lazy y

where lazy is a GHC primitve that prevents strictness of the second argument. In fact lazy is one of just two definitions living in the internal module GHC.Magic in the GHC source (the other is inline). Quoting from the source in base

-- The reason for the strange "lazy" call is that
-- it fools the compiler into thinking that pseq  and par are non-strict in
-- their second argument (even if it inlines pseq at the call site).
-- If it thinks pseq is strict in "y", then it often evaluates
-- "y" before "x", which is totally wrong.

Fusion

Several fusion rules are in effect. For NFDataN we have

  {-# RULES
    "rnfn/composition"
      forall n1 n2 x.  (.) (rnfn n2) (rnfn n1) x = rnfn (max n1 n2) x
        #-}

and for NFDataP we have

  {-# RULES
    "rnfp/composition"
      forall p1 p2 x.  (.) (rnfp p2) (rnfp p1) x = rnfp ( unionPat [p1, p2] ) x
        #-}

Other rules are probably possible (considering PatAlg), and may have been implemented since the last time this section was updated.

Unfortunately I get GHC warnings for all my rules, such as

   Rule "forcen/composition" may never fire
     because `.' might inline first
   Probable fix: add an INLINE[n] or NOINLINE[n] pragma on `.'

and it's not clear to me how to put an INLINE pragma on base composition.

Show

Optimisations will get more attention in the next round of development.

Generic Deriving is Supported

Strict monotonicity is assured, until convergence to full evaluation (for finite values). With GNFDataN, increasing the depth parameter will strictly increase the amount of forced evaluation, in a level-by-level manner within the shape of the value. Likewise, with GNFDataP, extending the pattern shape within the term shape will strictly increase the forcing.

To derive instances of NFDataN only, you can do:

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}

import Generics.SOP.TH
import Control.DeepSeq.Bounded ( NFDataN(..), grnfn )

data TA = A1 TB | A2
instance NFDataN TA where rnfn = grnfn

data TB = B1 Int TA
instance NFDataN TB where rnfn = grnfn

deriveGeneric ''TA
deriveGeneric ''TB

Show

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveDataTypeable #-}

import Generics.SOP.TH
import Control.DeepSeq.Bounded ( NFDataN(..), grnfn, NFDataP(..), grnfp )
import Control.DeepSeq.Generics ( NFData(..), genericRnf )
import GHC.Generics ( Generic )    -- for deriving NFData
import Data.Typeable ( Typeable )  -- for name-constrained pattern nodes

data TA = A1 TB | A2 deriving ( Show, Generic, Typeable )
instance NFData  TA where rnf  = genericRnf
instance NFDataN TA where rnfn = grnfn
instance NFDataP TA where rnfp = grnfp

data TB = B1 Int TA deriving ( Show, Generic, Typeable )
instance NFData  TB where rnf  = genericRnf
instance NFDataN TB where rnfn = grnfn
instance NFDataP TB where rnfp = grnfp

deriveGeneric ''TA
deriveGeneric ''TB

Note that mutually-recursive data types require all their deriveGeneric calls to come below their collective definitions.

SOP also offers an alternative approach to automatic instance derivation, piggybacking on GHC.Generics, in case Template Haskell is unacceptable in your application.

It might be worth noting that the seqaid package provides a mechanism for completely automating this process. However, it depends on use of a preprocessor, and was deemed inappropriate for this core library.

Pattern Algebra

  module Control.DeepSeq.Bounded.PatAlg

  import Control.DeepSeq.Bounded.Pattern


  Basic operations on Patterns

  -- Compute the union of a list of Patterns.
  unionPats :: [ Pattern ] -> Pattern

  -- Compute the intersection of a list of Patterns.
  intersectPats :: [ Pattern ] -> Pattern

  -- Return True if the first pattern matches the second
  -- (and False otherwise).  Note that matching does not imply
  -- spanning. Equality (==) or flip isSubPatOf will
  -- work there, depending on your intentions.
  isSubPatOf :: Pattern -> Pattern -> Bool


  Operations for obtaining and modifying Patterns based on a term

  -- Obtain a lazy pattern, matching the shape of
  -- an arbitrary term (value expression).
  -- Interior nodes will be WR, and leaves will be WS.
  mkPat :: forall d. Data d => d -> Pattern

  -- Obtain a lazy pattern, matching the shape of
  -- an arbitrary term, but only down to at most depth n.
  -- Interior nodes will be WR.  Leaf nodes will be WS if they
  -- were leaves in the host value; otherwise they will be WR.
  -- Satisfies forcep . mkPatN n = forcen n.
  mkPatN :: forall d. Data d => Int -> d -> Pattern

  -- Grow all leaves by one level within the shape of the provided value.
  growPat :: forall d. Data d => Pattern -> d -> Pattern


  Operations for obtaining subpatterns (in the 'isSubPatOf' sense)

  -- Given an integer depth and a pattern, truncate the pattern to
  -- extend to at most this requested depth.
  truncatePat :: Int -> Pattern -> Pattern

  -- Elide all leaves which have no non-leaf sibling.
  -- We want the pattern to still match the same value, only less of it.
  -- Merely eliding all leaves would, in most cases, cause match failure,
  -- so we have to be a bit more subtle.
  shrinkPat :: Pattern -> Pattern


  Operations for the direct construction and perturbation of Patterns

  -- There is no Nil in the Pattern type, but a single WI node as
  -- empty pattern is a dependable way to assure the empty pattern
  -- never forces anything.
  emptyPat :: Pattern

  -- This creates a new WR node, the common root. The argument patterns
  -- become the children of the root (order is preserved).
  liftPats :: [ Pattern ] -> Pattern

  -- Introduce siblings at a node (interior or leaf) of the target.
  -- The first argument is target, the second is a path, and the
  -- third is a list of subpatterns for insertion, along with the
  -- indices of the child before which to insert.
  splicePats :: Pattern -> [Int] -> [ (Int, Pattern) ] -> Pattern

  -- Elide siblings at a node (interior or leaf) of the target.
  -- The first argument is target, the second is a path, and the
  -- third is a list of child indices for elision.
  elidePats :: Pattern -> [Int] -> [Int] -> Pattern

  -- Select a leaf at random, and elide it.  In order to achieve fairness,
  -- the node probabilities are weighted by nodes in branch.  The path
  -- arg can "focus" the stochastic erosion to only consider leaves
  -- beneath a given node.
  erodePat :: StdGen -> [Int] -> Pattern -> (Pattern, StdGen)

Examples

First, note that we can handle infinite values, unlike deepseq.

     force $ take 5 [1,2..]   -- [1,2,3,4,5]
     take 5 $ force [1,2..]   -- << nonterminates >>

     forcen 100 $ take 5 [1,2..]   -- [1,2,3,4,5]
     take 5 $ forcen 100 [1,2..]   -- [1,2,3,4,5]

Oops, never finished this section... And that's a pretty silly example, although it illustrates the distinction. Best to refer to the tests for examples, or just play around. Will try to toss in a few more scraps...

Here is the result of iterating shrinkPat on a test pattern.

.{.{#.{*.{.*3}}}.{..{*1.{..{##}}}}}
.{.{#.{*5.{#*2}}}.{#.{#.{##}}}}
.{.{#.{*4.{#.}}}.{#.{##}}}
.{.{#.{*3.{##}}}.{##}}
.{.{#.{*2#}}#}
.{.{#.{.#}}#}
.{.{#.{##}}#}
.{.{##}#}
.{##}
#
#