New meta# nuget package published

I uploaded a new meta# NuGet package:

PS> Install-Package metasharp

It only has pattern matching api’s in this package now. To make patterns, just start with MetaSharp.Transformation.Pattern and all of the pattern factories are static methods from there. A simple example:

var p = Pattern.OneOrMore(Pattern.Range(‘a’, ‘z’));
var m = Pattern.Match(p, “metasharp”);
if (m.Matched) { … }

 

This package is .net 2.0 now too, so you can use it in more places (such as Unity3d). I’m planning on putting the actual grammars and build tasks etc into other packages so that the main package remains very portable. Also I changed it so that ‘p’ in the above scenario is a Pattern ast object instead of a Delegate. Which means that you could theoretically visit the pattern and transform it, itself. Also tracing produced objects will give you the pattern that produced it as well as the metadata.

The most major improvement of the API from before is the fact that you don’t have to implement INode on the objects you produce. Before everything had to be an INode and so you would have to do some awkward wrapping / unwrapping if your tree didn’t implement INode but now it just works with any plain old CRL object. Also it uses DynamicInvoke on productions so you can just bind them directly to any method with parameters of any type:

var p = Pattern.Production(
    Pattern.Variable(“x”, Pattern.Any()),
    (int x) => x + 1); // throws if the value consumed isn’t an int

 

I hope that makes sense. My first attempt made use of generics to attempt to flow static typing through the productions (which is definitely possible) but the insufficient type inference and support for monads in C# caused the complexity of the patterns to be unbearable. I found that if you use object and DynamicInvoke instead, you get similar results with reasonable complexity. The end result is that this api isn’t strictly monadic, since there is no Bind or Select/SelectMany. But it is monadic in spirit, all of the objects involved in the pattern matching operation are immutable and are safely parallelizable, except possibly your custom productions.

I’m pleased with the performance so far, the Or pattern executes each branch in parallel. I haven’t really stressed it that far yet but my 210 unit tests take about .45 seconds to run total so that seems pretty good. I want to create a Reflection.Emit visitor so I can get even better performance for rules but, unfortunately, that API isn’t available on all platforms (e.g. WinRT) so I’m not sure how best to do that.

The next big step is to create a new package with a C# grammar + roslyn transformer. Before it was a 1-off language. This time I plan to redo that work except as C# so that it is more appealing to users. I also want to change the grammar language to not be inheritance based, but compositional. This will require a little experimentation but I think it will make it a lot more appealing. The lack of extensibility in Roslyn is a real bummer because as far as I can tell there is no way for me to easily extend Roslyn to add pattern syntax to C# that way. The result is that I can leverage roslyn to generate assemblies from my AST but I still have to implement my own C# grammar if I want to extend it. A bummer but not harder than what I did before.

If you get a chance to try it out, I would appreciate feedback on the Pattern api though 🙂

Enjoy!

MELT at the University of Minnesota

I was invited to the University of Minnesota today for a brief talk by Eric Van Wyk who presented over lunch about some of his research on extensible language tools. I was very surprised to find out that the research he has been doing is very similar to what I have been doing with meta#, they are working on ways to compose language extensions and create domain specific languages on top of general purpose languages. The details are different and some of them are very interesting and require further investigation but I am surprised by how much is not different.

Also, similar to the PPL and maybe even more so, he has a treasure trove of research papers on DSLs that I will have to read through.

Martin Fowlers State Machine in meta#

Martin Fowlers State Machine is quickly becoming the 99 bottles of beer on the wall for DSLs. So I implemented it in meta# and will be using it in my presentation at the next Twin Cities Code Camp.

The state machine sample project consists of two grammars, a parser and a transformer. It also has a state machine AST (semantic model) and a state machine runtime. The accompanying sample app uses an almost identical syntax as the one Fowler has in his book and is driven using a very simple console app.

StateMachineParser.g

