Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
On Mon, Apr 20, 2009 at 2:54 PM, Peter Verswyvelen bugf...@gmail.comwrote: I find this very confusing. Is the documentation of seq wrong (should be weak head normal form)? Yes. Weak head normal form is really the only *essential* one. The popular runtimes do not know how to reduce under a lambda, so they can't reduce something to hnf. Anyway, so I guess we would actually need a function: iswhnf :: a - IO Bool But since the value of this iswhnf function depends on when it is called, I feel it has to be in the IO monad; actually multiple threads evaluating it have nothing to do with it? This is an impure function for a few reasons. I.e. not only does it give different answers at different times (depending on evaluation order), but it is not pure in the domain theory; i.e. (\x. x) 42 = 42, but iswhnf gives different answers for these. So yes, definitely in IO, as a runtime extension (I wouldn't even expect this function to be implementable on all runtimes). Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Optimizing unamb by determining the state of a thunk?
I was wandering if it would be possible to optimize unambhttp://hackage.haskell.org/packages/archive/unamb/0.1.9/doc/html/Data-Unamb.html#v%3Aunamb by checking if a value is already evaluated to head normal form. So f `unamb` g would then be extremely fast if either f or g is already evaluated to head normal form. Maybe using some vacuum tricks? This function would need to be in IO since it is of course not referentially transparent. Although threads are lightweight in Haskell, forking/waiting/killing surely must have more overhead than just checking the thunk of an expression? Of course one could also make unamb a primitive :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
On 20 Apr 2009, at 09:41, Peter Verswyvelen wrote: I was wandering if it would be possible to optimize unamb by checking if a value is already evaluated to head normal form. So f `unamb` g would then be extremely fast if either f or g is already evaluated to head normal form. Maybe using some vacuum tricks? This function would need to be in IO since it is of course not referentially transparent. Really? Is it any less referentially transparent than unamb already is - i.e. it's referentially transparent, as long as the two values really are equal. Although threads are lightweight in Haskell, forking/waiting/killing surely must have more overhead than just checking the thunk of an expression? Of course one could also make unamb a primitive :-) That would be a lovely solution for me. Bob___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
On Mon, Apr 20, 2009 at 10:23 AM, Thomas Davie tom.da...@gmail.com wrote: Really? Is it any less referentially transparent than unamb already is - i.e. it's referentially transparent, as long as the two values really are equal. I think it is. Suppose we call the function hnf :: a - Bool. hnf might return a different result for the same argument, since the evaluation of the argument might be happening on a different thread, so the result of hnf depends on the time when it is evaluated. Or am I missing something here? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
On 20 Apr 2009, at 10:57, Peter Verswyvelen wrote: On Mon, Apr 20, 2009 at 10:23 AM, Thomas Davie tom.da...@gmail.com wrote: Really? Is it any less referentially transparent than unamb already is - i.e. it's referentially transparent, as long as the two values really are equal. I think it is. Suppose we call the function hnf :: a - Bool. hnf might return a different result for the same argument, since the evaluation of the argument might be happening on a different thread, so the result of hnf depends on the time when it is evaluated. Or am I missing something here? Sure, so hnf would give us a non-determined result, but I don't think that makes unamb any less referentially transparent – the same value is always returned, and always reduced at least to hnf. Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
Sure, so hnf would give us a non-determined result, but I don't think that makes unamb any less referentially transparent – the same value is always returned, and always reduced at least to hnf. I think it is hnf that Peter was talking about needing to be in IO, not unamb. - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
Yes indeed. On Mon, Apr 20, 2009 at 3:42 PM, Jake McArthur jake.mcart...@gmail.comwrote: Sure, so hnf would give us a non-determined result, but I don't think that makes unamb any less referentially transparent – the same value is always returned, and always reduced at least to hnf. I think it is hnf that Peter was talking about needing to be in IO, not unamb. - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
I'm sort of backtracking from your opinion that this hnf would need to be
in IO. Are you imagining something like?
data (NFData a) = OnceNFData n = OnceNFData { the_data :: a, is_normal_form ::
(IORef Bool) }
I think GHC generally prevents parallel evaluation of the same unevaluated
shared thunk[1].
What we'd like to avoid is duplicate verification that a thunk is hnf.
Do we have evidence that this verification ever actually consumes a lot of
resources?
I don't see any reason why it shouldn't be possible to fully force a and
update the IORef from unsafePerformIO. I see no need for any
additional thread safety here.
There is a relevant proposal in the haskell prime wiki[2].
Unless I'm way off topic.
Friendly,
--Lane
[1]
http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/multiproc.pdf
[2] http://hackage.haskell.org/trac/haskell-prime/ticket/106
On Mon, 20 Apr 2009, Peter Verswyvelen wrote:
Yes indeed.
On Mon, Apr 20, 2009 at 3:42 PM, Jake McArthur jake.mcart...@gmail.com wrote:
Sure, so hnf would give us a non-determined result, but I don't
think that makes unamb any less referentially transparent ? the same value is
always returned, and always reduced at least to hnf.
I think it is hnf that Peter was talking about needing to be in IO, not unamb.
- Jake
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
Christopher Lane Hinson wrote: What we'd like to avoid is duplicate verification that a thunk is hnf. Do we have evidence that this verification ever actually consumes a lot of resources? I think the OP is trying to avoid spawning unnecessary threads at the cost of duplicate checks for HNF. - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing unamb by determining the state of a thunk?
f `unamb` g just needs f or g to be in weak head normal form I think. This should be much easier to test for I guess. I always confuse weak head normal form with reduced head normal form, but the documentation of GHC does not help here: E.g.: -- | Reduces its argument to weak head normal form.rwhnf :: Strategy a rwhnf x = x `seq` () but the documentation of seq says *seq* :: a - b - bSource file:///C:/app/ghc-6.10.2/doc/libraries/ghc-prim/src/GHC-Prim.html#seqEvaluates its first argument to head normal form, and then returns its second argument as the result. Furthermore: *rnf* :: Strategy file:///C:/app/ghc-6.10.2/doc/libraries/parallel/Control-Parallel-Strategies.html#t%3AStrategy aSource file:///C:/app/ghc-6.10.2/doc/libraries/parallel/src/Control-Parallel-Strategies.html#rnfReduces its argument to (head) normal form. So from the documentation rnf should be like seq, but it is not, rnf is a deep seq. I find this very confusing. Is the documentation of seq wrong (should be weak head normal form)? Anyway, so I guess we would actually need a function: iswhnf :: a - IO Bool But since the value of this iswhnf function depends on when it is called, I feel it has to be in the IO monad; actually multiple threads evaluating it have nothing to do with it? On Mon, Apr 20, 2009 at 10:05 PM, Jake McArthur jake.mcart...@gmail.comwrote: Christopher Lane Hinson wrote: What we'd like to avoid is duplicate verification that a thunk is hnf. Do we have evidence that this verification ever actually consumes a lot of resources? I think the OP is trying to avoid spawning unnecessary threads at the cost of duplicate checks for HNF. - Jake ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
