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