For my most recent batch of work on MetaSharp I have been working on a completely dynamic version of the Grammar grammar. The reason I’ve been working on it is that I want to start working UI portions of the tool and in order to do that I needed a way to be able to dynamically compile grammars and run them.

What’s interesting is that thus far the Grammar language has been static, meaning you compile it at build-time and it results in a class that inherits from something using the standard .net Type system. So doing things dynamically is tricky because one of my goals was to still be able to “inherit” from a grammar without creating any new .net types. I managed to get this working. This has been a very interesting discovery process for me and I think it has really given me a few revelations about dynamism in type system, I’ll try to share a few of them here.

• The only difference between dynamic and static is simply when you compile; during run-time or before run-time.
• A dynamic language is simply expression trees + custom Type system.
• Your Type system can be anything, it doesn’t need to actually be classes and structs, etc.

Here is an example of some unit tests I have been writing to verify certain functionality, which should hopefully give you a sampling of what it looks like to do pattern matching dynamically as well as some of the basics of MetaSharp.

Simple ‘And’ rule test

This rule says ‘a’ AND ‘b’. The CompileRule is actually adding the extra namespace and grammar declaration stuff automatically and compiling that grammar into a DynamicParser object and is returned as an IParser. Calling parse actually returns an object of Type dynamic but I have an explicit cast below as well.

[Test]
public void AndMatchTest()
{
    var dynamicParser = DynamicParser.CompileRule("'a' 'b'");

    var result = (dynamic)dynamicParser.Parse("ab");
    Assert.AreEqual('a', (char)result[0]);
    Assert.AreEqual('b', (char)result[1]);
}

Value projections

Here I’m projecting an actual double, not a string representation of a double.

[Test]
public void DoubleProjectionTest()
{
    var dynamicParser = DynamicParser.CompileRule("default -> 7.11");
    var result = (dynamic)dynamicParser.Parse("");
    Assert.AreEqual(7.11, (double)result);
}

Dynamic projections

This projection is returning a DynamicNode object. The Identifier is used instead of the Type Name. Properties can be dynamically added. This also has a variable assignment on the left hand side “a:” lets you use the a variable on the right hand side.

[Test]
public void CharacterMatchObjectProjectionTest()
{
    var dynamicParser = DynamicParser.CompileRule("a:'a' -> Test { Value = a }");
    var result = (dynamic)dynamicParser.Parse("a");
    Assert.AreEqual("Test", result.Identifier);
    Assert.AreEqual('a', (char)result.Value);
}

Matching multiple items

+ means One Or More. Here we’re matching an arbitrary number of a’s. This would fail if there were 0 a’s though.

[Test]
public void OneOrMoreMatchTest()
{
    var dynamicParser = DynamicParser.CompileRule("'a'+");
    var result = (dynamic)dynamicParser.Parse("a");
    Assert.AreEqual('a', (char)result[0]);

    result = dynamicParser.Parse("aaa");
    Assert.AreEqual('a', (char)result[0]);
    Assert.AreEqual('a', (char)result[1]);
    Assert.AreEqual('a', (char)result[2]);
}

Calling custom extensions

AsString() is actually a static method defined on Common. For now I am only searching for extensions in a very explicit whitelist. This will probably change into an Assembly whitelist eventually though.

[Test]
public void ExtensionReferenceProjectionTest()
{
    var dynamicParser = DynamicParser.CompileRule(
        @"'a' -> ""abc"".AsString()",
        typeof(MetaSharp.Transformation.Extensions.Common));

    var result = (dynamic)dynamicParser.Parse("a");
    Assert.AreEqual("abc", (string)result);
}

Static inheritance from a dynamic grammar

This one is a little crazy. Here we are actually doing the full grammar code not the abbreviated version and we are inheriting (that’s what the ‘<’ means) from BasicParser which is a static Type as you can tell by the white list. In grammar inheritance you can optionally add a Main rule which will be added to a queue of processors for the specified input. In this case BasicParser inherits from BasicInterleave which inherits from BasicTokenizer. So the input stream will be tokenized, interleaved then parsed by this dynamic grammar. Each step parses the output of the previous step. If you don’t have a Main rule you will be skipped but you can still provide rules for inheriting grammars to reference as well as override rules of grammars you are inheriting from.