namespace StateMachineCompiler:
    import MetaSharp.Transformation;
    import MetaSharp.Transformation.Lang;
    import StateMachineCompiler.Ast;
    import System;
    import System.CodeDom;
    import System.Linq;
    import System.Reflection;
    import System.Collections.Generic;

    grammar StateMachineParser < LangParser:

        override TypeDeclaration 
            = StateMachineDeclaration
            | super;

        StateMachineDeclaration
            =    StateMachine name:Identifier BlockBegin
                e:EventsDeclaration?
                r:ResetsDeclaration?
                c:CommandsDeclaration?
                s:StateDeclarations*
                error until BlockEnd -> {
                StateMachineDeclaration sm = new StateMachineDeclaration();
                sm.Name = name as string;
                sm.Events = e.Cast<EventDeclaration>();
                sm.Resets = r.Cast<ResetDeclaration>();
                sm.Commands = c.Cast<CommandDeclaration>();
                sm.States = s.Cast<StateDeclaration>();
                return sm;
            }

        EventsDeclaration
            =    Events BlockBegin
                e:EventMember*
                error until BlockEnd
                -> e;

        EventMember = name:Identifier code:Identifier StatementEnd -> {
                EventDeclaration e = new EventDeclaration();
                e.Name = name as string;
                e.Code = code as string;
                return e;
            }

        ResetsDeclaration
            =    Resets BlockBegin
                r:ResetMember*
                error until BlockEnd
                -> r;

        ResetMember = name:Identifier StatementEnd -> {
            ResetDeclaration r = new ResetDeclaration();
            r.Name = name as string;
            return r;
        }
            
        CommandsDeclaration
            =    Commands BlockBegin
                c:CommandMember*
                error until BlockEnd 
                -> c;

        CommandMember = name:Identifier code:Identifier StatementEnd -> {
            CommandDeclaration c = new CommandDeclaration();
            c.Name = name as string;
            c.Code = code as string;
            return c;
        }
            
        StateDeclarations
            =    State name:Identifier BlockBegin
                a:ActionsDeclaration?
                t:TransitionMember*
                error until BlockEnd -> {
                StateDeclaration s = new StateDeclaration();
                s.Name = name as string;
                s.Transitions = t.Cast<TransitionDeclaration>();
                if(a != null):
                    List<string> actions = new List<string>();
                    for(Node n in a.Cast<Node>()):
                        actions.Add(Node.Unwrap(n) as string);
                    end
                    s.Actions = actions;
                end
                return s;
            }

        ActionsDeclaration = Actions "{" a:List(Identifier, ",") "}" StatementEnd -> a;

        TransitionMember = e:Identifier "=>" s:Identifier StatementEnd -> {
            TransitionDeclaration t = new TransitionDeclaration();
            t.EventName = e as string;
            t.StateName = s as string;
            return t;
        }

        [Keyword] StateMachine = "statemachine";
        [Keyword] Events = "events";
        [Keyword] Resets = "resets";
        [Keyword] Commands = "commands";
        [Keyword] State = "state";
        [Keyword] Actions = "actions";

        override CustomTokens
            = '=' '>'
            | super;
    end
end

The parser inherits from LangParser and extends Fowlers DSL by being both inside of a namespace and also wrapped in a statemachine declaration block. Also I changed the block named “resetEvents” to just be “resets” which seemed more consistent to me.

StateMachineTransformer.g

