Bounded Forcing
Show ContentsThe deepseq-bounded package provides two means of forcing a Haskell expression to an arbitrary but bounded depth, deepseqn and deepseqp. As compared with plain seq (incremental forcing) and the beloved deepseq (full forcing), the bounded versions bridge the gap between these extremes.
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.
My particular motivation for deepseq-bounded is to support tool building for space leak characterisation (and provisional alleviation). Readers interested in those aspects might like to have a look at seqaid and leaky. Space leak is still an Achilles' heel of Haskell, they're often fatally severe, and can be as hard to debug as anything you see in other languages. With the present tools in use, it's fair to say Haskell space leak is more difficult to diagnose than pointer bugs in C/C++, being perhaps on a par with concurrent programming bugs (probably the most difficult class of bugs in all of contemporary computing). People talk about strict-by-default Haskell in the future, but it remains there, and anyway, laziness has its charm and strengths and is attractive to many.
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
Following the tradition of the deepseq package, the NFDataN module contains a class NFDataN, with a method called rnfn, instances of which do the work of forcing bounded evaluation. Additional functions deepseqn and forcen are provided, like in NFData. NFDataP also follows this design.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.
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
Note also that rnfp/forcep/deepseqp influence strictness of their second argument, but the strictness of their first, Pattern, argument is totally unspecified. It can, of course, be controlled by forcing the Pattern. Note how this is not the same as composition of forcing functions:
(φ πB . φ πA) x (1)
= φ πB (φ πA x)
versus
φ (φ πB πA) x (2)
In (1) both Patterns πA and πB have unspecified strictness.
However, in (2) πB has unspecified strictness, but πA has strictness determined (entirely) by πB.
We may say "entirely" since no additional demands placed on these expressions, in the context of execution of the program, can influence the strictness of either Pattern argument.
If we had φ πB πA, without the outer φ wrapper of (2), then the execution context might induce additional strictness in πA since now the program itself is demanding a value of type Pattern.
This is all a bit subtle, the above might not be totally correct...
Formally
In general, the behaviour can be formalised
b > a ⇒ forcen b ≻ forcen a -- (strict) monotonicity
∨ ∀ c > b . forcen c = forcen b -- 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?...).
Example
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 it's familiarity helps to concoct an example.
So, suppose the following expression occurs in your code, and you have need (for whatever reason) to force the evaluation of exp_A and exp_B. However, the total expression also contains some things you mustn't force, represented here by undefined and an infinite list.
expr = ( undefined :: SomeType
, ( exp_A, [2,4..] )
, exp_B
)
forcep "(.(*.)*)" expr = forcep_ ( compilePat "(.(*.)*)" ) expr = forcep_ (Node WR [Node WI [],Node WR [Node WW [],Node WI []],Node WW []]) expr
which can be (almost) translated as
= let x1 = exp_A
x2 = exp_B
in
rnf x1
`seq` rnf x2
`seq` ( undefined :: SomeType
, ( x1, [2,4..] )
, x2
)
This final translation is actually not quite correct — forcep forces the spine of the paths from expr to the substructures we want to hammer with rnf, but this translation does not. In particular, the pair constructor (,) for ( exp_A, [2,4..] ) is forced by forcep, but not by this translation. [Is this true?...]
The pattern (.(*.)*) will match any ternary constructor, ignoring the first subterm, completely forcing the third, and recursively matching subpattern (*.) on the middle subterm!
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.
Parallelism
Varieties of PatNode to trigger Control.Parallel.par parallel evaluation are of interest. This (along with a half dozen other things) is supported by the new PatNodeAttrs node attributes. In the DSL such nodes are represented by preceding them with an = character.So, revisiting our example
expr = ( undefined :: SomeType
, ( exp_A, [2,4..] )
, exp_B
)
forcep "(.(=*.)*)" expr = forcep_ ( compilePat "(.(=*.)*)" ) expr = forcep_ (Node WR [Node WI [],Node WR [Node PW [],Node WI []],Node WW []]) expr
which translates approximately as
= let x1 = exp_A
x2 = exp_B
in
rnf x1
`par` rnf x2 -- note `par` (not `seq`)
`seq` ( undefined :: SomeType
, ( x1, [2,4..] )
, x2
)
In particular, rnf x1 will be sparked in parallel with the remainder of the forcing (rnf x2).
Controlling Evaluation Order
We've noted that seq makes no guarantees about order of evaluation of its arguments. This is concisely explained in the Control.Parallel API document. Plain seq is strict in its second argument, so the evaluation semantics for x `seq` y amount to no guarantees at all about the order in which x and y are evaluated. Evaluation of x and y is probably interleaved, in general.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.
This lets us write something like
= let x1 = exp_A
x2 = exp_B
in
rnf x1
`pseq` rnf x2 -- note `pseq` (not `seq`)
`seq` ( undefined :: SomeType
, ( x1, [2,4..] )
, x2
)
Show
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.
This and more is now supported with the PatNodeAttrs. Specifically, controlling order of evaluation of sibling forcing patterns is expressed as the prefix modifier >cdba. (Prefix modifiers may appear in any order.)
Fusion
Little has been done so far to tune performance.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 PatUtil), 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.
There haven't been many cases of pattern composition coming up so far, except those deliberately written for the tests. Also, given the amount of pattern-matching required by unionPat, it's far from certain that this rule will improve performance. If the union could be computed once at compile-time (for static patterns only, of course) it would make a lot more sense. This could be useful, since seqaid is going to output optimised, static patterns for ancillary use in subsequent builds. But then seqaid might as well also compute and output the union itself.
Optimisations will get more attention in the next round of development.
Generic Deriving is Supported
The GNFDataN and GNFDataP classes support automatic derivation of instances of NFDataN and NFDataP for arbitrary types, using SOP (generics-sop), a relatively new generics library. Latterly, Seqable supports all types via SOP, and there is no Seqable class, only generic functions. This is an attractive alternative to wrestling with divers classes and constraints — one need only worry about one class constraint (Generics.SOP.Generic), instances of which are readily derived.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
To derive instances of NFDataP for a data type (which requires also instances of superclasses NFDataN and of NFData), the incantation is:
{-# 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 Utilities
In the course of developing NFDataP, several utility functions were written for creating, modifying and combining patterns. They've been collected in the PatUtil module.module Control.DeepSeq.Bounded.PatUtil -- implicitly imports Pattern also Basic operations on Pattern -- 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; flip subPat would work for that. subPat :: 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). -- All nodes will be WR. 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. -- Satisfies forcep (mkPatN n x) x = forcen n x. 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 'subPat' 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 ensure that 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 -- Add children to 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 children of 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)
Other Examples
More examples can be browsed in the testing output. Here we only touch on a few particulars.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.
Here is the result of iterating shrinkPat on a test pattern.
((.(*(!*3)))(!(*1(!(.!))))) ((.(*5(.*2)))(.(.(.(..))))) ((.(*4(.!)))(.(.(..)))) ((.(*3(..)))(.(..))) ((.(*2.))(..)) ((.(!.)).) ((.(..)).) ((..).) (..) . .
Afterthoughts
Better concrete pattern syntax
documents, have been revised to use the new grammar.
It seems possible to simplify the lexical syntax of the pattern DSL.
- If the PatNode is WR, don't show the dot!
- For PR, show =subpats instead of =.subpats
- For TR, show :type subpats instead of .:type subpats
Here is the shrinkPat sequence again, new syntax on the left.
{{#{*{.*3}}}{.{*1{.{#.}}}}} .{.{#.{*.{.*3}}}.{..{*1.{..{#.}}}}}
{{#{*5{#*2}}}{#{#{#{##}}}}} .{.{#.{*5.{#*2}}}.{#.{#.{#.{##}}}}}
{{#{*4{#.}}}{#{#{#.}}}} .{.{#.{*4.{#.}}}.{#.{#.{#.}}}}
{{#{*3{##}}}{#{#{##}}}} .{.{#.{*3.{##}}}.{#.{#.{##}}}}
{{#{*2.}}{#{#.}}} .{.{#.{*2.}}.{#.{#.}}}
{{#{.#}}{#{##}}} .{.{#.{.#}}.{#.{##}}}
{{#{##}}{#.}} .{.{#.{##}}.{#.}}
{{#.}{##}} .{.{#.}.{##}}
{{##}.} .{.{##}.}
{.#} .{.#}
{##} .{##}
. .
# #
# #
It'll require quite a few changes, and a major version bump, but I've filed the ticket. This didn't really get much attention, since my main thrust is toweard seqaid automation.
Later: And now the changes were made, and the concrete syntax is slightly different (refer to the grammar):
((.(*(!*3)))(!(*1(!(.!))))) !(!(.!(*!(!*3)))!(!!(*1!(!!(.!))))) ((.(*5(.*2)))(.(.(.(..))))) !(!(.!(*5!(.*2)))!(.!(.!(.!(..))))) ((.(*4(.!)))(.(.(.!)))) !(!(.!(*4!(.!)))!(.!(.!(.!)))) ((.(*3(..)))(.(.(..)))) !(!(.!(*3!(..)))!(.!(.!(..)))) ((.(*2!))(.(.!))) !(!(.!(*2!))!(.!(.!))) ((.(!.))(.(..))) !(!(.!(!.))!(.!(..))) ((.(..))(.!)) !(!(.!(..))!(.!)) ((.!)(..)) !(!(.!)!(..)) ((..)!) !(!(..)!) (!.) !(!.) (..) !(..) ! ! . . . .
It's nice to see this in the reverse sequence, as a "growth strategy" to arrive at the big pattern. As a bonus, I've added whitespace padding to emphasise the structural relationships — this can't be done automatcially yet, although whitespace is accepted by the parser.
. ! (. . ) (! . ) ((.. )! ) ((.! )(.. ) ((.(. . ))(.! ) ((.(! . ))(.(. . ))) ((.(*2! ))(.(. ! ))) ((.(*3(.. )))(.(. (.. )))) ((.(*4(.! )))(.(. (.! )))) ((.(*5(.*2)))(.(. (.(..))))) ((.(* (!*3)))(!(*1(!(.!)))))
Oops! I see my tree shape was more monotonous than intended (although this is the most common texture seen in the wild, namely, right-biased binary trees).
I've fainted some parentheses, because, while I hesitate to obliterate them, they just take up space.
Now, if only we could just write "3" instead of "*3"!
. 1 (. . ) (1 . ) ((.. )1 ) ((.1 )(.. ) ((.(.. ))(.1 ) ((.(1. ))(.(.. ))) ((.(21 ))(.(.1 ))) ((.(3(..)))(.(.(.. )))) ((.(4(.1)))(.(.(.1 )))) ((.(5(.2)))(.(.(.(..))))) ((.(*(13)))(1(1(1(.1)))))
But unfortunately note the "13" on the last line. (And this example was in no way contrived to exhibit this problem, it arises naturally enough.)
To get around this up to and including depth 19, we can continue to use "!" for "*1":
. ! (. . ) (! . ) ((.. )! ) ((.! )(.. ) ((.(.. ))(.! ) ((.(!. ))(.(.. ))) ((.(2! ))(.(.! ))) ((.(3(..)))(.(.(.. )))) ((.(4(.!)))(.(.(.! )))) ((.(5(.2)))(.(.(.(..))))) ((.(*(!3)))(!(!(!(.!)))))
If I were going to be doing a lot of manual work with patterns, and didn't need NFDataN facilities deeper than 19, I would probably go with this.
However, the default must remain "*23" as it is unambiguous in the general case.
I'll offer a .cabal flag to enable the short version, why not.... This flag must absolutely be False by default. It is at the user's risk that they adopt non-default syntax...
And this one's even better (because unambiguous), though it can only express *N nodes up to a depth of nine:
. ! (0 0 ) (1 0 ) ((00 )1 ) ((01 )(00 ) ((0(00 ))(01 ) ((0(10 ))(0(00 ))) ((0(21 ))(0(01 ))) ((0(3(00)))(0(0(00 )))) ((0(4(01)))(0(0(01 )))) ((0(5(02)))(0(0(0(00))))) ((0(*(13)))(1(1(1(01)))))
And I then see a mistake (this is an hour before uploading 0.6.0.0), that WS has greater forcing potential than any WR so situated! So cannot shrink into it. After changing shrinkPat:
0 (0 0 ) ((00 )0 ) ((0(00 ))0 ) ((0(10 ))0 ) ((0(20 ))(00 )) ((0(3(00)))(0(00 ))) ((0(4(01)))(0(0(00 )))) ((0(5(02)))(0(0(0(00))))) ((0(*(13)))(1(1(1(01)))))
"I can has data family?..."
I'm not normally big on type extensions, and rarely stray beyond the precincts of H98 in my own code, but type families allured me. I am hoping to use it to express things about forcing functions in general (e.g. commutativity of composition).The data family certainly packs a whollop, making an extremely concise summary of deepseq-bounded. I don't know how to use it yet, but it compiles. :) Thought I'd throw it in, since Haskellers like their type extensions.
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleInstances #-} -- b/c Pattern = Node PatNode [Pattern] class FF k where
data F k :: * -> *
-- phi :: (Seqable v, NFDataN v, NFDataP v) => k -> F k v -> v
phi :: (Generic v, NFDataN v, NFDataP v) => k -> F k v -> v
-- phi :: Generic v => k -> F k v -> v -- would be nice... instance FF SeqNode -- Seqable.force_
instance FF Int -- NFDataN.forcen
instance FF Pattern -- NFDataP.forcep
The constraints could probably shrink to just Generic with a bit of work... In fact, trying it now -- to do away with NFDataN and NFDataP classes, same way implemented JUST_ALIAS_GSEQABLE flag for Seqable…
(reddit)