deeqSeq proposal
Simon PeytonJones
simonpj at microsoft.com
Mon Apr 3 07:16:00 EDT 2006
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: haskellprimebounces at haskell.org
[mailto:haskellprimebounces at haskell.org] On Behalf Of
 Andy Gill
 Sent: 30 March 2006 23:12
 To: haskellprime 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 bangforbuck for Galois.
  Any alternatives to the key concern; stomping on space leaks.
 (This proposal is orthogonal to the seq/Class discussion)

 Andy Gill
 Galois

 _______________________________________________
 Haskellprime mailing list
 Haskellprime at haskell.org
 http://haskell.org/mailman/listinfo/haskellprime
More information about the Haskellprime
mailing list