Andy Gill wrote:

On Apr 4, 2006, at 3:47 AM, Simon Marlow wrote:

...

On 30 March 2006 23:12, Andy Gill wrote:

...

Implementation:

deepSeq (RAW_CONS ... fields ) = if == True then return /* hey, we've already deepSeq'd this */ else set to True. deepSeq (field_1) ... deepSeq (field_n) deepSEQ (REF/MVAR...) = return

So deepSeq doesn't return _|_ when passed a cyclic structure? This is a bad idea, because it lets you distinguish cyclic structures from infinite ones. deepSeq has to behave like a function, regardless of its implementation.

Cheers, Simon

Good observation, though pragmatically I'd rather the deepSeq to behave well on loops. Its the thunks I'm trying to remove, not the loop itself.

Allowing loops in the returned value gives the the beauty of laziness to construct the cycle, but the assurance that the structure does not contain thunks. A nice property, and a way to interact with laziness.

let xs' () = 1 : 2 : xs' () let xs2 = xs'

let xs = 1 : 2 : xs

So deepSeq xs2 ==> _|_, but deepSeq xs ==> xs

I appeal to the "morally correct reasoning" argument .. If the program terminates, then it is still correct. The deepSeq is an assertion about the ability to represent the result in finite space.

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. Simon? A -- Andy Adams-Moran Phone: 503.626.6616, x113 Galois Connections Inc. Fax: 503.350.0833 12725 SW Millikan Way, Suite #290 http://www.galois.com Beaverton, OR 97005 adams-moran@galois.com

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

On Tue, 04 Apr 2006, Andy Gill wrote:

let xs' () = 1 : 2 : xs' () let xs2 = xs'

let xs = 1 : 2 : xs

So deepSeq xs2 ==> _|_, but deepSeq xs ==> xs

I appeal to the "morally correct reasoning" argument .. If the program terminates, then it is still correct.

To avoid confusion I'd like to note that this has nothing to do with the kind of moral correctness that I and some others wrote about recently. (I guess that this is the downside of choosing a phrase like that. :) -- /NAD

On Wed, Apr 05, 2006 at 10:34:09AM -0500, Spencer Janssen wrote:

How about an implementation that sets the deepSeq'd bit *after* each field has been successfully deepSeq'd? deepSeq'ing a cyclic structure would behave just like an infinite structure.

what would be the point of having a bit then? in any case, we should talk about the meaning of deepseqing something, not its implementation. depth limited recursive seq seems like the best route to me. John -- John Meacham - ⑆repetae.net⑆john⑈

On Thu, Apr 06, 2006 at 12:06:53AM -0700, Andy Gill wrote:

Because deepSeq's cost to evaluate a list that will eventually be required is linear. The maximum number of deepSeq calls (and recursive calls) you can do over any structure is simply the number of nodes.

Consider:

foldr (\ a as -> deepSeq (a : as)) [] $ some list

With the bit ==> one deepSeq per cons, then we hit the 'is-pre- deepSeqd' bit. Without the bit ==> O(n^2)

Ah, I see, I was thinking of something else. unfortunatly, this scheme or any scheme with changes to the run-time representation will be impossible in jhc. there is no concept of WHNF or thunks, let alone a generic way to evaluate them at run time in GRIN. John -- John Meacham - ⑆repetae.net⑆john⑈