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 ;
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."
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 }
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."
20 ": check ( chickens cows -- ? )"
21 " [ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;"
24 " 1 30 [a..b] amb 1 30 [a..b] amb"
25 " [ check must-be-true ] [ 2array ] 2bi"
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:"
31 ": check ( chickens cows -- ? )"
32 " [ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;"
35 " 1 30 [a..b] amb 1 30 [a..b] amb"
36 " 2dup check must-be-true"
37 " \"%d chickens, %d cows\\n\" printf"
39 "] [ \"No solution.\" print ] if-amb drop"
42 "See more examples here: " { $url "https://re-factor.blogspot.com/search?q=backtrack" }
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 }
52 { "seq" "the alternatives" }
53 { "elt" "one of the alternatives" }
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 }
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 }
66 { "seq" "a list of words" }
68 { $description "Execute the first word in the list, and go to the next one if " { $link fail } " is called." } ;
72 { "true" { $quotation ( -- ? ) } }
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." } ;
80 { "quot" { $quotation ( -- ) } }
82 { $description "Execute all the alternatives in the quotation by calling " { $link fail } " repeatedly at the end." }
83 { $see-also bag-of fail }
88 { "quot" { $quotation ( -- result ) } }
91 { $description "Execute all the alternatives in the quotation and collect the results." }
92 { $see-also amb-all } ;