DeepSeq

Benefits

• It provides a mechanism to allow an effective, systematic tracking down of a class of space leaks.
• It provides a mechanism to simply stomp on a class of space leaks.
• It avoids the user having to explicitly declare instances for a homebrew deepSeq for every type in your program.
• It has a declarative feel; this expression is hyper strict.
• Is a specification of strictness.
• It will open up various optimization opportunities, avoiding building thunks. (I dont talk about this more, but I'm happy to elaborate)
• It can have an efficient implementation, or a simple (slow) implementation. (The fast implementation one can be used to stomp space leaks, the slow one can help find the same leaks.)
• We can ensure that there are no exceptions hiding inside a data structure.
• We can throw an exception, and know that there are no exceptions hidding inside it. (are there exceptions in Haskell'?)

Proposal

What is being proposes for Haskell' are four things:

Essential::

Add a strict function into Haskell'

strict :: a -> a

• I do not really care if its in a class or not; would prefer not for the reasons John Hughes talked about.
• This would Deep Seq all its children for regular constructors.
• strict would not indirect into IO or MVar.
• functions would be evaluated to (W?)HNF.
• IO, ST are functions under the hood for the purpose of strict.

Easy::

Add a $!! function, and a deepSeq function

f $!! a = strict a `seq` f a
deepSeq a b = strict a `seq` b

We use strict as our primitive, rather than deepSeq. The expressions (x deepSeq y deepSeq z) and (strict x seq strict y seq z) are equivalent, but only the latter makes it clear that z doesn't get fully evaluated.

Nice::

Add a !! notation, where we have ! in datatypes.

data StrictList a = Cons (!!a) (!!StrictList a) | Nil

Perhaps::

Add a way of making *all* the fields strict/hyperstrict.

data !!StrictList a = ..

We could also do this for !

Implementation

strict :: a -> a 
strict a@(RAW_CONS <is_deep_seq'd_bit> ... fields )) = 
    if <is_deep_seq'd_bit> == True
        then return a /* hey, we've already deepSeq'd this */
        else do strict# (field_1)
                strict# (field_2)
                ...
                strict# (field_N)
                /* we set the test bit after the recursive calls */
                set <is_deep_seq'd_bit> to True.
                return a

strict a@(REF/MVAR...) = return a

We check the deep_seq'd but *after* evaluating children.

• This Stops the (mis)use of strict to observe cycles.
• With this order, we do not need to catch exceptions.

Issues

• Should there be a DeepSeq? class?

• Perhaps have an unsafeStrict :: a → IO a, that tags the deep_seq'd bit when descending.

• What would you expect to happen here?

f x xs = let g y = x+y in map !! g xs

Here I'm evaluating the function g hyperstrictly before the call

to map. Does x, the free variable in g's function closure, get evaluated?

• Should we have the property strict g === strict . g . strict
• Another option would be for the DeepSeq? class (or whatver) have a depth limited version,

deepSeqSome :: DeepSeq a => Int -> a -> a

which would only traverse a limited depth into a structure.