It is non-deterministic in the sense that the program itself and its inputs are not sufficient to determine the program behavior, as the amb operator creates a set of "possible worlds" in which the same expression has different values. Of course to implement it on a traditional computer, one has to simulate this behavior and decide on some order of evaluation. In SICP, where this is discussed in more depth, one of the exercises asks the reader to modify amb to return a random choice instead of just the subsequent one and this expands the range of problems one can apply this technique to:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html... http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html...

There is no known real world non-deterministic Turing Machine. We could only simulate it using a deterministic Turing Machine (like a common computer).

Using this operator make the code really clear (IMHO) and I suppose it is its purpose.

Furthermore, if one day we discover an hardware able to be a non-deterministic Turing machine is discovered, the code will work.

[1]: I doubt such an hardware exists. But you could look about quantum computer for something close to what is a non-deterministic Turing machine.

"Non-deterministic" is a somewhat technical term... Wikipedia gives a good explanation of what aspect of this operation makes it be called nondeterministic. (http://en.wikipedia.org/wiki/Nondeterministic_algorithm)

The article mentions that it's related, but somewhat simpler because it's "only" backtracking, versus Prolog's full logic programming:

The embedding recalls the continuation strategies used to implement Prolog-style logic programming, but is sparer because the operator provided is much like a Scheme boolean operator, does not require special contexts for its use, and does not rely on linguistic infrastructure such as logic variables and unification.

Cool, I was wondering if it could be implemented in ruby; it's a shame that callcc isn't present anymore in ruby 1.9

I agree. I had to use NDP for solving a few CSPs recently. SICP was a godsend.