LINQ Does Logic? Chapter 7: Backtracking

In EXAMPL6.SPR [sic], Feraudy makes two points:

  1. Fail is Prolog’s way dump out of a sequence of goals
  2. backtracking automatically shifts evaluation to alternative definitions

Feraudy first shows just an ordinary sequence of goals

    ((demo6)
     (display success_goal1)
     (display success_goal2)
     (display success_goal3)
     (display success_goal4)
     (fail)
     (display success_goal5)
     (display success_goal6)
     (display success_goal7)
    )

When executed, we see displays of success_goals 1 through 4, then a “No,” Prolog’s standard way of reporting that it doesn’t have an answer (we can’t tell the difference between a real “no” and a “don’t know,” as discussed in Chapter 3).

A nice way to mimic this in LINQ is with a sequence of Actions, which are functions that produce no results.

    var demo6 = default(IEnumerable< Action > );

    var displayMaker = new Func<string, Action>
        (s => new Action
            (() => Console.WriteLine(s)));

    var fail = new Action(() =>
    {   throw new ApplicationException("fail");   });

    demo6 = new Action [] {
        displayMaker("success_goal1"),
        displayMaker("success_goal2"),
        displayMaker("success_goal3"),
        displayMaker("success_goal4"),
        fail,
        displayMaker("success_goal5"),
        displayMaker("success_goal6"),
        displayMaker("success_goal7"),
        };

Of course, we need a clean way to execute this. It’s often tricky to decide what to do with exceptions. Here, we’ll just print the string “fail” so that our output resembles that produced by SProlog.

    var performSequence = new Action<
        IEnumerable<Action> > (axs =>
        {    try
            {    axs
                    .Select(ax => {ax(); return 0;})
                    .Distinct()
                    .Dump()
                    ;
            } catch (Exception exception)
            {   Console.WriteLine ("fail");    }    });

    "".Dump("demo6"); 
    performSequence(demo6);

Now, in Feraudy’s demo6_1, there happens to be an additional definition. It first replicates demo6, and then there is an alternative:

    ((demo6_1)
     (display success_goal1)
     (display success_goal2)
     (display success_goal3)
     (display success_goal4)
     (fail)
     (display success_goal5)
     (display success_goal6)
     (display success_goal7)
    )

    ((demo6_1)
     (display haha)
     (nl)
    )

When Prolog encounters the fail, what does it do? Instead of saying “No,” it backtracks. That just means it looks for alternative definitions before bailing out. The order of presentation of the alternative definitions is important. Prolog searches the first one first, the second one next, and so on.

This is very similar to Mathematica’s behavior (Mathematica is the other travelling companion in our exploration of LINQ’s doing Logic). So similar, in fact, that it’s utterly straightforward to emulate EXAMPL6.SPR in Mathematica; it’s barely even an exercise for the reader and we won’t go into it here.

Since the alternatives are presented sequentially, and the order matters, the representation in LINQ is obvious: a sequence of sequences of actions, or

    var demo6_1 = default(
        IEnumerable< IEnumerable< Action > >);

    demo6_1 = new Action [] [] {
        new Action [] {
            displayMaker("success_goal1"),
            displayMaker("success_goal2"),
            displayMaker("success_goal3"),
            displayMaker("success_goal4"),
            fail,
            displayMaker("success_goal5"),
            displayMaker("success_goal6"),
            displayMaker("success_goal7"),
            },
        new Action [] {
            displayMaker("haha"),
        },
    };

All we need to get this going, generally, is a new way of handling the exception that only prints “fail” if there are no alternatives remaining.

    var performSequenceWithBacktracking = new Action<
        IEnumerable< Action > > (axs =>
        {   axs
                .Select(ax => {ax(); return 0;})
                .Distinct()
                .Dump()
                ; });

    var performSequencesWithBacktracking = new Action<
        IEnumerable< IEnumerable< Action > > > (axss =>
        {   axss
                .SelectMany(axs =>
                {    try
                    {    performSequenceWithBacktracking(axs); }
                    catch (Exception) {
                        if (axss.Last() == axs)
                            Console.WriteLine ("fail");   }
                        return new [] {0}; })
                .Distinct()
                .Dump()
                ; });

In the following invocation, it won’t print “fail” because the last alternative doesn’t contain a fail.

    "".Dump("demo6_1");
    performSequencesWithBacktracking(demo6_1);

But, if we change the second alternative of demo6_1 to contain an embedded fail

    new Action [] {
        displayMaker("haha"),
        fail,
        displayMaker("boohoo"),
    },

We get the printout of “fail,” plus, one of the debugging “Dump” calls is skipped — the one internal to “performeSequenceWithBacktracking.”

Note especially the use of “SelectMany,” the mother of all LINQ combinators, in “performSequencesWithBacktracking.”

Do we ever need deeper levels of nesting, say sequences of sequences of sequences of Actions? Not if all alternatives to a single definition are presented at the same level of nesting. We see again that a single level of nesting is fundamental. It seems to suffice to capture all kinds of containment structure, much in the way that binary trees can represent n-ary trees.

The LINQPad script for this chapter is available here.

Advertisements

~ by rebcabin on October 14, 2012.

One Response to “LINQ Does Logic? Chapter 7: Backtracking”

  1. […] 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 […]

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

 
%d bloggers like this: