February 2009 - Posts

Introduction

Last year at the PDC, we announced the modeling platform “Oslo”. It’s one of those technologies I’m extremely thrilled about, for various reasons. The mission to reduce the impedence mismatch between humans and computers is a huge one and great progress has been made in the past by making things more declarative in nature. Think of COM with its IDL files, think of custom attribute support in the CLR, think of configuration files to modify the behavior of an application without the need to recompile, and I’m sure you can think of many others. However, in solving this problem, quite often sub-optimal solutions arise where generic tools like XML are used, obfuscation the domain being modeled. And that’s precisely one of the things Oslo aims to help with: modeling of problem domains, in a DSL-capable way, with tool support.

 

The three pillars

The Oslo project consists of three core pillars. First, there’s the “M” modeling language. During the design of Oslo, the team realized that the “classic” approach to modeling – based on boxes and lines, a graphical representation that is – wasn’t the most appealing approach to developers (and more generally, “domain experts”). People love the low barrier to entrance that text brings, and that’s precisely what “M” enables: textual expressiveness to model domains (e.g. textual DSLs). The second pillar is the one that provides graphical (and interactive) representations over those domains, using a tool called Quadrant (more about that later). And finally, models need to be stored, and that storage space is called the Repository. Samples of repositories are SQL databases and XAML files.

Oslo = M + Quadrant + Repository = Write + Interact + Store

Ultimately the model stored in the repository is turned to execution, much like custom attributes (used to provide a model, e.g. to define a web service using attributes for a service and methods) in .NET influence the runtime (e.g. provide runtime generated code, like SOAP).

In this post, we’ll walk through M and Repository a little bit, based on the “Oslo” SDK – January 2009 CTP. Basically, I want to give people a jumpstart with M with the bare minimum of information required. In subsequent posts, I’ll dive into the details of the M programming language and cover other topics like MGrammar.

 

IntelliPad – your new textual editor toy

Without much further ado, let’s start writing a model in “M”. As “M” models are textual representations, you can use any text editor of your choice. Actually “Oslo” comes with a new fully customizable editor (written in WPF) called “IntelliPad”:

image

Because of its highly customizable nature, the first thing you should do is selecting an editor mode in the top-right corner:

image

We’ll go for “M Mode” obviously:

image

Switching the editor to this mode causes an additional menu to become available, which we’ll explore later on:

image

 

Writing your first model

Alright, time to write code now. Let’s model a collection of programming languages to take an easy start. The first concept to get used to is the one of a module. Modules are like namespaces and provide a unit of encapsulation that allows to control visibility and scope. Modules can contain exports (of types and such, see further) and can be imported somewhere else. In addition, modules have an impact on the deployment of the model to the repository, something that can get mapped on concepts like database schemas. Let’s call our module: Geeks. M is a curly brace language, so we end up with:

module Geeks
{
}

Notice how keywords in IntelliPad (see subsequent screenshot, or believe my code text formatting above) are shown in bold. Keywords are first-class citizens in domain-specific modeling as we’ll see in a future post on MGrammar.

