The Composition Design Pattern

You may have heard the expression “prefer composition over inheritance“.

But what does it really mean? What’s wrong with inheritance? Even the Wikipedia article on composition over inheritance is using classes and inheritance to explain composition. If composition is so much better than inheritance (at least sometimes), then why do we have to explain composition in terms of inheritance? And why do most modern programming languages and platforms support classes and inheritance syntactically but not composition? What would a programming language even look like if it had syntactic support for composition? Furthermore, what even is the design pattern for composition?

Many of the examples you see from cursory searches online simply show one class containing references to others and that’s about it. This kind of overly simple example seems to acknowledge the problem without really explaining the full solution and it’s completely framed in a context of inheritance. Simply introducing classes containing references to other classes doesn’t give us enough information to establish a pattern and it ends up raising more questions than it answers.

One really good example of composition can be found in Unity3D. Composition in Unity3D is a first class concept that runs very deeply into the built-in game engine that drives everything that Unity does. After studying it for a while I would like to use the patterns of composition found in Unity as a basis for our design pattern and our hypothetical programming language.

Aspects of the Composition Pattern

In a compositional system you therefore need at least two kinds of Types:

  • Object
  • Component

The Object in a compositional system is not the same as an Object in an inheritance based system. An Object in a minimal compositional system has the following attributes:

  • It may have a name
  • It may posses child objects
  • It may have a parent object
  • It may contain named components
  • It can send messages to components

A Component has the following attributes:

  • It has a reference to the Object it is contained by
  • It may have data
  • It can handle messages

Simple Example

If we were to design a minimal version of this system (in C#) it may look something like this:

For a more robust example I highly recommend studying Unity3D in detail. However the question I am asking is what would a system like this look like if it was not framed in the context of classes. How would it look if it were to have syntactic support in a language instead of simply implemented as a design pattern in terms of inheritance? I don’t fully know the answer to this question but I have been experimenting with some ideas and would like to have a discussion around them.

The first thing to realize with this system is that instead of designing Objects up front with static definitions like classes you can only instantiate them and you can only design their hierarchy.

Components are more interesting and do have a static definition. They contain state like a class which means they fulfill the OO principle of encapsulation. They may handle messages of any shape which also means they are polymorphic but they are not inheritable in this system. You may be tempted to add inheritance to components at this point but I believe that this is unnecessary and a mistake. The reason for this is that inheritance is basically just another kind of relationship but it is one that has a much higher degree of coupling between objects. There are a variety of reasons why this form of relationship can cause problems. One is the lack of abstraction and thus isolating the unit for test can become very complex and costly. Instead of using inheritance simply break out shared behavior and state into even more, smaller and more focused components.

A composition system like this is actually similar to the DOM you would find in a browser. The primary differences are that in this case it would not be tied specifically to a single domain (e.g. the domain of laying out and rendering documents) and instead of using an event system it uses message passing. In this way composition allows us to be extremely loosely coupled without requiring extra abstractions.

I can imagine systems where, instead of having a component keyword in the language, you compile entire files into components similar to the way you would compile an entire file into a module in a CommonJS system such as node.js. Your main app would essentially setup your starting objects the rest of your files would be Components. These ideas are very powerful I believe. The game industry has known about them and has been perfecting them for quite some time now, while the rest of the programming community appears to be largely unaware as far as I can tell. I would love to see some experimentation with these ideas in non game domains and find out what the community can come up with.

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