LogicGrowsOnTrees 1.1.0.1 → 1.1.0.2
raw patch · 6 files changed
+2119/−6 lines, 6 files
Files
- CHANGELOG.md +62/−0
- LogicGrowsOnTrees.cabal +10/−5
- README.md +363/−0
- TUTORIAL.md +1198/−0
- USERS_GUIDE.md +485/−0
- tests/tests.hs +1/−1
+ CHANGELOG.md view
@@ -0,0 +1,62 @@+version 1.1.0.2+===============++* Tweaked the test suite to resolve minor problems when running on Windows and+ older GHCs.++* Added the documentation files to the Hackage source distribution.++* Deleted some no longer relevant advice on building the tests (as the version+ dependency of test-framework-quickcheck was finally bumped).+++version 1.1.0.1+===============++* Bumped lens version dependency.+++Version 1.1+===========++Highlights+----------++* Many performance enhancements, speeding up code using `Main` and `Threads` by+ a factor of two and reducing the overhead of `LogicGrowsOnTrees` overall by a+ factor of two.+++New Features+------------++* Now statistics can be logged on a regular basis.++* Exposed `getCurentStatistics` in the `RequestQueueMonad`, allowing one to+ obtain the statistics at any time during the run.++* Added a system for estimating the total number of CPU-hours used (including+ the time spent waiting for a workload) in total by all of the workers during+ the run.++* Made the types `Arity` and `ArityAndDepth` serializable.+++Miscellaneous+-------------++* Revamped the command line options for specifying which statistics should be+ displayed in order to make them easier to use.++* Tweaked the log levels of some of the logged messages.++* Bumped version dependencies.++* Now `Context` is a list rather than a `Seq`. (This change is what caused the+ bump to version 1.1 to conform with the PVP.)+++Attempted Ideas That Turned Out To Be Bad+-----------------------------------------++* Converting from `operational` to `free` led to a performance regression.
LogicGrowsOnTrees.cabal view
@@ -1,5 +1,5 @@ Name: LogicGrowsOnTrees-Version: 1.1.0.1+Version: 1.1.0.2 License: BSD3 License-file: LICENSE Author: Gregory Crosswhite@@ -199,7 +199,12 @@ @LogicGrowsOnTrees.Parallel.Common.*@ modules are primarily geared towards people writing their own adapter. -Extra-source-files: c-sources/queens.c+Extra-source-files:+ c-sources/queens.c+ CHANGELOG.md+ README.md+ TUTORIAL.md+ USERS_GUIDE.md Bug-reports: https://github.com/gcross/LogicGrowsOnTrees/issues @@ -210,7 +215,7 @@ Source-Repository this Type: git Location: git://github.com/gcross/LogicGrowsOnTrees.git- Tag: 1.1.0.1+ Tag: 1.1.0.2 Library Build-depends:@@ -795,9 +800,9 @@ uuid >= 1.2 && < 1.4, void == 0.6.* if flag(warnings)- GHC-Options: -Wall -fno-warn-name-shadowing -with-rtsopts=-M256M+ GHC-Options: -Wall -fno-warn-name-shadowing -with-rtsopts=-M512M else- GHC-Options: -with-rtsopts=-M256M+ GHC-Options: -with-rtsopts=-M512M Test-Suite test-nqueens Type: exitcode-stdio-1.0
+ README.md view
@@ -0,0 +1,363 @@+What is LogicGrowsOnTrees?+==========================++LogicGrowsOnTrees is a library that lets you use a standard Haskell domain+specific language (`MonadPlus` and friends) to write logic programs (by which we+mean programs that make non-deterministic choices and have guards to enforce+constraints) that you can run in a distributed setting.+++Could you say that again in Haskellese?+=======================================++LogicGrowsOnTrees provides a logic programming monad designed for distributed+computing; specifically, it takes a logic program (written using `MonadPlus`),+represents it as a (lazily generated) tree, and then explores the tree in+parallel.+++What do you mean by "distributed"?+==================================++By "distributed" I mean parallelization that does not required shared memory but+only some form of communication. In particular there is package that is a+sibling to this one that provides an *adapter* for MPI that gives you+immediate access to large numbers of nodes on most supercomputers. In fact, the+following is the result of an experiment to see how well the time needed to+solve the N-Queens problem scales with the number of workers for N=17, N=18, and+N=19 on a local cluster:++++The above was obtained by running a job, which counts the number of solutions,+three times for each number of workers and problem size, and then taking the+shortest time of each set of three*; the maximum number of workers for this+experiment (256) was limited by the size of the cluster. From the above plot we+see that scaling is generally good with the exception of the N=18 case for 128+workers and above, which is not necessarily a big deal since the total running+time is under 10 seconds.++\* All of the data points for each value of N were usually within a small+percentage of one another, save for (oddly) the *left*-most data point+(i.e., the one with the fewest workers) for each problem size, which varied from+150%-200% of the best time; the full data set is available in the `scaling/`+directory.+++When would I want to use this package?+======================================++This package is useful when you have a large space that can be defined+efficiently using a logic program that you want to explore to satisfy some goal,+such as finding all elements, counting the number of elements, finding just one+or a few elements, etc.++LogicGrowsOnTrees is particularly useful when your solution space has a lot of+structure as it gives you full control over the non-deterministic choices that+are made, which lets you entirely avoid making choices that you know will end in+failure, as well as letting you factor out symmetries so that only one solution+is generated out of some equivalence class. For example, if permutations result+in equivalent solutions then you can factor out this symmetry by only choosing+later parts of a potential solution that are greater than earlier parts of the+solution.++What does a program written using this package look like?+=========================================================++The following is an example of a program (also given in+`examples/readme-simple.hs`) that counts the number of solutions to the n-queens+problem for a board size of 10:++NOTE: I have optimized this code to be (hopefully) easy to follow, rather than+to be fast.++```haskell+import Control.Monad+import qualified Data.IntSet as IntSet++import LogicGrowsOnTrees+import LogicGrowsOnTrees.Parallel.Main+import LogicGrowsOnTrees.Parallel.Adapter.Threads+import LogicGrowsOnTrees.Utils.Word_+import LogicGrowsOnTrees.Utils.WordSum++-- Code that counts all the solutions for a given input board size.+nqueensCount 0 = error "board size must be positive"+nqueensCount n =+ -- Start with...+ go n -- ...n queens left...+ 0 -- ... at row zero...+ -- ... with all columns available ...+ (IntSet.fromDistinctAscList [0..fromIntegral n-1])+ IntSet.empty -- ... with no occupied negative diagonals...+ IntSet.empty -- ... with no occupied positive diagonals.+ where+ -- We have placed the last queen, so this is a solution!+ go 0 _ _ _ _ = return (WordSum 1)++ -- We are still placing queens.+ go n+ row+ available_columns+ occupied_negative_diagonals+ occupied_positive_diagonals+ = do+ -- Pick one of the available columns.+ column <- allFrom $ IntSet.toList available_columns++ -- See if this spot conflicts with another queen on the negative diagonal.+ let negative_diagonal = row + column+ guard $ IntSet.notMember negative_diagonal occupied_negative_diagonals++ -- See if this spot conflicts with another queen on the positive diagonal.+ let positive_diagonal = row - column+ guard $ IntSet.notMember positive_diagonal occupied_positive_diagonals++ -- This spot is good! Place a queen here and move on to the next row.+ go (n-1)+ (row+1)+ (IntSet.delete column available_columns)+ (IntSet.insert negative_diagonal occupied_negative_diagonals)+ (IntSet.insert positive_diagonal occupied_positive_diagonals)++main =+ -- Explore the tree generated (implicitly) by nqueensCount in parallel.+ simpleMainForExploreTree+ -- Use threads for parallelism.+ driver++ -- Function that processes the result of the run.+ (\(RunOutcome _ termination_reason) -> do+ case termination_reason of+ Aborted _ -> error "search aborted"+ Completed (WordSum count) -> putStrLn $ "found " ++ show count ++ " solutions"+ Failure _ message -> error $ "error: " ++ message+ )++ -- The logic program that generates the tree to explore.+ (nqueensCount 10)+```++This program requires that the number of threads be specified via `-n #` on the+command line, where `#` is the number of threads. You can use `-c` to have the+program create a checkpoint file on a regular basis and `-i` to set how often+the checkpoint is made (defaults to once per minute); if the program starts up+and sees the checkpoint file then it automatically resumes from it. To find out+more about the available options, use `--help` which provides an automatically+generated help screen.++The above uses threads for parallelism, which means that you have to compile it+using the `-threaded` option. If you want to use processes instead of threads+(which could be more efficient as this does not require the additional overhead+incurred by the threaded runtime), then install `LogicGrowsOnTrees-processes`+and replace `Threads` with `Processes` in the import at the 8th line. If you+want workers to run on different machines then install+`LogicGrowsOnTrees-processes` and replace `Threads` with `Network`. If you have+access to a cluster with a large number of nodes, you will want to install+`LogicGrowsOnTrees-MPI` and replace `Threads` with `MPI`.++If you would prefer that the problem size be specified at run-time via a+command-line argument rather than hard-coded at compile time, then you can use+the more general mechanism illustrated as follows (a complete listing is given+in `examples/readme-full.hs`):++```haskell+import Control.Applicative+import System.Console.CmdTheLine+...+main =+ -- Explore the tree generated (implicitly) by nqueensCount in parallel.+ mainForExploreTree+ -- Use threads for parallelism.+ driver++ -- Use a single positional required command-line argument to get the board size.+ (getWord+ <$>+ (required+ $+ pos 0+ Nothing+ posInfo+ { posName = "BOARD_SIZE"+ , posDoc = "board size"+ }+ )+ )++ -- Information about the program (for the help screen).+ (defTI { termDoc = "count the number of n-queens solutions for a given board size" })++ -- Function that processes the result of the run.+ (\n (RunOutcome _ termination_reason) -> do+ case termination_reason of+ Aborted _ -> error "search aborted"+ Completed (WordSum count) -> putStrLn $+ "for a size " ++ show n ++ " board, found " ++ show count ++ " solutions"+ Failure _ message -> error $ "error: " ++ message+ )++ -- The logic program that generates the tree to explore.+ nqueensCount+```+++Where can I learn more?+=======================++Read [TUTORIAL.md](TUTORIAL.md) for a tutorial of how to write and run logic+programs using this package, [USERS_GUIDE.md](USERS_GUIDE.md) for a more+detailed explanation of how things work, and the haddock documentation available+at http://hackage.haskell.org/package/LogicGrowsOnTrees.++What platforms does it support:+===============================++The following three packages have been tested on Linux, OSX, and Windows using+the latest Haskell Platform (2013.2.0.0):++* `LogicGrowsOnTrees` (+ Threads adapter)++* `LogicGrowsOnTrees-processors`++* `LogicGrowsOnTrees-network`++`LogicGrowsOnTrees-MPI` has been tested as working on Linux and OSX using+[OpenMPI](http://www.open-mpi.org/), and since it only uses very basic+functionality (just sending, probing, and receiving messages) it should work on+any MPI implementation.++(I wasn't able to try Microsoft's MPI implementation because it only let me+install the 64-bit version (as my test machine was 64-bit) but Haskell on+Windows is only 32-bit.)+++Why would I use this instead of Cloud Haskell?+==============================================++This package is higher level than Cloud Haskell in that it takes care of all the+work of parallelizing your logic program for you. In fact, if one wished one+could potentially write an *adapter* for LogicGrowsOnTrees that lets one use+Cloud Haskell as the communication layer.+++Why would I use this instead of MapReduce?+==========================================++MapReduce and LogicGrowsOnTrees can both be viewed (in a *very* rough sense) as+mapping a function over a large data set and then performing a reduction on it.+The primary difference between them is that MapReduce is optimized for the case+where you have a huge data set that already exists (which means in particular+that optimizing I/O operations is a big deal), whereas LogicGrowsOnTrees is+optimized for the case where your data set needs to be generated on the fly+using a (possibly quite expensive) operation that involves making many+non-deterministic choices some of which lead to dead-ends (that produce no+results). Having said that, LogicGrowsOnTrees can also be used like MapReduce by+having your function generate data by reading it from files or possibly from a+database.+++Why would I use this instead of a SAT/SMT/CLP/etc. solver?+==========================================================++First, it should be mentioned that one could use LogicGrowsOnTrees to implement+these solvers. That is, a solver could be written that uses the `mplus` function+whenever it needs to make a non-deterministic choices (e.g. when guessing+whether a boolean variable should be true or false) and `mzero` to indicate+failure (e.g., when it has become clear that a particular set of choices cannot+result in a valid solution), and then the solver gets to use the parallelization+framework of this package for free! (For an example of such a solver, see the+[incremental-sat-solver+package](http://hackage.haskell.org/packages/archive/incremental-sat-solver/0.1.7/doc/html/Data-Boolean-SatSolver.html)+(which was not written by me).)++Having said that, if your problem can most easily and efficiently be expressed+as an input to a specialized solver, then this package might not be as useful to+you. *However*, even in this case you *might* still want to consider using this+package if there are constraints that you cannot express easily or efficiently+using one of the specialized solvers because this package gives you complete+control over how choices are made which means that you can, for example, enforce+a constraint by only making choices that are guaranteed to satisfy it, rather+than generating choices that may or may not satisfy it and then having to+perform an additional step to filter out all the ones that don't satisfy the+constraint.+++What is the overhead of using LogicGrowsOnTrees?+================================================++It costs approximately up to twice as much time to use LogicGrowsOnTrees with+a single worker thread as it does to use the List monad. Fortunately, it is+possible to eliminate most of this if you can switch to using the List monad+near the bottom of the tree. For example, my optimized n-queens solver switches+to a loop in C when fewer than eleven queens remain to be placed. This is not+``cheating'' for two reasons: first, because the hard part is the+symmetry-breaking code, which would have been difficult to implement and test in+C due to its complexity, and second, because one can't rewrite all the code+in C because then one would lose access to the automatic checkpointing and+parallelization features.++Why Haskell?+============++Haskell has many strengths that made it ideal for this project:++1. Laziness++ Haskell has lazy* evaluation which means that it does not evaluate anything+ until the value is required to make progress; this capability means that+ ordinary functions can act as control structures. In particular, when you+ use `mplus a b` to signal a non-deterministic choice, neither `a` nor `b`+ will be evaluated unless one chooses to explore respectively the left and/or+ right branch of the corresponding decision tree. This is very powerful+ because it allows us to explore the decision tree of a logic program as much+ or as little as we want and only have to pay for the parts that we choose to+ explore.++ \* Technically Haskell is "non-strict" rather than "lazy", which means+ there might be times in practice when it evaluates something more than is+ strictly needed.+++2. Purity++ Haskell is a pure language, which means that functions have no (observable)+ side-effects other than returning a value*; in particular, this implies that+ all operations on data must be immutable, which means that they result in a+ new value (that may reference parts or even all of the old value) rather+ than modifying the old value. This is an incredible boon because it means+ that when we backtrack up to explore another branch of the decision tree we+ do not have to perform an undo operation to restore the old values from the+ new values because the old values were never lost! All you have to do is+ "forget" about the new values and you are done. Furthermore, most data+ structures in Haskell are designed to have efficient immutable operations+ which try to re-use as much of an old value as possible in order to minimize+ the amount of copying needed to construct the new value.++ (Having said all of this, although it is strongly recommended that your+ logic program be pure by making it have type `Tree`, as this will cause the+ type system to enforce purity, you can add various kinds of side-effects by+ using type `TreeT` instead; a time when it might make sense to do this is if+ there is a data set that will be constant over the run which is large enough+ that you want to read it in from various files or a database as you need it.+ In general if you use side-effects then they need to be non-observable,+ which means that they are not affected by the order in which the tree is+ explored or whether particular parts of the tree are explored more than+ once.)++ \* Side-effects are implemented by, roughly speaking, having some types+ represent actions that cause side-effects when executed.++3. Powerful static type system++ When writing a very complicated program you want as much help as possible in+ making it correct, and Haskell's powerful type system helps you a lot here+ by harnessing the power of static analysis to ensure that all of the parts+ fit together correctly and to enforce invariants that you have encoded in+ the type system.+++I have more questions!+======================++Then please contact the author (Gregory Crosswhite) at gcrosswhite@gmail.com! :-)
+ TUTORIAL.md view
@@ -0,0 +1,1198 @@+This file contains a tutorial for using this package. The first part explains+through examples how to do logic programming in Haskell using `MonadPlus`. The+second part explains how to take a logic program in the form of a `Tree` (which+is an instance of `MonadPlus`) and use the infrastructure in this package to run+it in parallel.+++Logic programming+=================++In this part we shall show how to write logic programs through the use of three+example problems: generating ordered pairs of integers, finding valid map+colorings, and finding ways to place n queens on an n x n chess board.+++Ordered pairs of integers+-------------------------++Logic programming in Haskell is about making choices and applying constraints.+A simple example is the following:+++```haskell+pairs :: MonadPlus m => Int -> Int -> m (Int,Int)+pairs max_x max_y = do+ x <- between 1 max_x+ y <- between 1 max_y+ guard $ x < y+ return (x,y)+```++This program generates all pairs of integers within the given ranges such that+the first element of the pair is less than the second element of the pair. The+first line in the body of `pairs`,++```haskell+x <- between 1 max_x+```++makes a non-deterministic choice for `x` that is between `1` and `max_x`+(inclusive), and likewise for `y`; the `between` function is part of the+`LogicGrowsOnTrees` module. The third line in the function body is a guard that+succeeds if `x < y` and fails otherwise; failure results in backtracking to try+another choice of `x` and/or `y`.++`pairs` returns a value that can be an instance of an arbitrary type --- i.e.,+one the caller can choose --- so long as it is an instance of `MonadPlus`. For+example, if let you let `m` be `Maybe` then `pairs` will return either nothing+if no choices of `x` and `y` satisfy the guard and otherwise it will return a+`Just` value with the first found solution. If you let `m` be the List type then+the function will return the list of all solutions.++This function illustrates the basic functionality but it is not a good example+of how you would actually generate such pairs; a better implementation is given+by:++```haskell+pairs max_x max_y = do+ x <- between 1 max_x+ y <- between (x+1) max_y+ return (x,y)+```++This is more efficient because it restricts the choice of `y` to only those+values that will satisfy the constraint. This is actually an important+optimization that one should always try to make when working on non-trivial+problems: when possible, one should enforce a constraint by reducing the set of+available choices to those that meet the constraint rather than by generating a+larger set of choices and then applying a filter to eliminate those that don't+meet the constraint.+++Map coloring+------------++For our next example, we consider the problem of coloring a map. That is, we are+given a list of countries, a relation that tells us which are adjacent, and a+list of colors, and our goal is to find a way to choose a color for each country+such that no two adjacent countries have the same color. To keep things simple,+we will assume that the colors are numbered from `1` to `number_of_colors` and+the countries are numbered from `1` to `number_of_countries`. A function that+generates solutions to this problem is as follows:++```haskell+coloringSolutions :: MonadPlus m => Word -> Word -> (Word -> Word -> Bool) -> m [(Word,Word)]+coloringSolutions number_of_colors number_of_countries isAdjacentTo =+ foldM addCountryToColoring [] [1..number_of_countries]+ where+ addCountryToColoring coloring country = do+ color <- between 1 number_of_colors+ forM_ coloring $ \(other_country, other_color) ->+ when (country `isAdjacentTo` other_country) $+ guard (color /= other_color)+ return $ (country,color):coloring+```++This function works by calling `foldM` (in `Control.Monad`) which in turn calls+`addCountryToColoring` once for each country (i.e., it *folds* over the list+`[1..number_of_countries]`), carrying along the current coloring. The function+`addCountryToColoring` does the following:++1. First, it makes a non-deterministic choice for the color of the country:++ ```haskell+ color <- between 1 number_of_colors+ ```++2. Second, it checks that all other countries that have been colored and which+ are adjacent to the current country are a different color:++ ```haskell+ forM_ coloring $ \(other_country, other_color) ->+ when (country `isAdjacentTo` other_country) $+ guard (color /= other_color)+ ```++ The first line of this snippet loops over the current coloring. The second+ line checks to see whether the current country (in the loop) is adjacent to+ the country we just colored, and if so then the third line checks that the+ two adjacent countries have different colors and fails if this is not the+ case.++3. Finally, it adds this country's color to the coloring, and returns the+ updated coloring (which will then be passed to `addCountryToColoring` at the+ next call, if any).++ ```haskell+ return $ (country,color):coloring+ ```++A major inefficiency in the code above is that a large number of the solutions+generated are equivalent in the sense that they only differ by a permutation of+the colors and the selection of the colors used (when this is less than the+total number of colors). In particular, if all `n` colors are used in a given+solution then there are `n!` equivalent solutions, if `n-1` of the `n` colors+are used then there are `n!/2` equivalent solutions, etc; in general if `m`+colors are used out of `n` for a given solution then there are `n!/(n-m)!`+equivalent solutions.++The solution to this is a trick I like to call "symmetry breaking", where you+take a symmetry (in this case, the fact that permuting the colors and/or+changing the choice of colors results in an equivalent solution) and factor it+out by forcing a particular ordering. The following code does this:++```haskell+coloringUniqueSolutions number_of_colors number_of_countries isAdjacentTo =+ liftM snd $ foldM addCountryToColoring (0,[]) [1..number_of_countries]+ where+ addCountryToColoring (number_of_colors_used,coloring) country = do+ color <- between 1 ((number_of_colors_used + 1) `min` number_of_colors)+ forM_ coloring $ \(other_country, other_color) ->+ when (country `isAdjacentTo` other_country) $+ guard (color /= other_color)+ return (number_of_colors_used `max` color,(country,color):coloring)+```++The above is a modified version of `coloringSolutions` where we *force* the+first color chosen to be 1, the second color chosen (if not the same as the+first) to be 2, and so on. Specifically, we keep track of the number of colors+used so far, and when the next color is chosen we restrict ourselves to these+colors plus the next greatest color if we have not already used all the+available colors; if our choice involves a new color then we bump up the number+of colors used for the next call to `addCountryToColoring`, otherwise we use the+same set of colors.+++N-queens problem+----------------++Our final example is the n-queens problem, which is the problem of placing n+queens on an n x n board such that none of the queens conflict; recall that in+chess two queens conflict if they share the same row, column, or diagonal. A+function that generates solutions to this problem is as follows:++```haskell+import qualified Data.IntSet as IntSet+...+nqueensUsingSetsSolutions :: MonadPlus m => Word -> m [(Word,Word)]+nqueensUsingSetsSolutions n =+ go (fromIntegral n)+ 0+ (IntSet.fromDistinctAscList [0..fromIntegral n-1])+ IntSet.empty+ IntSet.empty+ []+ where+ go 0 _ _ _ _ !value = return . reverse $ value+ go !n+ !row+ !available_columns+ !occupied_negative_diagonals+ !occupied_positive_diagonals+ !value+ = do+ column <- allFrom $ IntSet.toList available_columns+ let negative_diagonal = row + column+ guard $ IntSet.notMember negative_diagonal occupied_negative_diagonals+ let positive_diagonal = row - column+ guard $ IntSet.notMember positive_diagonal occupied_positive_diagonals+ go (n-1)+ (row+1)+ (IntSet.delete column available_columns)+ (IntSet.insert negative_diagonal occupied_negative_diagonals)+ (IntSet.insert positive_diagonal occupied_positive_diagonals)+ ((fromIntegral row,fromIntegral column):value)+```++(The use of `fromIntegral` comes from the fact that the input board size and+output board positions are naturally `Word`s as they cannot be negative but the+`IntSet` type only stores `Int`s, which means that we need to work internally+using `Int` and use `fromIntegral` to convert from the input `Word` and to the+output `Word`s.)++The function `go` is where most of the work happens. For each row in the board,+it does the following:++1. First, it makes a non-deterministic choice from the available columns; here+ we use the function `allFrom` (part of the `LogicGrowsOnTrees` module) to+ convert the list of available columns to a `MonadPlus` that generates it:++ ```haskell+ column <- allFrom $ IntSet.toList available_columns+ ```++2. Next, it checks if this choice of column conflicts with the positive and+ negative diagonals, and if so it backtracks and tries a different column:++ ```haskell+ let negative_diagonal = row + column+ guard $ IntSet.notMember negative_diagonal occupied_negative_diagonals+ let positive_diagonal = row - column+ guard $ IntSet.notMember positive_diagonal occupied_positive_diagonals+ ```++3. Finally, it recursively calls `go` for the next row with updated values for+ the updated available columns and occupied diagonals, as well as the chosen+ board position added to the (partial) solution:++ ```haskell+ go (n-1)+ (row+1)+ (IntSet.delete column available_columns)+ (IntSet.insert negative_diagonal occupied_negative_diagonals)+ (IntSet.insert positive_diagonal occupied_positive_diagonals)+ ((fromIntegral row,fromIntegral column):value)+ ```++When we are done, we reverse the solution as it currently has the last row+first and the first row last.++While `IntSet` is very efficient, it is even more efficient to use a bit field+for a set --- i.e., a field such that bits that are 1 correspond to being+occupied and those that are 0 correspond to being available. A solution using+this approach is as follows:++```haskell+nqueensUsingBitsSolutions n =+ go n 0 (0::Word64) (0::Word64) (0::Word64) []+ where+ go 0 _ _ _ _ !value = return . reverse $ value+ go !n+ !row+ !occupied_columns+ !occupied_negative_diagonals+ !occupied_positive_diagonals+ !value+ = do+ column <- allFrom . goGetOpenings 0 $+ occupied_columns .|. + occupied_negative_diagonals .|.+ occupied_positive_diagonals+ let column_bit = bit (fromIntegral column)+ go (n-1)+ (row+1)+ (occupied_columns .|. column_bit)+ ((occupied_negative_diagonals .|. column_bit) `shiftR` 1)+ ((occupied_positive_diagonals .|. column_bit) `shiftL` 1)+ ((row,column):value)++ goGetOpenings column bits+ | column >= n = []+ | bits .&. 1 == 0 = column:next+ | otherwise = next+ where+ next = goGetOpenings (column + 1) (bits `shiftR` 1)+```++Now the function `go` does the following:++1. It makes a non-deterministic choice within the current row for the column,+ excluding those spaces which are either occupied columns or diagonals:++ ```haskell+ column <- allFrom . goGetOpenings 0 $+ occupied_columns .|.+ occupied_negative_diagonals .|.+ occupied_positive_diagonals+ let column_bit = bit (fromIntegral column)+ ```++2. It marks the column and diagonals as being occupied, and also shifts the+ occupied diagonals so that they correspond with the columns in the next row.+ That is, if a given positive diagonal intersects with column `i` for a given+ row then it intersects with column `i+1` in the next row, and if a given+ negative diagonal intersects with column `i` for a given row then it+ intersects with `i-1` in the next row. Finally, it adds the board position to+ the partial solution:++ ```haskell+ go (n-1)+ (row+1)+ (occupied_columns .|. column_bit)+ ((occupied_negative_diagonals .|. column_bit) `shiftR` 1)+ ((occupied_positive_diagonals .|. column_bit) `shiftL` 1)+ ((row,column):value)+ ```++The new nested function `getOpenings` scans through the input bits and builds a+list of columns where a queen may be placed without conflict. If there are no+such columns, then the list will be empty and the code will backtrack.++It is possible to use symmetry breaking gain a significant speed-up, though the+solution I came up with that does this ended up being quite complicated. You+can see it for yourself in the `LogicGrowsOnTrees.Examples.Queens.Advanced`+module.+++Using LogicGrowsOnTrees+=======================++In the preceding part, we gave some examples of how to write a logic program+using `MonadPlus`. In this part we will talk about how to use this package to+write such programs, and in particular how to run them in parallel. First we+will show how to use this package to run a logic program serially, which is done+for two reasons: first, to introduce the functionality of this package in a+simpler setting, and second, because it is useful when one is testing a program.+Next we will show how to run a logic program in parallel using the+`LogicGrowsOnTrees.Parallel.Adapter.Threads` module. Finally, we will show how+to run a logic program in parallel using the `LogicGrowsOnTrees.Parallel.Main`+module, which provides a universal interface to all adapters as well as+automating the work required to specify a command line interface.++Note that the examples in the preceding part have all been implemented in the+`LogicGrowsOnTrees.Examples.*` modules, so in the examples to follow we will+reference them by importing them for their corresponding module rather than by+copying and pasting their source code.++Serial+------++The central data structure in `LogicGrowsOnTrees` is the `Tree` type, which, as+the name suggests, is a tree data structure where each branch corresponds to a+binary choice made in a logic program by the `mplus` function, which takes two+trees and returns a new tree whose root is a choice between the two arguments.+We have not been using this function directly because we have wanted to make+choices from a list of elements, and so we used the `allFrom` function to+essentially convert this list to a tree using `mplus`.++Because `Tree` is an instance of `MonadPlus`, all of the logic programs we have+written are automatically available in `Tree` form. Thus, to run a logic program+in serial, you can use the `exploreTree*` family of functions in+`LogicGrowsOnTree`.++The `exploreTree` function explores the entire tree and sums over all the+results; for this reason, the result type of the tree needs to be a `Monoid`.+This means that in particular if you, say, want to get a list of all solutions,+then your logic program needs to put each result in a list singleton so that the+sum builds up the list of all solutions. The following program is an example of+applying this to prints a list of all the n-queens solutions for n = 5 (also+given in `tutorial/tutorial-1.hs`):++```haskell+import LogicGrowsOnTrees (exploreTree)+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = print . exploreTree . fmap (:[]) . nqueensUsingBitsSolutions $ 5+```++Note the use of `fmap (:[])` to replace every result generated by the logic+program with a singleton list containing the result. When there are a lot of+results it is better to use the `Seq` type in `Data.Sequence` as it has+(amortized) asymptotically faster concatenation operations; this is done in the+following (also given in `tutorial/tutorial-2.hs`):++```haskell+import qualified Data.Sequence as Seq+import LogicGrowsOnTrees (exploreTree)+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = print . exploreTree . fmap Seq.singleton . nqueensUsingBitsSolutions $ 5+```++Alternatively, if you are only interested in the *number* of solutions rather+than what they are, then you should replace every solution with `WordSum 1`,+where `WordSum` is a `Monoid` (included as part of this package in the module+`LogicGrowsTrees.Utils.WordSum`) with the property that the sum of two+`WordSum`s is a `WordSum` containing the sum of the two contained values; this+is done in the following (also given in `tutorial/tutorial-3.hs`):++```haskell+import LogicGrowsOnTrees (exploreTree)+import LogicGrowsOnTrees.Utils.WordSum (WordSum(..))+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = print . exploreTree . fmap (const $ WordSum 1) . nqueensUsingBitsSolutions $ 5+```++Note that the only change is that we replaced `fmap Seq.singleton` with+`fmap (const $ WordSum 1)`.++If you only want the first result then you should use `exploreTreeUntilFirst`,+which return the first result found wrapped in `Just` if any results are+present, and `Nothing` if no results were found; for example, see the following+(also given in `tutorial/tutorial-4.hs`):++```haskell+import LogicGrowsOnTrees (exploreTreeUntilFirst)+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = print . exploreTreeUntilFirst . nqueensUsingBitsSolutions $ 10+```++Finally, if you only want a few of the results, then use+`exploreTreeUntilFound`, which takes a condition function and will stop finding+new results when it is met; the result is a pair where the first component+contains the results that were found and the second contains a `Bool` indicating+whether the condition was met. Note that the returned results might be less than+those requested if there weren't enough found to meet your condition function,+and it also might be *more* than those requested because results are not found+one at a time but rather are merged from the bottom up, meaning that there might+be a choice point where the two branches separately did not meet the condition+but their merged results did. An example of using this to find at least three+results is illustrated as follows (also given in `tutorial/tutorial-5.hs`):++```haskell+import LogicGrowsOnTrees (exploreTreeUntilFound)+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main =+ print+ .+ exploreTreeUntilFound ((>= 3) . length)+ .+ fmap (:[])+ .+ nqueensUsingBitsSolutions+ $+ 10+```++The above will print a pair where the first component has *five* solutions and+the second component is true. Note the condition function `((>= 3) . length)`+which computes the length of the list and checks whether it is at least three.++NOTE: If for some reason you really don't want more than, say, three solutions+--- perhaps because the solutions are very large and you never want to keep+around more than three --- then your best bet is to create a custom `Monoid`+type that, say, contains a list and never allows concatenation to let it grow+bigger than three elements.+++Parallelization using the Threads module+----------------------------------------++The `LogicGrowsOnTrees.Parallel.Adapter.Threads` module provides functions that+let you run a logic program in parallel using multiple threads. You have a+couple of options for how to do this this.++First, you can use one of the many specialized functions which roughly follow+the same pattern as the `exploreTree*` functions in `LogicGrowsOnTrees`, such as+the following (also given in `tutorial/tutorial-6.hs`):++```haskell+import GHC.Conc (setNumCapabilities)++import LogicGrowsOnTrees.Parallel.Adapter.Threads+ (RunOutcome(..)+ ,TerminationReason(..)+ ,exploreTree+ ,setNumberOfWorkers+ )+import LogicGrowsOnTrees.Utils.WordSum (WordSum(..))+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = do+ setNumCapabilities 2+ RunOutcome statistics termination_reason <-+ exploreTree (setNumberOfWorkers 2)+ .+ fmap (const $ WordSum 1)+ .+ nqueensUsingBitsSolutions+ $+ 10+ case termination_reason of+ Aborted progress -> putStrLn "Count aborted."+ Completed (WordSum count) -> putStrLn $ "Found " ++ show count ++ " solutions."+ Failure progress message -> putStrLn $ "Failed: " ++ message+```++First, observe that `exploreTree` now has an additional argument,+`setNumberOfWorkers 2`. This argument is called the *controller*, and is a loop+that is run that lets you issue commands to the supervisor such as aborting,+requesting a progress update, and changing the number of workers (which can be+done at any time in the run and can even bring the number down to zero).+`setNumberOfWorkers` is a function that changes the number of workers to be+equal to its argument, spawning or killing workers as necessary.++In order for the two worker threads to run in parallel, two things need to+happen. First, you need to compile with the `-threaded` option, and second, you+need to set the number of capabilities to two so that up to two threads can run in+parallel, as is done in the first line of the body of `main`:++```haskell+setNumCapabilities 2+```++(Alternatively, you could also use the `+RTS -N#` command-line option to set the+number of capabilities to `#`.)++Now observe that in the first line of the body of the main function, we have++```haskell+RunOutcome statistics termination_reason <-+```++Now that we are running many workers in parallel, the result of the exploration+is a bit more complicated. The result type is a `RunOutcome`, which contains the+run statistics and the termination reason. The run statistics contain a lot of+information whose primary purpose is to help one diagnose why one is not getting+the appropriate speedup as the number of workers increases (should this happen).+The termination reason contains information about why the run terminated. As you+can see at the end of the code, there are three possibilities:++```haskell+case termination_reason of+ Aborted progress -> putStrLn "Count aborted."+ Completed (WordSum count) -> putStrLn $ "Found " ++ show count ++ " solutions."+ Failure progress message -> putStrLn $ "Failed: " ++ message+```++First, we have `Aborted`, which means that a request was made to abort the run;+it contains the `progress` that had been made up to that point, which can be+used to resume the run at the same point later.++Second, we have `Completed`, which means that the run terminated normally; it+contains the final result in the run, which in this case is a `Word` wrapped in+a `WordSum`.++Finally, we have `Failure`, which indicates that something went horribly wrong+during the run, such as an exception being thrown; it contains both the+`progress` that had been made up to that point and also a `message` that+describes what happened. If your logic program is pure, then this most likely+means that there is a bug somewhere in your program. (If it is not pure, which+we have not covered in this tutorial, a `Failure` might just mean that, say, an+external resource that is needed by the program was not available.)++In the case of both `Aborted` and `Failure`, there is an argument which+represents the current progress of the exploration, which you can use as the+starting point by calling the `exploreTreeStartingFrom` function.++There is an important caveat, however: it only makes sense to resume an+exploration using a checkpoint *if you have not changed the program*, because in+general if you change the program, then you change the tree, which means that+the checkpoint is no longer a valid; in particular, if the explored part of the+tree changes, then in general your current sum over results will no longer+correct, and if the shape of the tree changes, then in general the checkpoint+will not line up with it and will raise an error --- in fact, if you make a+mistake and change the parts of the tree that have been explored and resume from+a checkpoint anyway then you should *hope* that an error is raised as the+alternative is for your results to be silently corrupted!++Because of this, it will rarely make sense to resume from a `Failure` if your+program is pure, because an exception will almost always signal the presence of+a bug. The main reason for including the `progress` with the `Failure` is+because, although we have not discussed this, it is possible to write logic+programs that run in the I/O monad and require access to, say, a database+server; if the database server goes down, it makes perfect sense to restart it+and resume the run from the last `progress`.++In the following code, we show a (somewhat contrived) example of resuming after+aborting, as well as of a non-trivial controller (also given in+`tutorial/tutorial-7.hs`):++```haskell+import Control.Monad.IO.Class (liftIO)+import Data.Monoid (mempty)+import GHC.Conc (setNumCapabilities)+import System.Exit (exitFailure,exitSuccess)++import LogicGrowsOnTrees.Checkpoint (Progress(..))+import LogicGrowsOnTrees.Parallel.Adapter.Threads+ (RunOutcome(..)+ ,TerminationReason(..)+ ,abort+ ,exploreTreeStartingFrom+ ,requestProgressUpdate+ ,setNumberOfWorkers+ )+import LogicGrowsOnTrees.Utils.WordSum (WordSum(..))+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = setNumCapabilities 2 >> go mempty+ where+ go progress@(Progress _ (WordSum count)) = do+ putStrLn $ "Counting... (starting with " ++ show count ++ " solutions); press <Enter> to abort"+ RunOutcome statistics termination_reason <-+ exploreTreeStartingFrom+ progress+ (do setNumberOfWorkers 2+ _ <- liftIO $ getLine+ _ <- requestProgressUpdate+ abort+ )+ .+ fmap (const $ WordSum 1)+ .+ nqueensUsingBitsSolutions+ $+ 14+ case termination_reason of+ Aborted progress -> do+ putStrLn $ "Count aborted; will try again."+ go progress+ Completed (WordSum count) -> do+ putStrLn $ "Found " ++ show count ++ " solutions."+ exitSuccess+ Failure _ message -> do+ putStrLn $ "Failed: " ++ message+ exitFailure+```++(Note: If this code takes too much or too little time to finish on your+computer then you can adjust the problem size, which is currently set to 14.)++This code features a number of differences from the previous example. First we+note that the controller is non-trivial:++```haskell+(do setNumberOfWorkers 2+ _ <- liftIO $ getLine+ _ <- requestProgressUpdate+ abort+)+```++Whereas previously the controller just set the number of workers and quit, it+now instead waits for the user to press enter, and if the user does so, then the+controller tells the supervisor that it should perform a progress update ---+that is, that it should contact all the workers and fetch their current results+and checkpoints --- and then finally the controller tells the supervisor to+abort.++Next, note that the `main` function is a loop:++```haskell+main = setNumCapabilities 2 >> go mempty+ where+ go progress@(Progress _ (WordSum count)) = do+ ...+ case termination_reason of+ Aborted progress -> do+ putStrLn $ "Count aborted; will try again."+ go progress+ Completed (WordSum count) -> do+ putStrLn $ "Found " ++ show count ++ " solutions."+ exitSuccess+ Failure _ message -> do+ putStrLn $ "Failed: " ++ message+ exitFailure+```++Specifically, as long as the user keeps aborting by pressing enter, the code+will loop and immediately resume starting from its progress at the time the run+was aborted. If the run finishes by either terminating successfully or with a+failure, then the program exits. You don't have to worry about making sure that+the controller terminates because if the run terminates for any reason then it+kills the controller thread rather than leaving it hanging.++Obviously this is not a particularly useful controller, although it does+demonstrate that the run can be arbitrarily aborted and restarted from a+checkpoint without suffering any problems. For an example of a more useful+controller, see the following (also given in `tutorial/tutorial-8.hs`):++```haskell+import Control.Monad (forever)+import Control.Monad.IO.Class (liftIO)+import System.IO (hFlush,stdout)++import LogicGrowsOnTrees.Parallel.Adapter.Threads+ (RunOutcome(..)+ ,TerminationReason(..)+ ,exploreTree+ ,setNumberOfWorkers+ )+import LogicGrowsOnTrees.Utils.WordSum (WordSum(..))+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = do+ RunOutcome _ termination_reason <-+ exploreTree (forever $+ liftIO (do+ putStr "Enter the desired number of workers: "+ hFlush stdout+ readLn+ )+ >>=+ setNumberOfWorkers+ )+ .+ fmap (const $ WordSum 1)+ .+ nqueensUsingBitsSolutions+ $+ 14+ case termination_reason of+ Aborted progress -> putStrLn "Count aborted."+ Completed (WordSum count) -> putStrLn $ "Found " ++ show count ++ " solutions."+ Failure _ message -> putStrLn $ "Failed: " ++ message+```++Now the controller continually polls the user for the desired number of workers,+and then changes the number of workers to be equal to it, which, for example,+you could use to adjust the number of processors being used by the run to be+larger or smaller depending on how many processors you want to use for other+tasks at that moment.++(Unfortunately, calling `setNumCapabilities` many times in succession can+destabilize the GHC runtime, so for this example you will need to use `+RTS -N#`+on the command-line to set the number of capabilities to be equal to the largest+number of workers that you will want to run in parallel; it is worth mentioning+that the `Processes` adapter, provided in the `LogicGrowsOnTrees-procesess`+package, also features a controller that can change the number of workers, but+does not suffer from this problem because it creates and destroyers workers by+spawning and destroying single-threaded processes rather than telling the GHC+threaded runtime to grow and shrink the number of capabilities.)++As in the serial case, there are multiple modes in which an exploration can be+run. The following code only looks for the first result (also given in+`tutorials/tutorial-9.hs`):++```haskell+import GHC.Conc (setNumCapabilities)++import LogicGrowsOnTrees.Parallel.Adapter.Threads+ (RunOutcome(..)+ ,TerminationReason(..)+ ,exploreTreeUntilFirst+ ,setNumberOfWorkers+ )+import LogicGrowsOnTrees.Checkpoint (Progress(..))+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = do+ setNumCapabilities 2+ RunOutcome statistics termination_reason <-+ exploreTreeUntilFirst (setNumberOfWorkers 2)+ .+ nqueensUsingBitsSolutions+ $+ 10+ case termination_reason of+ Aborted _ -> putStrLn "Search aborted."+ Completed Nothing -> putStrLn "No result found."+ Completed (Just (Progress checkpoint result)) -> putStrLn $ "Found " ++ show result+ Failure _ message -> putStrLn $ "Failed: " ++ message+```++Note how now `Completed` contains a `Maybe` value:++```haskell+Completed Nothing -> putStrLn "No solution found."+Completed (Just (Progress checkpoint result)) -> putStrLn $ "Found " ++ show result+```++If the run finds no solution, then it returns `Nothing`. If it does return a+solution, then it returns a `Progress` value, which contains not only the+solution but also the `checkpoint`; the reason for returning the `checkpoint` is+that it allows you to resume from it if you decide that you want to find more+solutions at some point in the future.++As in the serial case, you can also request that only some of the results be+found, as in the following code which looks for at least five solutions (also+given in `tutorials/tutorial-10.hs`):++```haskell+import GHC.Conc (setNumCapabilities)++import LogicGrowsOnTrees.Parallel.Adapter.Threads+ (RunOutcome(..)+ ,TerminationReason(..)+ ,exploreTreeUntilFoundUsingPush+ ,setNumberOfWorkers+ )+import LogicGrowsOnTrees.Checkpoint (Progress(..))+import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main = do+ setNumCapabilities 2+ RunOutcome statistics termination_reason <-+ exploreTreeUntilFoundUsingPush+ ((>= 5) . length)+ (setNumberOfWorkers 2)+ .+ fmap (:[])+ .+ nqueensUsingBitsSolutions+ $+ 10+ case termination_reason of+ Aborted _ -> putStrLn "Search aborted."+ Completed (Left results) -> putStrLn $ "Only found:" ++ show results+ Completed (Right (Progress checkpoint results)) -> putStrLn $ "Found: " ++ show results+ Failure _ message -> putStrLn $ "Failed: " ++ message+```++Now the result in `Completed` is `Left results` if the run ended before the+condition function was satisfed and `Right (Progress checkpoint results)`+otherwise, where again the `checkpoint` allows you to resume the search at some+point in the future if you wish.++There is also an `exploreTreeUntilFoundUsingPull` function, which is similar to+this function except that it gathers the results in a different way. The+difference between them is that `exploreTreeUntilFoundUsingPull` sums results+locally on each worker until either a progress update is requested or the+condition is satisfied, whereas `exploreTreeUntilFoundUsingPush` pushes each+result to the supervisor immediately as soon as it is found. If you are only+looking for a few results then `exploreTreeUntilFoundUsingPush` is preferable+because the whole system will know right away when the desired results have been+found. If you are looking for a large number of results then the overhead of+sending each result to the supervisor may add up to the point where it is better+to sum locally and only send results to the supervisor periodically; note that+if you take the latter approach then it is your responsibility to have the+controller periodically request progress updates. (Note that the+`LogicGrowsOnTrees.Parallel.Common.RequestQueue` module has a `fork` function+that you can use to spawn another controller thread if this would make your life+easier; like the main controller thread, it will be killed when the run is+over.)+++Parallelization using the Main framework+----------------------------------------++`Threads` is one of the *adapters* provided by `LogicGrowsOnTrees` and its+siblings. Each of these adapters provides a way of adapting the+supervisor/worker parallelization model to a particular means of running+computations in parallel. The current adapters are as follows:++* `Threads`++ This adapter provides parallelism by spawning multiple threads; the number+ of workers can be changed arbitrarily at runtime (though you need to make+ sure that the number of capabilities is also high enough for all of them to+ run in parallel). This adapter is the only one that requires the threaded+ runtime, which adds additional overhead.++* `Processes`++ This adapter provides parallelism by spawning a child process for each+ worker; the number of workers can be changed arbitrarily at runtime.++ Install `LogicGrowsOnTrees-processes` to use this adapter.++* Network++ This adapter provides parallelism by allowing multiple workers to connect to+ a supervisor over a network; the number of workers is then equal to the+ number that are are connected to the supervisor. (It is possible for the+ same process to be both a supervisor and one or more workers.)++ Install `LogicGrowsOnTrees-network` to use this adapter.++* `MPI`++ This adapter provides parallelism using the Message Passing Interface (MPI),+ which is the standard communication system used in supercomputers, allowing+ you to use a very large number of nodes in your run. One of the nodes (#0)+ will act entirely as the supervisor, and the rest will act as workers.++ Install `LogicGrowsOnTrees-MPI` to use this adapter; note that you will need+ to have an MPI implementation installed (such as+ [OpenMPI](http://www.open-mpi.org/)).++All of these adapters provide low-level means of accessing their functionality+directly if you wish (though they are much more complicated to use than the+`exploreTree` functions in `Threads`), but there is also a universal high-level+interface that works for *all* of the adapters, which we will now discuss.++The `Main` module provides a framework that automates a lot of the work of+setting up and running an exploration in parallel, and the interface it provides+is completely agnostic about the adapter that is used; the `simpleMainFor*` and+`mainFor*` functions all take an argument which is the `driver` of the adapter+that you are using, and so switching to a different adapter is as simple as+switching the `driver` argument.++Here is a simple example of using the `Main` framework (also given in+`tutorial/tutorial-11.hs`):++```haskell+import LogicGrowsOnTrees.Parallel.Adapter.Threads (driver)+import LogicGrowsOnTrees.Parallel.Main (RunOutcome(..),TerminationReason(..),simpleMainForExploreTree)+import LogicGrowsOnTrees.Utils.WordSum (WordSum(..))++import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main =+ simpleMainForExploreTree+ driver+ (\RunOutcome _ termination_reason -> do+ case termination_reason of+ Aborted _ -> error "search aborted"+ Completed (WordSum count) -> putStrLn $ show count ++ " solutions were found"+ Failure _ message -> error $ "error: " ++ message+ )+ (fmap (const $ WordSum 1) (nqueensUsingBitsSolutions 10))+```++This program comes with an automatically generated help screen (via. `--help`),+and it already includes options to specify the location of the checkpoint file+(if it exists, then the run will be resumed from it), how often a checkpoint+should be written, at what level to print logging messages, and whether various+server statistics should be printed to the screen (possibly useful if your+computation is not scaling well). Because we are using the `Threads` driver,+there will also be a `-n` option to set the number of threads.++The reason why the function that processes the result of the run has be+specified as an argument rather than having the result be returned by+`simpleMainForExploreTree` is twofold: first, because in general the supervisor+and workers will be in separate processes and the result is only processed by+the supervisor, and second, because this allows `simpleMainForExploreTree` to be+sure that your code has successfully processes the result (as opposed to, say,+throwing an exception) before deleting the checkpoint file.++The following is a more complicated example that uses a more general function+in `Main` that lets one specify the board size using a command-line argument+(also given in `tutorial/tutorial-12.hs`):++```haskell+import System.Console.CmdTheLine (PosInfo(..),TermInfo(..),defTI,pos,posInfo,required)++import LogicGrowsOnTrees.Parallel.Adapter.Threads (driver)+import LogicGrowsOnTrees.Parallel.Main (RunOutcome(..),TerminationReason(..),mainForExploreTree)+import LogicGrowsOnTrees.Utils.WordSum (WordSum(..))++import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main =+ mainForExploreTree+ driver+ (required $+ pos 0+ (Nothing :: Maybe Int)+ posInfo+ { posName = "BOARD_SIZE"+ , posDoc = "the size of the board"+ }+ )+ (defTI+ { termName = "tutorial-11"+ , termDoc = "count the number of n-queens solutions for a given board size"+ }+ )+ (\board_size (RunOutcome _ termination_reason) -> do+ case termination_reason of+ Aborted _ -> error "search aborted"+ Completed (WordSum count) -> putStrLn $ show count ++ " solutions found for board size " ++ show board_size+ Failure _ message -> error $ "error: " ++ message+ )+ (fmap (const $ WordSum 1) . nqueensUsingBitsSolutions . fromIntegral)+```++This program calls `mainForExploreTree` with the following arguments:++1. the `driver`, which in this case was imported from `Threads`++2. a `Term` which specifies that our program takes a single required positional+ argument for the board size:++ ```haskell+ (required $+ pos 0+ (Nothing :: Maybe Int)+ posInfo+ { posName = "BOARD_SIZE"+ , posDoc = "the size of the board"+ }+ )+ ```++ Most of the functions above are part of+ [`cmdtheline`](http://hackage.haskell.org/package/cmdtheline), an+ applicative command-line parsing library. This library was used because it+ makes it easy to compose options together; your argument value here will+ essentially be merged in with the adapter options and some generic options+ (such as the checkpointing options).++ Specifically, `pos` here is a function that takes a position, a default+ value, and a `PosInfo` data structure that contains information about the+ name of the option and a brief description of it; the result is a value of+ type `Arg (Maybe Int)`. `required` then takes this term and maps it to a+ value of type `Term Int` with the property that an error is raised if this+ positional argument is not present.++3. a `TermInfo` which specifies the name and a short description of this+ program:+ + ```haskell+ (defTI+ { termName = "tutorial-11"+ , termDoc = "count the number of n-queens solutions for a given board size"+ }+ )+ ```++4. an action to be executed with the final result:++ ```haskell+ (\board_size (RunOutcome _ termination_reason) -> do+ case termination_reason of+ Aborted _ -> error "search aborted"+ Completed (WordSum count) -> putStrLn $ show count ++ " solutions found for board size " ++ show board_size+ Failure _ message -> error $ "error: " ++ message+ )+ ```++ The first argument to this function is equal to the value supplied by the+ user for the first command line argument.++ NOTE: When `Completed`, any existing checkpoint file will be deleted after+ this function returns *unless* an exception is thrown, in which case it is+ kept around.++5. a function that constructs the logic program:++ ```haskell+ (fmap (const $ WordSum 1) . nqueensUsingBitsSolutions . fromIntegral)+ ```++ The argument to this function is equal to the value supplied by the user+ for the first command line argument.++Again, there is additional complexity in this interface because, as the+supervisor and workers will in general be in different processes, the+configuration information needs to be sent from the supervisor to the worker+processes so that they can locally construct the tree. The `driver` automates+the mechanism for this.++Finally, it is worth noting that all that it takes to use multiple processes+instead of multiple threads is to install `LogicGrowsOnTrees-processes` and then+replace `Threads` with `Processes` in the imports.++For a slightly more sophisticated example, consider the following (also given in+`tutorial/tutorial-13.hs`):++```haskell+import Control.Applicative (liftA2)+import System.Console.CmdTheLine (PosInfo(..),TermInfo(..),defTI,pos,posInfo,required)++import LogicGrowsOnTrees.Checkpoint (Progress(..))+import LogicGrowsOnTrees.Parallel.Adapter.Threads (driver)+import LogicGrowsOnTrees.Parallel.Main (RunOutcome(..),TerminationReason(..),mainForExploreTreeUntilFoundUsingPush)+import LogicGrowsOnTrees.Utils.WordSum (WordSum(..))++import LogicGrowsOnTrees.Examples.Queens (nqueensUsingBitsSolutions)++main =+ mainForExploreTreeUntilFoundUsingPush+ (\(board_size,number_to_find) -> (>= number_to_find) . length)+ driver+ (liftA2 (,)+ (required $+ pos 0+ (Nothing :: Maybe Int)+ posInfo+ { posName = "BOARD_SIZE"+ , posDoc = "the size of the board"+ }+ )+ (required $+ pos 1+ (Nothing :: Maybe Int)+ posInfo+ { posName = "#"+ , posDoc = "the number of solutions to find"+ }+ )+ )+ (defTI+ { termName = "tutorial-12"+ , termDoc = "find some of the solutions to the n-queens problem for a given board size"+ }+ )+ (\(board_size,number_to_find) (RunOutcome _ termination_reason) -> do+ case termination_reason of+ Aborted _ -> error "search aborted"+ Completed (Left found) -> do+ putStrLn $ "For board size " ++ show board_size ++ ", only found " ++ show (length found) ++ "/" ++ show number_to_find ++ " solutions:"+ mapM_ print found+ Completed (Right (Progress checkpoint found)) -> do+ putStrLn $ "Found all " ++ show number_to_find ++ " requested solutions for board size " ++ show board_size ++ ":"+ mapM_ print found+ Failure _ message -> error $ "error: " ++ message+ )+ (fmap (:[]) . nqueensUsingBitsSolutions . fromIntegral . fst)+```++This differs from the previous example in two main respects: first, it prints+out solutions rather than just their count, and second there is a second+argument to the program that specifies how many should be found.++To understand what is going on, let us first look at the third argument to+`mainForExploreTreeUntilFoundUsingPush`:++```haskell+(liftA2 (,)+ (required $+ pos 0+ (Nothing :: Maybe Int)+ posInfo+ { posName = "BOARD_SIZE"+ , posDoc = "the size of the board"+ }+ )+ (required $+ pos 1+ (Nothing :: Maybe Int)+ posInfo+ { posName = "#"+ , posDoc = "the number of solutions to find"+ }+ )+)+```++This argument essentially takes the argument from the previous example,+duplicates it to create a second argument (the number of solutions to find), and+then merges the two terms together in `Applicative` style via a call to+`liftA2`. After parsing is complete, the result will be a pair where the first+value is the board size and the second value is the number of solutions to find.++Now we look a the first argument to `mainForExploreTreeUntilFoundUsingPush`:++```haskell+(\(board_size,number_to_find) -> (>= number_to_find) . length)+```++This argument is a function that takes the configuration information and returns+a condition function that indicates where enough results have been accumulated.+In this case, the condition function checks whether the number of solutions+found (obtained via. `length`) is at least as many as were requested+(`number_to_find`). Note that `board_size` is ignored and would probably+normally be replaced by `_` (or possibly by use of higher-order functions to+make the expression entirely point-free); we include it here purely for+pedagogical reasons.++Next we look at the last argument of `mainForExploreTreeUntilFoundUsingPush`:++```haskell+(fmap (:[]) . nqueensUsingBitsSolutions . fromIntegral . fst)+```++This is just like in the previous example, save that now at the end there is+`fst`, which takes the first value in the configuration pair (which is the board+size) and instead of replacing each solution with a `WordSum`, it turns it into+a singleton list.++Finally, we look at the second-to-last argument:++```haskell+(\(board_size,number_to_find) (RunOutcome _ termination_reason) -> do+ case termination_reason of+ Aborted _ -> error "search aborted"+ Completed (Left found) -> do+ putStrLn $ "For board size " ++ show board_size ++ ", only found " ++ show (length found) ++ "/" ++ show number_to_find ++ " solutions:"+ mapM_ print found+ Completed (Right (Progress checkpoint found)) -> do+ putStrLn $ "Found all " ++ show number_to_find ++ " requested solutions for board size " ++ show board_size ++ ":"+ mapM_ print found+ Failure _ message -> error $ "error: " ++ message+)+```++The difference compared to the previous example is that there are two cases for+a `Completed` run. In the first case, the run fully completed before it was+able to find all of the requested number of solutions; the solutions it did+find are returned in a `Left` value. In the second case, the run found all of+the requested solutions and then stopped; the result is a `Progress` value+whose `checkpoint` value allows you to resume the search later to find more+solutions if you wish and whose result value is the requested solutions.+++Conclusion+==========++At this point you have learned how to write logic programs and how to use this+package to write them in parallel. For more information, see+[USERS_GUIDE.md](USERS_GUIDE.md) for a more detailed discussion of some aspects+of this package as well as the package haddock documentation for reference.
+ USERS_GUIDE.md view
@@ -0,0 +1,485 @@+Introduction+============++`LogicGrowsOnTrees` revolves around the `Tree` datatype, which is an instance of+`MonadPlus` with the additional ability for one to cache values that are+expensive to compute (as resuming from a checkpoint and parallelizing both can+cause paths in the tree to be explored multiple times); see the documentation+for `MonadExplorable` for more information on this.++In the sections to follow we will present the various functionalities in this+package for exploring trees. First we will discuss how to explore trees+serially, and then we will discuss how to explore them in parallel; for the+parallel case there are multiple options that will be discussed separately.+Finally, we will discuss how to create new adapters.+++Serial exploration+==================++If you want to explore a `Tree` serially (and without using checkpointing) then+you can use the `exploreTree` family of functions in the `LogicGrowsOnTrees`+module. There are 6 functions, which is the result of there being three+different exploration modes, each of which in turn has with pure and impure+variants.++The default exploration mode, `All`, explores the entire tree and sums over all+of the results at the leaves of the tree; to use this mode your `Tree` needs to+generate results that are an instance of the `Monoid` class. The reason for this+is that sometimes you want to do things like counting the number of solutions+rather than generating the list of them, and it is much more efficient to be+able to do this directly rather than to generate a (possibly very large) list+which you only use by taking its length. If you do want to generate a list of+solutions, then you can use `fmap (:[])` on the `Tree` to turn each result into+a singleton list, though if you have a large number of results then you should+instead create singletons of the `Seq` type in `Data.Sequence` as this type has+(amortized) asymptotically faster concatenation operations.++The second mode, `First`, explores the tree until it has found the first result,+at which point it returns this result wrapped in `Just`; if no result is found,+then it returns `Nothing`. Note that in this case the result does not have to be+an instance of `Monoid`, as there is no sum being performed.++The third mode, `Found`, explores the tree summing over results until a given+condition function is satisfied; like `All` mode, the results have to be an+instance of `Monoid`. The returned value is all the results that were found, as+well as a flag indicating whether the condition function was ever satisfied.++For each of the modes above, there is a variant for when you have a pure `Tree`,+and a variant for when have a `TreeT`, which is a monad transformer; in the+latter case the exploration functions will return their value inside the monad+nested in the `TreeT`.+++Parallel exploration+====================++Although this package can be used to explore trees serially, it really shines+when you want to perform an exploration in parallel. In the first subsection we+will describe the worker/supervisor model used by this package for+parallelization. Following that, we will briefly cover the various parallel+exploration modes and tree purities. Next, we will discuss the various adapters+that are available, and in particular how to use the `Threads` adapter. Finally,+we will discuss how to use the `Main` infrastructure, including run outcomes.+++Supervisors and workers+-----------------------++`LogicGrowsOnTrees` uses a supervisor/worker model for parallelization. That is,+at any given time there is a supervisor that keeps track of the global state of+the exploration and zero or more workers that are exploring the tree in parallel+--- zero is a valid number because some adapters allow for the number of workers+to change during the run.++The supervisor functionality is given in the+`LogicGrowsOnTrees.Parallel.Common.Supervisor` module. Normally you will not be+using it directly but rather you will be using a provided adapter which builds+on top of it to provide a simplified, specialized interface. The+`LogicGrowsOnTrees` package provides a `Threads` adapter (parallelization via+threads); other packages provide a `Processes` adapter (parallelization via+processes), a `Network` adapter (parallelization via zero or more processes+connecting over the network to the supervisor), and an `MPI` (Message Passing+Interface) adapter.++The worker functionality is given in the+`LogicGrowsOnTrees.Parallel.Common.Worker` module. As with the `Supervisor`+module, you will not normally need to use this module directly.+++Exploration modes+-----------------++The modes in which a parallel exploration can be run are given by the+`ExplorationMode` type in the+`LogicGrowsOnTrees.Parallel.Common.ExplorationMode` module. Many of the+functions in the parallelization infrastructure come in specialized families+where there is a function for each mode (and purity), and if you use these then+you might never need to deal with `ExplorationMode` directly; nonetheless it is+good to know what values it can take anyway, as the constructor names are used+as suffixes in specialized functions.++The first mode is `AllMode`; functions specialized to this mode have no suffix.+It acts just like the `All` mode discussed in the serial exploration section,+i.e. it sums over all results (which must therefore be an instance of `Monoid`).++The second mode is `FirstMode`; functions specialized to this mode have the+suffix `UntilFirst`. It acts just like the `First` mode discussed in the serial+exploration section, i.e. the exploration terminates when the first result has+been found (which need not be an instance of `Monoid`).++The third mode is `FoundModeUsingPull`; functions specialized to this mode have+the suffix `UntilFoundUsingPull`. It acts like the `Found` mode discussed in the+serial exploration section, i.e. it sums over all results found until a+criterion specified by the argument to the `FoundModeUsingPull` constructor is+satisfied. All found results are kept locally at the various workers running in+parallel and only merged when the supervisor sends out a global progress update+request that "pulls" all of the results in the system to it. Because of this, it+is possible that the workers will have collectively found enough results to+satisfy the criteria, but the system as a whole will not know this until a+progress update has been performed; for this reason, if you are using this mode,+then you need to perform a progress update on a regular basis.++The last mode is `FoundModeUsingPush`; functions specialized to this mode have+the suffix `UntilFoundUsingPush`. This mode functions exactly like+`FoundModeUsingPull` except that every result found is sent straight to the+supervisor, which means that the very instant that the system finds the desired+results, it will know about it. The potential downside to this mode is that+there is a small amount of overhead incurred in sending the result to the+supervisor, and so if there are a large number of results it might be more+efficient to accumulate them locally with the occasional pull rather than to+send each result to the supervisor as it is found.+++Purity+------++The `Purity` of a tree indicates whether it is `Pure` or `ImpureAtopIO`. If a+tree is `Pure` then it has no side effects (more precisely, the nested monad is+the `Identity`). If a tree is `ImpureAtopIO`, then it has side-effects, and+furthermore it has `IO` as the base monad in the stack, where this latter+restriction comes from the fact that the worker needs to run in a monad that has+`IO` at the base; `ImpureAtopIO` takes a single parameter that indicates how to+run the given action in the `IO` monad.++The families of specialized functions actually have *three* cases: `Pure`,+`Impure`, and `IO`, where `IO` is a special case of `Impure` provided for+convenience. The functions accepting an impure tree also have an additional+parameter to specify how to run it in the `IO` monad.+++Adapters+--------++An adapter module provides a way of adapting the supervisor/worker+parallelization model to a particular means of running computations in parallel.+The current adapters are as follows:++* `Threads`++ This adapter provides parallelism by spawning multiple threads; the number+ of workers can be changed arbitrarily at runtime (though you need to make+ sure that the number of capabilities is also high enough for all of them to+ run in parallel). This adapter is the only one that requires the threaded+ runtime, which adds additional overhead.++* `Processes`++ This adapter provides parallelism by spawning a child process for each+ worker; the number of workers can be changed arbitrarily at runtime.++ Install `LogicGrowsOnTrees-processes` to use this adapter.++* Network++ This adapter provides parallelism by allowing multiple workers to connect to+ a supervisor over a network; the number of workers is then equal to the+ number that are are connected to the supervisor. (It is possible for the+ same process to be both a supervisor and one or more workers.)++ Install `LogicGrowsOnTrees-network` to use this adapter.++* `MPI`++ This adapter provides parallelism using the Message Passing Interface (MPI),+ which is the standard communication system used in supercomputers, allowing+ you to use a very large number of nodes in your run. One of the nodes (#0)+ will act entirely as the supervisor, and the rest will act as workers.++ Install `LogicGrowsOnTrees-MPI` to use this adapter; note that you will need+ to have an MPI implementation installed (such as+ [OpenMPI](http://www.open-mpi.org/)).++All of these modules offer 'low-level' interfaces that are more complicated to+use but which give you more control. To use these interfaces, look for the+functions named `runExplorer`, `runSupervisor`, and `runWorker` (except for+`Threads`, which only has `runExplorer`).++Through the `Main` framework, the above also offer high-level interfaces, but+before we discuss this it is worth discussing the `Threads` module, which offers+a higher-level direct interface than the others.+++Threads+-------++The `Threads` adapter offers a higher-level interface than the others, mainly+because it does everything within a single process and so does not have to worry+about things like whether the current process is worker of the supervisor. In+the Threads module, there are `3 x 4 x 2 = 24` specialized functions, which have+the naming convention `exploreTreeXYZ` where:++* `X` is empty for `AllMode` and takes the form `UntilM` for any other mode `M`;++* `Y` is empty for `Pure` trees, `IO` for trees running in `IO`, and `Impure`+ for general impure trees; and++* `Z` is `StartingFrom` if starting from an initial progress and empty+ otherwise.++All of these functions take a *controller*, which is a function that has the+ability to make requests to the supervisor. You would use this, for example, if+you wanted to write out checkpoint file on a regular basis; specifically, you+would do this by setting up a timer that regularly calls+`requestProgressUpdateAsync` (which tells the supervisor to request a progress+update from all active workers and then returns the current progress), and then+writing this progress to a file. All of the functions you can call in the+controller are exported by the `Threads`, and they include the ability to fork+new threads which can make life easier.+++Main+----++The `Main` framework is designed to make your life easier by automating things+like checkpointing. It provides a universal interface to all adapters through a+driver system whereby all of the `mainForExploreTree` functions have a `driver`+parameter which you import from the adapter that you want to use. This is the+*only* parameter that depends on the adapter, so if you want to switch to using+a different adapter you only need to change your adapter module import so that+the driver is pulled from the desired adapter.++The main functions that you will be interested in are the `simpleMainForExploreTreeXY`+and `mainForExploreTreeXY` functions,+where `X` corresponds to the purity (empty for `Pure`) and `Y`+corresponds to the exploration mode (empty for `All`). Unlike threads, there is+not argument to specify a starting progress because instead this will be derived+from a command-line option specifying the checkpoint file; if it exists, then it+is used as the starting point.++The `simpleMainForExploreTreeXY` functions provide a relatively simple interface+that only requires the driver, a function to process the result when the run has+completed, and the logic program.++The `mainForExploreTreeXY` functions provide a more complicated interface that+allows you to add command-line arguments and options whose values you can use to+define the tree being explored, how many solutions to find, etc. All of these+functions take a `Term` argument and a `TermInfo` argument. The latter just+specifies a brief name and description for your program; it should suffice to+glance at [TUTORIAL.md](TUTORIAL.md) to see what to do. The former specifies the+command-line arguments and/or options that your particular logic program needs+to, for example, specify the size of the problem (such as the board size in the+n-queens problem); for simple cases it should again suffice to glance at the+tutorials, but in general you may need to learn how to use+[`cmdtheline`](http://hackage.haskell.org/package/cmdtheline).+[`cmdtheline`](http://hackage.haskell.org/package/cmdtheline) is used is because+it provides a means of combining arguments and options from several sources,+which in this case includes the configuration for your logic program,+configuration for the adapter (such as the number of threads or processes), and+configuration that is used by the `Main` module itself (such as the checkpoint+file and frequency, and whether to print various server statistics). The+compiled program will also have a nice `--help` page. After the command line+arguments have been parsed, the configuration information for the term you+provided will be passed as an argument to the functions that you provide in+other arguments. (Again, see the tutorial for examples of this.)+++Outcomes+--------++Once the run has finished, a `RunOutcome` will be returned that is one of the+following three possibilities:++* `Aborted` means that a request was made to abort the run.++* `Completed` means that the run terminated normally.++* `Failure` means that an unexpected error occurred.++It is worth noting that `Completed` doesn't necessarily mean that the run was+successful; if you asked for the first solution and no solutions were found,+then the result will be `Nothing`. Likewise if you (using one of the `Found`+modes) ask for `k` results but fewer than `k` were found, then the result will+be `Left` with the results that were found. If only one or a few results are+requested and they were all found, then the result will also have the progress+so you can resume the run at a later time to find more results.++If the outcome is `Completed`, then it is your responsibility to do what needs+to be done with the results, as the checkpoint file will be deleted unless your+code throws an exception.++**WARNING:**+ You should almost never resume from a checkpoint if you change the tree!+ This is only safe if the only parts of the tree that have been changed are+ those that have not yet been explored. If you do change parts of the tree+ that have been explored, then if you are lucky an exception will be thrown+ (if the branching structure has changed) and if you are unlucky, then your+ results will be silently corrupted.+++Writing an adapter+==================++`LogicGrowsOnTrees` contains a lot of functionality that automates much of the+generalizable work in writing an adapter. Most of the modules providing this+functionality live in `LogicGrowsOnTrees.Parallel.Common`, so henceforth any+module brought up in this discussion should be assumed to live there unless+stated otherwise.++The main module is `Supervisor`, which is essentially a big state machine that+keeps track of all the workers and the progress that has been made. Your adapter+essentially acts as an intermediary between the supervisor and the workers,+relaying information from the workers to the supervisors and vice versa. The way+that this works is that you run your main loop in the `SupervisorMonad`; you+communicate to the supervisor by calling the appropriate functions that act in+this monad, and it communicates with you by calling functions from a set of+callbacks that you give it when starting the run. So for example, at the+beginning of the run you might call `addWorker` to tell the supervisor that a+worker has just been added to the system, and immediately after this the+supervisor will call your `sendWorkloadToWorker` callback function to ask you to+send it the workload.++If your adapter allows the number of workers to be adjusted arbitrarily at+runtime, then you should look at the `Workgroup` module which is designed+exactly for that case. You use it by calling `runWorkgroup` and passing in+an argument containing callbacks that the `Workgroup` uses to do things like+creating and destroying workers; your argument is a function that takes a+data structure that tells you how to send messages to the supervisor. See the+`Threads` and `Processes` adaptors for examples of how to do this.++If you are not using `Workgroup`, then you will need to write the main loop+yourself. Part of your job is to provide is for the controller to communicate to+the supervisor. Functionality for doing this is contained within the+`RequestQueue` monad. You use it by first calling `newRequestQueue` to create a+new request queue, and then processing any requests that are sent to it.++Your main loop can work in one of two ways: it can either continuously poll for+communications from workers, or it can block waiting for a communication. Each+of these modes corresponds to a `SupervisorProgram`; the former is a+`PollingProgram` and the latter is a `BlockingProgram`. You are expected to use+one of these two patterns rather than writing your own loop explicitly because+they allow the server to keep track of what fraction of the time it is busy; in+principle you can always use `UnrestrictedProgram`, but in this case it is your+responsibility to call `beginSupervisorOccupied` when the supervisor becomes+active (i.e., after having waited for an incoming communication) and to call+`endSupervisorOccupied` when the supervisor becomes inactive (i.e., as it waits+for another incoming communication).++If your main loop is polling, then you also need to regularly poll the request+queue and send any request there to the supervisor. If your main loop is+blocking, then an easy option is for you to use `requestQueueProgram` instead of+your own loop, and then to have incoming communication be handled by sending the+actions you want to run in response to the request queue. (The owner of the+request queue can send any `SupervisorMonad` action to it, but the controller+has to go through the `RequestQueueMonad`, which restricts the actions that they+can run to a subset so that the controller can't do things like adding and+removing workers.)++Your adapter also has responsibility for running the controller. You should do+this using the `forkControllerThread` function in `RequestQueue`, because this+automatically adds the forked `ThreadId` to the list of controller thread ids.+The controller is free to fork additional threads, and these will automatically+be added to this list as well. When you are done, you should kill all of these+threads by calling `killControllerThreads`.++Thus far we have only talked about the supervisor side, but you will also be+responsible for starting and communicating with workers. Most of the time you+will probably want to use either the `runWorker` or `runWorkerUsingHandles`+functions in the `Process` module, with the former taking actions that send and+receive messages and the latter taking handles for sending and receiving (the+latter calls the former). These functions provide a loop that listens for and+responds to messages from the supervisor. When a workload is received, they+spawn a new worker thread; the original thread then forwards requests for stolen+workloads and progress updates to the worker thread. When the worker thread+completes, it sends the result back to the supervisor.++The only adapter that does not use the `Process` module is the `Threads` adapter;+this is because, unlike the other adapters, the worker threads in this case run+in the same process as the supervisor. Thus, it is possible to talk directly+to the worker threads rather than creating an intermediary. In such cases,+you will want to use the `Worker` module; call `forkWorkerThread` to spawn a+worker thread, and then use `sendAbortRequest`, `sendProgressUpdateRequest`, and+`sendWorkloadStealRequest` on the request queue returned by `forkWorkerThread`+to communicate directly with the worker thread; it is designed to poll the+queue on a regular basis, though it does so merely by reading an `IORef`, which+might mean that it will take a while to receive the request as the CPU caches+synchronize. (This was a deliberate design decision to minimize the overhead+of polling the request queue.)++It is good practice to package the functionality offered by your adapter under a+`runSupervisor` function to be run on the supervisor process, a `runWorker`+function to be run on worker processes, and a `runExplorer` function that is run+on *both* kinds of nodes and automatically figures out if it this node is a+supervisor or a worker.++Once you have written these functions, you should also write a driver for your+adapter. This is a function that takes a `DriverParamters` and runs the+exploration. These parameters are as follows:++* `purity`++ This gives the purity of the tree being explored.++* `shared_configuration_term`++ This is a configuration term whose information is shared by both the+ supervisor and the workers; you may require that its type be serializable.++* `supervisor_configuration_term`++ This is a configuration term whose information is only available to the+ supervisor.++* `program_info`++ This is a `TermInfo` that the users use to customize the name and brief+ description of their program in the help screen.++* `initializeGlobalState`++ This function is called on *all* processes with the shared configuration;+ its job is to initialize process-specific settings such as the logging+ level.++* `constructExplorationMode`++ This function is called on both the supervisor and the workers; it takes the+ shared configuration and uses it to compute the exploration mode. (This is+ needed because the `Found` modes take a function argument which, for+ example, checks that enough results have been generated, which will in+ general be based on a command line argument.)++* `constructTree`++ This function is only called on workers; it takes the shared configuration+ and constructs the tree to be explored.++* `getStartingProgress`++ This function is only called on the supervisor; it takes *both* the shared+ and supervisor configuration and returns the starting progress of the run,+ which could be the result of reading a checkpoint file.++* `notifyTerminated`++ This function is only called on the supervisor; it takes *both* the shared+ configuration and the supervisor configuration, and processes the outcome of+ the run.++* `constructController`++ This function is only called on the supervisor; it takes *both* the shared+ configuration and the supervisor configuration, and constructs the+ controller that you are expected to run on the supervisor.++There is not a single pattern to follow from here because different adapters can+be very different how they glue the various bits together. For example, the+`Processes` adapter's driver looks at its command line arguments for a sentinel+value in order to determine whether it is the supervisor or a worker, the+`Network` adapter's driver uses uses the first command line argument to specify+whether it is a supervisor or a worker that needs to connect over the network to+a supervisor, and the MPI adapter checks whether it is process number 0, in+which case it is the supervisor, or some other process number, in which case it+is a worker. In most cases you will likely need to send the shared+configuration out to the workers.++For examples of how to write your own adapter, your best bet is to look at the+source code of the four adapters that have been provided.+++Conclusion+==========++This concludes the Users's Guide. For more information, see [TUTORIAL.md](TUTORIAL.md) for lots+of examples of how to write logic programs and run them in parallel, as well as+the package haddock documentation for reference.
tests/tests.hs view
@@ -73,7 +73,7 @@ import Test.QuickCheck.Instances () import Test.QuickCheck.Modifiers import Test.QuickCheck.Monadic-import Test.QuickCheck.Property hiding ((.&.),(==>),abort)+import Test.QuickCheck.Property (morallyDubiousIOProperty) import Test.SmallCheck ((==>)) import Test.SmallCheck.Series (Serial(..)) import Test.SmallCheck.Drivers as Small (test)