Here is a nice paper on how to prune the execution tree when using <i>amb</i>: <i>Non-deterministic lisp with dependency-directed backtracking</i>; <a href="http://www.aaai.org/Papers/AAAI/1987/AAAI87-011.pdf" rel="nofollow">http://www.aaai.org/Papers/AAAI/1987/AAAI87-011.pdf</a><p>I've not played much with <i>amb</i> or Prolog, but it would be cool to try out some alternative strategies for exhausting the search tree, perhaps simulated annealing or something like that.
This is the sort of language feature that looks very neat at first, but there are simpler ways to solve the same problems. If you want to search a space by trying all possibilities ("generate and test"), the most straightforward way is a nested for loop with an if statement.<p>The advantage of using nested for loops is that it's pretty clear that there's a performance problem and most programmers will have a good idea what to do about it. (Perhaps change the order of the loops, do checks in the outer loops to avoid running the inner loops, and so on. For larger problems, figure out how to parallelize.)<p>Of course, a for loop isn't very modular, so something like Python's generator expressions might be more suitable for building pipelines. In Java, this can be done with iterators and some good iterator utility methods, such as those in Guava.
Haven't seen this operator before; reminds me of angelic programming. (see eg. <a href="http://portal.acm.org/citation.cfm?id=1706339" rel="nofollow">http://portal.acm.org/citation.cfm?id=1706339</a>)<p>This also seems like a very natural application of monads.