Next, we’ll add a type to our module. A type is the definition of a “shape” of data. Instances of the type (in C# lingo) are called values, so you can also state that a type is an expression that describes a set of values. However, a type by itself doesn’t define storage, something that will be arranged by an extent. We’ll get to this in a second, but let’s first define a type called Language, that represents a programming language:

module Geeks
{
    type Language
    {
        Name : Text;
        Year : Integer16;
        Creator : Text;
    }
}

Some explanation is required. The declaration of the type itself should be fairly straightforward: again curly braces, specifying a name, nothing special. Inside the type, we declare its named fields. For example, Name is of (built-in) type Text. The ‘:’ operator used to specify the type of a field is called the “ascription operator”. Similarly we define other fields called Year and Creator. In most models, the default types are insufficiently specific to express the intent of the model. For example, we might want to restrict the length of a text field or restrict the range of a number. This can be done by defining constraints.

module Geeks
{
    type Language
    {
        Name : Text where value.Count < 20;
        Year : Integer16;
        Creator : Text;
    }
}

In the above, we’ve restricted the length of the name of a programming language to 20 characters (names of programming languages tend to be cryptic, sometimes just one-letter “words” <g>). The value keyword is used to refer to the current element being tested. Also the type itself can be annotated, for example to specify a key (which maps on primary keys in T-SQL):

module Geeks
{
    type Language
    {
        Name : Text where value.Count < 20;
        Year : Integer16;
        Creator : Text;
    } where identity Name;
}

As you can imagine this identity declaration will be used to define relationships between objects, something that’s outside the scope of this first blog post. Cool. Now we have a type, we need to define an extent. Extents map to tables in SQL and contain values of some declared type (that ultimately has the role of schematizing the table, i.e. the DDL). To declare an extent, no special keyword is required. We simply state the name of the extend an use the ascription operator again to specify the type, (optionally) suffixed with a Kleene operator to state its multiplicity. For example, we want to have 0 or more language, so we end up with:

module Geeks
{
    type Language
    {
        Name : Text where value.Count < 20;
        Year : Integer16;
        Creator : Text;
    } where identity Name;

    Languages : Language*;
}

Other multiplicity annotations are + (1 or more), ? (0 or 1) and #min..max. Here’s what the result should look like so far:

image

 

Inspecting the model declaration

Now let’s see what this model declaration corresponds to on the repository level. In other words, what code will get generated to define the model in the store. The default repository technology is SQL, so the language this gets translated into is T-SQL for the “Oslo” repository. In the “M Mode” menu, select “Repository T-SQL Preview”. Now you’ll see a split view between declaration and compilation result:

image

I’ve scrolled to the table definition code (the create table DDL statement), so you can see how fields and constraints are translated. Notice I’ve made a mistake: my programming language name should be restricted to 20 characters, not 19. Change the code on the left (< to <=) and the right will follow immediately:

image

 

Pre-populating data

What about declaring some data to be added to the repository? While the above is much like schematizing data and adding some deployment aspects to it (like extents and modules), we still need some way to declare data. We can do this by altering our extent definition as follows:

module Geeks
{
    type Language
    {
        Name : Text where value.Count <= 20;
        Year : Integer16;
        Creator : Text;
    } where identity Name;

    Languages : Language* {
        { Name = "Lisp", Year = 1958, Creator = "McCarthy"},
        { Name = "C++", Year = 1983, Creator = "Stroustrup"},
        { Name = "Haskell", Year = 1990, Creator = "Peyton-Jones"},
        { Name = "C#", Year = 2001, Creator = "Hejlsberg"},
        { Name = "F#", Year = 2005, Creator = "Syme"},
        { Name = "M", Year = 2008, Creator = "Langworthy"}
    }
}

Looks a lot like JSON, and as you can see the signal-to-noise ratio is quite optimal. Just some curly braces, assignments and commas (no closing tags or constructor calls). I’ll talk about M’s type-system another time, but its structural typing (as opposed to nominal typing, typically used by object-oriented languages like C#) provides a more natural way of dealing with data (the “has a” relationship outweighs the “is a” relationship in importance).

Notice how the Repository T-SQL preview updates itself as you type. Scrolling to the bottom will reveal a bunch of insert DML statements:

image

It’s important to point out that “Oslo” is a modeling language, not some new kind of data access technology. That means you’ll use it to write your models in a concise manner (using text), visualize and interact with them (using Quadrant), but to access and manipulate the data at the end of the day you’ll rely on your favorite data access technology of choice. That will obviously depend on the store you’re deploying to, but assuming the default of SQL, such a data access technology might be ADO.NET, LINQ to SQL, Entity Framework, or whatever you like.

 

Compile

Time to compile our model and deploy it to the repository. To do this, “Oslo” comes with a series of command-line tools (expect to see more IDE-level things in the future). First, save the model to a file called “Geeks.m”. In order to invoke the required tools in a convenient way, we’ll need to set the environment path. Unfortunately, the Oslo SDK doesn’t install an “Oslo Command Prompt” that does this, so I decided to cook my own (inspired by the Visual Studio 2008 Command Prompt):

cls
@echo Setting environment for using Microsoft Oslo SDK 1.0 tools.
@set PATH=%PATH%;%programfiles%\Microsoft Oslo SDK 1.0\Bin

Just create a shortcut that invokes %comspec% /k <path to the script above> and you’re in business. The two tools we’re going to use, m.exe and mx.exe, should be on the path now:

image

The first step to get our model deployed is to compile it. For that we use the M Compiler, m.exe. Let’s give it a try:

>m geeks.m

image

Hmm, a SQL file. Quite interesting. Take a look what’s in it: some DDL statements to create a schema and a table, as well as the DML statements to insert our data in the created table. Not bad at all and directly usable to create a schema, table and populate it with initial data. But typically we want some intermediate step, much like an object file in C or a .dll assembly in the managed word, so that we can deploy multiple of those together. We can do this by specifying the /p flag (for package), specifying the output format to be an “image” (instead of the default of “script” which created the SQL file):

m /p:image geeks.m

image

Quite a big file (a factor 10 compared to the original). You might wonder what’s inside. Curiosity is good, so let’s open it up in Notepad:

image

Ha, our friend “PK”: after the late Phil Katz, creator of PKZIP. A zip-file that is. Let’s copy it to a file with extension .zip, extract it and take a look at the contents:

image

The [Content_Types].xml file isn’t really interesting, but the others are. First the .manifest. Guess what, XAML!

image

Even more, this particular instance of XAML is a standard: OPC or the Open Packaging Convention (specified in ECMA-376, Part 2). What’s more important to our discussion here are the contents of the package, in our case two files. The first is a “sqldom” file (a SQL “Document Object Model”), the second one is an “m-ast” (an M “Abstract Syntax Tree”). I’ll dive into both in a second. But first, I wanted to point out that the use of OPC makes M-packages available to anyone for consumption. The “Oslo” platform has helpers (MImage in Microsoft.M.Framework.dll) to read the contents of an .mx “M image file”, but you can use any ZIP library and XAML parser to access the contents.

On to the .sqldom file first. This is the relevant portion to the deployment aspect of the image file, in that the MX tool (see further) reads it to generate T-SQL for execution on the repository in order to create the model over there. Let’s show a few relevant portions of the file (it’s quite a giant despite our small model – remember how verbose XML is, and what our DSL mission is all about? ;-)). Notice again it’s a XAML file, with the top-level parts denoting a database (unspecified yet, mx.exe will make it nonymous), with a schema (derived from the module declaration) containing database objects (in our case only a table but user defined functions and such are possible too):

<?xml version="1.0" encoding="utf-8"?>
<mts:AnonymousDatabase Name="{x:Null}"
                       xmlns:mts="clr-namespace:Microsoft.TSQL10.SyntaxTree;assembly=Microsoft.M.Framework"
                       xmlns:scg="clr-namespace:System.Collections.Generic;assembly=mscorlib"
                       xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
                       xmlns:x2="http://schemas.microsoft.com/netfx/2008/xaml">
  <mts:AnonymousDatabase.Schemas>
    <mts:Schema Name="Geeks">
      <mts:Schema.DatabaseObjects>

Let’s take a look at the Table definition for our Languages type:

<mts:Table x:Name="__ Reference ID 0" Name="Languages">
  <mts:Table.AdditionalStatements>
    <mts:InsertStatement DeclareVariableName="{x:Null}" DerivedTable="{x:Null}" DmlTableSource="{x:Null}" ExecuteStatement="{x:Null}" Label="{x:Null}" OutputClause="{x:Null}" Relation="{x2:Reference Name=&quot;__ Reference ID 0&quot;}" TopExpression="{x:Null}" WithCommonTableExpression="{x:Null}" RelationDependencySatisfiedExternally="False" TableHints="None" TopClauseOptions="None" UseDefaultValues="False">
      <mts:InsertStatement.Columns>
        <mts:SimpleColumn DefaultValue="{x:Null}" x:Name="__ Reference ID 1" IdentityIncrement="1" IdentitySeed="1" IsFileStream="False" IsIdentity="False" IsNullable="False" IsRowGuidColumn="False" Name="Name">
          <mts:SimpleColumn.Type>
            <mts:TSqlType Length="20" Precision="0" Scale="0" Type="NVarChar" />
          </mts:SimpleColumn.Type>
        </mts:SimpleColumn>
        <mts:SimpleColumn DefaultValue="{x:Null}" x:Name="__ Reference ID 2" IdentityIncrement="1" IdentitySeed="1" IsFileStream="False" IsIdentity="False" IsNullable="False" IsRowGuidColumn="False" Name="Year">
          <mts:SimpleColumn.Type>
            <mts:TSqlType Length="0" Precision="0" Scale="0" Type="SmallInt" />
          </mts:SimpleColumn.Type>
        </mts:SimpleColumn>
        <mts:SimpleColumn DefaultValue="{x:Null}" x:Name="__ Reference ID 3" IdentityIncrement="1" IdentitySeed="1" IsFileStream="False" IsIdentity="False" IsNullable="False" IsRowGuidColumn="False" Name="Creator">
          <mts:SimpleColumn.Type>
            <mts:TSqlType Length="2147483647" Precision="0" Scale="0" Type="NVarChar" />
          </mts:SimpleColumn.Type>
        </mts:SimpleColumn>
      </mts:InsertStatement.Columns>
      <mts:InsertStatement.Values>
        <scg:List x:TypeArguments="mts:ISqlExpression" Capacity="4">
          <mts:Constant Literal="Lisp" Type="UnicodeString" />
          <mts:Constant Literal="1958" Type="Integer" />
          <mts:Constant Literal="McCarthy" Type="UnicodeString" />
        </scg:List>
      </mts:InsertStatement.Values>
    </mts:InsertStatement>
</mts:Table.AdditionalStatements> <mts:Table.Columns> <x2:Reference Name="__ Reference ID 1" /> <x2:Reference Name="__ Reference ID 3" /> <x2:Reference Name="__ Reference ID 2" /> </mts:Table.Columns> <mts:Table.Constraints> <mts:PrimaryKeyConstraint Name="PK_Languages"> <mts:PrimaryKeyConstraint.Columns> <mts:ColumnReference Column="{x2:Reference Name=&quot;__ Reference ID 1&quot;}" Parent="{x:Null}" Qualifier="{x:Null}" Name="Name" /> </mts:PrimaryKeyConstraint.Columns> </mts:PrimaryKeyConstraint> </mts:Table.Constraints> </mts:Table>

Quite a bit of code, but rather self-explanatory. The table is called Languages, and additional statements are required to populate it. “Simple” columns are defined based on TSqlTypes and insert statements are paired with corresponding values. Finally, the table has constraints, in our case just the definition of a primary key. Notice how cross-references are made within the document using string literals like “__ Reference ID 1”, for example to refer to a column in the primary key constraint declaration.

Next, what’s up with the compilationunit.xaml file? Again XAML, this time representing the syntax tree of our model definition:

<?xml version="1.0" encoding="utf-8"?>
<CompilationUnit FileName="" Span="(0:1,1)#(0:1,1)"
                 xmlns="http://schemas.microsoft.com/languages/2008/M"
                 xmlns:p="http://schemas.microsoft.com/netfx/2008/xaml/schema"
                 xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
                 xmlns:x2="http://schemas.microsoft.com/netfx/2008/xaml">
  <ModuleDeclaration FileName="C:\temp\oslo\geeks\geeks.m" Span="(0:1,1)#(583:18,2)">
    <ModuleDeclaration.Imports>
      <ModuleImportDirective FileName="" Span="(0:1,1)#(0:1,1)">
        <ImportedName Alias="{x:Null}" FileName="" Span="(0:1,1)#(0:1,1)">
          <ImportedName.Name>
            <DeclarationReference FileName="" Span="(0:1,1)#(0:1,1)">Language</DeclarationReference>
          </ImportedName.Name>
        </ImportedName>
      </ModuleImportDirective>
    </ModuleDeclaration.Imports>
    <ModuleDeclaration.Name>
      <Parsed x:TypeArguments="p:String" FileName="C:\temp\oslo\geeks\geeks.m" Span="(7:1,8)#(12:1,13)" Value="Geeks" />
    </ModuleDeclaration.Name>
    <TypeDeclaration FileName="C:\temp\oslo\geeks\geeks.m" Span="(21:3,5)#(167:8,27)">
      <TypeDeclaration.Name>
        <Parsed x:TypeArguments="p:String" FileName="C:\temp\oslo\geeks\geeks.m" Span="(26:3,10)#(34:3,18)" Value="Language" />
      </TypeDeclaration.Name>
      <ParameterizedExpression FileName="C:\temp\oslo\geeks\geeks.m" Span="(21:3,5)#(167:8,27)">
        <ParameterizedExpression.Operation>
          <DeclarationReference FileName="C:\temp\oslo\geeks\geeks.m" Span="(21:3,5)#(167:8,27)">$Operator$Where</DeclarationReference>
        </ParameterizedExpression.Operation>
        <EntityType FileName="C:\temp\oslo\geeks\geeks.m" Span="(40:4,5)#(146:8,6)">

Notice you can actually visualize this from within the IntelliPad tool through the “M Mode” menu, option “AST”:

image

Quite interesting too, but not as relevant for this discussion as the rest of the OPC package. I’ll talk more about AST representations in a subsequent post on MGrammar.

 

Deploy

Now that we have an image file, we’re ready to deploy our model to the repository using the mx.exe tool. In order to do this, you’ll need to have a SQL Server in the proximity. Assuming you have a default instance with Windows authentication available (and you’re logged in as a user that’s a dbo on the database), you can issue the following command:

mx –d:Demo –c –f –i:geeks.mx

This tells the M command-line utility to create (-c) a database called “Demo” (-d), forcing it (-f, causing existing databases to be recreated, warning!) and based on the image (-i) geeks.mx. Once we’ve done this, we can connect to the database (e.g. using sqlcmd.exe) and dump the data from our created model:

image

(For pretty-printing purposes, I’ve added a constraint to the creator field to limit its length to 20 characters too.) Notice where the module name went (database schema) and where the type name went (table name).

 

Recap

Wow, that was easy. Let’s recap:

  1. We used IntelliPad to write a model, consisting of a module containing a type (~ schema) and an extent (~ storage) with prepopulated data (~ DML).
  2. With m.exe we compiled the model definition to an image (~ object file).
  3. Using mx.exe the created model image was deployed to the SQL server.

And of course we detoured a little into the specifics of an M image (.mx file) in between steps 2 and 3. In a future post, I’ll be talking in more detail about M’s structural type system, core language features, and such. We’ll also explore other pieces of the puzzle, like MGrammar.

Stay tuned!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Introduction

Once more I found myself in LINQ providers land recently for a project yet unannounced. Given the relative poverty of the query language we’re targeting in that particular provider, a very common question came up: what about complex expressions in predicates? Let me give you an example:

from p in products where p.Price > 100 select p

is a pretty innocent query, right? But what about:

from p in products where EnterUnknownTerritory(p.Price * Math.PI / 4) == 26 select p

That’s the totally opposite side of the spectrum, where we can’t translate the query anymore because the “EnterUnknownTerritory” method is definitely not known in the target language. So, take a look at something “in the center”, not quite trivial but by no means impossible:

from p in products where p.Price > minPrice select p

where minPrice is a variable. You might say this is as innocent as the original query, but in fact quite some stuff is going on here. Remember that LINQ queries are composed of chains of method calls each of which represent a query operator. In the sample above that boils down to:

products.Where(p => p.Price > minPrice)

The argument to the Where method is a lambda expression that captures an outer variable, so you end up with a closure and minPrice becomes a field access on the closure class. Here’s an illustration of this behavior:

image

So, MemberExpressions are lurking around every corner, sometime a little unexpectedly. Another sample of user-induced complication of expression trees (most likely well-intentioned anyway) is the following:

from p in products where p.Price > 100 && someThingLocal.Equals(alsoLocal) select p

where whole parts of the expression tree can be evaluated locally, meaning the above query can be simplified by applying the rules of Boolean logic after partial evaluation of the local portions.

 

Approach #1 – Foreign nodes

So, how to tackle this “issue”? As part of any expression tree translator (whether it’s LINQ or something else) you’ll turn the source tree into some target tree, resembling the abstract syntax of the target domain. Typically this is carried out by some kind of expression tree visitor that recursively “visits” the tree, translating nodes and putting them together. For example, you might recognize a BinaryExpression with NodeType set to ExpressionType.AndAlso and turn it into an AndPredicate:

public BinaryPredicate VisitAndAlso(BinaryExpression andAlso)
{
    return Predicate.AndAlso(Visit(andAlso.Left), Visit(andAlso.Right));
}

Here Visit is the top-level method that can take in an arbitrary (System.Linq-based) expression, and we’re turning everything into Predicate objects, our destination universe. The top-level method will look much like:

public Predicate Visit(Expression ex)
{
    switch (ex.NodeType)
    {
        case ExpressionType.AndAlso:
            return VisitAndAlso((BinaryExpression)ex);
        …
    }
}

Obviously you’ll add much more cases to the Visit method, and likely you’ll merge implementations for various binary operations that share a common implementation (recurse, construct, return). That said, at some point you’ll end up with things you don’t know about. Let’s use method calls as a sample. Maybe a method call itself is still of interest (in a sense it can be turned into a target-side equivalent), like:

  • p.Name.Equals(“Chai”)
  • String.Equals(p.Name, “Chai”)
  • p.Price.CompareTo(100)

but at some level, inevitably, you’ll end up with lots of unknowns, like (assuming the methods invoked below don’t have a target-side equivalent):

  • EnterUnknownTerritory(p.Price * Math.PI / 4)
  • p.Name.Normalize()

Outside the domain of method calls, similar unknowns can exist. Maybe the target language can’t cope with a Boolean Not, or with a simple numerical addition. Either way, you’re drowning in expression trees at that point, and the subtree you’re stuck at becomes an “unknown” to you.

Now two things can happen: either the unknown expression tree node has a dependency on a target-side thing (brought in scope through abstraction, i.e. lambda parameters), or it’s completely defined source-side (in the C#/VB local execution domain). The samples above fall under the former category because of the occurrence of “p” in the expression subtree.

During the first visit over the tree, you could (and maybe should) decide not to investigate the unknown territory yet, and invent some pseudo-node in the target domain AST that represents something “Foreign”:

return Predicate.Foreign(ex);

On a subsequent phase in the compiler, you’d decide whether or not you can evaluate the expression (some kind of partial evaluation of the entire expression) locally. If so, it gets substituted by a constant node (containing the result of source-side evaluation); if not, an exception occurs (like NotSupportedException). How to figure out whether you can do local evaluation or not? Detect whether or not foreign expression contains (again recursively by some visitor) references to the lambda parameter representing the input to the predicate clause (i.e. representing the target-side entity, e.g. a database row or entity).

The evaluation itself can be done in two ways:

  • A complete expression tree interpreter: quite a bit of work.
  • Some trick, like wrapping the remaining expression in a lambda expression, using the Compile method on it and invoke the resulting delegate, like this:

    object result = Expression.Lambda(foreignEx).Compile().DynamicInvoke();

    Note this could actually be used to figure out the foreign expression is lambda parameter free, because an InvalidOperationException will result from the Compile method if this is not the case. (Question for the reader: is the premise of requiring a foreign expression to be completely lambda-parameter-free valid?)

 

Approach #2 – Avoid the problem altogether

How’s that for a solution? If the target domain is sufficiently poor with a relatively little number of operators and such, you could try to avoid general expression trees altogether. But how? Let’s stick with query predicates (the where clause body) for our discussion to simplify matters a bit. Remember my post titled Who ever said LINQ predicates need to be Boolean-valued? from last year? That’s precisely the thing we’re going to leverage here. Instead of assigning the predicate lambda to an Expression<Func<T, bool>>, let’s “assign it” to a Func<T, Predicate>. Sounds awkward? Not really, if the way to build up the Predicate instance (which is already in a pretty good shape to be turned into the final destination language, as it reflects the AST of the target language quite accurately already) is user-friendly enough.

What do I mean with that? Well, you most certainly don’t want the user to write the following:

from p in products where Predicate.AndAlso(Predicate.LessThan(p.Price, 100), …) select p

but it would just work fine (for reasons outlined in my Who ever said LINQ predicates need to be Boolean-valued? post). However, let’s look at the problem step-by-step, inside-out. What’s up with that p.Price thing? How can we still know all the metadata about that guy? Remember, what we’re defining above in a hidden way is a simple lambda expression of type Func<Product, Predicate>:

p => Predicate.AndAlso(Predicate.LessThan(p.Price, 100), …)

That is, give it a Product instance and it will give you back a Predicate instance. But we won’t have Product instances till we’ve executed the query, and to execute the query we need to have the predicate first. Err, something’s not quite right yet as we’re turning in circles. The crux is in the use of p.Price somewhere deep inside the lambda expression (in fact, every reference to p is where the snake bites its own tail). We clearly want to have IntelliSense on every p. (“p dot”) showing all the properties on the entity we can use in our predicate. But on the other hand, executing the lambda with some Product instance, we don’t want to traverse the “dot” into the Price property above, as we need to capture the fact we’re putting a condition on the price of the product.

 

Columns and values

So, that’s where things get a little tricky. What about making the Price property something that behaves just like a decimal (assuming that’s the type we want) – well, possibly in a restricted way, see further – but still knows its own identity (i.e. it’s a representation of an underlying field/column/attribute/… with the name “Price”). Actually, here we already have an opportunity to control what the user can do with the field. Maybe the target-side doesn’t support, say, addition. So, we want to disallow that (statically). It should be clear by now that p.Price should have a type different from a “raw” decimal. It represents a column, that carries an identity, and can be instantiated at some time to become a value. Let’s ignore the latter part for now and just focus on the “column has a name” part (enough to formulate a query expression). Here’s a proposal:

class Column
{
    internal Column(string name)
    {
        Name = name;
    }

    public string Name { get; private set; }

    public NullCheck HasValue
    {
        get
        {
            return new NullCheck(this, false);
        }
    }

    public override string ToString()
    {
        return "[" + Name + "]";
    }
}

The class above acts as the base class for any column. As our target domain is “nullable” regardless of the data type (i.e. not discrepancies in nullability based on reference or value type taxonomies), we also provide a HasValue property here, which returns something that acts like a Boolean but captures semantics for use in query translation. Let’s come back to that in a few moments, but dive into the Column subclass for decimal columns first:

sealed class Number : Column
{
    internal Number(string name)
        : base(name)
    {
    }

    public Comparison Equals(NumberValue value)
    {
        return Comparison.Equal(this, value);
    }

    public static Comparison operator <(Number a, NumberValue b)
    {
        return Comparison.LessThan(a, b);
    }

    public static Comparison operator <(NumberValue a, Number b)
    {
        return Comparison.GreaterThan(b, a);
    }
    …
}

Again, here we have an opportunity to be different. In the above, I’m mimicking the target domain already in that I’m stepping away from the CLR types into target types. For example, here we talk about Number instead of Decimal (maybe because the target domain only has one numerical format). But notice how the operator overloads (I’ve omitted the opposite ones, which are identical in nature) don’t return Booleans but Comparison objects. Again, wait a moment for a peek at the Comparison type. First we need to talk about the difference between Number and NumberValue. NumberValue is the source-side representation of a constant number, e.g. in our sample query the “100” we’re comparing to would be a NumberValue. That’s where the two worlds meet: in writing a query, you simply use literals in your source language of choice, but NumberValue allows us to transition to the target domain smoothly:

sealed class NumberValue : Value
{
    private NumberValue(decimal value)
    {
        Value = value;
    }

    internal decimal Value { get; private set; }

    public override string ToString()
    {
        return Value.ToString();
    }

    public static implicit operator NumberValue(decimal x)
    {
        return new NumberValue(x);
    }
    …
}

Value is a trivial empty base class (just to have a base class in places where we need it to make our code as generic as possible). The only way to construct a NumberValue is by an implicit operator that (and that’s where things are seamless) “lifts” the CLR value into our domain-specific representation. Notice you could perfectly have additional such conversions that allow you to take in other numerical types, causing them to be normalized to the common type the target language knows about.

 

Comparisons

Now we know about the leaf nodes of the predicate trees, namely columns and values, we can turn to their parents. Predicates are based on conditions, that can be of various kind. Relational operators, null checks, string matching, etc are a few samples of such possibilities. What about the LessThan comparison?

class Comparison : Predicate
{
    internal Comparison(PredicateType type, Column column, Value value)
        : base(type)
    {
        Column = column;
        Value = value;
    }

    internal Column Column { get; private set; }
    internal Value Value { get; private set; }

    public override string ToString()
    {
        string op = null;

        switch (Type)
        {
            case PredicateType.LessThan:
                op = "<";
                break;
… } return Column.ToString() + " " + op + " " + (Value == null ? "null" : Value.ToString()); } public static Comparison LessThan(Column column, Value value) { if (column == null) throw new ArgumentNullException("column"); if (value == null) throw new NotSupportedException("Cannot apply comparison operator with a null value argument."); return new Comparison(PredicateType.LessThan, column, value); } …
}

Obviously, you can envision much more such factory methods. The key here is that all of those comparisons represent (part of) a predicate (see further) but are purely a representation instead of something executable locally. I.e. writing p.Price > 100 will result in a Comparison object with Column set to the Number(Column) pointing a the “Price” column, and Value set to a NumberValue carrying the decimal value of 100. We’ve just created a domain-specific representation of the essential building blocks of predicates.

Our NullCheck we met earlier is built in a very similar way, although it only refers to a column (it’s a unary operator so to speak):

class NullCheck : Comparison
{
    internal NullCheck(Column column, bool isNull)
        : base(isNull ? PredicateType.IsNull : PredicateType.IsNotNull, column, null)
    {
        IsNull = isNull;
    }

    internal bool IsNull { get; private set; }

    public static NullCheck operator !(NullCheck check)
    {
        return new NullCheck(check.Column, !check.IsNull);
    }

    public override string ToString()
    {
        return base.ToString();
    }
}

Notice we just play the rules of Booleans, and you can negate a null-check to get a not-null—check. Dead easy.

Actually there’s a special type of column that needs special treatment: Boolean columns (like p.IsInStock) can be used as a condition straight away (i.e. leaving off the == true comparison). That means a Boolean column should be implicitly convertible into a Condition:

sealed class Boolean : Column
{
    internal Boolean(string name)
        : base(name)
    {
    }

    public static Comparison operator !(Boolean a)
    {
        return Comparison.Equal(a, new BooleanValue(false));
    }

    public static implicit operator Comparison(Boolean a)
    {
        return Comparison.Equal(a, new BooleanValue(true));
    }
    …
}

Again I’ve omitted a bunch of operator overloads (like ==, !=) that are quite predictable.

 

Predicates

Finally the predicates themselves. Comparisons already are predicates, hence their base class being Predicate. However, predicates need to be combinable using Boolean operators, so we need a bit of plumbing there as well:

class Predicate
{
    internal Predicate(PredicateType type)
    {
        Type = type;
    }

    public PredicateType Type { get; private set; }

    public static Predicate operator &(Predicate a, Predicate b)
    {
        return new BinaryPredicate(PredicateType.And, a, b);
    }

    public static Predicate operator |(Predicate a, Predicate b)
    {
        return new BinaryPredicate(PredicateType.Or, a, b);
    }

    public static Predicate operator !(Predicate a)
    {
        return new UnaryPredicate(PredicateType.Not, a);
    }

    public static bool operator false(Predicate a)
    {
        // Used by operator && (7.11.2)
        // x && y --> T.false(x) ? x : T.&(x,y)
        return false;
    }

    public static bool operator true(Predicate a)
    {
        // Used by operator || (7.11.2)
        // x || y --> T.true(x) ? x : T.|(x,y)
        return false;
    }
}

The interesting thing here is that the operators && and || are not overloadable by themselves. The C# specification, section 7.11, details how short-circuiting operators && and || are defined in terms of more basic building blocks: &, |, true and false. So, we play a trick above: by defining operator overloads for true and false (you can think of those as “has value true” and “has value false” checks), we can force the overloads for & and | to be called at all times, eliminating short-circuiting behavior. Here’s a sample:

p.Name == “Chai” && p.Price < 100

Both sides of the && are Comparison objects, which have an overload for the & operator, in addition to the false operator (the || case is defined symmetrically in terms of | and true), so the expression above turns into:

Comparison left = p.Name == “Chai”;
Predicate.false(left) ? left : left & (p.Price < 100);

By returns “false” from the “false” call (I know, it gets abstract), we always end up in the bold part of the conditional expression above, forcing the & operator overload to be called (so, we’re in control again). And actually, it’s not much of a trick after all: by returning “false” from both the “false” and “true” operators, we actually say: “we don’t know yet whether this thing is true or false, please be pessimistic and don’t try to short-circuit this evaluation” (in a sneaky way mumbling to ourselves: “and we’ll do the rest, as you’ll blindly call us on either & or |”).

Now it should be clear that Boolean operators “just work” based on the operator overloads above. The UnaryPredicate returned from ! is straightforward, and so is the BinaryPredicate on & and |, so let’s show just one of the two:

class BinaryPredicate : Predicate
{
    public BinaryPredicate(PredicateType type, Predicate left, Predicate right)
        : base(type)
    {
        Left = left;
        Right = right;
    }

    internal Predicate Left { get; private set; }
    internal Predicate Right { get; private set; }

    public override string ToString()
    {
        string op = null;

        switch (Type)
        {
            case PredicateType.And:
                op = "and";
                break;
            case PredicateType.Or:
                op = "or";
                break;
        }

        return "(" + Left.ToString() + " " + op + " " + Right.ToString() + ")";
    }
}

No surprises here. So ultimately, the expression p.Name == “Chai” && p.Price < 100 results in a Predicate instance that carries all the semantics of the predicate and that can be translated (by means of a visitor over our AST representation) into the target domain. Here’s the PredicateType enum that illustrates the breadth of the predicate expressiveness:

enum PredicateType
{
    LessThan,
    LessThanOrEqual,
    GreaterThan,
    GreaterThanOrEqual,
    Equal,
    NotEqual,
    IsNull,
    IsNotNull,
    StartsWith,
    EndsWith,
    Contains,
    Matches,
    And,
    Or,
    Not,
}

 

Entities

We have all the materials to be successful in building up a Predicate given an entity object, like Person. Remaining question is how to write such an entity type in a straightforward way, given that the properties need to be subtypes of the Column class (like Number, (our own) Boolean, etc). Here’s a naive attempt:

class Product
{
    public String Name { get { return new String("productName"); } }
    public Number Price { get { return new Number("unitPrice"); } }
}

Brr, that’s by no means a nice representation. We’re stating the obvious a number of times: Name is a String (again, one of our subclasses of Column, maybe it should be called StringColumn after all, oh well), referring to a column with name “productName”. Same deal for Price. Lots of boilerplate here just to be able to write queries against a container of such objects. Ideally, we’d be able to write something like:

class Product
{
    [Column("productName")]
    public String Name { get; private set; } }

    [Column("unitPrice")]
    public Number Price { get; private set; } }
}

