LINQ Does Logic? Chapter 8: Cut and Fail

This time, we model Prolog’s cut and fail control pseudopredicates using Chapter 7’s IEnumerable of IEnumerables. In Chapter 7, we found that fail triggers backtracking and that backtracking is natural in LINQ if alternatives are represented with exactly one level of IEnumerable nesting. Now, we dig into Feraudy’s EXAMPL7.SPR [sic] to find a new exploit of that structure: the cut, which immediately bails out of all backtracking, producing “the nearest” result.

In keeping with the exploratory spirit of this blog, rather than attempt a “full-fidelity” emulation of Prolog’s cut, we’ll just reproduce Feraudy’s example as naturally as we can in LINQ, admitting that “naturally” is a subjective judgment, a matter of taste and aesthetics. We also admit that an early attempt at a full-fidelity emulation of cut looked like it was going down a slippery slope to an implementation of Prolog-proper in LINQ, and that is not at all what we want, at least not at this stage of our explorations. Instead, we’re looking for easy ways to get the effect of Prolog using LINQ in a straightforward way.

Feraudy presents the following factbase:

    (lives_in anca usa)
    (lives_in brian usa)
    (lives_in murray canada)

and the following alternative rules:

    ((north_american P)
      (lives_in P usa)
      /* experiment without the cut; 
       * experiment with fail; 
       * use (trace) to monitor internal execution; 
    ((north_american P)
     (lives_in P canada)

The interpretation is that someone is North-American if he or she lives in the USA or in Canada. The cut just means “as soon as you find someone in the USA, report that person and stop looking for more” (typical chauvinism, eh?).

In Feraudy’s interpreter, you can evaluate this goal with commands like the following:

    (consult "SPR/EXAMPL7.SPR")
    (findall P (north_american P) X)

Let’s try three versions of Feraudy’s example, one with no control pseudopredicates — no cut and no fail; one with our old friend fail; which triggers order-preserving backtracking; and one with cut, and see what we get.

First, represent the fact base the way we did in earlier chapters and scripts, only this time using anonymous types and C# dynamic, for reasons that become clear below

    var lives_in = new dynamic [] {
        new {person = "anca", country = "usa"},
        new {person = "brian", country = "usa"}, 
        new {person = "murray", country = "canada"},

This is just a non-nested IEnumerable because there are no rules, here, only facts. Rules are conjunctions, nested one more level. Let’s first write Feraudy’s rule alternatives, with no cut and no fail:

    var north_american_1 = new [] {
        lives_in.Where(l => == "usa"),
        lives_in.Where(l => == "canada"),

When we “evaluate” this rule, essentially the same as asking Feraudy’s Prolog interpreter to findall, we expect to see results for anca, brian, and murray:


Great. What’s the code for evaluate? Showing the full code will jump us ahead of cut, so let’s take it on faith for the moment.

Next, slip in a fail. Remember, fail says “give up looking down this conjunction and consider the next alternative.” A great way to model this is just to replace results with the empty IEnumerable. SelectMany will flatten those away. The deep thing happening here is that modeling alternatives with exactly one level of nesting sets up SelectMany as the evaluator because it removes exactly one level of nesting. We have a matching pair.

Write fail as follows, inside a public static class named Extensions, so that it’s an extension method:

    public static IEnumerable<dynamic> Fail (this IEnumerable<dynamic> these)
    { return new dynamic [] {}; }

This fail takes whatever it gets and discards it. Easy.

Our intrepid application programmer now modifies the knowledge base to the following:

    var north_american_2 = new [] {
        lives_in.Where(l => == "usa")
        lives_in.Where(l => == "canada"),

Think for a moment what you expect the output to be. Every time evaluation gets to the fail, results so far should be discarded and evaluation should proceed to the next alternative. We should see no one from the USA and just murray from Canada. A complying version of evaluate now becomes obvious:

    public static void evaluate(
        this IEnumerable< IEnumerable<dynamic> > alternatives)
    {    alternatives
            .SelectMany(predicates => predicates)

SelectMany flattens out the discarded USA-dwellers and our results are:

Cut says “get all the way out and produce the ‘nearest’ result.” Here, “nearest” must mean “the first result of all the possibilities.” Prolog represents “all possibilities” as a reference into the knowledge base including variables that get instantiated via unification, and we’re not modeling that process. Instead, in LINQ, we represent all possibilities as a filter — a .Where on an IEnumerable. A cut following the statement of such a filter should pick the first item in the filtered list and throw it out in an exception to be caught in evaluate. That’s the easiest way to bail out of backtracking.

First, a custom exception that can carry a payload, the “nearest” result:

    public class CutException : Exception
    { public IEnumerable<dynamic> payload; }

Next, a modified evaluate that catches these exceptions:

    public static void evaluate(
        this IEnumerable< IEnumerable<dynamic> > alternatives)
    {    try
        {    alternatives
            .SelectMany(predicates => predicates.evaluate())
        catch (CutException ce) { ce.payload.Dump(); }   }

We need an inner evaluate that can test whether an item “wants” to throw a cut exception. A slightly generalized way to do this is to check for the existence of an action property on a dynamic. If present, execute it. This is a general way to insert side effects into data items, at the cost of making everything dynamic. This cost is non-negligible, and, in a real-world application of these techniques, must be soberly traded off against other concerns. But it makes for a very pretty bit of code, here.

The best way to test for existence of a property on a dynamic object seems to be just to try it and catch the exception if the object is not present. This requires the Microsoft.CSharp.RuntimeBinder namespace and Microsoft.CSharp.dll, part of the DLR runtime. Our inner evaluate is as follows:

    public static IEnumerable<dynamic> evaluate(
        this IEnumerable<dynamic> alternative)
    {   var result = new List<dynamic>();
        foreach (var predicate in alternative)
        {   try { predicate.action(); }
            catch (RuntimeBinderException e) { /*e.Dump();*/ }
        return result;   }

Cut now inserts an action that throws the cut exception with the appropriate payload:

public static IEnumerable<dynamic> Cut (this IEnumerable<dynamic> these)
    {   return new [] {new {action = new Action(() =>
        {   throw new CutException {payload = these.Take(1)}; })
}};   }

When we run it, we get our expected chauvinistic result:

This code is available for you to play with in the usual spot.


~ by rebcabin on October 21, 2012.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: