deeqSeq proposal

[Andy Gill]

On Apr 4, 2006, at 2:18 PM, John Meacham wrote:

> On Tue, Apr 04, 2006 at 11:52:55AM -0700, Andy Adams-Moran wrote:
>> I'm not convinced Simon's argument holds, as I don't think you can  
>> use
>> deepSeq to write a Haskell function that will distinguish cyclic
>> structures from infinite ones. If we can't do that, then we haven't
>> really added any new semantic observational capability to the  
>> theory, so
>> I think the "morally correct reasoning" argument holds.
>
> compiler optimizations don't necessarily preserve cyclic  
> structures. in
> practice they probably do, but there is no guarentee and we wouldn't
> want to start making one.

This goes the heart of the problem. Haskell does not have a space
usage semantics. My job is taking something that is not specified,
and giving a Haskell program that has an understandable space usage  
profile.

As part of this, I want a way of assuring that a data structure is  
fully evaluated -
thunklessness we might call it.  And we already perform transformations
that may or may not change space behavior.

   let xs = [1..n]
   in sum xs / length xs

Inlining xs can give a version that runs in constant space, but the  
given
example will take O(n) space, given typical evaluation order.

> another option would be for the DeepSeq class (or whatver) have a  
> depth
> limited version,
>
> deepSeqSome :: DeepSeq a => Int -> a -> a
>
> which would only traverse a limited depth into a structure.

Interesting idea!

  deepSeq = deepSeq maxInt ?

==> deepSeq *will* terminate on any cyclic structure
==> we can implement the cycle spotting optimization.

The only difference is how long before it might terminate,
not if it will terminate.

> Another issue is that being able to detect cyclic structures would  
> make
> it impossible to express deepSeq as a Haskell -> Haskell translation.
> which is no good.

I am trying to understand this requirement. For the sake of what must
all primitives be expressible as a Haskell -> Haskell translation?

Andy Gill