-! Copyright (c) 2009 Samuel Tardieu.
+! Copyright (c) 2009, 2020 Samuel Tardieu, Alexander Ilin.
! See See http://factorcode.org/license.txt for BSD license.
USING: help.markup help.syntax kernel quotations sequences ;
IN: backtrack
+ABOUT: "backtrack"
+
+ARTICLE: "backtrack" "Simple backtracking non-determinism"
+"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."
+$nl
+"Find a first successful element:"
+{ $subsections if-amb }
+"Find all combinations of successful elements:"
+{ $subsections amb-all bag-of }
+"Select elements from a sequence:"
+{ $subsections amb amb-lazy }
+{ $examples
+ "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."
+ { $unchecked-example
+ ": check ( chickens cows -- ? )"
+ " [ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;"
+ ""
+ "["
+ " 1 30 [a,b] amb 1 30 [a,b] amb"
+ " [ check must-be-true ] [ 2array ] 2bi"
+ "] bag-of ."
+ "V{ { 23 7 } }"
+ }
+ "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:"
+ { $unchecked-example
+ ": check ( chickens cows -- ? )"
+ " [ + 30 = ] [ 4 * swap 2 * + 74 = ] 2bi and ;"
+ ""
+ "["
+ " 1 30 [a,b] amb 1 30 [a,b] amb"
+ " 2dup check must-be-true"
+ " \"%d chickens, %d cows\\n\" printf"
+ " t"
+ "] [ \"No solution.\" print ] if-amb drop"
+ "23 chickens, 7 cows"
+ }
+ "See more examples here: " { $url "https://re-factor.blogspot.com/search?q=backtrack" }
+} ;
+
HELP: fail
{ $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." }
{ $see-also amb cut-amb }
{ "false" quotation }
{ "?" boolean }
}
-{ $description "Execute the first quotation and returns " { $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." } ;
+{ $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." } ;
HELP: amb-all
{ $values