deeqSeq proposal

[Robert Dockins]

On Apr 3, 2006, at 7:16 AM, Simon Peyton-Jones wrote:

> Interesting idea.
>
> What would you expect to happen here?
>
> 	f x xs = let g y = x+y in map !! g xs
>
> Here I'm evaluating the function g hyperstrictly before the call to  
> map.
> Does x, the free variable in g's function closure, get evaluated?
>
>> From an implementation point of view, you could imagine that  
>> hyperstrict
> evaluation would pull apart function closures, as well as data
> structures.  But I'm not sure you could give that a sensible
> denotational semantics.


Indeed, the semantics would be troublesome.  I'd much prefer to see  
the semantics of hyperstrict (what a great term!) functions defined  
with a nice conjugation property, ie, if 'strict' is a partial  
function (forall a. a -> a) then for g::(b -> c)

strict g === strict . g . strict

Which (I believe) should do what you would expect for multi-argument  
functions; all arguments are evaluated hyperstrict, g is applied, and  
then the result is evaluated hyperstrict.
Easy to specify and reason about.




> Simon
>
> | -----Original Message-----
> | From: haskell-prime-bounces at haskell.org
> [mailto:haskell-prime-bounces at haskell.org] On Behalf Of
> | Andy Gill
> | Sent: 30 March 2006 23:12
> | To: haskell-prime at haskell.org
> | Cc: Laura McKinney
> | Subject: deeqSeq proposal
> |
> | For the reasons talked about in previous posts, I'd like to  
> propose a
> | deepSeq
> | for Haskell'.
> |
> |   - It provides a mechanism to allow an effective, systematic
> | tracking down of
> |   a class of space leaks.
> |   - It provides a mechanism to simply stomp on a class of space  
> leaks.
> |   - It avoids the user having to explicitly declare instances for a
> | homebrew deepSeq
> |    for every type in your program.
> | - It has a declarative feel; this expression is hyper strict.
> | - Is a specification of strictness.
> | - It will open up various optimization opportunities, avoiding
> | building thunks.
> |     (I dont talk about this more, but I'm happy to elaborate)
> | - 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.)
> |
> | What I would like to propose for Haskell' are four things:
> |
> | (Essential) Add a deepSeq function into Haskell'
> |
> | deepSeq :: a -> b -> b
> |
> |      - Don't really care if its in a class or not; would prefer not
> for
> |         the reasons John Hughes talked about.
> |      - This would deepSeq all its children for regular constructors.
> |      - deepSeq would not indirect into IO or MVar.
> |      - functions would be evaluated to (W?)HNF.
> |      - IO, ST are functions under the hood.
> |
> | (Easy) Add a $!! function, and a strict function
> |
> | f $!! a = a `deepSeq` f a
> | strict a = a `deepSeq` a
> |
> | (Nice) Add a !! notation, where we have ! in datatypes.
> |
> | data StrictList a = Cons (!!a) (!!StrictList a) | Nil
> |
> | (Perhaps) Add a way of making *all* the fields strict/hyperstrict.
> |
> | data !!StrictList a = ..,
> |
> | We could also do this for !
> |
> | --------------
> |
> | Implementation:
> |
> | deepSeq (RAW_CONS <is_deep_seq'd_bit> ... fields ) =
> |      if <is_deep_seq'd_bit> == True
> |          then return  /* hey, we've already deepSeq'd this */
> |          else set <is_deep_seq'd_bit> to True.
> |                   deepSeq (field_1)
> |                   ...
> |                   deepSeq (field_n)
> | deepSEQ (REF/MVAR...) = return
> |
> | 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.
> |
> | So,
> |
> |   - How easy is this to add to the compilers? It looks pretty simple
> | to me,
> |     and would provide huge bang-for-buck for Galois.
> |   - Any alternatives to the key concern; stomping on space leaks.
> |     (This proposal is orthogonal to the seq/Class discussion)
> |
> | Andy Gill
> | Galois


Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG