Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Non-determinstic choice with amb-operator

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#?

like image 548
Dario Avatar asked Jul 03 '09 17:07

Dario


2 Answers

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.

like image 169
Daniel Earwicker Avatar answered Nov 08 '22 19:11

Daniel Earwicker


This is not an answer to your question, but it may get you what you want.

amb is used for nondeterministic computing. As you may know, Prolog is a nondeterministic language using the notion of unification to bind values to variables (basically what amb ends up doing).

There IS an implementation of this functionality in C#, called YieldProlog. As you guessed, the yield operator is an important requisite for this.

http://yieldprolog.sourceforge.net/

like image 5
Mark Bolusmjak Avatar answered Nov 08 '22 21:11

Mark Bolusmjak