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.