Changes between Initial Version and Version 2 of Ticket #106


Ignore:
Timestamp:
Apr 6, 2006 4:54:20 PM (9 years ago)
Author:
guest
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #106

    • Property Topic changed from Unclassfied to Expressions & Patterns
    • Property Impact changed from normal to minor
    • 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.