Question is how we can magically populate those properties. There are lots of tricks to do this; I’ll illustrate one below. But first, the model above doesn’t allow us to use the same type for the results of the query (we have no place to stick values). In the typical LINQ providers world, that’s a problem. In more exotic scenarios, we might just want to use LINQ to formulate a query, send it to a server and get some kind of visualization of the results back other than raw data. If the latter is the case (as it turned out to be for the problem this blog post is inspired by), this restriction is not a problem. However, even if we’d have to write a “classic” LINQ provider that allows users to return data, you could hack up a solution that looks like this. Maybe I’ll cover that another time as it’s quite an elegant approach to the problem.

Back to reality: being able to formulate the query requires us to populate the entity object instance with “good” values for its column properties. How did we get here? Well, we don’t have a mechanism anymore that can capture things like p.Name (without causing client-side evaluation). I say “anymore” because we’ve given up expression trees which exactly have that power. In order to populate the properties on the entity type, we could sacrifice the inheritance hierarchy and require the user to derive from some base class called Entity. Again, if we’re just interested in formulating a query, the entity object doesn’t have to do much more than act as a client-side metadata-container in the local type system, so this restriction shouldn’t be a stumble block:

class Product : Entity
{
    [Column("productName")]
    public String Name { get { return new String("Name"); } }

