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);
            }
        }
    }
}

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

Programming and Scaling

tele-TASK Video: Programming and Scaling.

If you’ve heard me talk about DSLs but just haven’t quite been sold on the idea yet, watch this video. In fact, watch it anyway. Dr. Alan Kay gives a very inspirational and interesting speech about the past, present and future of Computer Science, technological innovation and creativity. The grand finale ties all of his ideas together in a beautiful example of the power of domain specific languages.

I found myself nodding throughout this entire presentation and even though I didn’t know where it was going I could see how it applied to my own personal research in meta#. Thank you Dr. Kay, I may never need to spend my time explaining the why’s of DSLs again, I will simply forward them to this presentation.

Metadata Based Syntax Highlighting

The culmination of many features has finally arrived: syntax highlighting grammars based on metadata!

hilighting1 

This is a screenshot of my prototype language workbench for meta#. In the grammar section you write rules that get combined together into an implicit grammar which is used to parse each of the code blocks below. On the right is the AST of whatever block you have currently selected. This is a basic “hello world” grammar.

Notice the syntax highlighting! Keywords are yellow, identifiers are gray, character and string literals are green and everything else is white.

The thing that’s cool about this is that the editor for each of those blocks actually does not know anything about the grammar of the code it is highlighting. The highlighting information is coming from the metadata of the grammar itself. In fact you can add that same metadata to the grammar you are authoring in order to get highlighting in the code blocks as well.

hilighting2

Here you can see that I have added the [Keyword] attribute onto the ident rule, this attribute is aggregated as metadata and can be harvested by the code editor. It uses that metadata to get information about the original code and add appropriate colors. The code editor is a custom control I am working on that inherits from RichTextEditor in wpf.

This language workbench is still just a prototype but it’s still kind of cool. I have some ideas on how to evolve it that I need to solidify still but it provides a nice playground for me to experiment with features like this.

Language Workbench Competition

I’m actually pretty close to having all of the MetaSharp grammars translated into .g files and Attila is working on the msbuild compiler components. Once we have them both done and merged we will have achieved dogfood status. There are plenty of Grammar and Lang features I want to work on still but the next major feature will be the Language Workbench, or in other words the interactive editor (I want to have some type of grammar REPL for the tclangug presentation I will be giving next month at least).

I just recently learned about the Code Generation Conference and now I am learning that there was also a Language Workbench website and that they sponsored a competition that went along with the conference. The most interesting part of this is the description of what a language workbench should do and how to rate them:

http://www.languageworkbenches.net/LWCTask-1.0.pdf

Which almost reads like a workbench spec! So this is very exciting, I have been thinking about what a MetaSharp workbench should be like and I think that I have a pretty good idea of what the external expectations are now, so this is good.

What’s funny about MetaSharp is that it is designed to solve all of the “Advanced” scenarios but currently doesn’t solve any of the “Basic” scenarios, lol. I’m not sure if that’s a good sign or a bad sign yet…