Changes between Initial Version and Version 1 of deep_seq


Ignore:
Timestamp:
Apr 2, 2007 9:16:20 PM (8 years ago)
Author:
diatchki
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • deep_seq

    v1 v1  
     1=== Benefits ===
     2
     3 * It provides a mechanism to allow an effective, systematic tracking down of a class of space leaks.
     4 * It provides a mechanism to simply stomp on a class of space leaks.
     5 * It avoids the user having to explicitly declare instances for a homebrew deepSeq for every type in your program.
     6 * It has a declarative feel; this expression is hyper strict.
     7 * Is a specification of strictness.
     8 * It will open up various optimization opportunities, avoiding building thunks. (I dont talk about this more, but I'm happy to elaborate)
     9 * 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.)
     10 * We can ensure that there are no exceptions hiding inside a data structure.
     11 * We can throw an exception, and know that there are no exceptions hidding inside it. (are there exceptions in Haskell'?)
     12
     13=== Proposal ===
     14
     15What is being proposes for Haskell' are four things:
     16
     17Essential::
     18  Add a strict function into Haskell'
     19
     20{{{
     21strict :: a -> a
     22}}}
     23
     24 * I do not really care if its in a class or not; would prefer not for the reasons John Hughes talked about.
     25 * This would Deep Seq all its children for regular constructors.
     26 * strict would not indirect into IO or MVar.
     27 * functions would be evaluated to (W?)HNF.
     28 * IO, ST are functions under the hood for the purpose of strict.
     29
     30Easy::
     31  Add a $!! function, and a deepSeq function
     32
     33{{{
     34f $!! a = strict a `seq` f a
     35deepSeq a b = strict a `seq` b
     36}}}
     37
     38
     39We use strict as our primitive, rather than deepSeq.
     40The 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.
     41
     42
     43Nice::
     44  Add a !! notation, where we have ! in datatypes.
     45
     46{{{
     47data StrictList a = Cons (!!a) (!!StrictList a) | Nil
     48}}}
     49
     50Perhaps::
     51  Add a way of making *all* the fields strict/hyperstrict.
     52
     53{{{
     54data !!StrictList a = ..
     55}}}
     56
     57We could also do this for !
     58
     59
     60=== Implementation ===
     61{{{
     62strict :: a -> a
     63strict a@(RAW_CONS <is_deep_seq'd_bit> ... fields )) =
     64    if <is_deep_seq'd_bit> == True
     65        then return a /* hey, we've already deepSeq'd this */
     66        else do strict# (field_1)
     67                strict# (field_2)
     68                ...
     69                strict# (field_N)
     70                /* we set the test bit after the recursive calls */
     71                set <is_deep_seq'd_bit> to True.
     72                return a
     73
     74strict a@(REF/MVAR...) = return a
     75}}}
     76
     77We check the deep_seq'd but *after* evaluating children.
     78 * This Stops the (mis)use of strict to observe cycles.
     79 * With this order, we do not need to catch exceptions.
     80
     81
     82=== Issues ===
     83
     84 
     85 * Should there be a DeepSeq class?
     86 * Perhaps have an  unsafeStrict :: a -> IO a, that tags the deep_seq'd bit when descending.
     87
     88 * What would you expect to happen here?
     89
     90    {{{f x xs = let g y = x+y in map !! g xs}}}
     91
     92  Here I'm evaluating the function g hyperstrictly before the call
     93to map. Does x, the free variable in g's function closure, get evaluated?
     94 * Should we have the property
     95   {{{strict g === strict . g . strict}}}
     96 * Another option would be for the DeepSeq class (or whatver) have a depth limited version,
     97
     98   {{{
     99deepSeqSome :: DeepSeq a => Int -> a -> a
     100}}}
     101
     102  which would only traverse a limited depth into a structure.