namespace StateMachineCompiler:
    import MetaSharp.Transformation;
    import MetaSharp.Transformation.Lang.Ast;
    import StateMachineCompiler.Ast;
    import System;
    import System.CodeDom;
    import System.Linq;
    import System.Collections.Generic;

    grammar StateMachineTransformer < StateMachineParser:
        Main = UnitVisitor;

        UnitVisitor = Unit { Namespaces = [NamespaceVisitor*] };

        NamespaceVisitor = Namespace { Types = [TypeVisitor*] };

        TypeVisitor
            = StateMachineVisitor
            | CodeTypeDeclaration { };

        StateMachineVisitor = smd:StateMachineDeclaration {
                e:Events = [EventVisitor*],
                r:Resets = [ResetVisitor*],
                c:Commands = [CommandVisitor*],
                s:States = [StateVisitor*] -> Parser.Flatten(match)
            } -> {
                StateMachineDeclaration d = smd as StateMachineDeclaration;
                d.BaseTypes.Add(typeof(StateMachineBuilder));
                Constructor cons = new Constructor();
                cons.Attributes = MemberAttributes.Public;
                cons.Parameters.Add(new ParameterDeclarationExpression(typeof(CommandChannel), "commandChannel"));
                cons.BaseConstructorArgs.Add(new ReferenceExpression("commandChannel"));
                d.Members.Add(cons);

                Method createMachineMethod = new Method();
                createMachineMethod.Name = "CreateMachine";
                createMachineMethod.Attributes = MemberAttributes.Family | MemberAttributes.Override;
                createMachineMethod.ReturnType = new TypeReference(typeof(StateMachine));
                d.Members.Add(createMachineMethod);

                createMachineMethod.Statements.AddRange(e.Cast<CodeStatement>().ToArray());
                createMachineMethod.Statements.AddRange(c.Cast<CodeStatement>().ToArray());
                createMachineMethod.Statements.AddRange(s.Cast<CodeStatement>().OfType<VariableDeclarationStatement>().ToArray());

                StateDeclaration first = d.States.First();
                VariableDeclarationStatement v = new VariableDeclarationStatement(
                    typeof(StateMachine),
                    "machine",
                    new NewExpression(
                        typeof(StateMachine),
                        new ReferenceExpression("state_" + first.Name)));

                createMachineMethod.Statements.Add(v);
                createMachineMethod.Statements.AddRange(r.Cast<CodeStatement>().ToArray());
                createMachineMethod.Statements.AddRange(s.Cast<CodeStatement>().OfType<ExpressionStatement>().ToArray());

                ReturnStatement ret = new ReturnStatement(new ReferenceExpression("machine"));
                createMachineMethod.Statements.Add(ret);

                return d;
            }

        EventVisitor = EventDeclaration { } -> {
            EventDeclaration e = match as EventDeclaration;
            VariableDeclarationStatement v = new VariableDeclarationStatement(
                typeof(Event),
                "event_" + e.Name,
                new NewExpression(
                    typeof(Event),
                    new PrimitiveExpression(e.Name), 
                    new PrimitiveExpression(e.Code)));

            return v;
        }

        ResetVisitor = ResetDeclaration { } -> {
            ResetDeclaration r = match as ResetDeclaration;
            MethodInvokeExpression addResetEvent = new MethodInvokeExpression(
                new ReferenceExpression("machine"),
                "AddResetEvents",
                new ReferenceExpression("event_" + r.Name));

            return new ExpressionStatement(addResetEvent);
        }

        CommandVisitor = CommandDeclaration { } -> {
            CommandDeclaration c = match as CommandDeclaration;
            VariableDeclarationStatement v = new VariableDeclarationStatement(
                typeof(Command),
                "command_" + c.Name,
                new NewExpression(
                    typeof(Command),
                    new PrimitiveExpression(c.Name), 
                    new PrimitiveExpression(c.Code)));

            return v;
        }

        StateVisitor = StateDeclaration { } -> {
            StateDeclaration s = match as StateDeclaration;
            Nodes statements = new Nodes();
            List<CodeExpression> parameters = new List<CodeExpression>();
            parameters.Add(new PrimitiveExpression(s.Name));
            for(string a in s.Actions):
                parameters.Add(new ReferenceExpression("command_" + a));
            end

            statements.Add(new VariableDeclarationStatement(
                typeof(State),
                "state_" + s.Name,
                new NewExpression(
                    typeof(State),
                    parameters.ToArray())));

            for(TransitionDeclaration td in s.Transitions):
                statements.Add(new ExpressionStatement(
                    new MethodInvokeExpression(
                        new ReferenceExpression("state_" + s.Name),
                        "AddTransition",
                        new ReferenceExpression("event_" + td.EventName),
                        new ReferenceExpression("state_" + td.StateName))));
            end

            return statements;
        }

    end
end