    [Column("unitPrice")]
    public Number Price { get { return new Number("Price"); } }
}

Now, what does the ColumnAttribute (used for mapping purposes) look like?

[AttributeUsage(AttributeTargets.Property, Inherited = false, AllowMultiple = false)]
sealed class ColumnAttribute : Attribute
{
    readonly string name;

    public ColumnAttribute(string name)
    {
        this.name = name;
    }

    public string Name
    {
        get { return name; }
    }
}

Given this, the role of the Entity base class will be to reflect upon the entity object itself, resolve the mapping attributes, new up column objects (like Number, String, etc), carrying the column they refer to:

sealed class Number : Column
{
    internal Number(string name)
        : base(name)
    {
    }

Here’s a possible simple implementation of the Entity constructor:

class Entity
{
    public Entity()
    {
        foreach (var prop in this.GetType().GetProperties())
        {
            var mapping = prop.GetCustomAttributes(typeof(ColumnAttribute), false).Cast<ColumnAttribute>().SingleOrDefault();
            if (mapping != null)
            {
                var column = prop.PropertyType.GetConstructor(BindingFlags.Instance | BindingFlags.NonPublic, null, new Type[] { typeof(string) }, null).Invoke(new object[] { mapping.Name });
                prop.SetValue(this, column, null);
            }
        }
    }
}

Nothing more than some reflection voodoo to find all the properties, corresponding mappings, private property setters and invoke the constructor for the column type required, passing in the column mapping value. “Cooperative instantiation” if you really want to hear a fancy word that summarizes it all :-).

 

The result

Let’s write a query and see how all of this works in concert. To be able to write such a query I’m going to provide a dummy implementation of a Source<T>, in order to allow the query expression pattern to work:

class Source<T> where T : new()
{
    private Predicate _predicate;

    public Source<T> Where(Func<T, Predicate> where)
    {
        _predicate = where(new T());
        return this;
    }
}

Now we can target this source with a LINQ query as follows:

var res = from p in new Source<Product>() where p.Price > 100 && p.Name == "Chai" select p;

Notice how all the operator overloads do their thing:

image 

The user can’t tell the difference with a regular query (i.e. against CLR types) but can’t fall off the ship either now: no exotic methods will be allowed in the expression if they don’t participate in the typing for the Predicate, Comparison, etc. Obviously, you can still substitute parts of the expression by local values (that can be retrieved by doing whatever you wish) but the other way around – trying to use the entity column references like p.Price and p.Name – won’t work:

image 

From an operation point of view, how did we manage to get the Predicate instance that represents the whole where clause? Take a look at the Where method definition:

public Source<T> Where(Func<T, Predicate> where)
{
    _predicate = where(new T());
    return this;
}

The only thing to realize here is that T, which is substituted for Product in the sample, is not a concrete instance of the entity type, but merely a metadata container as discussed before. In a bottom-up fashion, our query above translates into a Predicate as follows:

  • new T() gives us a new Product object, where the base constructor takes care of resolving the column mappings
  • calling the “where” delegate (which refers to the lambda expression from the query expression) will evaluate like this:
    • p.Price becomes a Number, as instantiated by the constructor trick above and pointing at the unitPrice column;
    • p.Price > 100 causes the 100 to become a NumberValue (through the implicit conversion), and the comparison becomes a Comparison through the > operator overload;
    • similar things happen for p.Name == “Chai”;
    • the two Comparison objects are combined through the & operator overload (together with the “false” operator trick), this produces a Predicate instance;
    • we’re done…

Under the debugger, the result looks like this (thanks to the ToString implementation):

image

Ah, I like it!

 

Download

You can find the code of this blog post here. All usual warnings apply: no quality assurance was carried out, use at your own risk, and blahblah.

 

Cheers!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Lately I’ve been playing quite a bit with mathematical representation formats like OMML (Office’s markup language for math) and MathML (the nice thing about standards is …, well you know). Both have their pros and cons, but let’s not dive into that for now. In today’s post, I’m showing you the new Windows 7 “Math Input Panel” and how you can retrieve its MathML data from the clipboard in a UI application. I’m actually using this technique to read MathML and feed it in to my interpreter that tries to turn it into execution. I’ll show how to do a similar thing with Office 2007’s OMML in a next post, using VSTO that time.

Okay, so what are we talking about. This:

image

When you open up this guy, you’ll see the following:

image

Now try to write something math-stylish. You’ll be surprised how good the recognition actually is. Forgive me for my bad handwriting (never thought I would actually ever show my handwriting through this medium):

image

Sweet! Now notice the Insert button in the bottom right corner. If you’d be in an application that knows about MathML, it would just paste fine as-is. One such application is Word 2007; give it a shot. However, we’re interested in reading the XML directly into our own application. Given that the data is put on the clipboard, we can use the Windows Forms Clipboard class to retrieve it easily. However, we want to go one step further and update our UI as soon as a MathML fragment is put on the clipboard. To be honest: in fact, I don’t care about UI at all. I just want to get the XML and feed it in to my library that tries to do stuff with it. It just turns out that, because of the clipboard-driven nature of the beast, a UI application is the fasted way to gain access to it.

So here it is: a simple form with a few events, using two user32 functions and a window message that were added in Vista:

using System;
using System.IO;
using System.Runtime.InteropServices;
using System.Windows.Forms;
using System.Xml.Linq;

namespace MathMLImport
{
    public partial class Form1 : Form
    {
        [DllImport("user32.dll")]
        public static extern bool AddClipboardFormatListener(IntPtr hwnd);

        [DllImport("user32.dll")]
        public static extern bool RemoveClipboardFormatListener(IntPtr hwnd);

        private static int WM_CLIPBOARDUPDATE = 0x031D;

        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            if (!AddClipboardFormatListener(this.Handle))
            {
                MessageBox.Show("Failed to add clipboard format listener.");
            }
        }

        protected override void DefWndProc(ref Message m)
        {
            if (m.Msg == WM_CLIPBOARDUPDATE)
            {
                UpdateClipboard();
            }
            else
            {
                base.DefWndProc(ref m);
            }
        }

        private void UpdateClipboard()
        {
            var data = (MemoryStream)Clipboard.GetData("MathML");
            if (data != null)
            {
                string tmp;
                using (data)
                {
                    tmp = Path.Combine(Path.GetTempPath(), Path.GetRandomFileName()) + ".xml";
                    using (var fs = File.OpenWrite(tmp))
                        data.WriteTo(fs);
                }

                webBrowser1.Navigate(tmp);
            }
        }

        private void Form1_FormClosed(object sender, FormClosedEventArgs e)
        {
            RemoveClipboardFormatListener(this.Handle);
        }
    }
}

The code is a bit quick-n-dirty but suffices for my purposes (I’m sure there will be other ways to code up similar functionality). As you can see, I have one single control on the form – the WebControl – used to display the XML. I wish I could simply use its DocumentStream property but turns out that doesn’t recognize the fact I’m trying to display XML and tries to show the markup as HTML. Oh well, a temporary file does the trick (yes, I know I really should delete it after being done with it…) and as expected it works just fine:

image

Besides the visualizer, I have the following to bridge the gap between the clipboard and the target format I use further on: System.Xml.Linq:

private static XDocument GetMathMLFromStream(Stream data)
{
    string mathMl;
    using (data)
    {
        using (var sr = new StreamReader(data))
        {
            mathMl = sr.ReadToEnd();
        }
    }

    return XDocument.Parse(mathMl);
}

Enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Today we’ll take a look at project “MLinq”, a very simple way to perform symbolic matrix calculations based on LINQ expression trees.

 

Introduction

But first, why would you even want to do this? Let me tell you I’m a big believer of the power of mathematical notation. Say you’ve been asked to write a piece of code that will carry out rotation of points in an n-dimensional space. To simplify matters, just consider two dimensions. Lots of readers will know this isn’t that hard using matrices:

So far so good, but now you need to know matrix multiplication in order to concretize the formula for both coordinates. Not a big deal for this particular case, but composability suffers: next you want to take the output of this rotation and feed it in to a transposition, another rotation, and so on. Wouldn’t it be nice just to write the formula as-is and let the system figure out how to turn it into execution? Obviously matrices are just the tip of the iceberg, arbitrary mathematical expressions can be represented in a symbolic format and turned to execution somehow. However, we don’t intend to write a whole symbolic math framework as part of the journey, as others have done this before (Maple, Matlab, Mathematica, to name a few)...

Let’s go back to our sample of matrix multiplication. What we’re after is something along those lines:

var t = MathExpression.Symbol<double>("t");
var p = MathExpression.Symbol<Point>("p");

MatrixExpression<double> rotate = new Expression[2, 2] { { MathExpression.Cos(t), -MathExpression.Sin(t) },
                                                         { MathExpression.Sin(t),  MathExpression.Cos(t) } };

MatrixExpression<double> point  = new Expression[2, 1] { { p.X() },
                                                         { p.Y() } };

var rot = (rotate * point).Compile<Func<Point, double, Point>>(p, t);

Console.WriteLine(rot(new Point(1, 0), Math.PI / 4));

