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.