This grammar inherits from StateMachineParser and therefore it receives the parsers output as input. It is an example of implementing a visitor pattern as a meta# grammar. It visits the state machine AST nodes and expands them into code objects, which a subsequent step uses to generate code.

Here is the modified ubiquitous state machine DSL, MissGrants.sm

namespace App:

    statemachine MissGrants:

        events:
            doorClosed D1CL;
            drawerOpened D20P;
            lightOn L10N;
            doorOpened D10P;
            panelClosed PNCL;
        end

        resets:
            doorOpened;
        end

        commands:
            unlockPanel PNUL;
            lockPanel PNLK;
            lockDoor D1LK;
            unlockDoor D1UL;
        end

        state idle:
            actions {unlockDoor, lockPanel};
            doorClosed => active;
        end

        state active:
            drawerOpened => waitingForLight;
            lightOn => waitingForDrawer;
        end

        state waitingForLight:
            lightOn => unlockedPanel;
        end

        state waitingForDrawer:
            drawerOpened => unlockedPanel;
        end

        state unlockedPanel:
            actions {unlockPanel, lockDoor};
            panelClosed => idle;
        end

    end

end

Here is the code generated by the meta# transformers…

//------------------------------------------------------------------------------
// <auto-generated>
//     This code was generated by a tool.
//     Runtime Version:4.0.30319.237
//
//     Changes to this file may cause incorrect behavior and will be lost if
//     the code is regenerated.
// </auto-generated>
//------------------------------------------------------------------------------

namespace App
{
    
    public class MissGrants : StateMachineCompiler.StateMachineBuilder
    {
        public MissGrants(StateMachineCompiler.CommandChannel commandChannel) : 
                base(commandChannel)
        {
        }
        protected override StateMachineCompiler.StateMachine CreateMachine()
        {
            StateMachineCompiler.Event event_doorClosed = new StateMachineCompiler.Event("doorClosed", "D1CL");
            StateMachineCompiler.Event event_drawerOpened = new StateMachineCompiler.Event("drawerOpened", "D20P");
            StateMachineCompiler.Event event_lightOn = new StateMachineCompiler.Event("lightOn", "L10N");
            StateMachineCompiler.Event event_doorOpened = new StateMachineCompiler.Event("doorOpened", "D10P");
            StateMachineCompiler.Event event_panelClosed = new StateMachineCompiler.Event("panelClosed", "PNCL");
            StateMachineCompiler.Command command_unlockPanel = new StateMachineCompiler.Command("unlockPanel", "PNUL");
            StateMachineCompiler.Command command_lockPanel = new StateMachineCompiler.Command("lockPanel", "PNLK");
            StateMachineCompiler.Command command_lockDoor = new StateMachineCompiler.Command("lockDoor", "D1LK");
            StateMachineCompiler.Command command_unlockDoor = new StateMachineCompiler.Command("unlockDoor", "D1UL");
            StateMachineCompiler.State state_idle = new StateMachineCompiler.State("idle", command_unlockDoor, command_lockPanel);
            StateMachineCompiler.State state_active = new StateMachineCompiler.State("active");
            StateMachineCompiler.State state_waitingForLight = new StateMachineCompiler.State("waitingForLight");
            StateMachineCompiler.State state_waitingForDrawer = new StateMachineCompiler.State("waitingForDrawer");
            StateMachineCompiler.State state_unlockedPanel = new StateMachineCompiler.State("unlockedPanel", command_unlockPanel, command_lockDoor);
            StateMachineCompiler.StateMachine machine = new StateMachineCompiler.StateMachine(state_idle);
            machine.AddResetEvents(event_doorOpened);
            state_idle.AddTransition(event_doorClosed, state_active);
            state_active.AddTransition(event_drawerOpened, state_waitingForLight);
            state_active.AddTransition(event_lightOn, state_waitingForDrawer);
            state_waitingForLight.AddTransition(event_lightOn, state_unlockedPanel);
            state_waitingForDrawer.AddTransition(event_drawerOpened, state_unlockedPanel);
            state_unlockedPanel.AddTransition(event_panelClosed, state_idle);
            return machine;
        }
    }
}

