LINQ does Logic? Chapter 5: Composable Recursion

Embedding recursive function in LINQ gives us opportunities for dynamically composable and remotable streams of operations. If we make a library of expression processors — evaluators, optimizers, rewriters of all kinds — all of type Expression -> Expression, then can put them in LINQ .Select and .SelectMany methods, which we can apply to IEnumerables and IObservables of expressions. We can send these around the system as data via IQueryable and IQbservable, allowing us to build up and tear down whole processing graphs completely dynamically, without rebuilding and redeploying applications and services.

Moving forward through the samples in Feraudy’s original distribution of SProlog, we see Exampl4.SPR is a demonstration of IO primitives. That isn’t specifically about logic programming, but rather about how Prolog interfaces with the “normal world”. We’ll skip it.

Exampl5.SPR is about recursion. This is interesting.

This particular example is a lesson in writing an expression evaluator in Prolog. Now, expression evaluation is a completely standard and classic lesson in recursion and method dispatch, and has been done to death in every programming language under the sun, e.g., F#, JavaScript, Scala, Python, etc. Could there possibly be anything more to say about it?

Maybe. Turns out that embedding such a thing in LINQ does give us a new twist: composable streaming. If we make the evaluator of type Expression -> Expression, then it becomes something we can put in a LINQ .Select method, which we can apply to an IEnumerable of expressions, or even better, to an IObservable of expressions. We can subscribe the evaluator to a potentially infinite stream of expressions and evaluate them as they arrive, forever. We can conceptually generalize from mere evaluators to all kinds of other expression processors.

Let’s first transcribe Feraudy’s example closely. He will take an expression and produce an integer. In the below, iplus, imult, and iminus are built-in Prolog primitives for integer arithmetic. Feraudy’s grammar presents two kinds of expressions: constants and binary expressions. The constant kind “bottom-out” the recursions and just produce integer values directly. The binary kind recursively walk the expression tree, evaluating left and right branches until they reduce to integers and then combining them with the built-in operators. Standard mathematical induction will furnish a proof of termination of this program on well formed finite inputs.

((evaluate V V)
 (integer V)
)
((evaluate (E1 Operator E2) V)
 (evaluate E1 V1) /* evaluate calls itself */
 (evaluate E2 V2)
 (apply_operator Operator V1 V2 V)
)

((apply_operator plus X Y Z)
 (iplus X Y Z)
)
((apply_operator minus X Y Z)
 (iminus X Y Z)
)
((apply_operator times X Y Z)
 (imult X Y Z)
)

This is pretty easy to emulate in C# LINQ. We’ll use abstract classes for the expression and operator types, putting specialized implementations of evaluate and apply in sealed subclasses. We won’t try to make the classes generic on the underlying numeric type; we’ll just use integers for now (while it’s interesting to pursue numeric generics, it’s non-trivial and a whole ‘nuther can of worms).

Here’s a real quick hack at it, with names decorated by ‘@’ both to conceal the use of a keyword, namely ‘operator,’ and to give a radiant aura of specialness to these classes:

public abstract class @expression 
{   public abstract int evaluate();   }

public sealed class @constant : @expression
{   public int Value {get; set;}
    public override int evaluate ()
    {   return Value;   }   }

public sealed class @binary : @expression
{   public @expression Left  {get; set;}
    public @operator   Op    {get; set;}
    public @expression Right {get; set;}
    public override int evaluate ()
    {   return Op.apply(Left.evaluate(), Right.evaluate());   }   
}

public abstract class @operator
{   public abstract int apply(int a, int b);   }

public sealed class @plus : @operator
{   public override int apply(int a, int b)
    {   return a + b;   }   }

public sealed class @times : @operator
{   public override int apply(int a, int b)
    {   return a * b;   }   }

public sealed class @minus: @operator
{   public override int apply(int a, int b)
    {   return a - b;   }   }

