Changes between Version 3 and Version 4 of Ticket #106


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

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #106 – Description

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