deeqSeq proposal

[Simon Peyton-Jones]

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.

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
| 
| _______________________________________________
| Haskell-prime mailing list
| Haskell-prime at haskell.org
| http://haskell.org/mailman/listinfo/haskell-prime