Changes between Initial Version and Version 2 of Ticket #106

Show
Ignore:
Timestamp:
04/06/06 09:54:20 (7 years ago)
Author:
guest
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #106

    • Property impact changed from normal to minor
    • Property topic changed from Unclassfied to Expressions & Patterns
    • Property adopt changed from to probably yes
    • Property summary changed from Adding deepSeq to Haskell' beside seq. to Adding deepSeq/strict to Haskell' beside seq.

  • Ticket #106 – description

    initial v2  
    1 I'd like to propose a deepSeq for Haskell'. 
     1We are considering deepSeq for Haskell'. 
     2 
     3=== Benefits === 
    24 
    35 * It provides a mechanism to allow an effective, systematic tracking down of a class of space leaks. 
    … …  
    810 * It will open up various optimization opportunities, avoiding building thunks. (I dont talk about this more, but I'm happy to elaborate) 
    911 * 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.) 
     12 * We can ensure that there are no exceptions hiding inside a data structure. 
     13 * We can throw an exception, and know that there are no exceptions hidding inside it. (are there exceptions in Haskell'?) 
    1014 
    11 What I would like to propose for Haskell' are four things: 
     15=== Proposal === 
     16 
     17What is being proposes for Haskell' are four things: 
    1218 
    1319Essential:: 
    14   Add a deepSeq function into Haskell' 
     20  Add a strict function into Haskell' 
    1521 
    1622{{{ 
    17 deepSeq :: a -> b -> b 
     23strict :: a -> a 
    1824}}} 
    1925 
    2026 * I do not really care if its in a class or not; would prefer not for the reasons John Hughes talked about. 
    21  * This would deepSeq all its children for regular constructors. 
    22  * deepSeq would not indirect into IO or MVar. 
     27 * This would Deep Seq all its children for regular constructors. 
     28 * strict would not indirect into IO or MVar. 
    2329 * functions would be evaluated to (W?)HNF. 
    24  * IO, ST are functions under the hood for the purpose of deepSeq. 
     30 * IO, ST are functions under the hood for the purpose of strict. 
    2531 
    2632Easy:: 
    27   Add a $!! function, and a strict function 
     33  Add a $!! function, and a deepSeq function 
    2834 
    2935{{{ 
    30 f $!! a = a `deepSeq` f a 
    31 strict a = a `deepSeq` a 
     36f $!! a = strict a `seq` f a 
     37deepSeq a b = strict a `seq` b 
    3238}}} 
     39 
     40 
     41We use strict as our primitive, rather than deepSeq. 
     42The 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. 
     43 
    3344 
    3445Nice:: 
    … …  
    4859We could also do this for ! 
    4960 
    50 -------------- 
    5161 
    52 Implementation: 
     62=== Implementation === 
    5363{{{ 
    54 deepSeq a b = strict# a `seq` b 
     64strict :: a -> a  
     65strict a@(RAW_CONS <is_deep_seq'd_bit> ... fields )) =  
     66    if <is_deep_seq'd_bit> == True 
     67        then return a /* hey, we've already deepSeq'd this */ 
     68        else do strict# (field_1) 
     69                strict# (field_2) 
     70                ... 
     71                strict# (field_N) 
     72                /* we set the test bit after the recursive calls */ 
     73                set <is_deep_seq'd_bit> to True. 
     74                return a 
    5575 
    56 strict# (RAW_CONS <is_deep_seq'd_bit> ... fields )) = 
    57     if <is_deep_seq'd_bit> == True 
    58         then return  /* hey, we've already deepSeq'd this */ 
    59         else set <is_deep_seq'd_bit> to True. 
    60                  deepSeq (field_1) 
    61                  ... 
    62                  deepSeq (field_n) 
    63 strict# (REF/MVAR...) = return 
     76strict a@(REF/MVAR...) = return a 
    6477}}} 
    6578 
    66 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. 
     79We check the deep_seq'd but *after* evaluating children. 
     80 * This Stops the (mis)use of strict to observe cycles. 
     81 * With this order, we do not need to catch exceptions. 
     82 
     83 
     84=== Issues === 
     85 
     86   
     87 * Should there be a DeepSeq class? 
     88 * Perhaps have an  unsafeStrict :: a -> IO a, that tags the deep_seq'd bit when descending. 
     89 
     90 * What would you expect to happen here? 
     91 
     92    {{{f x xs = let g y = x+y in map !! g xs}}} 
     93 
     94  Here I'm evaluating the function g hyperstrictly before the call 
     95to map. Does x, the free variable in g's function closure, get evaluated? 
     96 * Should we have the property  
     97   {{{strict g === strict . g . strict}}} 
     98 * Another option would be for the DeepSeq class (or whatver) have a depth limited version, 
     99 
     100   {{{ 
     101deepSeqSome :: DeepSeq a => Int -> a -> a 
     102}}} 
     103 
     104  which would only traverse a limited depth into a structure.