Iterators and Nondeterminism

12/12/2005 6:48:54 PM

Iterators and Nondeterminism

In the course of developing with C# 2.0, I realized that I could dramatically simplify much of my AI search code by using iterators. This is because iterators enable backtracking through which nondeterministic algorithms can be implemented.

We can think of iterators as multivalued functions that we would rather treat as single-value functions. So, we pretend that we are only interested in one value by arbitrarily choosing a value from the set returned to us. If the chosen value yields unsatisfactory results, we backtrack and try a different one. If no values remain, the operation has failed.

The example below illustrates backtracking, but also shows that the return value of the iterator is not necessarily important, if we only care about the changes to the world (or containing object).

IEnumerable Iterator()
{
// Save the state of the world
try
{
// Either change the state of the world,
// Or call nested iterators that do
foreach (object ignore in NestedIterator())
yield return null;

}
    finally
{
// Restore the original state of the world
    }
}

foreach (object ignore in Iterator())
{
if (stateOfWorld.Good)
{
Action();
break;
}

// continue == backtrack
}

If the state of world is good, then we call our function and break from the loop; otherwise, we backtrack and continue on the next state. We perform our desired action upon a successful find from within the loop, because exiting the loop will call Dispose() on the enumerator and revert the world back to how it was before the loop. To retain the world, we can’t use the built-in foreach loop, but must roll our own and skip the call to Dispose.

The downside to using iterators is that more objects are created and the developer must trust the garbage collector. Fortunately, there are many ways to mitigate the overhead. For instance, an empty IEnumerable object, that always returns false to a MoveNext() call, can stored in a static variable and shared. Singleton enumerators can be pooled; as soon as Dispose() is called, the enumerator goes back into a pool. 

Logic Programming

The LINQ preview includes samples illustrating how expression trees can be used to permit logical programming such as this example.

Rules rules = new Rules();
    
rules += small(HouseholdItems.doll);
rules += small(HouseholdItems.gun);
rules += safe(HouseholdItems.doll);
rules += X => toy(X) == (small(X) & safe(X));
   
Assert(rules.Prove(toy(HouseholdItems.doll)));   
Assert(!rules.Prove(toy(HouseholdItems.gun)));   

It turns out that it is possible to implement logic programming in C# natively through the use of iterators.  

grandparent(x, z) :– parent(x, y), parent(y, z).
parent(jebbush, gpbush).
parent(ghwbush, gwbush).
parent(ghwbush, jebbush).

The above rules in Prolog could be translated into following C# code.

IEnumerable GrandParent(Exp x, Exp z)
{
      Exp y = new Exp();
      return And(Parent(x,y), Parent(y,z));
}

IEnumerable Parent(Exp x, Exp y)
{
return Or(
Unify(x, y, “jebbush”, “gpbush”),
Unify(x, y, “ghwbush”, “gwbush”),
Unify(x, y, “ghwbush”, “jebbush”));
}

bool Exists(IEnumerable term)
{
foreach(object o in term)
return true;
return false;
}

// Returns 1 result: x = ghwbush and y = gpbush
Exp x = new Exp(), y = new Exp();

foreach (object ignore in GrandParent(x,y))
{
Console.WriteLine(“gp={0} child={1}”, x, y);
}

Calling Exists( Parent(“ghwbush”, “gpbush”) ) returns false. Note that there is an implicit cast from an object to a bound Exp. Enumerating over Parent( “ghwbush”, X ) results in two return states—the first state has X = gwbush and the second has X = jebbush. (X is an Exp, whose properties include Value and IsBound. X can only be set if unbound, and is bound once set.)

The standard Prolog operators could be defined as follows. Note the implementations below are for illustrative purposes; there are many possible optimizations for space and performance, not the least of which includes inlining of And and Or operations.

IEnumerable Or(IEnumerable term1, IEnumerable term2)
{
foreach(object o in term1)
yield return null;
foreach(object o in term2)
yield return null;

}





IEnumerable And(IEnumerable term1, IEnumerable term2)
{
foreach(object o1 in term1)
foreach(object o2 in term2)
yield return null;

}

IEnumerable Cut(IEnumerable term)
{
foreach(object o in term)
{
yield return null;
yield break;
}

}



IEnumerable Not(IEnumerable term)
{
if (!Exists(term))
yield return null;
}
IEnumerable Unify(Exp x1, Exp x2)
{
// Simplified
if (Equals(x1, x2))
{
yield return null;
}


else
{

if (!x1.IsBound)
{
try { x1.Value = x2; yield return null; }
finally { x1.IsBound = false; }
}
else if (!x2.IsBound)
{
try { x2.Value = x1; yield return null; }
finally { x2.IsBound = false; }
}
}


}

Comments

 

Navigation

Categories

About

Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media