Just as with the Prolog version, these don’t do much beyond converting infix notation to prefix notation. Here’s an example usage, essentially a unit test:

    // This is a transcription of 4 * (5 + 6) == 44
    new @binary {
        Left  = new @constant {Value = 4},
        Op    = new @times(),
        Right = new @binary {
            Left  = new @constant {Value = 5},
            Op    = new @plus(),
            Right = new @constant {Value = 6}}}
        .evaluate()
        .Dump("Non-LINQ method: expect 44")
        ;

Ok, great. Now, let’s package the expressions in an IEnumerable so we can use .Select to apply the evaluator:

    // LINQ method introduces one level of IEnumerable / IObservable
    var exprs = new [] { // Puts expression in IEnumerable<@expression>
        // The rest is as above
        new @binary {
            Left  = new @constant {Value = 4},
            Op    = new @times(),
            Right = new @binary {
                Left  = new @constant {Value = 5},
                Op    = new @plus(),
                Right = new @constant {Value = 6}}}};

The evaluator is now of type IEnumerable<@expression> to IEnumerable<int>, represented as a lambda expression inside a Select (i.e., a Map):

    exprs
        .Select(e => e.evaluate())
        .Dump("Bad LINQ method: expect IEnum of int containing 44")
        ;

Oops! We can’t compose this with downstream functions that manipulate expressions. We’ve left the world of expressions and entered the world of integers. For composability, the entire evaluator is of the WRONG TYPE! We must make it produce IEnumerable<@expression> and not IEnumerable<int>. Let’s do this by adding linqEvaluate and linqApply methods, and let’s make a different operator (a so-called co-monadic one) to “extract” values from an expression! Extract should only work on leaf-level expressions, so the default implementation in the base class throws an exception:

public abstract class @expression 
{   public virtual int extract()
    {   throw new InvalidOperationException(
        "cannot extract a value from an arbitrary expression");   }
    public abstract @expression linqEvaluate();   }

public sealed class @constant : @expression
{   public int Value {get; set;}
    public override int extract ()
    {   return Value;   }
    public override @expression linqEvaluate ()
    {   return this;   }   }

public sealed class @binary : @expression
{   public @expression Left  {get; set;}
    public @operator   Op    {get; set;}
    public @expression Right {get; set;}
    public override @expression linqEvaluate ()
    {   return Op.linqApply(Left.linqEvaluate(), Right.linqEvaluate());   }   
}

public abstract class @operator
{   public abstract @expression linqApply(@expression a, @expression b);   
}

public sealed class @plus : @operator
{   public override @expression linqApply(@expression a, @expression b)
    {   return new @constant {Value = a.extract() + b.extract()};   }   
}

public sealed class @times : @operator
{   public override @expression linqApply(@expression a, @expression b)
    {   return new @constant {Value = a.extract() * b.extract()};   }   
}

public sealed class @minus: @operator
{   public override @expression linqApply(@expression a, @expression b)
    {   return new @constant {Value = a.extract() - b.extract()};   }   
}

This is just like the old stuff, only it makes sure that the gazoutas are the same type as the gazintas, namely of type @expression. That means we can freely compose expression rewriters — not just evaluators — anywhere in a LINQ pipeline. Such rewriters can do all kinds of things: optimization, customization, repurposing, and reasoning with logic! So we have come full circle (though we’re not nearly done with this series!). While investigating logic programming via LINQ, we found that LINQ’s composability led us directly to opportunities to apply logic programming to expressions. This is a gold mine.

Let us end with a couple of examples of using these new classes. There is a complete LINQpad script here with all this in more for your experimentation. Here is a usage example generating random expression trees and evaluating them in an IEnumerable:

    Enumerable
        .Range(0, 10)
        .Select(_ => @expression.generate())
        .Select(e => e.linqEvaluate())
        .Dump("Values of 10 random expression trees")
        ;

and here is a similar example evaluating them via a push model in an IObservable:

    Observable
        .Interval(TimeSpan.FromSeconds(1.0))
        .Take(10)
        .Select(_ => @expression.generate())
        .Subscribe(e => new {expression = e, value = e.linqEvaluate()}
            .Dump("A new expression every tick")
            );
Advertisements

~ by rebcabin on September 18, 2012.

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: