andy at galois.com
Tue Apr 4 17:53:36 EDT 2006
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
>> 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
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
example will take O(n) space, given typical evaluation order.
> another option would be for the DeepSeq class (or whatver) have a
> limited version,
> deepSeqSome :: DeepSeq a => Int -> a -> a
> which would only traverse a limited depth into a structure.
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
> 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?
More information about the Haskell-prime