[Test]
public void GrammarStaticInheritanceTest()
{
    var grammar = new GrammarGrammar();
    var unit = (GrammarUnitNode)grammar.Parse(@"
        namespace N: 
            import MetaSharp.Transformation.Extensions;
            import MetaSharp.Transformation.Parsing.Common;

            grammar X < BasicParser:
                Main = a:(""a"" ""b"" ""c"") -> a.Flatten();
            end
        end");

    var parser = unit.DynamicCompile(
        "N.X",
        typeof(MetaSharp.Transformation.Extensions.Common),
        typeof(MetaSharp.Transformation.Parsing.Common.BasicParser));

    var result = (dynamic)parser.Parse("a b c");
    Assert.AreEqual("a", (string)result[0]);
    Assert.AreEqual("b", (string)result[1]);
    Assert.AreEqual("c", (string)result[2]);
}

Dynamic inheritance

This is essentially the same thing except in this case one of the dynamic grammars is inheriting from another dynamic grammar. You can create both and use them both.

[Test]
public void GrammarDynamicInheritanceDualNamespaceTest()
{
    var grammar = new GrammarGrammar();
    var unit = (GrammarUnitNode)grammar.Parse(@"
        namespace A: 
            grammar X:
                Main = 'a';
            end
        end
        namespace B:
            import A;

            grammar Y < X:
            end
        end");

    var parser = unit.DynamicCompile("A.X");
    var result = (dynamic)parser.Parse("a");
    Assert.AreEqual('a', (char)result);

    parser = unit.DynamicCompile("B.Y");
    result = (dynamic)parser.Parse("a");
    Assert.AreEqual('a', (char)result);
}

Rule references and parameterized rules

You can also create as many rules as you want and reference them, including parameterized rules like below.

[Test]
public void ParameterizedRuleReferenceTest()
{
    var parser = DynamicParser.Compile(
        @"namespace N: 
            import MetaSharp.Transformation.Extensions;
            grammar X:
                Main = (Expr('a'..'z') | ' ')+;
                Expr(a) = str:a+ -> str.AsString();
            end
        end",
        "N.X",
        typeof(MetaSharp.Transformation.Extensions.Common));

    var result = (dynamic)parser.Parse("hello world");
    Assert.AreEqual("hello", (string)result[0]);
    Assert.AreEqual(' ', (char)result[1]);
    Assert.AreEqual("world", (string)result[2]);
}

Direct left recursion

Direct left recursion is when, on the left hand side of a rule body you are referencing itself directly. This results in recursion but is completely solvable by PatternMatching grammars. Below the Expr rule is an example of DLR because it is referencing itself. DLR is a useful way to solve problems of forward lookup, such as binary expressions like below.

DLR is direct as opposed to indirect left recursion, where you reference a Rule which then references that Rule back directly. Indirect Left Recursion is also a solvable problem but I was not able to solve it for situations of cases of multiple nested indirect DLR. Also it results in a very confusing grammar which has diminishing returns in value. For now you get errors in the cases of indirect left recursion.

[Test]
public void LeftRecursiveReferenceTest()
{
    var parser = DynamicParser.Compile(
        @"namespace N: 
            import MetaSharp.Transformation.Extensions;
            grammar X:
                Main = Expr;
                Expr = l:Expr '+' r:Expr -> Binary { Left = l, Right = r, Operator = '+' }
                        | n:Num -> n.ToNumber();
                Num = '0'..'9';
            end
        end",
        "N.X",
        typeof(MetaSharp.Transformation.Extensions.Common));

    var result = (dynamic)parser.Parse("1+2+3+4");
    Assert.AreEqual("Binary", result.Identifier);
    Assert.AreEqual("Binary", result.Right.Identifier);
    Assert.AreEqual("Binary", result.Right.Right.Identifier);
    Assert.AreEqual(1, (int)result.Left);
    Assert.AreEqual(2, (int)result.Right.Left);
    Assert.AreEqual(3, (int)result.Right.Right.Left);
    Assert.AreEqual(4, (int)result.Right.Right.Right);
}

Overriding rules

Y is overriding the Expr rule to project true instead of false. Parsing using Y will now result in a new result compared to parsing with X. You can override rules on static grammars as well.

[Test]
public void RuleDynamicOverrideDynamicTest()
{
    var unit = DynamicParser.Parse(
        @"namespace N:
            grammar X:
                Main = Expr;
                Expr = any -> false;
            end
            grammar Y < X:
                override Expr = any -> true;
            end
        end");

    var parser = unit.DynamicCompile("N.X");
    var result = parser.Parse("1");
    Assert.IsFalse((bool)result);

    parser = unit.DynamicCompile("N.Y");
    result = parser.Parse("1");
    Assert.IsTrue((bool)result);
}

 

There is more too of course but this is probably too long already, it’s also not 100% complete yet. I will be considering it complete (sans bugs) when I can dynamically compile the Grammar grammar using itself! Next up:

• Silverlight
• VS integration
• Polish and an actual release

Previously in MetaSharp I had a custom Templating engine for textual transformations. It was a custom grammar and was pretty simple. It worked well and all was good but it was becoming a maintenance burden for me and, I think, turned people off to MetaSharp more than attracted them. So I decided to spend a little time and try to integrate T4 into my templating library as a replacement.

It was actually reasonably simple to accomplish. The hardest part, of course, was working with AppDomains. T4 is a dynamic tool living in a static world and as such it requires an AppDomain to do its magic so it can all be unloaded without a trace. Because of this T4 isn’t very amenable to input. Most examples I found online start with firing up your template then beginning by reading a file or creating a class that connects to a database. In my case I have already have my metadata and would like to pass it into a T4 template but it’s in memory only. The first thing you have to do is make your model Serializable.

Next you need to know about the “inherits” and the “hostspecific” attributes. You add something like this to the top of your template:

<#@ template language="C#" inherits="SongMetaTemplate" hostspecific="true" debug="true" #>

This is for my Song sample application. I then create a SongMetaTemplate class that knows how to cast the model into a Song enumeration.

public abstract class SongMetaTemplate : MetaTemplate
{
    public IEnumerable<Song> Songs
    {
        get { return ((IEnumerable<INode>)this.Model).Cast<Song>(); }
    }
}

Adding a hostspecific attribute to the template causes the template class that inherits from the SongMetaTemplate to also have a Host property which gets loaded up with the Model provided by my pipeline. The MetaTemplate knows how to fetch that host model for me.

public abstract class MetaTemplate : TextTransformation
{
    private object model = null;

    protected object Model
    {
        get
        {
            if (model == null)
            {
                dynamic metame = this;
                var metaHost = metame.Host as MetaSharpTextTemplatingHost;
                if (metaHost != null)
                    this.model = metaHost.Model;
            }

            return model;
        }
    }

    public override string TransformText()
    {
        return this.GenerationEnvironment.ToString();
    }
}

And that’s it! My template can now get a hold of the Song AST parsed from the DSL earlier in the pipeline. Here is an example template in its entirety:

<#@ template language="C#" inherits="SongMetaTemplate" hostspecific="true" debug="true" #>
<#@ assembly name="DynamicSongBuilder" #>
<#@ import namespace="DynamicSongBuilder" #>

<# foreach(var song in this.Songs) { #>
    <# foreach(var b in song.Bars) { #>
        <# foreach(var n in b.Notes) { #>
            play(<#=song.Duration #>, "<#=n.Key #>", <#=n.Octave #>);
        <# }
    }
} #>

The template code is C# but the code generated is actually for my own custom language. In this case it’s parsed into Linq expressions and compiled into a delegate using a context object with a play method. It’s then executed dynamically and also collected by the GC when dereferenced. I plan to replace the custom language also, but its proving difficult without a reasonable parser to replace it.

I have created a small routine that allows you to use the IronPython runtime to create dynamic Types without requiring you to write any Python code.

The normal use case for IronPython in C# requires you to provide the IronPython runtime with some source code files, which will essentially eval and return to you a context which you can interact with dynamically. With some help on the forums I was able to find a way to provide an IronPython AST to the runtime instead of source code. This will be very useful for MetaSharp, since I already have a lot of mechanisms for creating an AST I will only need to simply create a transformer that will change an existing AST into IronPython AST and you can suddenly compile any DSL into arbitrarily complex object hierarchies at runtime.

One of the reasons for this is that I want to create a language workbench tool, where you can experiment with your transformations dynamically without having to recompile in the traditional sense. Also, it just gives you more options at runtime. This should be very handy.

Here is an example of what I’m talking about. My example code is very simple, create a class that implements a simple .net interface then create an instance of that class and call it’s method. Here is the actual python version:

#sample.py
from ConsoleApplication4 import IExample

class Example(IExample):
    def Do(self):
        return "hello python"

Executing and calling this at runtime in C# is quite easy to do out of the box actually.

var runtime = Python.CreateRuntime();
runtime.LoadAssembly(typeof(IExample).Assembly);
dynamic python = runtime.UseFile("sample.py");
            
var example = (IExample)python.Example();
Console.WriteLine(example.Do());

The rub here though is that you need that python source file laying around somewhere. Or you could generate code, put it in a temp file and use that instead but nonetheless, the creation of the dynamic object is done by creating python code only. My problem was to figure out how to bypass most of the parsing semantics and to provide an AST directly to the runtime instead of code files. The AST could be created by a MetaSharp transform step.

So instead you can now do this:

var runtime = Python.CreateRuntime();
runtime.LoadAssembly(typeof(IExample).Assembly);

var iexampleImport = typeof(IExample).Import();

var classDefinition = Dlr.Class(
    "Example",
    iexampleImport.ToEnumerable(),
    Dlr.Function(
        "Do",
        Dlr.Self().ToEnumerable(),
        "hello python!".AsConstant().Return()));

dynamic python = runtime.Compile(
    iexampleImport,
    classDefinition);

var example = (IExample)python.Example();
Console.WriteLine(example.Do());

I won’t go into all of the extension methods I created (see link to source at the end) but suffice it to say that the Dlr.Class method is creating a ClassDefinition object. Passing these into the runtime.Compile method is where all of the magic happens.

Figuring out what to do in the Compile extension method was the real hard part. It’s not well documented and some of the side effects are downright bizarre, clearly the API was not intended to be (mis)used in this way.

Fortunately for you, all you have to do is download the file below and you’re off creating dynamic Types using the DLR!