LINQ does Logic? Chapter 6: Remotable Recursion

In Chapter 5, we used LINQ’s .Select operator to call recursive methods in a composable fashion. In this chapter, we make the recursive calls remotable via recursive lambda expressions, getting rid of pre-canned methods altogether. This will allow the crowd marketplace to innovate certain functions that are not pre-canned in the cloud, while not completely sacrificing sandbox security.

In earlier posts, we showed how to create remotable recursive lambda expressions in JavaScript. This time, we use Wes Dyer’s version of the same thing in C#, and add a redux in Mathematica and another in LINQPad of his superior derivation and explanation.

Chapter 5 presented a composable version of Feraudy’s EXAMPL5.SPR in Prolog, which implements a vestigial expression evaluator. The example is an architecturally sound foundation for a real-world expression evaluator. For example, we could, in principle, create an evaluator for Mathematica expressions. If those expressions are remotable, we could, for instance, author and test them in Mathematica and evaluate them in a sandbox written in C# or JavaScript, even on another machine. Such a sandbox would not have all the massive power and library knowledge of Mathematica, of course, but we could emulate Mathematica’s fundamental term-rewriting strategy to implement basic symbolic computations and pattern matching to enable advanced scenarios involving, say, units of measure, logic programming, and rules-driven workflow processes.

In chapter 5, we used instance methods on classes in C# to do the recursion. In particular, the linqEvaluate method on the @expression abstract class is the workhorse. Its recursive override on the @binary subclass looks like 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());  }
}

There we see that linqEvaluate on a @binary @expression recursively calls linqEvaluate on the Left and Right operand @expressions, then calls the operator’s linqApply method on the results.

In a remoting context, this will work fine if both the sender and the receiver have the definitions of the C# classes, in particular the CLR code that implements the methods. Such a situation even has security advantages: you can’t remote a call when the receiver does not statically know the class type and all its method code. But it’s also too restrictive. You can’t call any recursive function that isn’t statically pre-canned at a receiver. That means that the receiver must have pre-installed all allowable methods, and that means no innovation in the crowd. Depending on scenario, this may be exactly what you want, or exactly what you DON’T want.

What we can do, technically, is strip ALL methods off the classes, leaving only data. Remoting data is relatively easy — serialize into JSON or XML or whatever. Then, we package CODE as DATA, also, using .NET Expressions. This representation is automatically created from IQueryable and IQbservable so long as the code is stored in lambda expressions in LINQ query operators like .Select and .Where. It’s also possible to write .NET Expressions explicitly, and there will be a lot more to say about this later.

The current program, though, is to get rid of all methods and replace them with lambda expressions. Then, the calls to evaluate them, namely

    exprs
        .Select(e => Y(@eval)(e))
        .Dump(“Good LINQ method: expect IEnum of @expression”)
        ;

where

    var c1 = new @constant {Value = 4};
    var exprs = new [] { // IEnumerable<@expression>
        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}}}};

and

    Extensions
        .generate()
        .Return()
        .Dump(“Random Expression Tree”)
        .Select(e => Y(@eval)(e))
        .Dump(“Value of the Tree”)
        ;

The magic is in this definition of @eval, which takes its self-application as one input and the expression to evaluate as its second input. The Y Combinator, namely

    delegate Func<A,R> Rec<A,R>(Rec<A,R> _);
    public static Func<A,R> Y<A,R>(Func<Func<A,R>, Func<A,R>> s)
    { Rec<A,R> rec = f => n => s(f(f))(n);
        return rec(rec); // (g |-> g@g) applied to f => …
    }

creates the appropriately delayed self-application so that eval can “call itself” recursively. Here is @eval:

    Func<Func<@expression,@expression>,Func<@expression,@expression>>
        @eval = ev => ex =>
            (ex is @constant) ? ex
            : (ex is @binary) ?
            @apply(
                (ex as @binary).Op,
                ev((ex as @binary).Left),
                ev((ex as @binary).Right))
            : default(@expression)
            ;

The entire example is hosted here as a LINQPad script. Please follow the links in this post for detailed explanations of Y and how .NET Expressions are remoted. In this example, the expressions are remotable; actually remoting them involves more machinery such as implementing IQueryable, IQbservable, serialization, and various transforms on LINQ .NET Expressions. Of course, we want to use LINQ itself to perform such transformations, and that will lead us into deeper waters.

Advertisements

~ by rebcabin on September 30, 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: