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
_______________________________________________
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
