Talk:Amb

"The Amb operator takes some number of expressions (or values if that's simpler in the language) and nondeterministically yields the one or fails if given no parameter, amb returns the value that doesn't lead to failure."

Can someone make this a better sentence? Should it actually be something like:

"The Amb operator takes some number of expressions (or values if that's simpler in the language), and nondeterministically returns the value that doesn't lead to failure, or fails if given no parameter."

--Mwn3d 21:42, 22 March 2008 (MDT)

Note that the above statements suggest no relationship between the expressions and the values. It is not possible to comprehend the requirements from the current problem statement -- the programmer must reverse engineer other examples.

I would propose:

Given a sequence of sets, and some expression which would apply to two elements from two different sets, return some sequence of elements of sets where adjacent pair of elements satisfies this expression and where the order of the sets determines the order of elements in the result. The sets and the required result would remain unchanged.

(This variant not really great but I believe it is accurate and complete). -- RDM 12:53, 27 August 2009 (EDT)

Nondeterministic

Can we assume, for the purposes of the task, that the pseudo-randomness of "random" numbers available on PCs without external assistance qualify as non-deterministic? --Short Circuit 22:47, 22 March 2008 (MDT)

The non-determinism is a red herring. No implementation of Amb I've seen is actually random. The important feature of Amb is backtracking via capturing the continuation. The result is something closer to exception handling. (Can Amb be implemented using only exceptions?)

This is an advanced (almost esoteric) concept covered in SICP among other places. See: http://c2.com/cgi/wiki?AmbSpecialForm wp:Continuation. --IanOsgood 09:30, 24 March 2008 (MDT)

Nondeterminism has nothing to do with randomness.

Wouldn't it more sense just to call the task something like "nondeterministic choice" and leave it to the implementations to use whatever language feature works best for that? The SICP implenetation uses call/cc and side-effects, but to require a special operator amb for Prolog, where nondeterminism is in-built, is a bit silly. Python has generators. And it's equally silly in the Haskell example, where amb just reduces to the identity in the List-Monad. One could emulate the construction in the Continuation-and-State-Monad, but that would be even more silly :-) After all, the article "Replacing failure with a list of successes" was written long after SICP. The List-Monad construction also probably carries over more easily to other languages than call/cc. --Dirkt 02:22, 25 March 2008 (MDT)

What I think the first sentence is trying to say (and also the conventional meaning) is that Amb is a bottom-avoiding choice combinator. Suppose you have a function $f$ that works fine for some inputs $x$, but crashes or fails to terminate for others. Similarly a function $g$ works only for some limited set of inputs, not necessarily the same as $f$. Then $\mathrm {Amb} (f,g)$ is a function that returns either $f(x)$ or $g(x)$ when given an input $x$, but is guaranteed (!) to choose the one that terminates correctly if one of them does and the other doesn't. Once you understand this definition, you'll realize that the only right way to implement Amb for arbitrary unknown functions $f$ and $g$ is by multi-threading or interleaving on some level, which is where the emphasis in this task belongs. (You can't get away with using only exception handlers unless you exclude the possibility of non-termination.) Note that this semantics differs from non-deterministic choice. If $f$ and $g$ happen to have disjoint domains, it's completely deterministic.

--Sluggo 22:20, 6 September 2009 (UTC)

Haskell

The code

  unless (joins w1 w2) (amb [])

could be replaced with simply

  guard (joins w1 w2)

I didn't make the change because I don't know if you are trying to point out how to use (amb []).

C

Please put a complete C program, that can be compiled as it is.

We'll need more than that. What's the error you're getting? --Mwn3d 18:34, 27 June 2009 (UTC)