First we define two symbolic constants, t and p. The first symbol, t, stands for the rotation angle (theta) in radians; the second symbol, p, stands for the point to rotate. Next, we define two matrices: one for the rotation matrix (using factory methods for the symbolic representation of cos(theta) and sin(theta)), and another one for the components of the point (actually the X and Y over there could benefit from some dynamic typing features, see further, as the empty method call parentheses pairs are aesthetically unpleasing). Where the magic happens is in the line below:

var rot = (rotate * point).Compile<Func<Point, double, Point>>(p, t);

Here we do a bit too much all at once, but it should still be comprehendible enough. First we multiply the two matrices in a “natural” way (you can already smell operator overloading everywhere, don’t ya?), and friendly ask the resulting expression to compile itself into a delegate that given a point and a rotation angle carries out the rotation, returning the resulting point.

Once we have all of this, we have a compiled piece of code at our service to rotate as much points as we see fit to. The sample above prints the following to the screen, rotating point (1,0) over an angle of 45° (counter-clockwise that is):

(0.707106781186548,0.707106781186547)

… something every self-respecting math-aware programmer should have predicted almost instantaneously.

 

Matrix expressions

The first piece of glue we need to get this to work is a way to express matrices. Core question becomes what makes up a matrix. The answer is: cells. What do we want those cells to contain? Answer: expressions. So we end up with an array of cells (let’s stick with two dimensions as we’re talking about matrices and not a higher-order construct like tensors).

Next, what can we do with a single matrix by itself? It makes sense to be able to retrieve an arbitrary cell’s “value”, i.e. the expression that lives in the cell with indices i and j. Notice this “value” isn’t actually a value, it’s an expression representing the cell’s contents in a symbolic way (e.g. x + y, where x and y come from somewhere, maybe as a result of adding together two matrices of the same dimensions).

Now that we know our intent with individual matrices, what about operations on one or more matrices, like negation, addition, subtraction, multiplication, and more matrix-specific operations like transposition and calculating the determinant of a matrix? An obvious choice here is to leverage the power of operator overloading. Say we want to add up two matrices, what will the result look like? Assuming the dimensions of both arrays match up (a requirement to add two matrices together), each cell will consist of an expression that is the sum of the corresponding expressions in both the input matrices. In other words, we do cell-by-cell addition. Operations like multiplication are a bit more involved though.

An important question in this whole discussion is whether we want to build up the individual cell expressions at the time a matrix operation is carried out (like addition), or we just want to keep around the fact we applied an operation between different matrices, without building up the expressions for individual cells. In some sense, the former approach is eager while the latter is lazy. And actually, the lazy approach makes sense as the user might just be interested in retrieving the contents of cell (123, 654) after carrying out a bunch of operations on 1024x1024 matrices. It would clearly be a waste of effort to build up expression trees for all other cells. This said, it should be possible to forcefully build up the resulting (symbolic) matrix expression if the user thinks that’s the thing to do (maybe because all cell values are needed). So we’ll go with the lazy variant as the foundation.

Enough about design, let’s go into implementation. Or wait, one more thing: we’ll treat expressions as immutable for very good reasons and stay in a functional world as much as possible. This said, here’s the class with factory methods for matrices (omitted null checks and such for clarity):

public static class MatrixExpression
{
    public static NewMatrixExpression<T> New<T>(Expression[,] elements)
    {
        return new NewMatrixExpression<T>(elements);
    }

    public static BinaryMatrixExpression<T> Sum<T>(MatrixExpression<T> left, MatrixExpression<T> right)
    {
        return new SumMatrixExpression<T>(left, right);
    }

    public static BinaryMatrixExpression<T> Product<T>(MatrixExpression<T> left, MatrixExpression<T> right)
    {
        return new ProductMatrixExpression<T>(left, right);
    }

    public static UnaryMatrixExpression<T> Negate<T>(MatrixExpression<T> operand)
    {
        return new NegateMatrixExpression<T>(operand);
    }

    public static UnaryMatrixExpression<T> Transpose<T>(MatrixExpression<T> operand)
    {
        return new TransposeMatrixExpression<T>(operand);
    }

    public static Expression Determinant<T>(MatrixExpression<T> operand)
    {
        throw new NotImplementedException("Left as an exercise for the reader.");
    }
}

For instance, to get into matrix world, we have to start by calling MatrixExpression.New<T> at some point. This takes in a two-dimensional array of LINQ expression trees that represent, symbolically, the contents of the matrix’s cells. I didn’t want to call this guy a “constant expression” because of its possibly parameterized nature (containing x’s and y’s). The other operators are quite easy to grasp I guess: most of them build up new matrix expressions based on existing ones, with the exception of Determinant that returns to LINQ expression tree land (and is left as a fun exercise for the reader :-)). In essence all of those play the role of constructors, which will become more convenient once we have operator overloads in place (see further).

So, what does a matrix expression by itself look like?

public abstract class MatrixExpression<T>
{
    internal MatrixExpression(MatrixExpressionType type)
    {
        NodeType = type;
    }