And finally the console app to drive and simulate the state machine, Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using StateMachineCompiler;

namespace App
{
    class Program
    {
        static void Main(string[] args)
        {
            CommandChannel channel = new CommandChannel(a => Console.WriteLine("Action: " + a));
            var builder = new MissGrants(channel);

            bool done = false;
            while (!done)
            {
                Console.WriteLine("State: " + builder.CurrentState);
                Console.Write("> ");
                var cmd = Console.ReadLine();
                builder.Handle(cmd);
            }
        }
    }
}

Language Workbench in Visual Studio

image

This is far from polished and complete but here you can see the grammar defined in foo.g being dynamically compiled and used to parse the text in the grammar console. You can see how the [Keyword] attribute is used to generate syntax highlighting in that grammar window also, as well as automatic error generation for the errant ‘!’.

Next up is visualization of the node graph produced by the parse as well as error information. Very promising progress though!

Error until and Error unless

I’ve been working on improving error handling in meta# for the last couple of weeks. Previously there was no support and basically your code would either parse correctly or it would not.

So I cracked open the Purple Dragon book, dug into Martin Fowlers DSL book, asked on the OMeta forums and read about how some other grammar tools do error handling.

It would probably have helped to have someone sit down and show me but I had a real hard time understanding exactly what the various solutions were. But other than not fully getting the specifics I think I got the general idea and was able to add two new error handling semantics to meta#.

Parsing errors basically all boil down to a single type of problem: the thing that is next in the stream is not what you were expecting. I decided that you could look at this problem two different ways. You could either say that something you expect is missing or something you didn’t expect is present.

So I added two new pattern semantics “error unless X” and “error until X”, where X is any pattern.

Error Unless

In the case of “error unless”, that is like saying something you expected is missing. In this case an error will be logged, input from the stream will not be consumed and null will be returned rather than fail. This will let whatever rule that uses these semantics to still project and give you a very specific message and if the following code is well formed the parser could even recover without any additional errors. This is very useful for missing ‘;’ at the end of statements.

image

image

Error Until

For “error until”, it is like saying something you were not expecting is present. In this case all of the input will be consumed until the X pattern is matched. An error will be reported and fail will be returned. This is very good for sync’ing to the next close bracket because it will read all unknown input and treat it as an error.

image

image

LogError

One last way to report errors is just by calling context.LogError(…) from within a projection. Then you can handle more complex cases and log arbitrary error messages. I might have to expand the api for this but here is an example of how I’m using it so far.

image

On Premature Optimization

I have heard the phrase “premature optimization is the root of all evil” many times but have never had a chance to consciously put it to the test before. Meta# has a few critical execution paths where performance is a very big concern and has a large impact on how performant the overall process of parsing goes.

I intentionally ignored all performance concerns up till this point however, choosing to trust in the wisdom that says to avoid premature optimization. I finally got to a point where most of the main features I wanted were in place and I have some very good test coverage (turns out I had 91% test coverage the first time I ran the code coverage tool). So I decided to embark upon a journey of performance optimization.

Before/After
Tests: 662, Failures: 0, Skipped: 1, Time: 32.402 seconds
Tests: 665, Failures: 0, Skipped: 0, Time: 16.977 seconds

I’d say that it was a huge success! The three new tests are actually parsing all of the .g files in meta# again and tracking their performance. Which means that the slowest tests are now run twice and the whole run is taking about half time time it was before.

I can tell you when I first went to look into where to do optimizations I almost panicked. I thought my code was perfect and that the performance flaw was in the design itself, I had a moment of crisis. But there were tons of low hanging fruit ready for optimization.

So I’m officially a believer in avoiding premature optimization at this point. I would include that I relied heavily on an excellent unit test base to prove that my changes still worked and that is a crucial piece to being able to make these types of systemic changes.

Also, I used the excellent TestDriven.NET performance tools to do give me my data. I highly recommend it. You just right click a test and select Run Test -> Performance. It gives you a very detailed report and the ability to find out your slowest calls very quickly. Optimize and try again! A very clean cycle.