The Comonad.Reader

Thu 22 Jul 2010

11 Responses to “Introducing Speculation”

1. Asger Ottar Alstrup Says:
   July 23rd, 2010 at 4:00 pm
   

   The techniques about inspecting the tags and the spark queue are interesting. It seems they would be very useful for search algorithms that continuously guess at solutions, until a solution that is good enough is found, or the entire search space has been exhausted, or time has run out.

   I.e. think of genetic algorithms, swarm optimization, and other randomized or heuristic search algorithms.

   Do you think the speculation primitive could be used to express such algorithms in a way that would exploit those tricks?

2. Edward Kmett Says:
   July 28th, 2010 at 8:34 am
   

   @Asger: You could likely exploit the speculation primitive if you supply your own equality check that checked fitness instead of value and used it to wrap the continuation, but I’ll admit I haven’t thought it through in depth.

3. pepeiborra Says:
   August 1st, 2010 at 6:37 am
   

   Looking at the unboxed version of unsafeGetTagBits, defined as:

   unsafeGetTagBits a = W# (and# (unsafeCoerce# a) (int2Word# mask#))

   I believe that this performs some evaluation of its argument. The program

   import Data.TagBits
   import Debug.Trace

   main = do
   let i = trace “X” [1]
   print (unsafeGetTagBits i)
   print i
   print (unsafeGetTagBits i)

   produces the output

   X
   2
   [1]
   2

   Also, I have been experiencing segfaults with this unboxed version.

   The boxed version does not segfault nor perform any evaluation, but in my experiments it seems to return always the value 0.
   For the program above, I obtain

   0
   X
   [1]
   0

   Concretely, I am using this code:

   data Box a = Box a
   unsafeGetTagBits a = unsafeCoerce (Box a) .&. fromIntegral (sizeOf (undefined :: Int) – 1)

   Any idea of what is going on?

4. Edward Kmett Says:
   August 1st, 2010 at 1:39 pm
   

   @Pepe: There are a couple of things happening here.

   You definitely shouldn’t be getting segfaults on the unboxed version. If so, then I have faulty reasoning and will need to revert to the boxed version.

   With regards to the boxed version still showing unevaluated-ness, what you’re experiencing is that the ‘i’ value at that point still points to the indirection because a garbage collection hasn’t happened yet to propagate the tag bits. I’d hazard that if you inserted a call to performGc in the middle there that you’d start seeing the tags.

5. pepeiborra Says:
   August 2nd, 2010 at 10:03 am
   

   Ed,

   thanks for the tips. I tried inserting a call to performGC in the example, but it didn’t help the boxed version.

   main = do
   let i = trace “–> evaluated” ()
   putStrLn $ “tagbits: ” ++ show (unsafeGetTagBits i)
   print i
   performGC >> putStrLn “–> GC performed”
   putStrLn $ “tagbits: ” ++ show (unsafeGetTagBits i)

   pepe:~/Dropbox/code/snippets$ ghc –make TagBits&& ./TagBits
   Linking TagBits …
   tagbits: 0
   –> evaluated
   ()
   –> GC performed
   tagbits: 0

   Nevertheless, I have gone back to my actual use case (pruning the non-evaluated branches of an incomplete infinite proof tree, for display purposes), and found I was traversing the tree bottom-up, with a non strict fold. In a bottom-up traversal, the boxed version was *correctly* returning False for subtrees (since the fold is lazy), whereas the unboxed version was actually seq’ing subtrees and returning True, which in the particular example at hand was what I expected. Hence the unboxed version was hiding an actual mistake in my reasoning. Now the boxed version works as expected with a top-down traversal.

   To see why the unboxed version forces evaluation of the argument, let’s look at the core generated by ghc:

   Data.TagBits.unsafeGetTagBits =
   \ (@ a_aqz) (a_syV :: a_aqz) ->
   case a_syV
   `cast` (CoUnsafe a_aqz GHC.Prim.Word# :: a_aqz ~ GHC.Prim.Word#)
   of wild_syX { __DEFAULT ->
   case GHC.Prim.and# wild_syX __word 3 of sat_sz3 { __DEFAULT ->
   GHC.Word.W# sat_sz3
   }
   }

   There is a case expression where the scrutinee is the argument. Unless I am wrong, this case expression forces the evaluation of the argument.

   If you are curious I also cooked a version of unsafeIsEvaluated which avoids the tricky pointer tagging business and looks directly at the info table: http://gist.github.com/504764

6. Edward Kmett Says:
   August 2nd, 2010 at 10:26 am
   

   I was deliberately avoiding reading the info table to avoid dealing with variations in ghc compilation options changing the layout.

   I’ll revert to the boxed version for now I guess and then see if I can get a better way to do the unsafeCoerce# without forcing.

7. Edward Kmett Says:
   August 2nd, 2010 at 10:30 am
   

   That said, it might be worthwhile to add that as a second check, assuming we can get something like the unboxed version to work in the first place.

   That way it could check the tag bits, and if zero, before giving up it could double check the info table, that way we avoid having to actually use the target object in case where the tag bits having been propagated, which potentially avoids paging it in.

8. Edward Kmett Says:
   September 16th, 2010 at 6:11 am
   

   FYI, I did wind up adding that info table check to the tag-bits library, although I do so only after checking the tag bits themselves as a fallback.

   It works well, and lets the library be useful even from ghci.

   Thanks!

9. Edward Kmett Says:
   September 22nd, 2010 at 3:28 pm
   

   Apparently, undefined will sometimes claim to be evaluated. Now I need to chase bottoms too!

10. Rafael Calsaverini Says:
    December 25th, 2010 at 10:22 pm
    

    This may be useful for Markov Chain Monte Carlo simulations by using the guess that the new sample proposal will be rejected… seems interesting.

11. Edward Kmett Says:
    December 26th, 2010 at 3:45 pm
    

    @Rafael: Good idea =)