    public Expression this[int i, int j]
    {
        get
        {
            if (i < 0 || i >= Rows)
                throw new ArgumentOutOfRangeException("i");


if (j < 0 || j >= Columns) throw new ArgumentOutOfRangeException("j"); return Retrieve(i, j); } } public MatrixExpressionType NodeType { get; private set; } public int Rows { get; internal set; } public int Columns { get; internal set; } internal abstract Expression Retrieve(int i, int j); public Expression ToBLOCKED EXPRESSION {
// See further.
} public override string ToString() { // See further.
} public R Compile<R>(params ParameterExpression[] parameters) {
// See further. } public static BinaryMatrixExpression<T> operator +(MatrixExpression<T> left, MatrixExpression<T> right) { return MatrixExpression.Sum(left, right); } public static BinaryMatrixExpression<T> operator *(MatrixExpression<T> left, MatrixExpression<T> right) { return MatrixExpression.Product(left, right); } public static UnaryMatrixExpression<T> operator -(MatrixExpression<T> operand) { return MatrixExpression.Negate(operand); } public static UnaryMatrixExpression<T> operator ~(MatrixExpression<T> operand) { return MatrixExpression.Transpose(operand); } public static implicit operator MatrixExpression<T>(Expression[,] ex) { return MatrixExpression.New<T>(ex); } }

The operator overloads at the bottom shouldn’t be too strange (I’ve omitted a few for simplicity), but maybe the last one deserves some more attention. It’s nothing more but an implicit conversion operator between a two-dimensional array of expressions into a matrix expression, allowing you to write things like:

MatrixExpression<double> rotate = new Expression[2, 2] { { MathExpression.Cos(t), -MathExpression.Sin(t) },
                                                         { MathExpression.Sin(t),  MathExpression.Cos(t) } };

As you can see, a matrix expression by itself is quite an abstract beast (at least on the instance level). It knows how much rows and columns it has, what its node-type is (just to reduce type casts) and how to retrieve elements (the abstract method will be implemented by the various subclasses and omits bounds checking, we control the bounds of the indices that come in through the indexer and trust implementers to provide a meaningful implementation for indices that are within range). There’s some common functionality though, like pretty printing (ToString). Let’s show that one first:

public override string ToString()
{
    StringBuilder sb = new StringBuilder();

    sb.Append("{ ");
    for (int i = 0; i < Rows; i++)
    {
        sb.Append("{ ");
        for (int j = 0; j < Columns; j++)
        {
            sb.Append(Retrieve(i, j).ToString());
            if (j != Columns - 1)
                sb.Append(", ");
        }
        sb.Append(" }");

        if (i != Rows - 1)
            sb.Append(", ");
    }
    sb.Append(" }");

    return sb.ToString();
}

No surprises here, just calling into ToString on the individual expressions for the cells retrieved through the Retrieve method. So, in essence, ToString forces the cells to be “computed” in a symbolic fashion (e.g. ToString invoked on a summation matrix expression will yield cell-left + cell-right in a symbolic fashion, e.g. x + y).

Printing isn’t the most exciting thing though, but we’ll defer the discussion of ToExpression and Compile for a little while longer, and show how to implement concrete matrix expressions first.

 

Implementing sum and product

So, how does a concrete matrix expression implementation look like? Let’s start by taking a quick look at the NewMatrixExpression, which will act as a leaf node in matrix expression trees:

public sealed class NewMatrixExpression<T> : MatrixExpression<T>
{
    private Expression[,] _elements;

    internal NewMatrixExpression(Expression[,] elements)
        : base(MatrixExpressionType.New)
    {
        _elements = elements;

        Rows = elements.GetLength(0);
        Columns = elements.GetLength(1);
    }

    internal override Expression Retrieve(int i, int j)
    {
        return _elements[i, j];
    }
}

This thing does nothing more but storing a reference to the array of expressions (representing each individual cell), with a trivial implementation of Retrieve on top of it. All we’ve done is abstracted the concept of a two-dimensional array a bit further. (Notice we don’t have true immutability here as we pass in a reference to an existing array of expressions, modifying that will have effects on the whole matrix expression tree defined on top of it…).

Enough trivialities, let’s turn to the real stuff by taking a glimpse of the SumMatrixExpression:

public sealed class SumMatrixExpression<T> : BinaryMatrixExpression<T>
{
    internal SumMatrixExpression(MatrixExpression<T> left, MatrixExpression<T> right)
        : base(MatrixExpressionType.Sum, left, right)
    {
        if (left.Rows != right.Rows || left.Columns != right.Columns)
            throw new InvalidOperationException("Dimensions do not match.");

        Rows = left.Rows;
        Columns = left.Columns;
    }

    internal override Expression Retrieve(int i, int j)
    {
        return Expression.Add(Left.Retrieve(i, j), Right.Retrieve(i, j));
    }
}

Still we’re fairly minimalistic in the implementation. We do a little checking of the incoming matrices to make sure the dimensions match, and call into our base class constructor to create a “binary matrix expression” (nothing more than a container for a two MatrixExpression instances, of the same generic parameter T, named Left and Right). The interesting part is Retrieve, which locates the requested cell in both matrices and returns a new expression tree representing the sum of the cells. So, internally matrix expressions perform their operations based on the underlying LINQ expression trees.

Cool, so how does a product matrix look like? A bit more complicated due to the less trivial mathematical definition, but again relatively straightforward and without boilerplate code:

public sealed class ProductMatrixExpression<T> : BinaryMatrixExpression<T>
{
    private int _k;

    internal ProductMatrixExpression(MatrixExpression<T> left, MatrixExpression<T> right)
        : base(MatrixExpressionType.Product, left, right)
    {
        if (left.Columns != right.Rows)
            throw new InvalidOperationException("Dimensions do not line up.");

        Rows = left.Rows;
        Columns = right.Columns;

        _k = left.Columns;
    }

    internal override Expression Retrieve(int i, int j)
    {
        var res = Expression.Multiply(Left.Retrieve(i, 0), Right.Retrieve(0, j));

        for (int k = 1; k < _k; k++)
            res = Expression.Add(res, Expression.Multiply(Left.Retrieve(i, k), Right.Retrieve(k, j)));

        return res;
    }
}

If you can’t remember how to multiply matrices, open up your favorite search engine to find the answer. You’ll see we’re simply encoding that algorithm above by means of a single for-loop, building up an expression tree that’s a sum of products of cells.

I’ll leave the implementation of Transpose (rows become columns and vice versa) and Negate (negate every cell) to the reader.

 

Preparing for evaluation

Next we need to take a look at how to evaluate a matrix expression, i.e. how to yield concrete values when supplying substitutions for the symbols. But wait a minute, where to those symbols come from? Say, we’re creating a new matrix and want to stick x and y in some cells, what precisely are x and y? The answer is: ParameterExpression, one of the node types of LINQ expression trees. That by itself is simple enough, but on the surface we might want to abstract that a little to make things more general and more aesthetically pleasing. (Actually, I’m deviating a little here into the world of OMMLinq, where MatrixExpressions are a subset of MathExpressions.) Here’s the glue we want to add:

public class MathExpression
{
    private Expression _ex;

    internal MathExpression(Expression ex)
    {
        _ex = ex;
    }

    public static MathExpression operator -(MathExpression op)
    {
        return new MathExpression(Expression.Negate(op._ex));
    }

    public static MathExpression Cos(MathExpression arg)
    {
        return new MathExpression(Expression.Call(typeof(Math).GetMethod("Cos"), arg._ex));
    }
    
    public static MathExpression Sin(MathExpression arg)
    {
        return new MathExpression(Expression.Call(typeof(Math).GetMethod("Sin"), arg._ex));
    }

    public static SymbolMathExpression Symbol<T>(string name)
    {
        return new SymbolMathExpression(Expression.Parameter(typeof(T), name));
    }

    public static implicit operator MathExpression(Expression ex)
    {
        return new MathExpression(ex);
    }

    public static implicit operator Expression(MathExpression ex)
    {
        return ex._ex;
    }
}

public class SymbolMathExpression : MathExpression
{
    private ParameterExpression _ex;

    internal SymbolMathExpression(ParameterExpression ex) : base(ex)
    {
        _ex = ex;
    }

    public static implicit operator ParameterExpression(SymbolMathExpression ex)
    {
        return ex._ex;
    }
}

I’ve omitted a bunch of operators (trigonometry functions, exponentials and logarithms, combinatorials, etc), to reduce the concept of MathExpression to the bare minimum needed for our rotation sample. The key thing here is to see how implicit conversions allow us to go back and forth between LINQ expression trees and math expressions. It’s a bit unfortunate the LINQ expression trees form a closed world (but for a very good reason), so you don’t get to extend that library, ending up with a common base type for all expression tree nodes, so we cook our own. But in essence, once we’re in the world of MathExpression, operations are defined to apply operators and such, without leaking the LINQ expression tree implementation to the outside as part of those operations (unless the raw expression tree is needed, it stays within the walls of this domain-specific expression tree format).

From the above, you can see how we’ve introduce syntactical sugar for a ParameterExpression in the form of MathExpression.Symbol<T>:

var t = MathExpression.Symbol<double>("t");
var p = MathExpression.Symbol<Point>("p");

This feels much more natural and domain-specific than a raw ParameterExpression from LINQ. What Point is defined like shouldn’t be too much of a surprise: two double-valued properties X and Y (and again, immutable).

Given all of this, you can see how (with additional operators on MathExpression if required) larger and more complex math expressions are built: simply by using the constructor factory methods on MathExpression. That’s how we end up with the definition of the rotation and point matrices:

MatrixExpression<double> rotate = new Expression[2, 2] { { MathExpression.Cos(t), -MathExpression.Sin(t) },
                                                         { MathExpression.Sin(t),  MathExpression.Cos(t) } };

MatrixExpression<double> point  = new Expression[2, 1] { { p.X() },
                                                         { p.Y() } };

A few things should stand out here. First, why did I decide to make MatrixExpression “compatible with” a two-dimensional array of LINQ expressions, as opposed to MathExpression objects? The sole reason right now is because of simplification in the implementation of matrices; more specifically, Expression.Add (and its brothers) can’t do operator overload resolution by themselves. For instance, if you’d have two matrices of complex numbers and the ComplexNumber class has an operator overload for +, Expression.Add on two such terms won’t be able to find that operator overload by itself. To avoid distraction on implementing overload resolution rules, I’ve omitted this kind of plumbing (although you can still make it crash by using “unconventional” matrices, e.g. of string elements, which do not have a built-in + operator either).

The second observation is the use of methods on p to retrieve the point’s coordinates. As I wanted to show the point’s coordinates explicitly (as opposed to multiplying the rotation matrix, which is 2 x 2, with a point, that would look like 1 x 1), I needed a way to extract the coordinates. Simply calling the properties for X and Y doesn’t help, as those return the double values directly. Rather, we need some kind of indirection: a symbolic representation of “take the X coordinate of point p”. I’ve hacked this up using a couple of extension methods:

static class PointExtensions
{
    public static MathExpression X(this MathExpression ex)
    {
        // Could be generalized using C# 4.0 "dynamic".
        return new MathExpression(Expression.MakeMemberAccess(ex, ((Expression)ex).Type.GetProperty("X")));
    }

    public static MathExpression Y(this MathExpression ex)
    {
        // Could be generalized using C# 4.0 "dynamic".
        return new MathExpression(Expression.MakeMemberAccess(ex, ((Expression)ex).Type.GetProperty("Y")));
    }
}

Essentially, those build up math expressions based on expression trees that refer to the respective properties. We can’t make this happen automatically while still having somewhat nice syntax. Expression trees can be created for lambda expressions in C#, like – with a closure capturing outer variable p – () => p.X, but not for “stand-alone” expressions. Even if we’d go with the lambda syntax, using p.X won’t work as p is of type SymbolMathExpression and that doesn’t have an X property by itself (the thing it refers to might have though, as is the case in our sample). That’s where “dynamic” in expression trees would come in handy.

 

Evaluation

So, how do we want to go about evaluating the result of a symbolic computation using those matrix expressions? The answer is, we need to be able to turn cells or the whole matrix into code that can compute values, given the substitutions for the symbols. For example, if we multiply rotate by point and want to know the topmost, leftmost cell’s value, we still need to supply values for the point and the rotation angle, because the cell’s computation might depend on those. So, ultimately we need to turn the cell into the body of a lambda expression that’s parameterized in the symbols.

Let’s start by looking at the plumbing to evaluate a single cell:

MatrixExpression<double> res = rotate * point;
Expression cell00 = res[0, 0];
Console.WriteLine(cell00);

LambdaExpression fCell00 = Expression.Lambda(cell00, p, t);
var f = (Func<Point, double, double>)fCell00.Compile();
double xNew = f(new Point(1, 0), Math.PI / 4);
Console.WriteLine(xNew);

Step-by-step now. The first line is obvious, we take our two matrices and multiply them, giving us back a new matrix containing double-valued (though symbol) cells. Next, we call into the public indexer to retrieve the expression tree for the topmost, leftmost cell. Again, that’s symbolic. You should be able to predicate the third line therefore prints (modulo precise knowledge of Expression.ToString):

((Cos(t) * p.X) + (-Sin(t) * p.Y))

As you can see, this contains ingredients from different cells in the original matrices, but composed through LINQ expression tree operations like product and sum. Next, we want to evaluate this, which means we need to get rid of the symbolic representation of p (the pont) and t (the rotation angle). So, we wrap this in a lambda expression that has p and t as parameters. This is what fCell00 is all about. If you’d printf that one, you’d see something like:

(p, t) => ((Cos(t) * p.X) + (-Sin(t) * p.Y))

We know the type of p and t, as well as the result (a cell of the matrix is of type double), so we can provide a signature for the to-be-compiled lambda: Point –> double –> double, or in C# style: Func<Point, double, double>. That’s what gets stored in f. And finally, we can call through the delegate, applying our function to a point (x = 1, y = 0) and with a rotation angle of 45° (Pi/4 in radians).

Quite some boilerplate code to get this to work, but if you want you could compactify the whole thing quite a bit:

var f = (Func<Point, double, double>)Expression.Lambda((rotate * point)[0,0], p, t).Compile();

and indeed, this kind of logic would rightfully belong inside MatrixExpression, returning a delegate given cell indices and a (symbols) parameter order.

Now that we got an idea about how to evaluate a single cell, what about evaluating a whole matrix? What would the result of that be? Clearly, a two-dimensional array of concrete values that are computed based on substitution values for the symbols. That’s exactly what the ToExpression method on MatrixExpression is meant for:

public Expression ToBLOCKED EXPRESSION
{
    var res =
        Expression.NewArrayInit(typeof(T[]), Enumerable.Range(0, Rows).Select(i =>
            Expression.NewArrayInit(typeof(T), Enumerable.Range(0, Columns).Select(j =>
                Retrieve(i, j)
            ))).Cast<Expression>() // Missing generic variance (C# 4.0).
        );

    return res;
}

This might look quite dense, but uses the power of LINQ to build up (the expression tree for) an array of symbolic computations, based on the Retrieve method for each individual cell. Insert a few curly braces and it starts to look like nested foreach loops:

public Expression ToBLOCKED EXPRESSION
{
    var res =
        Expression.NewArrayInit(typeof(T[]), Enumerable.Range(0, Rows).Select(i =>
{ Expression.NewArrayInit(typeof(T), Enumerable.Range(0, Columns).Select(j =>
{ Retrieve(i, j); });
})).Cast<Expression>() // Missing generic variance (C# 4.0). ); return res; }

What this creates is an expression tree to create an instance of a T[][] array. Notice I’m using jagged arrays because expression trees do not support the creation of multi-dimensional arrays at the time of writing. The use of the Cast<Expression> is interesting. If you emit this, you’ll get a compile error saying: cannot convert an IEnumerable<NewArrayExpression> into an IEnumerable<Expression>. Clearly this is valid because of covariance (IEnumerable<Elephant> should be assignable to IEnumerable<Animal>), but we don’t have this feature at our service for the moment (but C# 4.0 will, yippie, hence my comment in the code).

Anyway, let’s try the following:

MatrixExpression<double> res = rotate * point;
Expression matrix = res.ToBLOCKED EXPRESSION;
Console.WriteLine(matrix);

LambdaExpression fMatrix = Expression.Lambda(matrix, p, t);
var f = (Func<Point, double, double[][]>)fMatrix.Compile();
double[][] pNew = f(new Point(1, 0), Math.PI / 4);
pNew.Print();

Notice the parallels with the code to evaluate a single cell. Now the first Console.WriteLine prints:

new [] {new [] {((Cos(t) * p.X) + (-Sin(t) * p.Y))}, new [] {((Sin(t) * p.X) + (Cos(t) * p.Y))}}

or, with some manual touch-ups,

new [] {
    new [] {((Cos(t) * p.X) + (-Sin(t) * p.Y))},
    new [] {((Sin(t) * p.X) + ( Cos(t) * p.Y))}
}

Clearly the formula we expected for both coordinates, in a LINQ expression tree format. Again, the compilation code is fairly similar, but notice how the return type of the delegate is degraded to a double[][] instead of a Point. We’ll do something about this in a minute, but first the output of the call to Print():

{ { 0.707106781186548 }, { 0.707106781186547 } }

What’s Print anyway? Just a plain extension method on jagged arrays:

static class Extensions
{
    public static void Print<T>(this T[][] array)
    {
        StringBuilder sb = new StringBuilder();

        sb.Append("{ ");
        int m = array.Length;
        for (int i = 0; i < m; i++)
        {
            int n = array[i].Length;
            sb.Append("{ ");
            for (int j = 0; j < n; j++)
            {
                sb.Append(array[i][j].ToString());
                if (j != n - 1)
                    sb.Append(", ");
            }
            sb.Append(" }");

            if (i != m - 1)
                sb.Append(", ");
        }
        sb.Append(" }");

        Console.WriteLine(sb);
    }
}

So, what about that broken return type in our delegate (also some kind of covariance, although a double[][] is not really to be treated as a Point in the general case)? Can we do better? With a little hack we can. Say we can trust the user to call Compile on a MatrixExpression, passing in a compatible delegate for the result, like this:

var rot = (rotate * point).Compile<Func<Point, double, Point>>(p, t);

(Notice this trust relationship is of a kind that we can still throw exceptions in the abuser’s face :-).) It’s clear we can take a look at the generic parameter passed in to Compile, make sure it’s a Func<…>, an extract the return type from it (the last generic parameter). Once we have that, we can emit a LINQ expression tree that wraps the result of a ToExpression call in a Convert expression tree node that makes the return value of the desired type (Expression.Convert is smart enough to find such conversions):

public R Compile<R>(params ParameterExpression[] parameters)
{
    var t = typeof(R);
    if (!t.IsGenericType || !t.GetGenericTypeDefinition().Name.StartsWith("Func"))
        throw new Exception("Not a Func<...>.");

    var a = t.GetGenericArguments();
    var r = a[a.Length - 1];

    return Expression.Lambda<R>(Expression.Convert(this.ToBLOCKED EXPRESSION, r), parameters).Compile();
}

Isn’t that beautiful? We just need to have a conversion available from double[][] to Point, obviously one that checks – omitted below – the input dimensions to be conform with expectations for a point’s dimensions (1 x n, with n = 2 in our case, thus a vector):

public static implicit operator Point(double[][] point)
{
    return new Point(point[0][0], point[1][0]);
}

This will do the trick for now, but notice how this makes the intermediate array allocation totally redundant. Can we eliminate that inefficiency? Sure, we have all the materials in the room to do so. We just shouldn’t apply the "Point conversion” from the outside, but extract the two relevant cells from the resulting matrix and feed them in to the Point constructor straight away. Adding this intelligence to our little engine isn’t that hard, even in a somewhat generic way (i.e. “intelligent conversions” as expression tree rewriters), but let’s keep that for another time when we talk about optimizing techniques (tip: try this at home with sparse matrices, i.e. lots of zero-valued cells, and watch the output of simple matrix calculations…).

Just for the record, here are the results for rotating 10,000,000 (randomly chosen) points with a direct (but naive, i.e. equivalent to the generated expressions from the matrix multiplication, without extracting common subexpressions for sine and cosine calculation) implementation versus our symbolic one (excluding the initial compilation of the lambda):

Symbolic: 00:00:05.2810564
Classic:  00:00:03.0292995

Applying the optimization for Point-conversion I’m hinting at above puts them on par actually (we even did a little better, but that’s just a test noise artifact):

Symbolic: 00:00:03.1099769
Classic:  00:00:03.2106196

and if we’d go all the way in the optimizer, we could even eliminate common subexpressions (a bit tricky though, but doable), at the cost of additional compile and analysis time upfront (and getting into territory where LINQ expression trees do not longer help as we need to generate multiple statements now, welcome DLR!).

Did I tell you I’m a big believer of the power of mathematical notation? Yielding control to the runtime might sound frightening to some, but it has its merits as you can see…

Have fun!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

First of all – way too late – a happy 2009. I know, it’s been dead silent over here lately, but for good reasons. I’ve been quite busy on a few personal fun “hacking” projects (an ideal way to spend the Holiday season), my work on the upcoming 4.0 release of the .NET Framework, LINQifying the world (currently on a project I can’t talk about yet), book reviews and reading lots of stuff. First of all, I’d like to thank the numerous readers of my blog reminding me gently to start blogging again. Two months of silence was unprecedented here, so some started to worry :-).

So, what to expect on my blog in the near future:

  • In-depth explorations of (hopefully) inspiring fun projects.
  • More info on the .NET Framework 4.0 release, exploring various new APIs.
  • Windows 7 adventures.
  • Fun with F# and the DLR.
  • Reports on my studies of various other technologies, such as MVC, MEF, Oslo, etc.

Let’s dive a little deeper in the “fun projects” category to wet the reader’s appetite…

 

#1 - Batch Language Runtime (BLR)

The BLR is a (partial) implementation of the CLI specification (ECMA 335), v1 (i.e. without support for generics and such), in … batch script. Kind of traditionally, I’ve been (re-)reading technical specifications every Holiday season, and in a round-robin fashion the CLI specification got scheduled for last December. However, just reading the thing isn’t very appealing, so I wanted to implement core portions of the runtime myself in a rather odd way: the ancient batch interpreter (cmd.exe).

First of all, a warning: the BLR is not meant to be a solution to be used in production. Microsoft’s story for scripting and management is Windows PowerShell, so go for that if you want (you should!) to use the .NET runtime in a scripting and automation environment. The BLR is just a crazy fun project to study the CLI in depth (actually to torture myself in some way :-)).

Without further ado, here’s a very basic sample.

Below is the IL code for an imperative implementation of Fibonacci:

.method private hidebysig static void  Main() cil managed
{
  .entrypoint
  // Code size       32 (0x20)
  .maxstack  2
  .locals init (int32 V_0,
           int32 V_1,
           int32 V_2,
           int32 V_3)
  IL_0000:  ldc.i4.0
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.1
  IL_0003:  stloc.1
  IL_0004:  ldc.i4.0
  IL_0005:  stloc.2
  IL_0006:  br.s       IL_001a
  IL_0008:  ldloc.1
  IL_0009:  call       void [mscorlib]System.Console::WriteLine(int32)
  IL_000e:  ldloc.1
  IL_000f:  ldloc.0
  IL_0010:  add
  IL_0011:  stloc.3
  IL_0012:  ldloc.1
  IL_0013:  stloc.0
  IL_0014:  ldloc.3
  IL_0015:  stloc.1
  IL_0016:  ldloc.2
  IL_0017:  ldc.i4.1
  IL_0018:  add
  IL_0019:  stloc.2
  IL_001a:  ldloc.2
  IL_001b:  ldc.i4.s   10
  IL_001d:  blt.s      IL_0008
  IL_001f:  ret
} // end of method Fib::Main

After cross-compilation (currently mostly a manual step) to BIL (Batch Intermediate Language), it looks like this:

:sample_fib
:sample_fib_0
    goto :ldc.i4.0
:sample_fib_1
    goto :stloc.0
:sample_fib_2
    goto :ldc.i4.1
:sample_fib_3
    goto :stloc.1
:sample_fib_4
    goto :ldc.i4.0
:sample_fib_5
    goto :stloc.2
:sample_fib_6
    set __op0=21
    goto :br
:sample_fib_7
    goto :ldloc.1
:sample_fib_8
    set __op0=[bsborlib]echo_int
    goto :call
:sample_fib_9
    goto :ldloc.1
:sample_fib_10
    goto :ldloc.0
:sample_fib_11
    goto :add
:sample_fib_12
    goto :stloc.3
:sample_fib_13
    goto :ldloc.1
:sample_fib_14
    goto :stloc.0
:sample_fib_15
    goto :ldloc.3
:sample_fib_16
    goto :stloc.1
:sample_fib_17
    goto :ldloc.2
:sample_fib_18
    goto :ldc.i4.1
:sample_fib_19
    goto :add
:sample_fib_20
    goto :stloc.2
:sample_fib_21
    goto :ldloc.2
:sample_fib_22
    set __op0=10
    goto :ldc.i4
:sample_fib_23
    set __op0=7
    goto :blt
:sample_fib_24
    goto :ret
goto :eof

Notice how instructions become goto batch instructions that call into the BLR’s runtime implementation (completely in batch, yes). Currently about 90% of the IL instruction set is implemented, including encodings for the required metadata about methods (method table), types and method bodies (like exception handling). For example, here’s the module initializer for the Fibonacci assembly in BIL:

:__init
call :import bsborlib
call :addmt main 0 0 0
call :addmt sample_fib 0 0 4
goto :eof

It indicates that sample_fib is a (static – the build I’m showing this on doesn’t have support for instance methods yet, i.e. that support is unstable currently) method with 0 parameters, doesn’t return anything and needs room for 4 locals. In the build I’m showing this on, the runtime is more or less untyped although I’m currently hacking up support for arbitrary types (both value types and reference types). Also notice the BLR can load libraries (also written in batch obviously), in this case we load “bsborlib” (Batch Scripting Batch Object Runtime Library, as in mscorlib) to have access to [bsborlib]echo_int (used in sample_fib_8). Oh, and there are much more analogies with CLR terminology, e.g. the entry-point function of the BLR is called BorBatMain (like CorExeMain).

Other methods require much more metadata, e.g. to deal with exceptions (protected regions with catch, filter, fault or finally blocks):

call :addeh TryFinally_impl %__C_EH_FINALLY% 0 5 5 3
call :addeh TryFinallyNested_impl %__C_EH_FINALLY% 2 5 7 3
call :addeh TryFinallyNested_impl %__C_EH_FINALLY% 0 13 13 3
call :addeh TryFinallyNestedInFinally_impl %__C_EH_FINALLY% 0 3 3 11
call :addeh TryFinallyNestedInFinally_impl %__C_EH_FINALLY% 5 3 8 3
call :addeh TryCatch_impl %__C_EH_CATCH% 0 6 6 7 1
call :addeh TryCatchStackWalk_impl2 %__C_EH_FINALLY% 0 6 6 3
call :addeh TryCatchStackWalk_impl %__C_EH_CATCH% 0 6 6 7 "Oops"
call :addeh TryFaultWithout_impl %__C_EH_FAULT% 0 3 3 3
call :addeh TryFaultWith_impl %__C_EH_FAULT% 0 3 3 3
call :addeh TryFaultWith_impl %__C_EH_CATCH% 0 6 6 6 "Oops"
call :addeh TryFinallyFail_impl %__C_EH_FINALLY% 2 3 5 4
call :addeh TryFinallyFail_impl %__C_EH_CATCH% 0 10 10 3 "Oops"
call :addeh Rethrow_impl %__C_EH_CATCH% 2 3 5 3 "Oops"
call :addeh Rethrow_impl %__C_EH_CATCH% 0 8 8 3 "Oops"
call :addeh Filter_impl %__C_EH_FILTER% 0 3 11 5 3

The fragment above is from a sample file called “ex.bil” (unoptimized batch libraries are .bil, optimized ones are .lib – ultimately there should be some kind of “ngen” process code-named BatMan to make this translation) and sets up protected blocks of a given type. E.g. on the first line, lines 0-4 (start from 0, length 5) in TryFinally_impl have a corresponding finally block that runs from lines 5-7 (start from 5, length 3). So, if an exception occurs, the BLR has all the information it needs to find exception handlers. In the build I’ve extracted this info from, exceptions are simply strings (e.g. “Oops”) but ultimately they’ll become arbitrary objects as is the case in the CLR.

Exception handling is quite a bit of art (a few 100 lines of batch file), required to handle stack unwinds (we only have a “fake” stack of our own, no OS support at all). So, is there a runtime stack? Sure there is. And even a symbolic debugger (:o):

So, now we’ve set a (symbolic!) breakpoint, we can let it go and ultimately it will break into the debugger:

Notice how locals have a name. That’s because our samples.bat file has a samples.bdb (batch debug database, as in PDB) next to it:

:__init_bdb
set __sym_sample_prime_loc0=int i
set __sym_sample_prime_loc1=bool prime
set __sym_sample_prime_loc2=int j
set __sym_sample_fac_rec_arg0=int n
goto :eof

Actually, the debugger is just a nested command prompt that has access to the whole environment, so if I run “set” I can investigate the runtime data structures (which are just a bunch of environment variables). E.g. here’s our stack:

Here you can see the various stack frames, starting with __mt_main (the method table entry for main, encoding the number (and type) of the parameters, pointers to other tables like exception handling structures, etc). __stk3 for instance contains the program counter within the frame (i.e. we’re at line :main_302 currently). I leave it to a psychic debugging exercise for the reader to find out about the location for incoming arguments and locals given that we’re calculating fac(5).

Finally, let’s show what happens if an exception got unhandled:

Again, a BDB file was used to figure out symbolic information.

But enough about the BLR for now. I’ll blog more about it (possibly sharing out some builds if I’m satisfied about their stability – warning upfront: performance is not a consideration at all in this project :-)), covering topics like:

  • The BIL instruction set.
  • The BLR runtime stack.
  • Encoding of metadata.
  • Exception handling.
  • Garbage collection (currently work in progress).
  • (Cooperative) threading (also work in progress).
  • x/Invoke (P = PowerShell, B = Batch, W = Windows Scripting Host) (more work in progress).
  • Much more.

Just to emphasize, the BLR does not have a single line of code in a language other than batch script.

 

#2 – MAML

MAML stands for the “Method Application Markup Language”, where application does not stand for the synonym of “program” but for “beta-reduction” from the lambda calculus. In other words, it’s a way to write method applications in a markup format. This project actually entered my head when I was trying to distribute LINQ queries (based on expression trees) over multiple machines:

from x in sharepoint
where x.Bar < 123
join y in sql on x.Id equals y.Id 
where y.Foo > 100
select new { x.Bar, y.Foo }

This query could travel to a web service closer to the SharePoint and SQL machines, execute the Where methods over there (through the respective IQueryable LINQ providers) and join the results before traveling back to the client. However, to be able to do this, lots of info about the sources (actually whole IQueryable<T> objects) and the query operators applied to them needs to travel to the web service. This problem is not generally solvable without making everything serializable, but we can do better than that. Besides the source, all we’re sending over to the server is a set of operations that can be represented using XML, where each element corresponds to an operator. Let’s simplify a bit:

from x in y
where x.Bar < 123
select x.Foo

becomes

<l:Select>
   <l:Where>
      <m:Const>y</m:Const>
      <m:Lambda>
         <m:Params>
            <m:Param Name=”x” />
         </m:Params>
         <m:Body>
            <m:Lt>
               <m:Member>
                  <m:ParamRef Name=”x” />
                  <m:Property Name=”Bar” />
               </m:Member>
               <m:Const Value=”123” Type=”{x:Type int}” />
            </m:Lt>
         </m:Body>
      </m:Lambda>
   </l:Where>
   <m:Lambda>
      <m:Params>
         <m:Param Name=”x” />
      </m:Params>
      <m:Body>
         <m:Member>
            <m:ParamRef Name=”x” />
            <m:Property Name=”Foo” />
         </m:Member>
      </m:Body>
   </m:Lambda>
</l:Select>

This feels a lot like SharePoint’s CAML, but it’s generalized in that schemas denote the set of methods to import (e.g. “l” above stands for LINQ). In practice that corresponds to a CLR namespace. The first argument to a method call acts as the “this” pointer, which can lead to either an instance method or an extension method being called. The requirement in the case above is that the source should somehow be serializable (but in case of a LINQ provider, often some information like a connection string or URL suffices). Ultimately, the MAML fragment is turned into executable code in the form of a delegate to a piece of LCG (lightweight code-gen) code, generated by the MAML compiler (leveraging System.Linq.Expressions where possible).

Below is a fragment to do string manipulation:

<s:Substring>
   <s:ToLower>
      <m:Const Value=”Bart” Type=”{x:Type string}” />
   </s:ToLower>
   <m:Const Value=”2”>
</s:Substring>

Sometimes types can be inferred, as in the case above the first parameter to Substring requires an integer, hence we can omit the type information on the m:Const tag. Furthermore, there’s support to abbreviate the expression syntax considerably, but in an XML-friendly way. For example, the original fragment can be turned into:

<l:Select>
   <l:Where>
      <m:Const>y</m:Const>
      <m:Lambda>
         x |- x.Bar –lt 123
      </m:Lambda>
   </l:Where>
   <m:Lambda>
      x |- x.Foo
   </m:Lambda>
</l:Select>

Notice how the lambda arrow is written as |- to avoid XML notation issues (=&gt; would become unreadable). Similarly inequality operators have names like lt, le, gt, ge, and logical operators have similar replacements (&& becomes –and; always short-circuiting). For those of you who’re interested about implementation details: the parsing of the expressions is done using fslex and fsyacc (worth a bunch of blog posts by itself) but I want to take a look into MGrammar at some point as well.

All of this is very early work in progress (requiring quite some study of type theory topics), so stay tuned for more information.

 

#3 – OMMLinq

OMML stands for the Office Math Markup Language (see http://blogs.msdn.com/murrays/default.aspx for lots of info of Math in Office). Again we’re in ECMA land, this time ECMA-376. Although OMML is all about presentation of math, there’s lots of great stuff that can be done to make it more operational, in a sense that you’d be able to execute those expressions in some way. For example, wouldn’t it be great to write code for Fourier’s expansion in a presentation-friendly way:

There are quite a few issues to be resolved in order to be able to do this. The first stumble block is the fact the OMML doesn’t capture any semantics. Because of this the OMML content is insufficiently tokenized: things like “a + b” will be part of one “text run” as opposed to a much more desirable (well, for execution purposes that is) tree representation à la: “binary infix operator with left ‘a’ and right ‘b’”. So, that’s one thing I kept myself busy with: extracting OMML fragments and turning them into an expression tree format, capturing much more fine-grained pieces of information. Again fslex and fsyacc were of great help (I really should blog about those some time). But it doesn’t end there (in fact, it just starts there).

The lack of semantics is not a trivial thing to solve; to begin with, we’re missing important clues about the mathematical domain the user is operating in. For instance, does a vertical stack of two letters “n” and “k” in between big parentheses mean a matrix of two rows and one column with elements “n” and “k”, or does it mean we’re looking for the number of combinations of n elements in groups of k (making n and k integer values for sure). That’s precisely what goes wrong with the binomial theorem. Just having type information about n and k obviously does not suffice.

Another (much more mechanical thing to some extent) is to extract unbound variables from the equation and promote them to become parameters of the compiled delegate. In other words, things like Fourier get compiled into a function of one argument x? Maybe not, what about the coefficients an and bn? What about the L? There’s clearly need for an environment in which the formula operators; in essence, those are just other parameters, but of what type (are a and b integer-valued arrays?). And what about infinity symbols in sums (not to mention integrals yet)?

So, where am I with this crazy experiment? OMML turns nicely in a much more granular (domain-specific) expression tree and very basic interpretations of various domains (e.g. executing the binomial one in the domain of integers “mixed in” with combinatorial operators) works out quite well.

All of this is (even more early than #1 and #2) work in progress, but the next project is a nice subset of it, much more complete. (Oh, why is this thing suffixed with “Linq”? Not unsurprisingly, the ultimate destination are LINQ expression trees, or similar beasts.)

 

#4 – MLinq

Matrix LINQ is a symbolic matrix calculator based on LINQ expression trees (once more, as if expression trees are as cool as an invention as sliced bread…). It’s a spin-off from the OMMLinq project, at the same time acting as a great example on other uses of expression trees outside the domain of LINQ. Here’s a sample of its use:

a = Expression.Parameter(typeof(int), "a");
b = Expression.Parameter(typeof(int), "b");
c = Expression.Parameter(typeof(int), "c");
d = Expression.Parameter(typeof(int), "d");

var z = Expression.Constant(0);

MatrixExpression<int> ab = new Expression[2, 2] { { a, z },
                                                  { z, b } };

MatrixExpression<int> cd = new Expression[2, 2] { { z, c },
                                                  { d, z } };

Demo("ab", ab);
Demo("cd", cd);

Demo("-ab", -ab);
Demo("-cd", -cd);

Demo("ab^T", ~ab);
Demo("cd^T", ~cd);

Demo("ab + cd", ab + cd);
Demo("ab x cd", ab * cd);

First we built up two two-dimensional square matrices (just to keep things simple) that contain symbolic values a, b, c and d in various positions, as well as the zero value. Next, we apply different operations to it, like negation, transposition, addition, multiplication. All of this happens in a symbolic fashion, so ultimately we end up we an expression in a, b, c and d that represents the result. Compiling that into a delegate, we can now instantiate e.g. ab + cd for any value of a, b, c and d, without creating intermediate arrays. Obviously, the resulting expression tree to build up the matrices can be transformed in many ways to eliminate common subexpressions, apply optimization tricks, etc.

How does it work? Let’s keep the full discussion for a later time, but here’s the essence of it based on a concrete implementation for a (result-of-a-)multiplication-array:

sealed class ProductMatrixExpression<T> : BinaryMatrixExpression<T>
{
    private int _k;

    internal ProductMatrixExpression(MatrixExpression<T> left, MatrixExpression<T> right)
        : base(MatrixExpressionType.Product, left, right)
    {
        if (left.Columns != right.Rows)
            throw new InvalidOperationException("Dimensions do not line up.");

        Rows = left.Rows;
        Columns = right.Columns;

        _k = left.Columns;
    }

    internal override Expression Retrieve(int i, int j)
    {
        var res = Expression.Multiply(Left.Retrieve(i, 0), Right.Retrieve(0, j));

        for (int k = 1; k < _k; k++)
            res = Expression.Add(res, Expression.Multiply(Left.Retrieve(i, k), Right.Retrieve(k, j)));

        return res;
    }
}

From this, the reader should be able to infer the essentials of the base class, BinaryMatrixExpression<T> (and its own parent, MatrixExpression<T>), as well as the signatures for some operator overloads on MatrixExpression<T>. The essentials are:

  • A matrix of expression trees represents a MatrixExpression
  • Operations on MatrixExpressions are turned into cell-by-cell operations on expression trees.

Let’s illustrate with a simplified sample:

var a = Expression.Parameter(typeof(int), "a");
var b = Expression.Parameter(typeof(int), "b");
var z = Expression.Constant(0);

MatrixExpression<int> ab = new Expression[2, 2] { { a, z },
                                                  { z, b } };

var abpow5 = ab * ab * ab * ab * ab;
Console.WriteLine("Matrix expression");
Console.WriteLine(abpow5);
Console.WriteLine();

var f = Expression.Lambda(abpow5.ToBLOCKED EXPRESSION, a, b);
Console.WriteLine("LINQ expression");
Console.WriteLine(f);
Console.WriteLine();

var ctor = (Func<int, int, int[][]>)f.Compile();

ctor(1, 2).Print();
ctor(2, 3).Print();
ctor(3, 2).Print();
ctor(2, 1).Print();

Turning this into execution yields the following:

Ignore all the redundant zeroes; I didn’t run the optimizer (work in progress :-)) on it. Key to all of this, is that we didn’t create any intermediate arrays in memory (no arrays holding the values of ab^2, ab^3, ab^4). Now, the sky is the limit with this: any expression tree can go inside a matrix cell (as long as it’s sound in the type dimension); I’ll leave the rest to your imagination (there’s a reason this is called “MLinq” other than the use of expression trees in a namespace that coincidentally is called System.Linq.BLOCKED EXPRESSION.

 

#5+ – Still secret

Oh the suspense :-).

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

More Posts « Previous page