deeqSeq proposal

31 Mar 2006

      For the reasons talked about in previous posts, I'd like to propose a  
deepSeq
for Haskell'.

  - 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.)

What I would like to propose for Haskell' are four things:

(Essential) Add a deepSeq function into Haskell'

deepSeq :: a -> b -> b

     - Don't really care if its in a class or not; would prefer not for
        the reasons John Hughes talked about.
     - This would deepSeq all its children for regular constructors.
     - deepSeq would not indirect into IO or MVar.
     - functions would be evaluated to (W?)HNF.
     - IO, ST are functions under the hood.

(Easy) Add a $!! function, and a strict function

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

(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:

deepSeq (RAW_CONS <is_deep_seq'd_bit> ... fields ) =
     if <is_deep_seq'd_bit> == True
         then return  /* hey, we've already deepSeq'd this */
         else set <is_deep_seq'd_bit> to True.
                  deepSeq (field_1)
                  ...
                  deepSeq (field_n)
deepSEQ (REF/MVAR...) = return

So we only deepSeq any specific constructor once! Sorta like lazy  
evaluation :-)
We'd need to catch exceptions, unset the is_deep_seq'd_bit, so that any
subsequent call of deepSeq would also have the option of raising the  
exception.

So,

  - How easy is this to add to the compilers? It looks pretty simple  
to me,
    and would provide huge bang-for-buck for Galois.
  - Any alternatives to the key concern; stomping on space leaks.
    (This proposal is orthogonal to the seq/Class discussion)

Andy Gill
Galois