Non-determinstic choice with amb-operator

Question

Is it possible to implement McCarthy's amb-operator for non-deterministic choice in C#?

Apparently .NET lacks continuation support but yield return could be useful. Would this be possible in other static .NET-languages like F#?

Answer 1

Yes, yield return does a form of continuation. Although for many useful cases, Linq provides functional operators that allow you to plug together a lazy sequence generator, so in fact in C# 3 it isn't necessary to use yield return so much (except when adding more Linq-style extensions of your own to plug gaps in the library, e.g. Zip, Unfold).

In the example we factorise an integer by brute force. Essentially the same example in C# can be done with the built-in Linq operators:

var factors = Enumerable.Range(2, 100)
        .Join(Enumerable.Range(2, 100), 
              n => 1, n => 1, (i, j) => new { i, j })
        .First(v => v.i*v.j == 481);

Console.WriteLine("Factors are " + factors.i + ", " + factors.j);

Here the starting points are my two calls to Enumerable.Range, which is built-in to Linq but you could implement yourself as:

IEnumerable<int> Range(int start, int stop)
{
    for (int n = start; n < stop; n++)
        yield return n;
}

There are two odd parameters, the n => 1, n => 1 parameters to Join. I'm picking 1 as the key value for Join to use when matching up items, hence all combinations will match and so I get to test every combination of numbers from the ranges.

Then I turn the pair of values into a kind of tuple (an anonymous type) with:

(i, j) => new { i, j })

Finally, I pick the first such tuple for which my test is satisfied:

.First(v => v.i*v.j == 481);

Update

The code inside the call to First need not be merely a short test expression. It can be a whole lot of imperative code which needs to be "restarted" if the test fails:

.First(v => 
       {
           Console.WriteLine("Aren't lambdas powerful things?");

           return v.i*v.j == 481;
       );

So the part of the program that potentially needs to be restarted with different values goes in that lambda. Whenever that lambda wants to restart itself with different values, it just returns false - the equivalent of calling amb with no arguments.