extra/backtrack/backtrack-docs.factor

   1 ! Copyright (c) 2009, 2020 Samuel Tardieu, Alexander Ilin.
   2 ! See See http://factorcode.org/license.txt for BSD license.
   3 USING: help.markup help.syntax kernel quotations sequences ;
   4 IN: backtrack
   5
   6 ABOUT: "backtrack"
   7
   8 ARTICLE: "backtrack" "Simple backtracking non-determinism"
   9 "The " { $vocab-link "backtrack" } " vocabulary implements simple non-determinism by selecting an element of a sequence, performing a test and backtracking to select the next element if the test fails."
  10 $nl
  11 "Find a first successful element:"
  12 { $subsections if-amb }
  13 "Find all combinations of successful elements:"
  14 { $subsections amb-all bag-of }
  15 "Select elements from a sequence:"
  16 { $subsections amb amb-lazy }
  17 { $examples
  18     "Let's solve the following puzzle: a farmer has some chickens and some cows for a total of 30 animal, and the animals have 74 legs in total."
  19     { $unchecked-example
  20         ": check ( chickens cows -- ? )"
  21         "    [ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;"
  22         ""
  23         "["
  24         "    1 30 [a..b] amb 1 30 [a..b] amb"
  25         "    [ check must-be-true ] [ 2array ] 2bi"
  26         "] bag-of ."
  27         "V{ { 23 7 } }"
  28     }
  29     "The output means there is only one solution: the farmer has 23 chickens and 7 cows. If we want to only find the first solution, the following approach could be used:"
  30     { $unchecked-example
  31         ": check ( chickens cows -- ? )"
  32         "    [ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;"
  33         ""
  34         "["
  35         "    1 30 [a..b] amb 1 30 [a..b] amb"
  36         "    2dup check must-be-true"
  37         "    \"%d chickens, %d cows\\n\" printf"
  38         "    t"
  39         "] [ \"No solution.\" print ] if-amb drop"
  40         "23 chickens, 7 cows"
  41     }
  42     "See more examples here: " { $url "https://re-factor.blogspot.com/search?q=backtrack" }
  43 } ;
  44
  45 HELP: fail
  46 { $description "Signal that the current alternative is not acceptable. This will cause either backtracking to occur, or a failure to be signalled, as explained in the " { $link amb } " word description." }
  47 { $see-also amb cut-amb }
  48 ;
  49
  50 HELP: amb
  51 { $values
  52   { "seq" "the alternatives" }
  53   { "elt" "one of the alternatives" }
  54 }
  55 { $description "The amb (ambiguous) word saves the state of the current computation (through the " { $vocab-link "continuations" } " vocabulary) and returns the first alternative. When " { $link fail } " is invoked, the saved state will be restored and the next alternative will be returned. When there are no more alternatives, " { $link fail } " will go up one level to the location of the previous " { $link amb } " call. If there are no more calls up the chain, an error will be signalled." }
  56 { $see-also fail cut-amb }
  57 ;
  58
  59 HELP: cut-amb
  60 { $description "Reset the amb system. Calling this word resets the whole stack of " { $link amb } " calls and should not be done lightly." }
  61 { $see-also amb fail }
  62 ;
  63
  64 HELP: amb-execute
  65 { $values
  66   { "seq" "a list of words" }
  67 }
  68 { $description "Execute the first word in the list, and go to the next one if " { $link fail } " is called." } ;
  69
  70 HELP: if-amb
  71 { $values
  72   { "true" { $quotation ( -- ? ) } }
  73   { "false" quotation }
  74   { "?" boolean }
  75 }
  76 { $description "Execute the first quotation and return " { $link t } " if it returns " { $link t } " itself. If it fails with " { $link fail } " or returns " { $link f } ", then the second quotation is executed and " { $link f } " is returned." } ;
  77
  78 HELP: amb-all
  79 { $values
  80   { "quot" { $quotation ( -- ) } }
  81 }
  82 { $description "Execute all the alternatives in the quotation by calling " { $link fail } " repeatedly at the end." }
  83 { $see-also bag-of fail }
  84 ;
  85
  86 HELP: bag-of
  87 { $values
  88   { "quot" { $quotation ( -- result ) } }
  89   { "seq" sequence }
  90 }
  91 { $description "Execute all the alternatives in the quotation and collect the results." }
  92 { $see-also amb-all } ;